アルゴリズム

アルゴリズム 、有限のステップ数で、質問への回答または問題の解決策を生成する体系的な手順。名前はラテン語の翻訳に由来し、 インド人のアルゴリズム数 、9世紀のイスラム教徒の数学者の アルクワリズミ の算術 論文 ヒンドゥー教のレコニングの芸術に関するアル・クワリズミ。

ビートジェネレーションの本を定義する

ケースまたは値の有限セットのみに関する質問または問題の場合 アルゴリズム 常に存在します（少なくとも原則として）。それは答えの値の表で構成されています。一般に、質問や問題に答えるのはそれほど簡単な手順ではありません。 無限 考慮すべきケースまたは値の数（自然数（1、2、3、…）など） に プライム？または自然数の最大公約数は何ですか に そして b ？これらの質問の最初のものは、決定可能と呼ばれるクラスに属しています。はいまたはいいえの答えを生成するアルゴリズムは、決定手順と呼ばれます。 2番目の質問は、computableと呼ばれるクラスに属しています。特定の数の答えにつながるアルゴリズムは、計算手順と呼ばれます。

アルゴリズム そのような無限のクラスの質問の多くに存在します。ユークリッド原論 要素 、約300を公開bce、2つの自然数の最大公約数を見つけるための1つが含まれています。すべての小学生は、自然数を除算する際の質問のアルゴリズムである筆算でドリルされます に 別の自然数で b 、商と剰余は何ですか？この計算手順を使用すると、決定可能な質問への回答が得られます。 b 分割する に ？ （余りがゼロの場合、答えは「はい」です）。これらのアルゴリズムを繰り返し適用すると、最終的に決定可能な質問に対する答えが得られます。 に プライム？ （答えはノーです に 1）以外の小さい自然数で割り切れる。

共和制の政府形態とは

無限のクラスの問題を解決するためのアルゴリズムが存在できない場合があります。特に、受け入れられたメソッドにさらに制限が加えられている場合はそうです。たとえば、ユークリッドの時代から、コンパスと直定規（マークのない定規）のみを使用する必要がある2つの問題、つまり角の三等分と特定の円に等しい面積の正方形の作成は、不可能であることが示される前に何世紀にもわたって追求されてきました。 。 20世紀の変わり目に、影響力のあるドイツの数学者David Hilbertは、数学者が次の世紀に解決すべき23の問題を提案しました。彼のリストの2番目の問題は、算術の公理の一貫性の調査を求めました。ほとんどの数学者は、オーストリア生まれの論理学者クルト・ゲーデルが証明または反証できない算術命題（または質問）が存在しなければならないという驚くべき結果を示した1931年まで、この目標の最終的な達成にほとんど疑いを持っていませんでした。本質的に、そのような提案は、決して終わらない決定手順につながります（停止問題として知られている状態）。失敗した努力で 確認する 少なくともどの命題が解決できないのか、英国の数学者で論理学者のアラン・チューリングは、大まかに理解されているアルゴリズムの概念を厳密に定義しました。チューリングは、決定不可能な命題が存在する必要があることを証明することになりましたが、汎用アルゴリズムマシンまたはチューリングマシンの本質的な機能に関する彼の説明は、 コンピュータサイエンス 。今日、決定可能性と計算可能性の問題は、特別なタイプのアルゴリズムであるコンピュータープログラムの設計の中心となっています。