アルゴリズム(英: algorithm)とは、解が定まっている「計算可能」問題に対して、その解を正しく求める手続きをさす。算法、計算手順、処理手順とも和訳される。「ヒューリスティック」に対置する概念である。

実用上は、アルゴリズムの実行に要する記憶領域の大きさや完了までに要する時間(空間計算量と時間計算量)が小さいこと、特に問題の規模を大きくした際に必要な記憶領域や計算量が急激に大きくならないことが重要となる。

アルゴリズムの実行は形態によらない。たとえばアルゴリズムはコンピュータ上にコンピュータプログラムとして実装して実行できる。

## 概要

岩波国語辞典「算法」に、まず「計算の方法」とした後に2番目の詳細な語義でalgorithmの訳として、

とある。一見では国語辞典らしい平易な日本語で書かれた説明だが、例えば解が無いと無限ループに陥るといったようなものは除外されるし、「アルゴリズムの視覚的表現」としてよく使われるフローチャートのようなもので書いてあっても、基本的操作がはっきりと書いてなければそれはアルゴリズムではない、というわけである。これは、#形式化の節で述べるような、理論計算機科学での「アルゴリズム」の扱いに沿っている。

## 歴史

記録に残る最古のアルゴリズムは、エウクレイデスの原論のものである。その中でも、二つの整数の最大公約数を求めるユークリッドの互除法は、典型的なアルゴリズムとして知られている。

「アルゴリズム」という名称は、現在のイラクのバグダードにおける9世紀の数学者アル=フワーリズミーの名前から来ているといわれている。彼がインド数学を紹介した著作『インドの数の計算法』(825年)が、12世紀にチェスターのロバート(あるいはバースのアデラード)によってラテン語に翻訳され、『algoritmi de numero Indorum アルゴリトミ・デ・ヌーメロ・インドルム』(直訳すると「インドの数におけるアルゴリトミ」)という題で、以後500年間にわたってヨーロッパ各国の大学で数学の主要な教科書として用いられた。この書は、冒頭に「algoritmi dicti(アル・フワリズミーに曰く)」という一節があるので『algoritmi(アルゴリトミ)』と呼ばれていた。

1920〜30年代、計算可能性のための数学モデル(計算モデル)がいくつも提案された(チューリングマシン、帰納的関数、ラムダ計算など)。後にこれらの定義はすべて同等であることがわかり、それらにより同値な概念を「計算可能」とすることが提案された(チャーチ=チューリングのテーゼ、提案者はスティーヴン・コール・クリーネ。なお、チューリングのほうを先とする専門家もいる)。したがって、現在では「これらによって『計算可能なもの』を計算する手続き」をアルゴリズムと呼ぶ。

## 形式化

ここではまず非形式的にアルゴリズムについて述べた後で、停止性など形式的な議論を続ける。

アルゴリズムはコンピュータが情報を処理する基盤である。すなわち、プログラムは本質的にはアルゴリズムであり、コンピュータが特定のタスク(従業員の給与計算、学生の成績表の印刷など)を(指定された順序で)実行するためのステップをコンピュータに指示する。したがって、アルゴリズムはチューリング完全なシステムで実行可能な操作の並びとみなすこともできる。

アルゴリズムは情報処理と結びついていることが多く、データは何らかの入力源(機器)から読み込まれ、結果は何らかの出力先(機器)に書かれるか、次の処理の入力となるよう保持される。保持されたデータはアルゴリズムを実行する実体の内部状態の一部とみなされる。実際、コンピュータでは状態をデータ構造に保持したりする。

このような計算過程について、アルゴリズムは厳密に定義されなければならず、ありうる全ての状況に適用可能な形で指定される。すなわち、どのような条件のステップでも、ケースバイケースで体系的に扱わなければならず、各ケースの扱い方は明確で(計算可能で)なければならない。

アルゴリズムは明確なステップの明確なリストなので、その計算順序は最も重要である。命令列は、先頭から最後尾に向かって逐次的に実行されるよう記述される。この考え方をより形式的にしたものが制御構造である。

以上の説明は、命令型プログラミングを前提としてアルゴリズムを定式化する場合である。これは、最も典型的な概念であり、タスクを離散的かつ機械的なものとして表すものである。その場合に特有の操作として、変数に値を設定する「代入」がある。これは、直観的にはメモリをメモ帳のようなものとみなすところから生まれた。

これ以外のアルゴリズムの概念化として、関数型プログラミングや論理プログラミングがある。

### アルゴリズムの記述

プログラマは擬似コードなどを使うことが多いが、理論計算機科学での形式的で厳密な議論には計算モデルを使う。もちろん相互に得失があり、必要であれば互いにどちらも使う。

### 停止性

アルゴリズムは最終的に必ず停止しなければならないとする定義もある。というより形式的で厳密な議論では停止するものだけがアルゴリズムである(チャーチ=チューリングのテーゼも参照)。

そのため、そうでないものと呼び分ける必要があることもあり、クリーネは停止性のあるアルゴリズムを「decision procedure for the question」「decision method for the question」「algorithm for the question」とした。停止しない可能性のある手続きについては、クヌースは「computational method」と呼び、クリーネは「calculation procedure」「algorithm」と呼んでいる。

ミンスキーは、(特定の状態から開始された)アルゴリズムの停止性について次のように述べている。

アラン・チューリングが停止性問題として提起したとおり、任意のプロシージャと初期状態が与えられたとき、それが停止するかどうかを判定するアルゴリズムは存在しない(この前半を「任意のアルゴリズムと初期状態が」としてはいけない。この記事の他の部分では完全に混用されているが、この文の後半の「アルゴリズムは」という表現は、必ず停止するもののみを指してそう言っているのだから。せめて1文の中では混用はまずい)。

不完全な(あるいは間違った)アルゴリズムは、次のいずれかの結果となる。

- 停止しない。
- 解の範囲を逸脱した値を返して停止する。
- 誤った解を返して停止する。
- 解を返さずに停止する。
- これらの組合せ。

クリーネはこれらをアルゴリズム内で検出してエラーメッセージを返すか、可能ならば無限ループに入らせることを提案した。また、結果が真理値である場合についてクリーネは第三の論理記号「$u$」を使うことも提案している。そうすれば、命題を扱うアルゴリズムで何らかの値を常に生成できるとした。誤った答えを返す問題は、帰納法を使ったアルゴリズムに関する個別の「証明」で解決される。

### その他の表現

アルゴリズムには様々な記法があり、自然言語、擬似コード、フローチャート、プログラミング言語などがある。アルゴリズムの自然言語表現は冗長であいまいになる傾向があり、複雑なアルゴリズムや技術的な場面では単独ではほとんど使用されない。擬似コードやフローチャートはアルゴリズムを構造的に表現でき、自然言語のようなあいまいさもほとんどない。プログラミング言語でアルゴリズムを示すこともよくある。

アルゴリズムの記述は、例えばチューリング機械を使ったならば、として次の3つに分類している書籍などがある。

(以上の2つのような内容では、そもそも概要で説明したように「はっきり」していない可能性もあるし、詳細が無ければ無限ループに陥らないことを証明することもできない。従ってそもそも実際には「アルゴリズムを記述」してはいない)

### 実装

多くのアルゴリズムは、コンピュータプログラムとして実装されることを意図している。しかし、アルゴリズムの実装手段はほかにもあり、電気回路で実装したり、機械で実装したりすることもある。人間が算術を覚えるのも、脳内の神経網にアルゴリズムが実装されたものと見ることもできる。

## 例

簡単なアルゴリズムの例として、(整列されていない)有限長の数列(リスト)に含まれる(大きさが一定値以下の整数の)最大の数を見つけ出すアルゴリズムを考える。ここでは、リストに含まれる全ての数を調べる必要があるが、一度に調べらることができるのは1つだけであるとする。ここから得られるアルゴリズムを、日本語で記述すると次のようになる。

### 概念的記述

1. 最初の要素(数)が最大と仮定する。
2. 残りのリスト上の数を順に見ていき、最大の数よりも大きい数が見つかったら、それを新たな最大として記憶する。
3. 最後に記憶した数がそのリストでの最大の数であり、これで処理が完了する。

次に、プログラミング言語的にやや形式的に記述すると、次のような擬似コードになる(「←」は代入を表し、「return」はその後に記された値を返してアルゴリズムが終了することを意味する)。

### 擬似形式的記述

入力: 空でない数リスト L、出力: リスト L 内の最大(largest)の数。

## アルゴリズム解析

あるアルゴリズムの実行に必要な計算資源(時間や記憶領域)の量を見積もることは重要である。そのような量を定量的に求める分析法はアルゴリズム解析と呼ばれ、研究がなされてきた。例えば、上記のアルゴリズムの実行に必要な時間はリストの長さを $n$ とするときO記法を用いて表せば $O(n)$ となる。このアルゴリズムでは、(与えられたリスト以外には)常に(その時点での最大の数と、現在見ているリスト上の位置)2つの値だけを記憶しておけばよい。したがって、必要となる記憶領域の量は $O(1)$ となるが、リストの長さnを記憶して入力として与える場合にはそのための領域も含めるとすると $O(\log n)$ になる。

同じ問題であっても、アルゴリズムが異なれば、必要とする時間や記憶領域の量も異なる。例えば、ソートには様々なアルゴリズムがあり、それぞれ必要な時間や記憶領域の量が異なる。

アルゴリズム解析は計算機科学の一部であり、特定のプログラミング言語や実装を前提とせずに、抽象的に解析を行うことも多いが、特定のプログラミング言語や実装を前提として、具体的に解析を行うことも多い。これは、アルゴリズムの様々な属性に注目した他の数学的分野とも共通する。

## 分類

アルゴリズムには様々な分類方法があり、それぞれに利点がある。

### 実装による分類

アルゴリズム分類の1つの方法として、実装手段による分類がある。

### 設計パラダイムによる分類

別の分類方法として、アルゴリズムの設計方法論やパラダイムで分類する方法がある。それぞれ異なるいくつかのパラダイムが存在する。さらに、個々のパラダイムの中にも様々な異なる形式のアルゴリズムが含まれている。以下に主なパラダイムを挙げる。

### 研究分野による分類

科学のどんな分野にも固有の問題があり、効率的なアルゴリズムが必要とされている。ある分野の問題はまとめて研究されることが多い。そのような分類として、探索アルゴリズム、ソートアルゴリズム、マージアルゴリズム、数値アルゴリズム、グラフアルゴリズム、文字列アルゴリズム、計算幾何アルゴリズム、組合せアルゴリズム、機械学習、暗号理論、データ圧縮アルゴリズム、構文解析などがある。

各分野はオーバーラップしており、ある分野でのアルゴリズムの進歩が、時には全く異なる分野での改善につながることがある。例えば、動的計画法は、本来、産業における資源消費の最適化のために発明されたが、現在では様々な分野での各種問題に適用されている。

### 計算量による分類

アルゴリズムは、入力長に対する計算時間で分類される。あるアルゴリズムは入力長に対して線形時間で完了する。また別のアルゴリズムは指数時間以上かかるし、場合によっては完了しないこともある。さらに、問題によっては計算量の異なる複数のアルゴリズムが存在するし、効率的なアルゴリズムが全く知られていない問題もある。問題によっては、別の問題への写像が存在する。以上のようなことから、計算量による分類は、アルゴリズムについてではなく、問題について行うのが適当とされている。つまり、問題を解く最善のアルゴリズムの計算量に基づいて、問題を分類する。

### 計算能力による分類

アルゴリズムは計算能力によっても分類される。一般にアルゴリズムは計算能力によって階層的に分類される。「再帰的クラス」とは、全てのチューリング計算可能関数についてのアルゴリズムを含むクラスである。このような階層化によって、計算に必要とされる計算資源(時間とメモリ)を制限できる可能性が生じる。「部分再帰クラス」は、全てのチューリング計算可能な関数を得ることはできない。例えば、多項式時間で実行されるアルゴリズムには多くの重要な計算が含まれるが、チューリング計算可能な関数全体を含むことはない。原始再帰関数で実装されるアルゴリズムのクラスは、別の部分再帰的クラスの例である。

Burgin (2005, p. 24) は、関数を計算するアルゴリズムは有限ステップ後に必ず出力が決定されなければならないという一般的条件を緩めたアルゴリズムの汎用的定義を行った。彼は「超再帰的クラス」を「チューリングマシンで計算可能でない関数を計算可能なアルゴリズムのクラス」と定義した(Burgin 2005, p. 107)。これはハイパーコンピュータの手法の研究と密接に関係している。

## 法的問題

### 特許

アルゴリズム自体は一般に特許化できない。アメリカ合衆国では、抽象概念、数、信号の単純な操作だけから成る請求項は「プロセス」を構成しないとされるので、アルゴリズムは特許化できない。

しかし、アルゴリズムの具体的応用は特許化可能な場合がある。例えば、Diamond v. Diehrのケースでは、単純なフィードバックアルゴリズムを使った合成ゴムの硬化処理が特許として認められた。

データ圧縮アルゴリズムの分野では、ソフトウェア特許が論争の元になることが多く、例えばユニシスのLZWアルゴリズムの特許問題が有名である。

圧縮アルゴリズムで有名な特許問題は他に算術符号も挙げられる。算術符号で取得されている特許の範囲は3点であるとされている。算術符号によって断念されたソフトウェアやファイル形式は多く、代替品が相次いで開発された。

線型計画問題の解法であるカーマーカーのアルゴリズムは日本において特許無効審判がなされたが、2000年12月11日付けで特許庁に当該特許の放棄による特許権抹消の登録が行われたため、最終的に審判が却下された。

### 著作権

著作権の観点では、日本において著作権法10条3項にて明示的にアルゴリズムは同法の保護対象の外であることが定められている。ただし人がアルゴリズムを記述した文書や、人がアルゴリズムを実装したプログラムコードは著作物として保護対象になりうる(文書やプログラムを経由して「アルゴリズムが保護」されるということではない。つまりこの文章は、アルゴリズムについて書いてあるわけではない。保護を受けるのはアルゴリズムそのものではなくて、アルゴリズムの具体的な表現としての著作物である)。

### 登録商標

アルゴリズム自体が保護される訳では無いが、商標の基準を満たしていればアルゴリズム名称を商標として登録することはできる。ただしアルゴリズム名称はその性質上から通常は一般名詞として通用するものであり、一般名詞と同じ語について商標の基準を満たして商標として登録しても、一般名詞の一般名詞としての(すなわちごく当然の)使用を妨げるという通念に反するような権利の濫用はできないような商標法上の制限があるため、通常の、商品名などを登録した場合と違い権利は制限される。

### その他

暗号アルゴリズムには輸出規制されているものもある(アメリカでの例)。

## 代表的なアルゴリズム

- 探索
  - 線型探索、二分探索
  - 幅優先探索、深さ優先探索
  - 文字列探索
  - ハッシュ関数
- ソート
  - 挿入ソート
  - バブルソート
  - クイックソート
  - マージソート
  - ヒープソート
  - バケットソート
- 選択
- マージ

### 数学の問題に対するアルゴリズム

- 筆算 - かけ算(尾乗法)、わり算(長除法)
- ユークリッドの互除法 - 最大公約数を求める
- ガウスの消去法 - 線型方程式系(連立方程式)の解を求める
- ニュートン法 - 繰り返し計算により解の精度を高める方法で非線型方程式の数値解を1つ求める
- ガウス=ルジャンドルのアルゴリズム - 円周率を求める
- 素数判定法 - 与えられた自然数が素数かどうかを判定する
- 素因数分解 - 与えられた自然数を素因数分解する
- 高速フーリエ変換(FFT) - 離散フーリエ変換を計算機上で計算する。工学、理学、医療工学などに広く応用されている。例えば、波形データが含む周波数成分を算出するなど。
- 高速乗算法(数、行列など)

### 設計パラダイム

- 力まかせ探索(ブルートフォース) - 全ての要素を片っ端から調べて探す方法。単純だが非常に汎用的な計算機科学の問題解決法
- 分割統治法
- 動的計画法
- 近似アルゴリズム
  - 貪欲法
  - 局所探索法
- 乱択アルゴリズム(確率的アルゴリズム)
  - ラスベガス法
  - モンテカルロ法
    - ブートストラップ法
- 遺伝的アルゴリズム
- ヒューリスティクス
- 分散アルゴリズム
- 並列アルゴリズム

### 各分野の固有の問題に対するアルゴリズム

- 各種線型計算(連立1次方程式、線型固有値問題、特異値問題)
- 数値積分
- 微分方程式の近似解法(常微分方程式、偏微分方程式、確率微分方程式)

- 線型計画問題
  - シンプレックス法 - 線型計画法の1つ
  - カーマーカー法

- 非線形最適化

- 離散最適化

- グラフ理論における最短経路問題
  - ダイクストラ法
  - ベルマン-フォード法
  - A\* - 推定値つきの場合のダイクストラ法。

- グラフ理論における最小全域木問題
  - クラスカル法 - 貪欲法の一種
  - プリム法

- データ圧縮(デジタル圧縮)
  - ファイル圧縮(ZIP)、画像圧縮(JPEG、GIF)、音声圧縮(MP3)、動画圧縮(MPEG-4、H.264)。

- 暗号
  - RSA暗号 - インターネットセキュリティにおける重要な技術。素因数分解の計算の困難さを利用した公開鍵暗号方式。デジタル署名にも応用されている。

- 誤り検出訂正
  - リード・ソロモン符号 - 最も実用化されている誤り訂正符号の一つ。身近なところではQRコードに使われている。アルゴリズムには有限体の理論が応用されている。
  - ターボ符号 - 第三世代携帯電話の規格や、宇宙探査機での通信などに使われている。
  - LDPC符号 - 最も効率的な誤り訂正符号の一つ。復号法に確率伝播法が応用されているところが特徴。実用化も進められていて、デジタルテレビの衛星通信の標準として採用されている。

- 擬似乱数生成法
  - 線形合同法
  - メルセンヌ・ツイスタ

- 完全情報ゲームにおける思考法
  - ミニマックス法
  - アルファ・ベータ法 - ミニマックス法の改良

- パターン認識
  - サポートベクターマシン
  - カーネル法

- 確率伝播法 - ベイジアンネットワーク上の計算アルゴリズム。人工知能学習や情報理論の分野などに応用されている。

- ページランク - Google社が開発したウェブページの重要度の判定技術

- 顔認識システム
- 音声認識