有限の数のステップで、質問への回答または問題の解決策を生成するアルゴリズム、体系的な手順。この名前は、9世紀のイスラム教徒数学者アルクワリズミの算数論「ヒンドゥー教の算術に関するアルクワリズミ」のラテン語訳Algoritmi de numero Indorumに由来しています。
コンピュータサイエンス：アルゴリズムと複雑さ
アルゴリズムは、明確に定義された計算問題を解決するための特定の手順です。アルゴリズムの開発と分析が基本です
。
有限のケースまたは値のセットのみを持つ質問または問題の場合、アルゴリズムは常に存在します（少なくとも原則として）。回答の値の表で構成されています。一般に、「自然数（1、2、3、…）は素数ですか？」のように、検討するケースまたは値が無限にある質問または問題に答えるのは、それほど簡単な手順ではありません。または「自然数aとbの最大公約数は何ですか？」これらの質問の最初の質問は、decidableと呼ばれるクラスに属しています。はいまたはいいえの答えを生成するアルゴリズムは、決定手順と呼ばれます。2番目の質問は、computableというクラスに属しています。特定の数値の答えを導くアルゴリズムは、計算手順と呼ばれます。
アルゴリズムは、このような無限のクラスの質問に対して存在します。ユークリッドの要素は、紀元前300年頃に発行され、2つの自然数の最大公約数を見つけるためのものを含んでいました。すべての小学生は、「自然数aを別の自然数bで除算すると、商と剰余は何ですか？」という質問のアルゴリズムである長い除算にドリルされます。この計算手順を使用すると、「bはaを分割するか」という決定可能な質問への回答につながります。（残りがゼロの場合、答えはイエスです）。これらのアルゴリズムを繰り返し適用すると、最終的には決定的な質問「プライムか？」に対する答えが生成されます。（aが1以外の小さい自然数で割り切れる場合、答えはノーです）。
特に、受け入れられたメソッドにさらに制限が加えられている場合は、問題の無限クラスを解決するためのアルゴリズムが存在できない場合があります。たとえば、コンパスと定規（マークされていない定規）だけを使用する必要があるユークリッドの時代からの2つの問題（角度を3等分し、所定の円に等しい面積の正方形を構築する）は、不可能であることが示される前に何世紀にもわたって追求されました。20世紀の初めに、影響力のあるドイツの数学者David Hilbertは、次の世紀に数学者が解く23の問題を提案しました。彼のリストの2番目の問題は、算術の公理の一貫性の調査を求めていました。ほとんどの数学者は、オーストリア生まれの論理学者カートゲーデルが証明または反証できない算術的命題（または質問）が存在しなければならないという驚くべき結果を示した1931年まで、この目標の最終的な達成にほとんど疑いがありませんでした。本質的に、そのような命題は、決して終わらない決定手順（停止問題として知られる状態）につながります。少なくともどの命題が解決できないかを確認することに失敗したが、イギリスの数学者で論理学者のアランチューリングは、アルゴリズムの大まかに理解された概念を厳密に定義した。チューリングは決定できない命題が存在しなければならないことを証明することになったが、あらゆる汎用アルゴリズムマシン、またはチューリングマシンの本質的な機能の彼の説明は、コンピューターサイエンスの基礎となった。今日、決定可能性と計算可能性の問題は、特別なタイプのアルゴリズムであるコンピュータープログラムの設計の中心となっています。
