アルゴリズムとは何か?

アルゴリズムとは、明示的で、精確で、曖昧さを持たない、機械で実行できる簡単な命令を並べたものです。アルゴリズムは通常何らかの目的を念頭において作られます。例えば次のアルゴリズムは、"99 Bottles of Beer on the Wall" という歌の 99 の部分を任意の値にした歌を歌います:

procedure \(\texttt{BottlesOfBeer}\)(\(n\))

for \(i \leftarrow n\) downto \(1\) do

" \(i\) bottles of beer on the wall \(i\)," と歌う

"Take one down, pass it around, \(i - 1\) bottles of beer on the wall." と歌う

"No bottles of beer on the wall, no bottles of beer," と歌う

"Go to the store, buy some more, \(n\) bottles of beer on the wall." と歌う

アルゴリズム恐怖症の古典学者は「アルゴリズム (algorithm)」という語がギリシャ語の「数 (arithmos, \(\acute{\alpha} \varrho \iota \theta \acute{o} \varsigma\))」と「痛み (algos, \(\ddot{\alpha} \lambda \gamma o \varsigma\))」の派生語であると思うかもしれませんが、そうではありません。「アルゴリズム」 という語は九世紀のペルシャ人科学者 Abū 'Abdallāh Muḥammad ibn Mūsā al-Khwārizmī1 (アブー・アブドゥッラー・ムハンマド・イブン・ムーサー・アル=フワーリズミー) に由来します。

Al-Khwārizmī は Al-kitāb al-mukhtaṣar fī ḥisāb al-ğabr wa'l-muqābala (アル・キターブ・アル・ムクタザール・フィ・ヒサブ・アルジャバ・ヴァルムカバラ) という文献2の著者としてもっともよく知られています (現代の「代数 (algebra)」という語はこの文献に由来します)。また Al-Khwārizmī はこれとは別の文献で、数世紀前のインドで発明された、数の処理と筆記のための革新的な十進法 ――ある量が存在しないことを示す小さな円 ṣifr を使う方法―― を説明しています。この文献で数字や石を使って説明される様々な手続きは後に英語で algorism あるいは augrym (アラビア式記数法) と呼ばれるようになり、その数字には cipher (アラビア数字) という名前が付きました。

位取り記数法と Al-Khwārizmī の著作は両方ともヨーロッパの学者の一部には知られていましたが、この "ヒンズー・アラビア式" 記数法がヨーロッパ中に広まったのは中世のイタリア人数学者であり商人でもあった Leonardo of Pisa (ピサのレオナルド) によるところが大きいです。彼は Fibonacci (フィボナッチ) という名の方がよく知られているでしょう。Fibbonacci の 1202 年の著作 Liber Abaci3 などによって、十三世紀のヨーロッパにおける計算4の手段は表 (アバカス) と指5から手書きの数字に移っていきました。なお移行が進んだ理由は数字が使いやすかったり学びやすかったりしたためではなく、手書きの数字を使うと会計の追跡が可能なためです。アラビア数字が西洋で広く使われるようになるのは活版印刷が発明されてからであり、本当に世界中至る所で使われるようになるのはようやく十九世紀になって安い紙が大量に手に入るようになってからです。

やがて algorism という語はギリシャ語 arithmos の派生語だと (そしておそらくは前に触れた algos の派生語だとも6) 誤解され、現代的な algorithm という表記になりました。こういった歴史から、ごく最近まで algorithm という語はアラビア数字を使った位取り法という技法だけを意味していました。この数字を使った手続きをミスなく高速に実行できる人は algorist とか computator あるいは computer と呼ばれました。


  1. 名前を直訳すると 「Adbdulla の父、Moses の子、Khwārizmī 人の Mohammad」となります。Khwārizmī はウズベキスタンの Khorezm (ホラズム) 州にあった古代都市で、現在では Kiva (ヒヴァ) と呼ばれます。[return]

  2. タイトルを直訳すると「約分と消約による計算についての概説」となります。[return]

  3. Liber Abaci は「アバカスについての書」と翻訳したくなるかもしれませんが、より正確な訳は「計算についての書」です。Fibonacci の時代の前も後も、イタリア語 abaco は計算のための機械、技法、学校、書物など、数値計算に関するもの全てを指します。これは英語における "computer science" という語の使われ方と似ています。また、オペレーションリサーチに対応する中国語 ("運籌學") を直訳すると「物を数えるときに使う棒についての学問」となることにも似ていると言えるでしょう。[return]

  4. calculate (計算) という語は「小さい石」を意味するラテン語の calculus が語源です。この石は計算のとき表の上に置く石、つまり詩人チョーサーが言うところの augrym stone のことです。紀元前 440 年、Herodotus (ヘロドトス) は著書『歴史』にこう書いています:「計算をしてその結果を書き留める ("\(\lambda o \gamma \acute{\iota} \zeta \varepsilon \sigma \theta \alpha \iota\, \) \(\psi \acute{\eta} \phi o \iota \varsigma\)" 直訳すると「計算して小石を敷き詰める」) ときギリシャ人は左から右に向かって書くが、エジプト人はその逆である。しかしエジプト人に聞くと、彼らは数を右に向かって書いていると言い、ギリシャ人は左に向かって書いていると言う」 (奇妙なことに、 Herodotus はエジプト人が卵をどちら側から食べるかについては疑問に思わなかったようです)[return]

  5. ☞ Reckoning with digits! ☜[return]

  6. ギリシャ語の接頭語 "algo-" が「技法」あるいは「解説」を意味すると記している中世の資料がいくつかあります。また他の資料を見ると、algorithm という語を発明したのがギリシャの哲学者だったり、インドの王だったり、"Algus" や "Algor"、または "Argus" という名のスペイン王だったりします。 Dante Alighieri (ダンテ・アリギエーリ) の著作をおそらくは含むいくつかの文献では、語源となった神話上のギリシャ人造船技師 (Argonaut) が特定されています。これらの全く誤っている主張が歴史的な正確さを求めてなされたのか、それともただの記憶を助けるための作り話だったのかははっきりしません。[return]

広告