アルゴリズムのソースを表示

{{Wikiversity|アルゴリズム}}
'''アルゴリズム'''（{{lang-en-short|algorithm}}{{efn2|{{IPA-en|ˈælgəˌrɪð''ə''m|}}}}）とは、[[解]]が定まっている「[[計算可能性理論|計算可能]]」問題に対して、その[[解]]を正しく求める手続きをさす<ref group="注">解が存在しない問題に対しては、それを正しく判定できなければならない。</ref>。'''算法'''<ref>{{cite Kotobank|word=アルゴリズム|encyclopedia=百科事典マイペディア|hash=#E7.99.BE.E7.A7.91.E4.BA.8B.E5.85.B8.E3.83.9E.E3.82.A4.E3.83.9A.E3.83.87.E3.82.A3.E3.82.A2|access-date=2024-09-29}}</ref><ref>{{cite Kotobank|word=アルゴリズム|encyclopedia=改訂新版　世界大百科事典|hash=#E6.94.B9.E8.A8.82.E6.96.B0.E7.89.88.E3.80.80.E4.B8.96.E7.95.8C.E5.A4.A7.E7.99.BE.E7.A7.91.E4.BA.8B.E5.85.B8|access-date=2024-09-29}}</ref>、'''計算手順'''<ref>{{cite Kotobank|word=フローチャート|encyclopedia=日本大百科全書(ニッポニカ)|hash=#E6.97.A5.E6.9C.AC.E5.A4.A7.E7.99.BE.E7.A7.91.E5.85.A8.E6.9B.B8.28.E3.83.8B.E3.83.83.E3.83.9D.E3.83.8B.E3.82.AB.29|access-date=2024-09-29}}</ref><ref>{{cite encyclopedia|和書|title=algorithm|encyclopedia=英和 用語・用例辞典|url=https://kotobank.jp/ejword/algorithm%20algorism|via=コトバンク|access-date=2024-09-29}}</ref>、'''処理手順'''<ref>{{cite Kotobank|word=プログラム|encyclopedia=ブリタニカ国際大百科事典 小項目事典|hash=#E3.83.96.E3.83.AA.E3.82.BF.E3.83.8B.E3.82.AB.E5.9B.BD.E9.9A.9B.E5.A4.A7.E7.99.BE.E7.A7.91.E4.BA.8B.E5.85.B8.20.E5.B0.8F.E9.A0.85.E7.9B.AE.E4.BA.8B.E5.85.B8|access-date=2024-09-29}}</ref>とも和訳される。「[[ヒューリスティック]]」に対置する概念である<ref>{{Cite web|和書|url=https://www.keyence.co.jp/ss/general/iot-glossary/algorithm.jsp |title=アルゴリズム {{!}} IoT用語辞典 {{!}} キーエンス |access-date=2024-12-27 |publisher=[[キーエンス]]}}</ref>。

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

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

== 概要 ==
[[画像:LampFlowchart.svg|thumb|right|[[フローチャート]]はアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。]]
[[岩波書店|岩波]]国語辞典「算法」に、まず「計算の方法」とした後に2番目の詳細な語義でalgorithmの訳として、
{{quotation|特に、同類の問題一般に対し、有限回の基本的操作を、指示の順を追って実行すれば、解がある場合にはその解が得られ、解がない場合にはそのことが確かめられるように、はっきりと仕組んである手順。}}
とある。一見では国語辞典らしい平易な日本語で書かれた説明だが、例えば解が無いと[[無限ループ]]に陥るといったようなものは除外されるし、「アルゴリズムの視覚的表現」としてよく使われる[[フローチャート]]のようなもので書いてあっても、基本的操作がはっきりと書いてなければそれはアルゴリズムではない、というわけである。これは、[[#形式化]]の節で述べるような、[[理論計算機科学]]での「アルゴリズム」の扱いに沿っている。

== 歴史 ==
記録に残る最古のアルゴリズムは、[[エウクレイデス]]の[[ユークリッド原論|原論]]のものである。その中でも、二つの整数の[[最大公約数]]を求める[[ユークリッドの互除法]]<ref>ユークリッド『[[ユークリッド原論|原論]]』第 7 巻「数論」、命題 1〜3。</ref>は、典型的なアルゴリズムとして知られている。

「アルゴリズム」という名称は、現在の[[イラク]]の[[バグダード]]における9世紀の数学者[[フワーリズミー|アル=フワーリズミー]]{{efn2|{{Rtl翻字併記|ar|الخوارزمي|al-Khwarizmi}}}}の名前から来ているといわれている。彼が[[インド数学]]を紹介した著作『[[インドの数の計算法]]』（[[825年]]）が、12世紀に[[チェスターのロバート]]（あるいは[[バースのアデラード]]）によってラテン語に翻訳され、『{{lang|la|algoritmi de numero Indorum}} アルゴリトミ・デ・ヌーメロ・インドルム』<ref>{{Cite web |url=https://www.britannica.com/science/algorithm |title=Britannica Encyclopedia - Algorithm: Definition, Types, & Facts |access-date=2023年1月14日 |first=The Editors of Encyclopaedia Britannica |editor=Erik Gregersen |language=en}}</ref>（直訳すると「インドの数における<!--についての？-->アルゴリトミ」）という題で、以後500年間にわたってヨーロッパ各国の大学で数学の主要な教科書として用いられた。この書は、冒頭に「{{lang|la|algoritmi dicti}}（アル・フワリズミーに曰く）」という一節があるので『{{読み仮名|{{lang|la|algoritmi}}|アルゴリトミ}}』と呼ばれていた。

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

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

アルゴリズムは[[コンピュータ]]が情報を処理する基盤である。すなわち、[[プログラム (コンピュータ)|プログラム]]は本質的にはアルゴリズムであり、コンピュータが特定のタスク（従業員の給与計算、学生の成績表の印刷など）を（指定された順序で）実行するためのステップをコンピュータに指示する。したがって、アルゴリズムは[[チューリング完全]]なシステムで実行可能な操作の並びとみなすこともできる。
{{quotation|&hellip;チューリングの命題についての非形式的な論証から、より強い命題が正当化される。すなわち、全てのアルゴリズムはチューリング機械でシミュレート可能である&hellip;Savage <nowiki>[1987]</nowiki> によれば、アルゴリズムはチューリング機械によって定義される計算過程である。<ref>{{cite journal|first=Yuri|last=Gurevich|title=Sequential Abstract State Machines Capture Sequential Algorithms|journal=ACM Transactions on Computational Logic|volume=1|issue=1|date=2000-07-01|pages=77–111|doi=10.1145/343369.343384}}</ref>}}
アルゴリズムは[[情報処理]]と結びついていることが多く、データは何らかの入力源（機器）から読み込まれ、結果は何らかの出力先（機器）に書かれるか、次の処理の入力となるよう保持される。保持されたデータはアルゴリズムを実行する実体の内部状態の一部とみなされる。実際、コンピュータでは状態を[[データ構造]]に保持したりする。

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

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

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

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

=== アルゴリズムの記述 ===
プログラマは[[擬似コード]]などを使うことが多いが、[[理論計算機科学]]での形式的<ref group="注">{{lang-en-short|formal}}</ref>で厳密<ref group="注">{{lang-en-short|rigorous}}</ref>な議論には[[計算モデル]]を使う。もちろん相互に得失があり、必要であれば互いにどちらも使う。

=== 停止性 ===
{{seealso|計算可能性理論}}
アルゴリズムは最終的に必ず停止しなければならないとする定義もある。というより形式的で厳密な議論では停止するものだけがアルゴリズムである（[[チャーチ＝チューリングのテーゼ]]も参照）。

そのため、そうでないものと呼び分ける必要があることもあり、[[スティーヴン・コール・クリーネ|クリーネ]]は停止性のあるアルゴリズムを「{{lang|en|decision procedure for the question}}」「{{lang|en|decision method for the question}}」「{{lang|en|algorithm for the question}}」とした<ref name="Kleene1952">{{cite book|last=クリーネ|first=ステフェン|authorlink=ステフェン・コール・クリーネ|title=Introduction to Metamathematics|edition=第10版|year=1991|publisher=ノースホーランド出版|origyear=1952}}</ref>。停止しない可能性のある手続きについては、[[ドナルド・クヌース|クヌース]]は「{{lang|en|computational method}}」<ref>{{cite book|last=クヌース|first=ドナルド|authorlink=ドナルド・クヌース|title=Fundamental Algorithms, Third Edition|publisher=アジソン・ウェスレイ|location=米国マサチューセッツ州リーディング|year=1997|ISBN 0-201-89683-4}}</ref>と呼び、クリーネは「{{lang|en|calculation procedure}}」「{{lang|en|algorithm}}」<ref name="Kleene1952"/>と呼んでいる。

[[マービン・ミンスキー|ミンスキー]]は、（特定の状態から開始された）アルゴリズムの停止性について次のように述べている。
{{quotation|しかしもし実行中のプロセスの長さが不明ならば、それを試すことは得策ではないかもしれない。何故なら、もしプロセスが永遠に続くなら、我々は答えを得られないかもしれないのだから。<ref name="Minsky1967">{{cite book|last=ミンスキー|first=マービン|authorlink=マービン・ミンスキー|title=Computation: Finite and Infinite Machines|edition=初版|publisher=プレンティスホール、米国ニュージャージー州|year=1967}}</ref>}}

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

不完全な（あるいは間違った）アルゴリズムは、次のいずれかの結果となる。
*停止しない。
*解の範囲を逸脱した値を返して停止する。
*誤った解を返して停止する。
*解を返さずに停止する。
*これらの組合せ。
クリーネはこれらをアルゴリズム内で検出してエラーメッセージを返すか、可能ならば無限ループに入らせることを提案した<ref name="Kleene1952"/>。また、結果が真理値である場合についてクリーネは第三の論理記号「<math>u</math>」<ref group="注">{{lang-en-short|undecided}}、不定</ref>を使うことも提案している<ref name="Kleene1952"/>。そうすれば、命題を扱うアルゴリズムで何らかの値を常に生成できるとした。誤った答えを返す問題は、帰納法を使ったアルゴリズムに関する個別の「証明」で解決される。
{{quotation|通常、これ（アルゴリズムが[[μ再帰関数]]を正しく定義しているかという問題）には補助的な証拠を必要とする。それは例えば、個々の引数の値について、計算が一意な値で終了するかという帰納的証明の形式で示される。<ref name="Minsky1967"/>}}

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

アルゴリズムの記述は、例えば[[チューリングマシン|チューリング機械]]を使ったならば、として次の3つに分類している書籍などがある<ref>{{cite book|last=Sipser|first=Michael|title=Introduction to the Theory of Computation|publisher=PWS出版社|year=2006}}</ref>。
;高レベルな記述
:自然言語でアルゴリズムを説明したもの。実装の詳細は省かれている。このレベルでは、チューリング機械のテープやヘッドの動きまでは説明しない。
;実装レベルの記述
:チューリング機械のヘッドの動きやテープへのデータ格納方法を自然言語で説明する。このレベルでは機械の状態や遷移関数の詳細は説明しない。
（以上の2つのような内容では、そもそも概要で説明したように「はっきり」していない可能性もあるし、詳細が無ければ無限ループに陥らないことを証明することもできない。従ってそもそも実際には「アルゴリズムを記述」してはいない）
;形式的記述
:[[チューリングマシン#形式的な定義]]を参照。

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

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

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

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

===擬似形式的記述===
入力: 空でない数リスト <var>L</var>、出力: リスト <var>L</var> 内の最大（<var>largest</var>）の数。

 '''algorithm''' 最大値を求める '''is'''
   ''largest'' ← <var>L<sub>0</sub></var>
   '''for each''' <var>item</var> '''∈''' リスト <var>L<sub>≧1</sub></var> '''do'''
     '''if''' <var>largest</var> ＜ <var>item</var> '''then'''
       <var>largest</var> ← <var>item</var>
     '''end'''
   '''end'''
   '''return''' <var>largest</var>
 '''end'''

==アルゴリズム解析==
{{出典の明記| date = 2021年7月| section = 1}}
あるアルゴリズムの実行に必要な計算資源（時間や記憶領域）の量を見積もることは重要である。そのような量を定量的に求める分析法は[[アルゴリズム解析]]と呼ばれ、研究がなされてきた。例えば、上記のアルゴリズムの実行に必要な時間はリストの長さを <math>n</math> とするとき[[ランダウの記号|O記法]]を用いて表せば <math>O(n)</math> となる。このアルゴリズムでは、（与えられたリスト以外には）常に（その時点での最大の数と、現在見ているリスト上の位置）2つの値だけを記憶しておけばよい。したがって、必要となる記憶領域の量は <math>O(1)</math> となるが、リストの長さ''n''を記憶して入力として与える場合にはそのための領域も含めるとすると <math>O(\log n)</math> になる。

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

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

== 分類 ==
{{出典の明記| date = 2021年7月| section = 1}}
アルゴリズムには様々な分類方法があり、それぞれに利点がある。

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

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

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

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

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

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

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

== 法的問題 ==
=== 特許 ===
{{See also|ソフトウェア特許}}
アルゴリズム自体は一般に特許化できない。[[アメリカ合衆国]]では、抽象概念、数、信号の単純な操作だけから成る請求項は「プロセス」を構成しないとされるので<ref>[[米国特許商標庁]] (2006), [http://www.uspto.gov/web/offices/pac/mpep/documents/2100_2106_02.htm ''2106.02 **>Mathematical Algorithms< - 2100 Patentability''], Manual of Patent Examining Procedure (MPEP).</ref>、アルゴリズムは特許化できない。

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

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

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

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

=== 著作権 ===
[[著作権]]の観点では、[[日本]]において[[著作権法]][[b:著作権法第10条|10条]]3項にて明示的にアルゴリズムは同法の保護対象の外であることが定められている<ref>[http://chosakuken.bunka.go.jp/naruhodo/answer.asp?Q_ID=0000033 著作権なるほど質問箱] - 文化庁</ref>。ただし人がアルゴリズムを記述した文書や、人がアルゴリズムを実装したプログラムコードは著作物として保護対象になりうる<ref>[http://www.fe-siken.com/kakomon/24_haru/q78.html 基本情報技術者 平成24年春期 午前問78] - 基本情報技術者試験ドットコム</ref>（文書やプログラムを経由して「アルゴリズムが保護」されるということではない。つまりこの文章は、アルゴリズムについて書いてあるわけではない。保護を受けるのはアルゴリズムそのものではなくて、アルゴリズムの具体的な表現としての著作物である）。

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

=== その他 ===
暗号アルゴリズムには輸出規制されているものもある（[[アメリカ合衆国からの暗号の輸出規制|アメリカでの例]]）。

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

{{seealso|en:List_of_algorithms}}

* [[探索]]
** [[線型探索]]、[[二分探索]]
** [[幅優先探索]]、[[深さ優先探索]]
** [[文字列探索]]
** [[ハッシュ関数]]
* [[ソート]]
** [[挿入ソート]]
** [[バブルソート]]
** [[クイックソート]]
** [[マージソート]]
** [[ヒープソート]]
** バケットソート
* [[選択アルゴリズム|選択]]
* [[マージ]]

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

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

=== 設計パラダイム ===

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

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

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

* [[線型計画問題]]
** [[シンプレックス法]] - [[線型計画法]]の1つ
** [[カーマーカーのアルゴリズム|カーマーカー法]]

* 非線形最適化

* 離散最適化

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

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

* [[データ圧縮]]（デジタル圧縮）
** ファイル圧縮（ZIP）、画像圧縮（JPEG、GIF）、音声圧縮（MP3）、動画圧縮（MPEG-4、H.264）。

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

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

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

* [[二人零和有限確定完全情報ゲーム|完全情報ゲーム]]における思考法
** [[ミニマックス法]]
** [[アルファ・ベータ法]] - ミニマックス法の改良

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

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

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

* [[顔認識システム]]
* [[音声認識]]

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist2}}
=== 出典 ===
{{Reflist|2}}

== 関連項目 ==
* [[逐次アルゴリズム]]
* [[並列アルゴリズム]]
* [[分散アルゴリズム|分散アルゴリズム/分散プロトコル]]
* [[近似アルゴリズム]]
* [[確率的アルゴリズム]]
* [[オンラインアルゴリズム]]
* [[進化的計算]]
* [[アルゴリズム作曲法]]([[:en:Algorithmic composition|en]])
* データ構造

=== 計算可能性と複雑性の理論の関連 ===
* [[計算可能性理論]]
* [[計算複雑性理論]]（計算量理論）

=== 計算モデル関連 ===
* [[チューリングマシン]]
* [[帰納的関数]]
* [[機械学習]]
* [[λ計算]]
* [[チャーチの提唱]]
* 量子計算
* DNA計算

== 外部リンク ==
* {{MathWorld | urlname=Algorithm | title=Algorithm}}
* [http://everydaymath.uchicago.edu/educators/Algorithms_final.pdf Algorithms in Everyday Mathematics]
* {{Curlie|Computers/Algorithms/|Algorithms}}
* [https://algs4.cs.princeton.edu/home/ The web site of the textbook Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne]
* {{Kotobank}}

{{アルゴリズム}}{{コンピュータ科学}}{{Normdaten}}
{{DEFAULTSORT:あるこりすむ}}
[[Category:アルゴリズム|*]]
[[Category:離散数学]]
[[Category:数理論理学]]
[[Category:理論計算機科学]]
[[Category:数学に関する記事]]
[[Category:アラビア語の語句]]
[[Category:数学のエポニム]]