アルゴリズム

数学の問題を解くための段階的な手順は、古代から記録されてきました。これには、バビロニアの数学（紀元前2500年頃）^{[ 20 ]} 、エジプトの数学（紀元前1550年頃）^{[ 20 ]} 、インドの数学（紀元前800年頃以降）^{[ 21 ] [ 22 ]}、イファ神託（紀元前500年頃）^{[ 23 ]} 、ギリシャの数学（紀元前240年頃）^{[ 24 ]} 、中国の数学（紀元前200年頃以降）^{[ 25 ]}、アラビアの数学（西暦800年頃）^{[ 26 ]}が含まれます。

アルゴリズムの最も古い証拠は、古代メソポタミアの数学に見られます。バグダッド近郊のシュルッパクで発見された紀元前2500年頃のシュメールの粘土板には、最古の除算アルゴリズムが記述されています。^{[ 20 ]}紀元前1800年～1600年頃のハンムラビ王朝時代には、バビロニアの粘土板に計算式のアルゴリズムが記述されていました。^{[ 27 ]}アルゴリズムはバビロニアの天文学でも使用されていました。バビロニアの粘土板には、重要な天文現象の時間と場所を計算するためのアルゴリズムの手順が記述され、使用されています。^{[ 28 ]} 

算術のアルゴリズムは、紀元前1550年頃のリンド数学パピルスに遡る古代エジプトの数学にも見られます。[ 20 ]アルゴリズムは^後に古代ヘレニズム数学でも使用されました。例としては^、ニコマコスの『算術入門』 [ ^{29 ] [ 24 ]第9章2節}で説明されているエラトステネスの篩^と、ユークリッドの『原論』 （紀元前300年頃） ^{[ 24 ]}第9章1節で初めて説明されたユークリッドのアルゴリズムがあります。古代インドの数学の例としては^、シュルバ・スートラ、ケーララ学派、ブラーフマスプタシッ^ダーンタなどがあります。^{[ 21 ]}

9世紀、ムハンマド・イブン・ムーサー・アル＝フワーリズミーは、数学の問題を解決するための論理的な手順の体系的かつ有限なシーケンスとしてアルゴリズムを確立することで、この分野に革命をもたらしました。彼の影響力のある著作『完全化とバランスによる計算に関する簡潔な書』の中で、彼は具体的な数値解を超えて、代数的還元とバランスのための一般的な手順を導入しました。これにより、数学は明確に定義された規則の「機械的」プロセスへと変容し、現代のアルゴリズム理論の基礎を築いた根本的な変化となりました。彼の算術論文のラテン語訳である『Algoritmi de numero Indorum』は、彼の名前のラテン語化であるAlgoritmiからアルゴリズムという用語が派生し、特にこの新しい規則に基づく数学のアプローチを説明するために使用されました。^{[ 30 ]}

暗号化されたコードを解読するための最初の暗号アルゴリズムは、9世紀のアラビアの数学者アル・キンディによって『暗号メッセージの解読に関する手稿』の中で開発されました。彼は、最も初期の暗号解読アルゴリズムである周波数分析による暗号解読の最初の記述を与えました。^{[ 26 ]}

1928年、デイヴィッド・ヒルベルトの決定問題（Entscheidungsproblem）を解こうとする試みから、アルゴリズムの現代的概念の部分的な形式化が始まった。後の形式化は、「有効計算可能性」^{[ 37 ]}または「有効方法」^{[ 38 ]}を定義しようとする試みとして位置づけられた。これらの形式化には、1930年、1934年、1935年のゲーデル-ヘルブランド-クリーネの再帰関数、1936年のアロンゾ・チャーチのラムダ計算、 1936年のエミール・ポストの定式化1、1936 ～37年および1939年のアラン・チューリングのチューリングマシンが含まれる。

数十年にわたり、アルゴリズムの進化はヒューリスティックから形式的アルゴリズムへと進むと考えられてきた。記号積分はその典型的な例である。1961年、ジェームズ・スレーグルのプログラムSAINTは、MITの教科書に掲載された54問の初級微積分演習のうち52問（約96%）をヒューリスティックを用いて解いた。1967年、ラリー・モーゼスのSINはヒューリスティックを改良し、100%の成功率を達成したが、依然としてヒューリスティックな手法であった。そして1969年、ロバート・リッシュは形式的な保証付きのリッシュアルゴリズムを発表した。この軌跡は、ヒューリスティックが進化し、最終的に決定的な保証付きアルゴリズムが出現するという、従来の道筋を定義づけた。

しかし、トランスフォーマー型AIの台頭により、この流れは逆転し、従来のアルゴリズムは再びヒューリスティックに取って代わられつつある。

アルゴリズムは、時間の経過とともに様々な面で進化し、改良されてきました。今日、アルゴリズムが一般的に使用されている例としては、InstagramやYouTubeなどのソーシャルメディアアプリが挙げられます。アルゴリズムは、人々の好みを分析し、それらの好みに合ったコンテンツをより多くのユーザーに提供するために使用されます。量子コンピューティングは、量子アルゴリズムの手順を用いて問題をより迅速に解決します。さらに最近では、2024年にNISTがポスト量子暗号化規格を更新し、量子コンピューティングを用いた攻撃に対する防御を強化するための新しい暗号化アルゴリズムを追加しました。

表現方法は数多くあり、チューリングマシンプログラムは、マシンテーブルのシーケンス（詳細については、有限状態マシン、状態遷移テーブル、および制御テーブルを参照）、フローチャートおよびドラコンチャート（詳細については、状態図を参照）、基本的なマシンコードまたはアセンブリコードの形式である「四つ組のセット」などとして表現できます。アルゴリズムの表現は、チューリングマシンの記述の 3 つの許容レベルに分類することもできます。高レベル記述、実装記述、および形式記述です。^{[ 39 ]}高レベル記述は、チューリングマシン上でどのように実装されるかを無視して、アルゴリズム自体の特性を記述します。^{[ 39 ]}実装記述は、マシンがヘッドを動かし、アルゴリズムを実行するためにデータを格納する一般的な方法を記述しますが、正確な状態は示しません。^{[ 39 ]}最も詳細な形式記述は、チューリングマシンの正確な状態テーブルと遷移のリストを示します。^{[ 39 ]}

フローチャートは、アルゴリズムを記述・文書化するための図解ツールです。主な記号は4つあり、プログラムの流れを示す矢印、四角形（シーケンス、GOTO）、分岐を表すひし形、そしてドット（OR条件）です。サブ構造は四角形の中に「入れ子」にすることができますが、それは上位構造から単一の出口がある場合に限ります。

アルゴリズムの分析と研究は、コンピュータサイエンスの一分野です。アルゴリズムは、特定のプログラミング言語や実装を参照することなく、抽象的に研究されることがよくあります。他の数学分野と同様に、実装ではなくアルゴリズムの特性に焦点を当てます。擬似コードは、シンプルで一般的な表現であるため、分析によく用いられます。ほとんどのアルゴリズムは特定のハードウェア/ソフトウェアプラットフォーム上で実装され、実際のコードを使用してアルゴリズムの効率がテストされます。特定のアルゴリズムの効率は、多くの「単発」の問題では重要ではないかもしれませんが、高速でインタラクティブな商用利用や長期にわたる科学用途向けに設計されたアルゴリズムでは、非常に重要になる場合があります。入力サイズを大きくすると、それまで無害だったアルゴリズムの非効率性が明らかになることがよくあります。

経験的テストは、パフォーマンスに影響を与える予期せぬ相互作用を明らかにするのに役立ちます。ベンチマークは、プログラム最適化後のアルゴリズムの潜在的な改善の前後を比較するために使用できます。経験的テストは形式的分析を完全に置き換えることはできず、公平に実施することは困難です。^{[ 40 ]}

確立されたアルゴリズムであっても改善の余地があることを示す例として、画像処理に使用されるFFTアルゴリズムに関する最近の重要なイノベーションにより、医療画像処理の処理時間を最大1,000倍短縮できる可能性があります。^{[ 41 ]}一般的に、速度の改善は問題の特殊な特性に依存しますが、これは実際のアプリケーションでは非常に一般的です。^{[ 42 ]}

アルゴリズムの最良ケースとは、アルゴリズムまたはデータ構造がタスクを完了するのにかかる時間とリソースが最小となるシナリオまたは入力を指します。^{[ 43 ]} アルゴリズムの最悪ケースとは、アルゴリズムまたはデータ構造が最大の時間と計算リソースを消費するケースです。^{[ 44 ]}

任意のアルゴリズムは、任意のチューリング完全モデルで計算できます。チューリング完全性には、条件付きGOTO、無条件GOTO、代入、HALTの4種類の命令のみが必要です。タウスワースは、 3つのBöhm-Jacopini標準構造^{[ 47 ]} SEQUENCE、IF-THEN-ELSE、WHILE-DOに加えて、DO-WHILEとCASEの2つを追加しました。^{[ 48 ]}構造化プログラムのもう1つの利点は、数学的帰納法を使用して正当性の証明に適していることです。^{[ 49 ]}

再帰

再帰アルゴリズムは、終了条件を満たすまで自身を繰り返し呼び出すもので、一般的な関数型プログラミングの手法です。反復アルゴリズムは、ループなどの繰り返し処理やスタックなどのデータ構造を用いて問題を解決します。問題によっては、どちらかの実装方法に適している場合があります。ハノイの塔は、再帰的な実装でよく解かれるパズルです。すべての再帰バージョンには、同等の（ただし、複雑さの程度が異なる）反復バージョンが存在し、その逆もまた然りです。

直列、並列、または分散

アルゴリズムは通常、シリアルコンピュータ上でコンピュータがアルゴリズムの命令を一度に1つずつ実行するという前提で議論されます。シリアルアルゴリズムは、並列アルゴリズムや分散アルゴリズムとは異なり、このような環境向けに設計されています。並列アルゴリズムは、複数のプロセッサが同時に問題を処理できるコンピュータアーキテクチャを活用します。分散アルゴリズムは、コンピュータネットワークを介して接続された複数のマシンを使用します。並列アルゴリズムと分散アルゴリズムは、問題をサブ問題に分割し、結果をまとめて収集します。これらのアルゴリズムにおけるリソース消費は、各プロセッサの処理サイクルだけでなく、プロセッサ間の通信オーバーヘッドも含まれます。一部のソートアルゴリズムは効率的に並列化できますが、通信オーバーヘッドが大きくなりがちです。反復アルゴリズムは一般的に並列化可能ですが、並列アルゴリズムが存在しない問題もあり、それらは本質的にシリアル問題と呼ばれます。

決定論的か非決定論的か

決定論的アルゴリズムは、各ステップで正確な判断を下すことで問題を解決します。一方、非決定論的アルゴリズムは、推測によって問題を解決します。推測の精度は、通常、ヒューリスティックを用いることで向上します。

正確か近似か

多くのアルゴリズムは正確な解に到達するが、近似アルゴリズムは真の解に近い近似値を求める。このようなアルゴリズムは、多くの難問に対して実用的な価値がある。例えば、ナップサック問題では、一連のアイテムがあり、ナップサックに詰めて合計価値を最大にすることが目標である。各アイテムには重量と価値がある。持ち運べる合計重量は、ある固定値X以下である。したがって、解はアイテムの重量と価値の両方を考慮する必要がある。^{[ 51 ]}

量子アルゴリズム

量子アルゴリズムは、量子計算の現実的なモデルに基づいて動作します。この用語は通常、本質的に量子的なアルゴリズム、または量子重ね合わせや量子もつれといった量子計算の本質的な特徴を利用するアルゴリズムに対して用いられます。

アルゴリズムを分類するもう一つの方法は、その設計手法またはパラダイムによる分類です。一般的なパラダイムには以下のようなものがあります。

総当たり検索または徹底的な検索

総当たり攻撃とは、最適な解決策が見つかるまで、考えられるすべての選択肢を体系的に試していく問題解決手法です。この手法は、あらゆる変数の組み合わせを試すため、非常に時間がかかる場合があります。他の方法が利用できない場合や、複雑すぎる場合によく用いられます。総当たり攻撃は、2点間の最短経路の探索やパスワードの解読など、さまざまな問題を解決することができます。

分割統治

分割統治アルゴリズムは、問題が簡単に解決できるほど小さくなるまで、問題を1つ以上のより小さなインスタンスに繰り返し縮小します（通常は再帰的に）。マージソートは分割統治の一例で、順序付けされていないリストが繰り返しより小さなリストに分割され、同じ方法でソートされてからマージされます。^{[ 52 ]}分割統治のより単純なバリアントである剪定と探索または縮小統治アルゴリズムでは、より小さなインスタンスを1つ解決し、マージステップは必要ありません。^{[ 53 ]}剪定と探索アルゴリズムの例は、二分探索アルゴリズムです。

検索と列挙

チェスなどの多くの問題は、グラフ上の問題としてモデル化できます。グラフ探索アルゴリズムは、グラフ内を移動するためのルールを規定し、このような問題に役立ちます。このカテゴリには、探索アルゴリズム、分岐限定法、バックトラッキングなども含まれます。

ランダム化アルゴリズム

このようなアルゴリズムは、いくつかの選択をランダム（または擬似ランダム）に行います。正確な解を見つけることが非現実的な場合に近似解を見つけます（下記のヒューリスティック法を参照）。問題によっては、最速の近似解には何らかのランダム性が必要となる場合があります。^{[ 54 ]}多項式時間計算量を持つランダム化アルゴリズムが、いくつかの問題に対して最速のアルゴリズムになり得るかどうかは、 P対NP問題として知られる未解決の問題です。このようなアルゴリズムには、大きく分けて2つのクラスがあります。

1. モンテカルロ法は高い確率で正しい答えを返します。例えば、RPは多項式時間で実行されるこれらのアルゴリズムのサブクラスです。
2. ラスベガスアルゴリズムは常に正しい答えを返しますが、その実行時間は確率的にしか制限されません。たとえば、ZPPなどです。

複雑性の軽減

この手法は、難しい問題を、漸近的に最適なアルゴリズムで解決可能な、よりよく知られた問題に変換するものです。目標は、結果として得られる縮小アルゴリズムの複雑さに支配されないような、より単純なアルゴリズムを見つけることです。例えば、ある選択アルゴリズムは、まずリストをソートし（コストのかかる部分）、次にソートされたリストの中央の要素を取り出す（コストの低い部分）ことで、ソートされていないリストの中央値を求めます。この手法は、変換と征服法とも呼ばれます。

バックトラッキング

このアプローチでは、複数の解決策を段階的に構築し、有効な完全な解決策に繋がらないと判断された時点でそれらを放棄する。

最適化問題に関しては、アルゴリズムはより具体的に分類されます。このような問題に対するアルゴリズムは、上述の一般的なカテゴリの1つ以上、あるいは以下のいずれかに分類される可能性があります。

線形計画法

線形等式および不等式制約によって制限された線形関数の最適解を探索する場合、制約を直接使用して最適解を生成することができます。このカテゴリのあらゆる問題を解決できるアルゴリズムがあり、よく知られているシンプレックス法などがあります。^{[ 55 ]}線形計画法で解決できる問題には、有向グラフの最大フロー問題などがあります。問題で未知数のいずれかが整数である必要がある場合、それは整数計画法に分類されます。線形計画法アルゴリズムは、整数値に対するすべての制約が表面的である、つまり、いずれにせよ解がこれらの制約を満たすことが証明できる場合に、そのような問題を解決できます。一般的には、問題の難易度に応じて、特殊なアルゴリズムまたは近似解を見つけるアルゴリズムが使用されます。

動的計画法

問題が最適な部分構造（つまり、最適な解が部分問題の最適な解から構築できる）と重複する部分問題（つまり、同じ部分問題が多くの異なる問題インスタンスの解決に使用される）を示す場合、動的計画法と呼ばれるより高速なアプローチは解の再計算を回避します。たとえば、フロイド・ウォーシャルアルゴリズムでは、重み付きグラフの開始頂点と目標頂点間の最短経路は、すべての隣接頂点から目標への最短経路を使用して見つけることができます。動的計画法とメモ化は一緒に使用されます。分割統治法とは異なり、動的計画法の部分問題は重複することがよくあります。動的計画法と単純な再帰の違いは、再帰呼び出しのキャッシュまたはメモ化です。部分問題が独立していて繰り返されない場合、メモ化は役に立ちません。したがって、動的計画法はすべての複雑な問題に適用できるわけではありません。メモ化を使用すると、動的計画法は多くの問題の複雑さを指数関数から多項式に削減します。

貪欲法

貪欲アルゴリズムは、動的計画法と同様に、部分構造を調べることで機能します。この場合、問題ではなく、与えられた解の部分構造を調べます。このようなアルゴリズムは、何らかの解から始めて、小さな修正を加えることでそれを改善します。問題によっては、常に最適解を見つけることができますが、他の問題では局所最適解で停止してしまう場合があります。貪欲アルゴリズムの最も一般的な用途は、負のサイクルを持たないグラフの最小全域木を見つけることです。ハフマン木、クラスカル法、プリム法、ソリン法は、この最適化問題を解決できる貪欲アルゴリズムです。

ヒューリスティック法

最適化問題において、ヒューリスティックアルゴリズムは、最適解を見つけることが非現実的な場合に、最適解に近い解を見つけます。これらのアルゴリズムは、実行が進むにつれて最適解にどんどん近づいていきます。原理的には、無限の時間実行すれば最適解を見つけることができます。理想的には、比較的短い時間で最適解に非常に近い解を見つけることができます。これらのアルゴリズムには、局所探索、タブー探索、シミュレーテッドアニーリング、遺伝的アルゴリズムなどがあります。シミュレーテッドアニーリングのように非決定論的なアルゴリズムもあれば、タブー探索のように決定論的なアルゴリズムもあります。最適解ではない解の誤差の上限がわかっている場合、そのアルゴリズムはさらに近似アルゴリズムに分類されます。