アルゴリズム

アルゴリズム︵英: algorithm︶とは、解が定まっている﹁計算可能﹂問題に対して、その解を正しく求める手続きをさす。あるいはそれを形式的に表現したもの。

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

アルゴリズムの実行は形態によらない。コンピュータプログラムはコンピュータ上に実装されたアルゴリズムの例である。

概要

フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。

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

特に、同類の問題一般に対し、有限回の基本的操作を、指示の順を追って実行すれば、解がある場合にはその解が得られ、解がない場合にはそのことが確かめられるように、はっきりと仕組んである手順。

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

歴史

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

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

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

形式化

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

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

…チューリングの命題についての非形式的な論証から、より強い命題が正当化される。すなわち、全てのアルゴリズムはチューリング機械でシミュレート可能である…Savage [1987] によれば、アルゴリズムはチューリング機械によって定義される計算過程である。

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

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

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

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

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

アルゴリズムの記述

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

停止性

「計算可能性理論」も参照

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

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

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

しかしもし実行中のプロセスの長さが不明ならば、それを試すことは得策ではないかもしれない。何故なら、もしプロセスが永遠に続くなら、我々は答えを得られないかもしれないのだから。

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

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

●停止しない。

●解の範囲を逸脱した値を返して停止する。

●誤った解を返して停止する。

●解を返さずに停止する。

●これらの組合せ。

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

通常、これ︵アルゴリズムがμ再帰関数を正しく定義しているかという問題︶には補助的な証拠を必要とする。それは例えば、個々の引数の値について、計算が一意な値で終了するかという帰納的証明の形式で示される。

その他の表現

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

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

高レベルな記述

自然言語でアルゴリズムを説明したもの。実装の詳細は省かれている。このレベルでは、チューリング機械のテープやヘッドの動きまでは説明しない。

実装レベルの記述

チューリング機械のヘッドの動きやテープへのデータ格納方法を自然言語で説明する。このレベルでは機械の状態や遷移関数の詳細は説明しない。

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

形式的記述

チューリングマシン#形式的な定義を参照。

実装

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

例

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

概念的記述

(一)最初の要素︵数︶が最大と仮定する。

(二)残りのリスト上の数を順に見ていき、最大の数よりも大きい数が見つかったら、それを新たな最大として記憶する。

(三)最後に記憶した数がそのリストでの最大の数であり、これで処理が完了する。

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

擬似形式的記述

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

algorithm 最大値を求める is
  largest ← L0
  for each item ∈ リスト L≧1 do
    if largest ＜ item then
      largest ← item
    end
  end
  return largest
end

アルゴリズム解析

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

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

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

分類

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

実装による分類

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

再帰 / 反復

再帰アルゴリズムは、ある条件が成り立つまで自身を再帰的に呼び出すものであって、関数型言語でよく使われる。反復アルゴリズムは、ループのような反復構造と場合によってはスタックなどのデータ構造を補助的に使い、問題を解く。一部の問題は、どちらか一方の実装が自然である。例えば、ハノイの塔は再帰的実装の方が分かりやすい。再帰アルゴリズムは全て反復アルゴリズムでも実装可能であり、逆も同じである︵ただし、複雑さは変化する︶。

論理

アルゴリズムは、制御された演繹であるとも言われる。これを アルゴリズム = 論理 + 制御 と表現することもある。論理部分は計算で使われる公理を表し、制御部分は公理に演繹が適用される方法を決定する。これは論理プログラミングというパラダイムの基本である。純粋な論理プログラミングでは、制御部分が固定されていて、アルゴリズムは論理部分だけで指定される。この手法の魅力は、プログラム意味論的なエレガントさがある点である。公理の変化は定式化されたアルゴリズムの変更を伴う。

逐次 / 並列 / 分散

アルゴリズムは通常、コンピュータが一度に1つのアルゴリズム内の1つの命令だけを実行するものと仮定して議論される。このようなコンピュータは、シリアル・コンピュータなどと呼ばれることもある。そういった環境向けに設計されたアルゴリズムは逐次アルゴリズムと呼ばれ、それとは対照的な分類として並列アルゴリズムや分散アルゴリズムがある。並列アルゴリズムは、複数のプロセッサが同時並行して同じ問題を解くのに使えるコンピュータアーキテクチャで有効である。また、分散アルゴリズムは、複数のマシンがコンピュータネットワークで相互接続された環境で使われる。並列/分散アルゴリズムは、問題を分割して解き、その結果を集めて最終的な結果を得る。その場合、個々のプロセッサの計算時間︵実行命令数︶だけでなく、プロセッサ間の通信オーバーヘッドも計算資源の消費量として問題になる。例えば、ソートアルゴリズムは効率的に並列化できるものもあるが、通信オーバーヘッドは高くつく︵部分数列をソートした結果を集めるには、結局部分数列そのものをやりとりしなくてはならない︶。反復アルゴリズムは一般に並列化可能である。並列アルゴリズムがない問題は、本質的に逐次的な問題である。

決定性 / 非決定性

決定性アルゴリズムでは解法の全ステップが常に正確に決定されるが、非決定性アルゴリズムはいわば推量や推測で問題を解くものであり、ヒューリスティクスを使ってより正確に推測する。

正解 / 近似解

一般にアルゴリズムは正解を得るものだが、近似アルゴリズムは近似解を求め、その近似性に一定の根拠があれば、これも広義のアルゴリズムとして含めて考えることができる。近似には、決定性の戦略もあれば、乱択の戦略もある。多くの難しい問題では、近似アルゴリズムしか実用的な解法が存在しない。近似アルゴリズムはその近似解の近似性能も評価・保証などがされる必要がある。

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

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

分割統治法

分割統治法は、問題を︵通常再帰的に︶複数または単一の同じ種類のもっと小さい問題に還元していき、最終的に容易に解ける程度の大きさにする。分割統治の例としてはマージソートがある。ソートは入力データを分割してそれぞれに対して行われ、統治フェーズではそれらの結果をマージする。分割統治法を単純化したものとして decrease and conquer algorithm がある。これは、問題を全く同じ複数の部分問題に分割し、その解をより大きな問題を解くのに利用する。分割統治法では一般に分割された個々の部分問題は全く同じではないため、統治フェーズは decrease and conquer algorithm よりも複雑になる。decrease and conquer algorithm の例として二分探索がある。

動的計画法

部分問題の最適解から全体の最適解が得られるような構造の問題や、同じ部分問題の最適解が様々な問題の解法に有効であるような問題の場合、動的計画法を使って既に計算済みの解を再計算するのを避けることができ、解法を効率化できる。例えば重み付けのあるグラフでの最短経路を求める場合、始点に隣接する全ての頂点について最短経路が分かっていれば、容易に最短経路が求められる。動的計画法とメモ化は密接な関係がある。分割統治法との違いは、分割統治法では部分問題は多少なりとも独立しているのに対して、動的計画法では部分問題が重複している。単純な再帰との違いは、再帰部分をキャッシュ化またはメモ化する点である。部分問題が互いに独立している場合、メモ化は何の役にも立たない。したがって、動的計画法はあらゆる複雑な問題の解法とはならない。動的計画法では、メモ化あるいは既に解かれた部分問題の表を使うことによって、指数関数的性質をもつ問題を多項式レベルの複雑性に削減することができる。

貪欲法

貪欲法は動的計画法に似ているが、部分問題の解を各段階では知る必要がないという点が異なる。その代わりに、各時点で最もよい選択と思われるものを選んでいく。貪欲法では、それまでの選択と現時点の局所最適解から最適と思われる解を構築していくのであって、考えられるあらゆる解を評価することはない。したがって網羅的ではなく、必ずしも正解にたどり着けるわけではない。しかし、性能は非常によい。貪欲法としてよく知られている例として、最短経路木を求めるクラスカル法、プリム法、ダイクストラ法などがある。

線型計画法

線型計画法で解ける問題では、制約条件として入力に関する線型の不等式があり、入力に関するある線型の関数を最大化︵または最小化︶する値の組合せを求めるものである。有向グラフに関する最大フロー問題など、多くの問題が線型計画問題として記述でき、シンプレックス法などの汎用アルゴリズムで解くことができる。線型計画法の解空間を整数に限定したものを整数計画法と呼ぶ。

還元

この技法は、難しい問題をほぼ最適なアルゴリズムが既知の別の問題に変換するものである。例えば、ソートされていない数列から中央値を求める選択アルゴリズムとして、まずその数列をソートし、そこから真ん中に位置する値を取り出すという方式がある。

探索と数え上げ

チェスの手を考えるなどといった問題は、グラフ問題としてモデル化できる。そのような問題では、比較的よく研究されているグラフ探索アルゴリズムを使うことができる。このカテゴリーには、探索アルゴリズム、分枝限定法、バックトラッキングも含まれる。

確率的パラダイムとヒューリスティクス

ここに分類されるのは広義のアルゴリズム、ないし、遺伝的アルゴリズムのように︵名前に反して︶アルゴリズムではないものである。
●乱択アルゴリズム - 選択を無作為︵あるいは擬似無作為︶的に行う。問題によっては、無作為性をもった解法が最も性能がよいと証明されているものもある。

●遺伝的アルゴリズム - 生物の進化過程をまねた手法で解を求めるもの。無作為な突然変異を加えて、次世代の解を生成していく。自然淘汰と自己複製をエミュレートしているものと看做す視点から﹁遺伝的﹂という命名がされた。

●ヒューリスティクス - 計算資源が限られている状況での近似解を求めることを目的としている。正解を求めるのには適さない。例えば、局所探索法、タブーサーチ、焼きなまし法といった、何らかの無作為性を導入して確率的に解を発見しようとするアルゴリズムがある。例えば焼きなまし法という名前は、冶金学の焼きなましに由来する。加熱と冷却によって金属結晶の欠陥がなくなるように、無作為性を与えて局所的な最適解に陥るのを防ぎ、徐々に無作為性を小さくすることによって最終的に1つの解に落ち着くという手法である。

研究分野による分類

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

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

計算量による分類

「複雑性クラス」も参照

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

計算能力による分類

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

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

法的問題

特許

「ソフトウェア特許」も参照

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

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

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

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

詳細は「算術符号」を参照

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

詳細は「カーマーカーのアルゴリズム」を参照

著作権

著作権の観点では、日本において著作権法10条3項にて明示的にアルゴリズムが同法の保護対象外であることが定められている。ただしアルゴリズムを記した文書や、アルゴリズムを実装したプログラムは著作物として保護対象となる︵文書やプログラムを通して﹁アルゴリズムが保護﹂されるわけではない。つまりこの文章は、アルゴリズムについて書いてあるわけではない︶。

登録商標

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

その他

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

代表的なアルゴリズム

「en:List_of_algorithms」も参照

●探索
●線型探索、二分探索

●幅優先探索、深さ優先探索

●文字列探索

●ハッシュ関数

●ソート
●挿入ソート

●バブルソート

●クイックソート

●マージソート

●ヒープソート

●選択

●マージ

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

●筆算 - かけ算︵尾乗法︶、わり算︵長除法︶

●ユークリッドの互除法 - 最大公約数を求める

●ガウスの消去法 - 線型方程式系︵連立方程式︶の解を求める

●ニュートン法 - 繰り返し計算により解の精度を高める方法で非線型方程式の数値解を1つ求める

●ガウス＝ルジャンドルのアルゴリズム - 円周率を求める

●素数判定法 - 与えられた自然数が素数かどうかを判定する

●素因数分解 - 与えられた自然数を素因数分解する

●高速フーリエ変換︵FFT︶ - 離散フーリエ変換を計算機上で計算する。工学、理学、医療工学などに広く応用されている。例えば、波形データが含む周波数成分を算出するなど。

設計パラダイム

●力まかせ探索︵ブルートフォース︶ - 全ての要素を片っ端から調べて探す方法。単純だが非常に汎用的な計算機科学の問題解決法

●分割統治法

●動的計画法

●近似アルゴリズム
●貪欲法

●局所探索法

●乱択アルゴリズム︵確率的アルゴリズム︶
●ラスベガス法

●モンテカルロ法
●ブートストラップ法

●遺伝的アルゴリズム

●ヒューリスティクス

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

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

●カーマーカー法

●グラフ理論における最短経路問題
●ダイクストラ法

●ベルマン-フォード法

●A* - 推定値つきの場合のダイクストラ法。

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

●プリム法

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

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

●誤り検出訂正
●リード・ソロモン符号 - 最も実用化されている誤り訂正符号の一つ。身近なところではQRコードに使われている。アルゴリズムには有限体の理論が応用されている。

●ターボ符号 - 第三世代携帯電話の規格や、宇宙探査機での通信などに使われている。

●LDPC符号 - 最も効率的な誤り訂正符号の一つ。復号法に確率伝播法が応用されているところが特徴。実用化も進められていて、デジタルテレビの衛星通信の標準として採用されている。

●擬似乱数生成法
●線形合同法

●メルセンヌ・ツイスタ

●完全情報ゲームにおける思考法
●ミニマックス法

●アルファ・ベータ法 - ミニマックス法の改良

●パターン認識
●サポートベクターマシン

●カーネル法

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

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

●顔認識システム

●音声認識

脚注

関連項目

• 逐次アルゴリズム
• 並列アルゴリズム
• 分散アルゴリズム/分散プロトコル
• 近似アルゴリズム
• 確率的アルゴリズム
• オンラインアルゴリズム
• 進化的計算
• アルゴリズム作曲法(en)

計算可能性と複雑性の理論の関連

• 計算可能性理論
• 計算複雑性理論（計算量理論）

計算モデル関連

• チューリングマシン
• 帰納的関数
• λ計算
• チャーチの提唱

外部リンク

• Weisstein, Eric W. "Algorithm". mathworld.wolfram.com (英語).
• Algorithms in Everyday Mathematics
• Algorithms - Curlie（英語）
• The web site of the textbook Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne
• 『アルゴリズム』 - コトバンク