コンピュータを進化させてきた偉大なるアルゴリズムまとめ

By Kai Schreiber

IT技術の進化のスピードには目を見張るものがありますが、それを支えているのはアルゴリズムと呼ばれる処理方法(技術的アイデア)です。さまざまなアルゴリズムの中でも、コンピュータの進化に革命的な影響をもたらしたとされる偉大なアルゴリズムは以下の通りです。

Great Algorithms that Revolutionized Computing
http://en.docsity.com/news/interesting-facts/great-algorithms-revolutionized-computing/

◆ハフマン符号(圧縮アルゴリズム)

Huffman coding(ハフマン符号)は、1951年にデービッド・ハフマン氏によって開発されたアルゴリズム。頻出頻度の大小によって対戦するトーナメントツリーを考えて、ブロックごとに0と1の符号をもたせることで、頻出頻度の大きいものには短い符号を、頻出頻度の小さいものには長い符号が与えられます。単純かつ高速に計算できるハフマン符号は、JPEGやMP3などの圧縮技術に活用されています。

◆公開鍵暗号(暗号化アルゴリズム)

By Richard-G

通信の秘匿性を高める暗号化では、復号する鍵の受け渡し過程で盗聴される危険がありました。これを解決したのが公開鍵暗号で、「秘密鍵」だけでなくたとえ盗聴されても問題ない「公開鍵」という2種類の暗号鍵を用意することで盗聴リスクを解消しています。公開鍵による平文の暗号化だけでなく、公開鍵で復号できる暗号化を秘密鍵で行うことも可能で、「秘密鍵を持っているという事実」を証明できることからデジタル署名にも活用されています。

◆ダイクストラ法(探索アルゴリズム)

ダイクストラ法は、最短経路を探索するアルゴリズムとして1956年にエドガー・ダイクストラ氏によって考案されました。ダイクストラ法の最大の利点は「不要な経路であると分かった時点でそれ以降の計算を省略できる」というところ。ダイクストラ法は、カーナビの経路探索などに活用されています。

◆二分探索(探索アルゴリズム)

二分探索は、整列されたリストを二分割しながら探索することで、探索範囲を絞りこみながら効率的に目的に到達できるアルゴリズムで、電話帳探索技術などに応用されています。

◆クイックソート(整列アルゴリズム)

クイックソートは、1960年にトニー・ホーア氏によって開発されたアルゴリズムで、UNIXのデフォルト整列機能に採用されて一躍有名になりました。最大の特徴はその処理速度。クイックソートはデータの比較・交換回数が非常に少ないアルゴリズムであるため、ランダムに散らばるデータを効率よく並び替えることができ、実用上最も高速なソートアルゴリズムであると評価されています。

◆カラツバ法(乗算アルゴリズム)

大きな数の乗算(かけ算)において、加減算(たし算・ひき算)の回数を増やして乗算の回数を4分の3にできるアルゴリズムがカラツバ法です。乗算に比べて加減算の方が計算速度(処理速度)がはるかに大きいため、トータルでの計算速度を高速化できるところがミソです。

◆ユークリッドの互除法

紀元前300年に明示された世界最古のアルゴリズムとして知られるのがユークリッドの互除法。2つの自然数の最大公約数を単純なわり算とひき算で素早く探し出せるこのアルゴリズムは、公開鍵暗号を求める計算に活用されるなど現代のコンピュータ技術に活用されている現役のアルゴリズムです。

◆ブレゼンハムのアルゴリズム(描画アルゴリズム)

ブレゼンハムのアルゴリズムは、1962年にIBMのジャック・エルトン・ブレゼンハム氏によって開発されたアルゴリズムで、コンピュータスクリーン上で直線を描画するのに利用され、拡張することで円を描くことも可能。ブレゼンハムのアルゴリズムは、整数の加減法とビットシフトを使うだけというシンプルな手法であるため多くのコンピュータで利用でき、コンピュータグラフィックの草創期を支えた革命的なアルゴリズムと言えます。さらに、その高速性・シンプルさゆえに、現代のグラフィックボードにも導入されています。

◆高速逆平方根計算

高速逆平方根計算アルゴリズム(Fast Inverse Square Root)は、1999年に発売されたQuake III ArenaというFPSゲームで採用されたアルゴリズムで、3Dグラフィックでの光の反射を高速に計算することが可能で、精度よりも速度が求められる場面で活用されています。