テストサイトVo.2

• カテゴリ

• ITリンク集

IT用語：アルゴリズム

概要

アルゴリズム（英: Algorithm）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための効率的手順を定式化した形で表現したものを意味する。算法（さんぽう）と訳されることもある。

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

歴史

記録に残る最古のアルゴリズムは、エウクレイデスの原論のものである。その中でも、二つの整数の最大公約数を求めるユークリッドの互除法[1]は、典型的なアルゴリズムとして知られている。
「アルゴリズム」という名称は、現在のイラクのバグダードにおける9世紀の数学者アル・フワーリズミー (al-Khwarizmi、?????????) の名前から来ているといわれている。825年に書かれた彼の著作『インドの数の計算法』が、12世紀にチェスターのロバート（あるいはバスのアデレード）によってラテン語に翻訳され、『Algoritmi de numero Indorum アルゴリトミ・デ・ヌーメロ・インドルム』（直訳すると「インドの数におけるアルゴリトミ」）という題で、以後500年間にわたってヨーロッパ各国の大学で数学の主要な教科書として用いられた。この書は、冒頭に「Algoritmi dicti（アル・フワリズミーに曰く）」という一節があるので『Algoritmi（アルゴリトミ）』と呼ばれていた。

大雑把な定義

「アルゴリズム」の広く受け入れられている形式的定義はまだ存在しない。しかし、その手がかりはいくつかあり、その大まかな意味は次の引用に表されている。

人間は、何らかの記法で1つの可算無限集合の全ての元の名前を、十分に速く、あるいは長く、あるいは小さく、順に記述することはできない。しかし、特定の可算無限集合について、同程度に役に立つことはできる。例えば、任意の有限な n について、集合の n 番目の元を決定する明確な指示を与えることができる。そのような指示は極めて明示的にすることができ、計算機械が実行できる形式にもできるし、記号について初歩的な操作しかできない人が実施できる形式にもできる。

「可算無限」とは、「無限にまで拡張した整数で数えられる」という意味である。つまり、ここで言うアルゴリズムは、理論的には 0 から無限大までを含む任意の整数（群）の「入力」から、出力すべき整数を「生成」する過程についての指示を「含む」ものとされている。したがって、例えば、y = m + n のような（2つの任意の入力変数 m と n から出力 y を生成する）代数方程式もアルゴリズムと見ることができる。実際には、アルゴリズムの意味はもっと広く、方程式の例で言うと、次のようになる。

（計算主体が理解できる言語で書かれた）正確な指示であり、計算主体（適当な情報と機能を内包した機械や人）の動作を示した効率的な過程を表す。その過程には、任意の入力の m と n といった整数/記号や + と = といった記号を受け付けて、復号し、妥当な時間内に出力整数 y を指定された位置に指定された形式で確実かつ効率的に生成することが含まれる。

アルゴリズムの概念は、決定可能性の概念定義にも使われる。その概念は、小さな公理群と規則群を始点として形式体系がいかに形成されるかを説明する際の重要な部分となる。論理学では、アルゴリズムが完了するまでに要する時間は、一般的な物理的次元とは関連していないので、測定できない。そのような不確実性があるので、アルゴリズムという用語を正確に定義できないという側面もある。