世界を支配するトップ 10 のアルゴリズムをご存知ですか?

Reddit に、私たちの現代生活におけるアルゴリズムの重要性と、どのアルゴリズムが現代文明に最も大きく貢献したかを紹介する投稿があります。アルゴリズムについて何か知っている人なら、この記事を読んで「著者はアルゴリズムが何であるか知っているのか？」または「Facebook のニュースフィードはアルゴリズムなのか？」と疑問に思うかもしれません。「ニュースフィード」がアルゴリズムであるなら、すべてがアルゴリズムによるものと言えます。私はあまり知識がないので、その投稿に基づいて、アルゴリズムとは何か、そしてどの 10 個のアルゴリズムが世界を支配しているかを説明してみたいと思います。

アルゴリズムとは何ですか?

簡単に言えば、アルゴリズムとは、値または値のセットを入力として受け入れ、値または値のセットを出力する、明確に定義された計算手順です。 (出典: Thomas H. Cormen、Charles E. Leiserson「アルゴリズム入門第 3 版」)

アルゴリズムは、特定の問題を解決するために使用される一連の手順であると理解できます (コンピューターだけがアルゴリズムを必要とするのではなく、私たちも日常生活でアルゴリズムを使用しています)。アルゴリズムには、次の 3 つの重要な特性が必要です。

[1]有限。有限数のステップを実行した後、アルゴリズムは終了する必要があります。

[2]正確さ。アルゴリズムの各ステップを正確に定義する必要があります。

[3]実現可能性特定のアルゴリズムは、特定の時間内に特定の問題を解決できなければなりません。

実際、アルゴリズムはコンピュータ分野で広く使用されていますが、それらは完全に数学から派生したものです。実際、最も古い数学アルゴリズムは紀元前 1600 年にまで遡ります。因数分解と平方根を求めるバビロニア人のアルゴリズムです。

では、今日の私たちの生活を形作ってきた 10 個のコンピューターアルゴリズムは何でしょうか?以下の表を順不同でご覧ください。

1.マージソート（MERGE SORT）、クイックソート（QUICK SORT）、ヒープソート（HEAP SORT）

最も効率的なソートアルゴリズムはどれですか?それは状況によります。これが、私がこれら 3 つのアルゴリズムをまとめた理由です。おそらく、そのうちの 1 つをより頻繁に使用するかもしれませんが、それぞれに利点があります。

マージソートアルゴリズムは、現在までに最も重要なアルゴリズムの 1 つです。これは分割統治法の典型的な応用であり、1945 年に数学者ジョン・フォン・ノイマンによって発明されました。

セット分割アルゴリズムと分割統治アルゴリズムを組み合わせたクイックソートアルゴリズムは、安定性はそれほど高くありませんが、ランダム配列 (AM ベースの配列) を処理する場合に非常に効率的です。

ヒープソートは、ソート中の検索時間を短縮するために優先キューメカニズムを使用しますが、あまり安定していません。

初期のソートアルゴリズム (バブルアルゴリズムなど) と比較すると、これらのアルゴリズムはソートアルゴリズムを新しいレベルに引き上げました。これらのアルゴリズムのおかげで、今日のデータマイニング、人工知能、リンク分析、そしてほとんどの Web コンピューティングツールが実現しました。

2.フーリエ変換と高速フーリエ変換

これら 2 つのアルゴリズムはシンプルですが、非常に強力です。デジタルの世界全体がこれらなしでは成り立ちません。これらのアルゴリズムの機能は、時間領域関数と周波数領域関数の相互変換を実現することです。これらのアルゴリズムのおかげでこの記事を見ることができます。

インターネット、WIFI、スマートフォン、固定電話、コンピューター、ルーター、衛星、そしてほぼすべてのコンピューター関連デバイスは、多かれ少なかれこれらに関連しています。これら 2 つのアルゴリズムを知らなければ、電子工学、コンピューター工学、通信工学の学位を取得することは決してできません。（アメリカ合衆国）

3.ダイクストラのアルゴリズム

このアルゴリズムがなければ、インターネットは今日ほど効率的ではなかっただろうと断言できます。問題が「グラフ」モデルで表現できる限り、このアルゴリズムを使用して「グラフ」内の 2 つのノード間の最短距離を見つけることができます。

今日では最短経路問題を解決するより優れた方法が数多くありますが、デクスターアルゴリズムの安定性は依然としてかけがえのないものです。

4. RSA非対称暗号化アルゴリズム

このアルゴリズムが暗号化とネットワークセキュリティに貢献していなければ、インターネットが今日これほど高い地位を獲得することはなかっただろうと言っても過言ではありません。インターネットには今や安心感がありませんが、お金に関する問題に遭遇したときは、十分な安心感を持つようにしなければなりません。インターネットが安全でないと感じたら、ウェブページに銀行カードの情報を入力するほど愚かなことは絶対にしないでしょう。

暗号分野で最も強力なアルゴリズムの 1 つである RSA アルゴリズムは、RSA の 3 人の創設者によって提案され、今日の重要な研究分野の基礎を築きました。このアルゴリズムによって解決される問題は、セキュリティを確保しながら独立したプラットフォームとユーザー間でキーを共有する方法という、単純でありながら複雑なものです。

5.セキュアハッシュアルゴリズム

正確に言うと、これはアルゴリズムではなく、米国国立標準技術研究所によって最初に提案された暗号化ハッシュ関数のセットです。アプリストア、電子メール、ウイルス対策ソフトウェア、ブラウザーなど、すべてがこのアルゴリズムを使用して、正常にダウンロードが行われ、「中間者攻撃」や「フィッシング」による攻撃が行われていないことを確認します。

6.整数因数分解アルゴリズム

これは実際には数学的なアルゴリズムですが、コンピューター分野では広く使用されています。このアルゴリズムがなければ、暗号化された情報はそれほど安全ではありません。一連の手順を通じて、合成数を既約因数に分解できます。

先ほど述べた RSA アルゴリズムなど、多くの暗号化プロトコルがこのアルゴリズムを使用しています。

7.リンク分析

インターネット時代においては、さまざまなポータル間の関係を分析することが重要です。検索エンジンやソーシャルネットワーキングサイトから市場分析ツールに至るまで、すべてがインターネットの真の構造を解明しようと懸命に努力しています。

リンク解析アルゴリズムは、この分野で常に最も混乱を招くアルゴリズムの 1 つです。さまざまな実装方法があり、独自の特性により、各実装のアルゴリズムは異なりますが、基本原理は非常に似ています。

リンク分析アルゴリズムのメカニズムは実際には非常に単純です。行列を使用して「グラフ」を表し、固有値問題を形成できます。固有値問題は、この「グラフ」の構造と各ノードの重みを分析するのに役立ちます。このアルゴリズムは、1976 年に Gabriel Pinski と Francis Narin によって提案されました。

このアルゴリズムを誰が使うのでしょうか? Google のページランキング、Facebook が情報フローを送信するタイミング（つまり情報フローはアルゴリズムではなく、アルゴリズムの結果です）、Google+ と Facebook の友達推奨機能、LinkedIn の求人推奨、Youtube の動画推奨などです。

一般的に、このタイプのアルゴリズムを使用した最初の組織は Google であると考えられていますが、実際には、1996 年 (Google が立ち上げられる 2 年前) に、Robin Li によって作成された「RankDex」という小さな検索エンジンがこのアイデアを使用していました。ハイパーサーチアルゴリズムの作成者であるマッシモ・マッキオーリも同様のアルゴリズムを使用していました。二人は後に Google の歴史に残る伝説の人物となった。

8.比例積分微分アルゴリズム

このアルゴリズムは、飛行機、自動車、テレビ、携帯電話、衛星、工場、ロボットなど、さまざまなものに使用されています。

簡単に言えば、このアルゴリズムは主に「制御ループフィードバックメカニズム」を通じて、事前に設定された出力信号と実際の出力信号間の誤差を減らします。このアルゴリズムは、信号処理が必要な場所や、自動化された機械、油圧システム、暖房システムを制御するために電子システムが使用される場所で使用されます。

それがなければ、現代文明は存在しなかったでしょう。

9.データ圧縮アルゴリズム

データ圧縮アルゴリズムはたくさんありますが、どれが最適ですか?アプリケーションによって圧縮された mp3、JPEG、MPEG-2 ファイルはすべて異なります。

どこで見ることができますか？フォルダ内の圧縮ファイルだけではありません。現在表示している Web ページでは、データ圧縮アルゴリズムを使用して情報をコンピューターにダウンロードしています。テキストのほか、ゲーム、ビデオ、音楽、データストレージ、クラウドコンピューティングなども含まれます。さまざまなシステムをより簡単に、より効率的にします。

10.乱数生成アルゴリズム

現在まで、コンピューターは「真の」乱数を生成できていませんが、疑似乱数生成アルゴリズムで十分です。これらのアルゴリズムは、ネットワーク接続、暗号化、安全なハッシュ、オンラインゲーム、人工知能、問題分析における条件付き初期化など、多くの分野で応用されています。

このリストは完全なものではなく、機械学習や行列乗算など、私たちに密接に関連する多くのアルゴリズムは言及されていません。なお、私の知識は限られているので、抜けているところがあればご指摘いただければ幸いです。

この記事は http://www.199it.com/archives/233832.html から引用しました。

【編集者のおすすめ】