アルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動先: 案内、 検索
ファイル:LampFlowchart.svg
フローチャートはアルゴリズムの視覚的表現としてよく使われる

アルゴリズム（テンプレート:Lang-en-short）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。「テンプレート:ルビ」と訳されることもある。

問題はその解を持っているが、アルゴリズムは正しくその解を得るための具体的手順を与える。さらに多くの場合に効率性が重要となる。

コンピュータにアルゴリズムを指示するための（電子）文書をプログラムという。人間より速く大量に正しい結果を導くことができるのがコンピュータの強みであるが、そのためにはプログラムは正しく効率的なアルゴリズムに基づくことが必要である。

歴史

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

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

厳密な定義

1920〜30年代、アルゴリズムの概念を定式化するための数学モデル（計算モデル）がいくつも提案された（チューリングマシン、帰納的関数、λ計算など）。後にこれらの定義はすべて同等であることがわかり、チャーチはこれらの同値な概念をアルゴリズムと考えることを提案した（チャーチの提唱）。したがって、現在では、チューリング機械の状態遷移図（またはそれと等価なもの）をアルゴリズムと呼ぶ。

アルゴリズムの定式化

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

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

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

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

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

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

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

停止性

アルゴリズムは最終的に必ず停止しなければならないとする定義もある。例えば、クリーネは停止性のあるアルゴリズムを「decision procedure for the question」「decision method for the question」「algorithm for the question」とした[4]。停止しない可能性のある手続きについては、クヌースは「computational method」[5]と呼び、クリーネは「calculation procedure」「algorithm」[4]と呼んでいる。

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

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

アラン・チューリングが停止性問題として提起したとおり、任意のアルゴリズムと初期状態が与えられたとき、それが停止するかどうかを判定するアルゴリズム的手続きは存在しない。なお、アルゴリズムの停止性を解析するテンプレート:仮リンクというものもある。

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

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

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

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

アルゴリズムの表現

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

アルゴリズムの記述は、チューリング機械に関する記述として次の3つに分類される。[8]

高レベルな記述
自然言語でアルゴリズムを説明したもの。実装の詳細は省かれている。このレベルでは、チューリング機械のテープやヘッドの動きまでは説明しない。
実装レベルの記述
チューリング機械のヘッドの動きやテープへのデータ格納方法を自然言語で説明する。このレベルでは機械の状態や遷移関数の詳細は説明しない。
形式的記述
最も詳しい説明。チューリング機械の「状態表」を提示する。

実装

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

例

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

概念的記述:

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

次に、プログラミング言語的にやや形式的に記述すると、次のような擬似コードになる（「←」は代入を表し、「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

アルゴリズム解析

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

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

アルゴリズム解析は計算機科学の一部であり、特定のプログラミング言語や実装を前提とせずに、抽象的に解析を行うことが多い。これは、アルゴリズムの様々な属性に注目した他の数学的分野とも共通する。一般に、非常に単純化した汎用的表現として擬似コードが使われる。

分類

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

実装による分類

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

再帰 / 反復
再帰アルゴリズムは、ある条件が成り立つまで自身を再帰的に呼び出すものであって、関数型言語でよく使われる。反復アルゴリズムは、ループのような反復構造と場合によってはスタックなどのデータ構造を補助的に使い、問題を解く。一部の問題は、どちらか一方の実装が自然である。例えば、ハノイの塔は再帰的実装の方が分かりやすい。再帰アルゴリズムは全て反復アルゴリズムでも実装可能であり、逆も同じである（ただし、複雑さは変化する）。
論理
アルゴリズムは、制御された演繹であるとも言われる。これを アルゴリズム = 論理 + 制御 と表現することもある[9]。論理部分は計算で使われる公理を表し、制御部分は公理に演繹が適用される方法を決定する。これは論理プログラミングというパラダイムの基本である。純粋な論理プログラミングでは、制御部分が固定されていて、アルゴリズムは論理部分だけで指定される。この手法の魅力は、プログラム意味論的なエレガントさがある点である。公理の変化は定式化されたアルゴリズムの変更を伴う。
逐次 / 並列 / 分散
アルゴリズムは通常、コンピュータが一度に1つのアルゴリズム内の1つの命令だけを実行するものと仮定して議論される。このようなコンピュータは、シリアル・コンピュータなどと呼ばれることもある。そういった環境向けに設計されたアルゴリズムは逐次アルゴリズムと呼ばれ、それとは対照的な分類として並列アルゴリズムや分散アルゴリズムがある。並列アルゴリズムは、複数のプロセッサが同時並行して同じ問題を解くのに使えるコンピュータアーキテクチャで有効である。また、分散アルゴリズムは、複数のマシンがコンピュータネットワークで相互接続された環境で使われる。並列/分散アルゴリズムは、問題を分割して解き、その結果を集めて最終的な結果を得る。その場合、個々のプロセッサの計算時間（実行命令数）だけでなく、プロセッサ間の通信オーバーヘッドも計算資源の消費量として問題になる。例えば、ソートアルゴリズムは効率的に並列化できるものもあるが、通信オーバーヘッドは高くつく（部分数列をソートした結果を集めるには、結局部分数列そのものをやりとりしなくてはならない）。反復アルゴリズムは一般に並列化可能である。並列アルゴリズムがない問題は、本質的に逐次的な問題である。
決定性 / 非決定性
決定性アルゴリズムでは解法の全ステップが常に正確に決定されるが、非決定性アルゴリズムはいわば推量や推測で問題を解くものであり、ヒューリスティクスを使ってより正確に推測する。
正解 / 近似解
一般にアルゴリズムは正解を得るものだが、近似アルゴリズムは近似解を求め、これも広義のアルゴリズムとして含めて考えることができる。近似には、決定性の戦略もあれば、乱択の戦略もある。多くの難しい問題では、近似アルゴリズムしか実用的な解法が存在しない。近似アルゴリズムはその近似解の近似性能も評価・保証などがされる必要がある。

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

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

分割統治法
分割統治法は、問題を（通常再帰的に）複数または単一の同じ種類のもっと小さい問題に還元していき、最終的に容易に解ける程度の大きさにする。分割統治の例としてはマージソートがある。ソートは入力データを分割してそれぞれに対して行われ、統治フェーズではそれらの結果をマージする。分割統治法を単純化したものとして decrease and conquer algorithm がある。これは、問題を全く同じ複数の部分問題に分割し、その解をより大きな問題を解くのに利用する。分割統治法では一般に分割された個々の部分問題は全く同じではないため、統治フェーズは decrease and conquer algorithm よりも複雑になる。decrease and conquer algorithm の例として二分探索がある。
動的計画法
部分問題の最適解から全体の最適解が得られるような構造の問題や、同じ部分問題の最適解が様々な問題の解法に有効であるような問題の場合、動的計画法を使って既に計算済みの解を再計算するのを避けることができ、解法を効率化できる。例えば重み付けのあるグラフでの最短経路を求める場合、始点に隣接する全ての頂点について最短経路が分かっていれば、容易に最短経路が求められる。動的計画法とメモ化は密接な関係がある。分割統治法との違いは、分割統治法では部分問題は多少なりとも独立しているのに対して、動的計画法では部分問題が重複している。単純な再帰との違いは、再帰部分をキャッシュ化またはメモ化する点である。部分問題が互いに独立している場合、メモ化は何の役にも立たない。したがって、動的計画法はあらゆる複雑な問題の解法とはならない。動的計画法では、メモ化あるいは既に解かれた部分問題の表を使うことによって、指数関数的性質をもつ問題を多項式レベルの複雑性に削減することができる。
貪欲法
貪欲法は動的計画法に似ているが、部分問題の解を各段階では知る必要がないという点が異なる。その代わりに、各時点で最もよい選択と思われるものを選んでいく。貪欲法では、それまでの選択と現時点の局所最適解から最適と思われる解を構築していくのであって、考えられるあらゆる解を評価することはない。したがって網羅的ではなく、必ずしも正解にたどり着けるわけではない。しかし、性能は非常によい。貪欲法としてよく知られている例として、最短経路木を求めるクラスカル法、プリム法、ダイクストラ法などがある。
線型計画法
線型計画法で解ける問題では、制約条件として入力に関する線型の不等式があり、入力に関するある線型の関数を最大化（または最小化）する値の組合せを求めるものである。有向グラフに関する最大フロー問題など、多くの問題が線型計画問題として記述でき、シンプレックス法などの汎用アルゴリズムで解くことができる。線型計画法の解空間を整数に限定したものを整数計画法と呼ぶ。
還元
この技法は、難しい問題をほぼ最適なアルゴリズムが既知の別の問題に変換するものである。例えば、ソートされていない数列から中央値を求める選択アルゴリズムとして、まずその数列をソートし、そこから真ん中に位置する値を取り出すという方式がある。
探索と数え上げ
チェスの手を考えるなどといった問題は、グラフ問題としてモデル化できる。そのような問題では、比較的よく研究されているグラフ探索アルゴリズムを使うことができる。このカテゴリーには、探索アルゴリズム、分枝限定法、バックトラッキングも含まれる。
確率的パラダイムとヒューリスティクス
ここに分類されるのは広義のアルゴリズムである。
  • 乱択アルゴリズム - 選択を無作為（あるいは擬似無作為）的に行う。問題によっては、無作為性をもった解法が最も性能がよいと証明されているものもある。
  • 遺伝的アルゴリズム - 生物の進化過程をまねた手法で解を求めるもの。無作為な突然変異を加えて、次世代の解を生成していく。つまり、自然淘汰と自己複製をエミュレートしている。遺伝的プログラミングでは、この考え方をアルゴリズム生成にまで拡大している（アルゴリズム自体を問題の解とみなす）。
  • ヒューリスティクス - 計算資源が限られている状況での近似解を求めることを目的としている。正解を求めるのには適さない。例えば、局所探索法、タブーサーチ、焼きなまし法といった、何らかの無作為性を導入して確率的に解を発見しようとするアルゴリズムがある。例えば焼きなまし法という名前は、冶金学の焼きなましに由来する。加熱と冷却によって金属結晶の欠陥がなくなるように、無作為性を与えて局所的な最適解に陥るのを防ぎ、徐々に無作為性を小さくすることによって最終的に1つの解に落ち着くというアルゴリズムである。

研究分野による分類

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

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

計算量による分類

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

計算能力による分類

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

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

法的問題

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

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

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

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

また、暗号アルゴリズムには輸出規制されているものもある（アメリカでの例）。

代表的なアルゴリズム

テンプレート:Seealso

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

設計パラダイム

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

  • データ圧縮（デジタル圧縮）
    • ファイル圧縮（ZIP）、画像圧縮（JPEG、GIF）、音声圧縮（MP3）、動画圧縮（MPEG-4、H.264）。
  • 誤り検出訂正
    • リード・ソロモン符号 - 最も実用化されている誤り訂正符号の一つ。身近なところではQRコードに使われている。アルゴリズムには有限体の理論が応用されている。
    • ターボ符号 - 第三世代携帯電話の規格や、宇宙探査機での通信などに使われている。
    • LDPC符号 - 最も効率的な誤り訂正符号の一つ。復号法に確率伝播法が応用されているところが特徴。実用化も進められていて、デジタルテレビの衛星通信の標準として採用されている。
  • ページランク - Google社が開発したウェブページの重要度の判定技術

脚注

テンプレート:Reflist

関連項目

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

計算モデル関連

外部リンク

テンプレート:Link GA

  1. ↑ ユークリッド『原論』第 7 巻「数論」、命題 1〜3。
  2. ↑ テンプレート:Rtl翻字併記
  3. ↑ Yuri Gurevich「Sequential Abstract State Machines Capture Sequential Algorithms」ACM Transactions on Computational Logic、第1巻、no 1 (2000年7月)、pages 77–111
  4. ↑ 4.0 4.1 4.2 4.3 テンプレート:Cite book
  5. ↑ テンプレート:Cite book
  6. ↑ 6.0 6.1 テンプレート:Cite book
  7. ↑ テンプレート:Lang-en-short、不定
  8. ↑ テンプレート:Cite book
  9. ↑ テンプレート:Cite journal
  10. ↑ 10.0 10.1 Burgin, M. Super-recursive algorithms, Monographs in computer science, Springer, 2005. ISBN 0387955690
  11. ↑ 米国特許商標庁 (2006), 2106.02 **>Mathematical Algorithms< - 2100 Patentability, Manual of Patent Examining Procedure (MPEP).
「http://wikippe.e-do-match.com/index.php?title=アルゴリズム&oldid=771」から取得