■アルゴリズム

アルゴリズム（英: Algorithm）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための効率的手順を定式化した形で表現したものを意味する。算法（さんぽう）と訳されることもある。 コンピュータにアルゴリズムを指示するための（電子）文書をプログラムという。人間より早く大量に正しい結果を導くことができるのがコンピュータの強みであるが、そのためには正しいアルゴリズムにもとづくプログラムが必要である。 歴史 記録に残る最古のアルゴリズムは、履歴書の原論に載っているユークリッドの互除法であるといわれている。これは、二つの整数の最大公約数を求めるアルゴリズムである。 アルゴリズムという名称は、9世紀の現在のイラクのバグダードの数学者アル・フワーリズミー (al-Khwarizmi、?????????) の名前から来ているといわれている。彼の著作『インドの数の計算法』825年が、12世紀にチェスターのロバート（あるいはバスのアデレード）によってラテン語に翻訳され、『Algoritmi de numero Indorum』（アルゴリトミ・デ・ヌーメロ・インドルム、直訳すると「インドの数に関して」）という題で、以後500年間にわたってヨーロッパ各国の大学で数学の主要な教科書として用いられた。この書は、冒頭にある「Algoritmi dicti」（「アル・フワリズミに曰く」）の一節のため『Algoritmi』（アルゴリトミ）と呼ばれていた。 大雑把な定義 「アルゴリズム」の広く受け入れられている形式的定義はまだ存在しない。しかし、その手がかりはいくつかあり、その大まかな意味は次の引用に表されている。 人間は、何らかの記法で1つの可算無限集合の全ての元の名前を、十分に速く、あるいは長く、あるいは小さく、順に記述することはできない。しかし、特定の可算無限集合について、同程度に役に立つことはできる。例えば、任意の有限な n について、集合の n 番目の元を決定する明確な指示を与えることができる。そのような指示は極めて明示的にすることができ、計算機械が実行できる形式にもできるし、記号について初歩的な操作しかできない人が実施できる形式にもできる。[1] 「可算無限」とは、「無限にまで拡張した整数で数えられる」という意味である。つまり、ここで言うアルゴリズムは、仕事には 0 から無限大までを含む任意の整数（群）の「入力」から、出力すべき整数を「生成」する過程についての指示を「含む」ものとされている。従って例えば、y = m + n のような（2つの任意の入力変数 m と n から出力 y を生成する）代数方程式もアルゴリズムと見ることができる。実際には、アルゴリズムの意味はもっと広く、方程式の例で言うと、次のようになる。 （計算主体が理解できる言語で書かれた）正確な指示であり、計算主体（適当な情報と機能を内包した機械や人）の動作を示した効率的な過程を表す。その過程には、任意の入力の m と n といった整数/記号や + と = といった記号を受け付けて、復号化し、妥当な時間内に出力整数 y を指定された位置に指定された形式で確実かつ効率的に生成することが含まれる。 アルゴリズムの概念は、決定可能性の概念定義にも使われる。その概念は、小さな公理群と規則群を始点として形式体系が如何に形成されるかを説明する際の重要な部分となる。論理学では、アルゴリズムが完了するまでに要する時間は、一般的な物理的次元とは関連していないため、測定できない。そのような不確実性があるため、アルゴリズムという用語を正確に定義できないという側面もある。 厳密な定義 1920?30年代、アルゴリズムの概念を定式化する為の数学モデル（計算モデル）がいくつも提案された（チューリングマシン、帰納的関数、λ計算など）。のちにこれらの定義はすべて同等であることがわかり、チャーチはこれらの同値な概念をアルゴリズムと考えることを提案した（チャーチの提唱）。このため現在では、チューリング機械の状態遷移図（もしくはそれと等価なもの）をアルゴリズムと呼ぶ。 アルゴリズムの定式化 アルゴリズムはコンピュータが情報を処理する基盤である。すなわち、プログラムは本質的にはアルゴリズムであり、コンピュータが特定のタスク（従業員の給与計算、学生の成績表の印刷など）を（指定された順序で）実行するためのステップをコンピュータに指示する。従って、アルゴリズムはチューリング完全なシステムで実行可能な操作の並びと見做すこともできる。 …チューリングの命題についての非形式的な論証から、より強い命題が正当化される。すなわち、全てのアルゴリズムはチューリング機械でシミュレート可能である…Savage [1987] によれば、アルゴリズムはチューリング機械によって定義される計算過程である。[2] アルゴリズムは情報処理と結びついていることが多く、ネットキャッシングは何らかの入力源/機器から読み込まれ、結果は何らかの出力先/機器に書かれるか、更なる処理の入力となるよう保持される。保持されたデータはアルゴリズムを実行する実体の内部状態の一部と見做される。実際、コンピュータでは状態をデータ構造に保持したりする。 このような計算過程について、アルゴリズムは厳密に定義されなければならず、ありうる全ての状況に適用可能な形で指定される。すなわち、どのような条件のステップでも、ケースバイケースで体系的に扱われなければならず、各ケースの扱い方は明確で（計算可能で）なければならない。 アルゴリズムは明確なステップの明確なリストであるため、その計算順序は最も重要である。命令列は、先頭から最後尾に向かって逐次的に実行されるよう記述される。この考え方をより形式的にしたものが制御構造である。 以上の説明は、命令型プログラミングを前提としてアルゴリズムを定式化する場合である。これは、最も典型的な概念であり、タスクを離散的かつ機械的なものとして表すものである。その場合に特有の操作として、変数に値を設定する「代入」がある。これは、直観的にはメモリをメモ帳のようなものと見做すところから生まれた。 これ以外のアルゴリズムの概念化として、関数型プログラミングや論理プログラミングがある。 停止性 アルゴリズムは最終的に必ず停止しなければならないとする定義もある。例えば、クリーネは停止性のあるアルゴリズムを "decision procedure or decision method or algorithm for the question" とした[3]。停止しない可能性のある手続きについては、クヌースは "computational method"[4]と呼び、クリーネは "calculation procedure or algorithm"[3]と呼んでいる。 ミンスキーは、（特定の状態から開始された）アルゴリズムの停止性について次のように述べている。 しかしもし実行中のプロセスの長さが不明ならば、それを試すことは得策ではないかもしれない。何故なら、もしオンラインゲームが永遠に続くなら、我々は答えを得られないかもしれないのだから。[5] アラン・チューリングが停止性問題として提起した通り、任意のアルゴリズムと初期状態が与えられたとき、それが停止するかどうかを判定するアルゴリズム的手続きは存在しない。なお、アルゴリズムの停止性を解析するtermination analysisというものもある。 不完全な（あるいは間違った）アルゴリズムは、次のいずれかの結果となる。 停止しない。 解の範囲を逸脱した値を返して停止する。 間違った解を返して停止する。 解を返さずに停止する。 これらの組合せ。 クリーネはこれらをアルゴリズム内で検出してエラーメッセージを返すか、可能ならば無限ループに入らせることを提案した[3]。また、結果が真理値である場合についてクリーネは第三の論理記号 "u"（undecided）を使うことも提案している[3]。そうすれば、命題を扱うアルゴリズムで何らかの値を常に生成できるとした。間違った答えを返す問題は、帰納法を使ったアルゴリズムに関する個別の「証明」で解決される。 通常、これ（アルゴリズムがμ再帰関数を正しく定義しているかという問題）には補助的な証拠を必要とする。それは例えば、個々の引数の値について、計算が一意な値で終了するかという帰納的証明の形式で示される。[5] アルゴリズムの表現 アルゴリズムには様々な記法があり、自然言語、擬似コード、フローチャート、プログラミング言語などがある。アルゴリズムの自然言語表現は冗長であいまいになる傾向があり、複雑なアルゴリズムや技術的な場面では単独ではほとんど使用されない。擬似コードやフローチャートはアルゴリズムを構造的に表現でき、自然言語のようなあいまいさもほとんどない。プログラミング言語でアルゴリズムを示すこともよくある。 アルゴリズムの記述は、チューリング機械に関する記述として以下の3つに分類される。[6] 高レベルな記述 自然言語でアルゴリズムを説明したもの。実装の詳細は省かれている。このレベルでは、テープやヘッドの動きまでは説明しない。 実装レベルの記述 チューリング機械のヘッドの動きやテープへのデータ格納方法を自然言語で説明する。このレベルでは機械の状態や遷移関数の詳細は説明しない。 形式的記述 最も詳しい説明。チューリング機械の「状態表」を提示する。 最初の要素（数）が最大と仮定する。 残りのリスト上の数を順に見ていき、最大の数よりも大きい数が見つかったら、それを新たな最大として記憶する。 最後に記憶した数がそのリストでの最大の数であり、これで処理が完了する。 次に、プログラミング言語的にやや形式的に記述すると、次のような擬似コードになる（"←" は代入を表し、"return" はその後に記された値を返し、アルゴリズムが終了することを意味する）。 擬似形式的記述: 入力: 数の空でないリスト L 出力: リスト L 内の最大（largest）の数 アルゴリズム解析 あるアルゴリズムが必要とする計算資源（時間や記憶領域）の量を知ることは重要である。そのような定量的な値を求める手法はアルゴリズム解析と呼ばれ、研究されてきた。例えば、上記のアルゴリズムの必要とする時間をO記法とリストの長さを表す n を使って表すと O(n) となる。このアルゴリズムでは、常に2つの値だけを記憶しておけばよい（その時点での最大の数と現在見ているリスト上の位置）。従って、必要とする領域は O(1) となるが、入力となっているリスト上の要素数を数える記憶領域も含めるなら O(log n) となる。 同じ問題であっても、アルゴリズムが異なれば、必要とする時間や記憶領域の量も異なる。例えば、ソートには様々なアルゴリズムがあるが、それぞれ必要な時間や記憶領域の量が異なる。 アルゴリズム解析は計算機科学の一部であり、特定のプログラミング言語や実装を前提とせずに、抽象的に解析を行うことが多い。これは、アルゴリズムの様々な属性に注目した他の数学的分野とも共通する。一般に非常に単純化した汎用的表現として擬似コードが使われる。 分類 アルゴリズムには様々な分類方法があり、それぞれに利点がある。 実装による分類 アルゴリズム分類の1つの方法として、実装手段による分類がある。 決定的アルゴリズムでは解法の全ステップが常に正確に決定されるが、非決定的アルゴリズムは言わば推量や推測で問題を解くもので、ヒューリスティクスを使ってより正確に推測する。 「正確」か、「近似」か 多くのアルゴリズムは正確な解を得るものだが、近似アルゴリズムは真の解に近い近似値を探す。近似には決定性の戦略もあれば、乱択の戦略もある。多くの難しい問題では、近似アルゴリズムしか実用的な解法が存在しない。 設計パラダイムによる分類 別の分類方法として、アルゴリズムの設計方法論やパラダイムで分類する方法がある。それぞれ異なるいくつかのパラダイムが存在する。さらに、個々のパラダイムの中にも様々な異なる形式のアルゴリズムが含まれている。以下に主なパラダイムを挙げる。