コンピューティング技術を変えた偉大なアルゴリズムを数えてみましょう

これまで、多くの独創的なコンピュータ アルゴリズムの設計が私たちのコンピューティング技術を変えてきました。標準的なコンピュータが提供する中間演算子を操作することで、多くの効率的な関数を生成できます。これらの機能はコンピュータ プログラムの複雑さと多様性につながり、今日のコンピュータ時代の急速な発展の重要な理由でもあります。以下に、コンピューターの使用方法を変えたアルゴリズムをいくつか示します。

圧縮技術

ハフマン符号化

[[110280]]

ハフマン符号化はロスレスデータ圧縮に広く使用されています。効率的なバイナリコードを見つけるために、ハフマンは 1951 年に文字の頻度でソートされたバイナリツリーというコーディング方法を提案しました。この方法は最も効果的なエンコード方法であることが証明されています。この方法はシンプルで効率的であるため、DEFLATE (PKZIP 圧縮ソフトウェアのアルゴリズム) などの多くの圧縮方法や、JPEG や MP3 などの多くのマルチメディア エンコーディングで使用されています。

暗号化

公開鍵暗号

[[110278]]

暗号化アルゴリズムには、2 つの異なるキーが必要です。公開キーは、プレーンテキストを暗号化したり、デジタル署名を検証したりするために使用されます。秘密鍵は、暗号文を復号化したり、デジタル署名を生成するために使用されます。公開鍵暗号化により、ユーザーはパブリック チャネルを介してデータを安全に送信できます。この方法は 1997 年に公開されましたが、1973 年に英国政府通信本部 (GCHQ) の James H. Ellis、Clifford Cocks、Malcolm Williamson によって設計され、使用されました。

検索アルゴリズム

ダイクストラ最短経路アルゴリズム

[[110281]]

このアルゴリズムは 1956 年にダイクストラによって完成され、グラフ用に設計された検索アルゴリズムです。これは、単方向グラフ内の最短経路問題を解決するため、最短経路ツリーの生成にも使用できます。このようなアルゴリズムは、パス計画やサブパス選択のための多くのグラフベースのアルゴリズムで使用されます。上の図は、このようなアルゴリズムを使用して一方向グラフ内の最短経路を見つけるプロセスを示しています。

二分探索アルゴリズム

[[110282]]

バイナリ検索アルゴリズムは、すでにソートされた配列内のキーワードの位置を見つけるために使用されます。言葉の意味を説明する辞書では、言葉の並びは基本的に整然としています。電話帳では、記録は名前、住所、電話番号で分類されます。このようなアルゴリズムにより、人の名前に基づいて電話帳内の対応する電話番号と住所をすばやく見つけることができます。

ソートアルゴリズム

クイックソート

[[110283]]

このアルゴリズムは 1960 年に Tony Hoare によって設計されました。このアルゴリズムはもともと、翻訳する単語の順序を辞書の順序とより一致させて翻訳しやすくするために調整するために使用されていました。このアルゴリズムは、Unix システムのデフォルトのソート アルゴリズムとして使用されたため有名になりました。同時に、このアルゴリズムは、C 言語の標準ライブラリの関数名「qsort」にちなんで命名されています。

#p#

数学的手法

Karatsuba高速乗算アルゴリズム

[[110284]]

このアルゴリズムは、乗算の数学演算をより速く完了するために使用されます。 1962年にアナトリー・アレクセーエヴィッチ・カラツバによって提案された。乗算に必要な演算回数を減らし、高速な乗算方法を提供します。このアルゴリズムの改良版が Toom-Cook アルゴリズムです。ただし、大きな数を乗算する場合は、Schönhage-Strassen アルゴリズムの方が高速なソリューションです。

ユークリッドの互除法（ユークリッドの互除法）

[[110285]]

ユークリッドの互除法を使用すると、最大公約数を計算できます。つまり、2 つの正の整数で割り切れる数値の最大数です。このアルゴリズムは減算と比較のみを使用して最大公約数を見つけますが、多くの高度なアルゴリズムで使用されます。このアルゴリズムはユークリッドが発明したと考えられており、ユークリッドのアルゴリズムはユークリッドの時代（紀元前 300 年頃）にまで遡る最も古いアルゴリズムの 1 つと考えられています。

グラフィックスの発展

ブレゼンハムのラインアルゴリズム

このアルゴリズムは、1962 年に IBM で働いていたジャック・エルトン・ブレゼンハムによって提案されました。このアルゴリズムはもともと、コンピュータ画面上に直線を描くために使用されていました。アルゴリズムで使用される演算は非常に単純で、整数の加算、減算、シフト演算です。これはコンピュータグラフィックスにおける非常に高度な方法です。この方法に基づいて、アルゴリズムは後に円描画アルゴリズムなどの一連の拡張を受けました。このアルゴリズムは、その高い効率性と速度により、今でも非常に重要であり、多くのハードウェア (プロッターや最新のグラフィック カードなど) で使用されています。 。

高速平方根逆数アルゴリズム

このアルゴリズムは、平方根の逆数を高速に計算する方法を提供します。この方法は、光と投影の関係を決定するために 3D 画像で広く使用されており、1 秒あたり数千万回の計算が必要になる場合があります。このようなアルゴリズムは Quake III: Arena のソース コードにすでに存在していましたが、2002 年までは広く使用されていませんでした。このアルゴリズムは、一連の単純な操作を使用して複雑な問題を解決します。このアルゴリズムは John Carmack によって開発されたと多くの人が信じていますが、SGI と 3dfx は、Gary Tarolli によって実装されたバージョンを使用して、すでにこのアルゴリズムを自社製品に使用していました。

オリジナルリンク: docsity 翻訳: Bole Online - programmer_lin

翻訳リンク: http://blog.jobbole.com/61815/