アルゴリズムとは何か
約2,300年前に書かれたユークリッドの『原論』第VII巻にある最大公約数の求め方は、今でもコンピューターの中で動いています。
いつでもうまくいく方法
1071と462の両方を割り切る最大の数が必要だとしましょう。462から1まで順にすべての数を試し、両方を割り切る最初の数で止めることもできます。これでも答えは出ますが、何百回も試すことになるかもしれません。もっと短い方法があります。1071を462で割り、余りの147を残します。次に462を147で割り、余りの21を残します。147を21で割ると余りは0なので、答えは21です。数百回ではなく、3回の割り算ですみます。
この短い方法がアルゴリズムです。アルゴリズムとは、何かの入力を受け取って正しい出力を返す、有限個の正確な手順の並びのことです。これは最大公約数を求めるユークリッドの互除法で、紀元前300年ごろに書かれた『原論』の第VII巻に出てきます。ユークリッドは割り算ではなく、長さを何度も引く形で説明しましたが、考え方は同じです。今のプログラムが使うのは余りを使う形です。
function gcd(a, b) {
while (b !== 0) {
const r = a % b; // 余り
a = b;
b = r;
}
return a;
}
console.log(gcd(1071, 462)); // 21手順の並びがアルゴリズムになる条件
コーメン、レイサーソン、リベスト、シュタインによる教科書などでは、アルゴリズムを「入力を出力に変える、きちんと定められた手続き」と説明しています。この説明には3つのことがつまっていて、どれもコードを書くときに大切です。
- 正確である。どの手順も意味が1つに決まります。「aをbで割って余りを残す」は正確ですが、「なんとかして数を小さくする」は正確ではありません。
- 有限である。必ず止まらなければなりません。ユークリッドの互除法では、余りはいつも割る数より小さくなるので、毎回小さくなっていき、いつか必ず0になります。
- 正しい。試した例だけでなく、許されるすべての入力に対して、出力が正しい答えになります。
身近な例として料理のレシピがよく挙げられますが、これはよい例です。材料が入力、できた料理が出力で、手順には順番があります。違うのは、読む人がどれだけ補うかです。料理をする人は「ひとつまみ」がどれくらいかを自分で決めます。コンピューターは何も決めません。だからコンピューター向けのアルゴリズムは、すべての手順をはっきり書いておくのです。
同じ問題、違うアルゴリズム
1つの問題には、ふつう正しいアルゴリズムがいくつもあり、その仕事量は大きく違うことがあります。1071と462の最大公約数なら、462から順に下へ試していく方法では21にたどりつくまでに442回試しますが、ユークリッドの方法なら割り算3回です。どちらも正しいのですが、速いのは片方だけです。このコースの多くは、その2つ目の問いを扱います。方法が正しいとして、何ステップかかるのか。そして入力が大きくなると、その数はどう増えるのか。
この問いに答えるために、計算機科学者は秒数ではなく基本的なステップ（比較、交換、割り算）の回数を数えます。秒数は機械によって変わります。ステップ数はアルゴリズムと入力だけで決まるので、2つの方法を公平に比べられます。下のラボは、棒の列を並べかえながら比較の回数を数えてくれます。同じはじめの並びで2つの方法を試し、カウンターを見てみましょう。
ドラッグで回転、スクロールまたはピンチで拡大・縮小。
入力、出力、そしてその間の手順
アルゴリズムを書く前に、何が入って何が出てこなければならないかを正確に書き出しましょう。最大公約数なら、入力は2つの正の整数、出力は両方を割り切る整数1つで、それより大きな数では同じことができないものです。この説明から結果の確かめ方がわかり、手順のヒントになることもよくあります。エッジケースも見えてきます。一方の数が0だったら？（上のループはもう一方の数を返し、それが正しい答えです。）2つの数が等しかったら？コードを実行する前にエッジケースを考えておくと、多くのまちがいを防げます。
- 紀元前300年ごろ: ユークリッド『原論』第VII巻：最大公約数の求め方。
- 9世紀: バグダッドのフワーリズミーがインド数字について書く。ラテン語化した名前がアルゴリズムという言葉のもとになる。
- 1843: エイダ・ラブレスの注釈G：解析機関がベルヌーイ数を計算する手順。
- 1945: ジョン・フォン・ノイマンがマージソートを考案。
- 1959: トニー・ホーアがモスクワでクイックソートを考案（発表は1961年）。
| アルゴリズム | 入力を正しい出力に変える、有限個の正確な手順の並び |
| 入力 | アルゴリズムが出発点にするデータ |
| 出力 | アルゴリズムが出さなければならない結果 |
| 正しい | 許されるすべての入力に対して正しい出力を出す |
| 有限 | いくつかのステップの後に必ず止まる |
| 最大公約数 | 2つの数をどちらも割り切る最大の整数 |
| エッジケース | 0、空のリスト、等しい値など、ふつうでない入力 |
| ステップ数 | アルゴリズムが行う基本操作の回数 |
- ユークリッドの互除法を使うと、48と18の最大公約数はいくつですか？
- 1071と462に対して、ユークリッドの互除法では割り算が何回必要ですか？
- 次のうち、すべてのアルゴリズムが持たなければならない性質でないものはどれですか？
- 有限回のステップの後に止まる
- どの手順も正確である
- コンピューターを使う
- 許されるすべての入力に対して正しい出力を出す
- ユークリッドの互除法が必ず止まるのはなぜですか？
- 余りはいつも割る数より小さいので、小さくなって0になる
- 10回くり返すと止まる
- コンピューターがループを自動的に止める
- 数が大きくなって一致する
- アルゴリズムという言葉の由来になった名前は
- ユークリッド
- フワーリズミー
- エイダ・ラブレス
- アラン・チューリング
- 計算機科学者が秒数を計るのではなく、ステップを数えるのはなぜですか？
- 秒数は機械によって変わるが、ステップ数はアルゴリズムと入力だけで決まる
- 時計が正確でない
- ステップのほうがいつも速い
- 秒数はコードで測れない
- ある方法が、試した5つの例で正しい答えを出しました。この方法は正しいですか？
- はい、5つの例で証明できる
- そうとは限らない。許されるすべての入力で正しくなければならない
- 速い場合だけ正しい
- ループを使う場合だけ正しい
- このユニットのループでは、gcd(35, 0) は何を返しますか？
- エイダ・ラブレスが注釈Gを含む注釈を発表したのは何年ですか？
- 1801
- 1843
- 1945
- 1961
- ユークリッドの互除法の手順を正しい順に並べましょう。
- アルゴリズムとは、入力から正しい出力を出す、有限個の正確な手順の並びです。
- ユークリッドの互除法は、余りをくり返し求めて最大公約数を見つけます。
- 1つの問題に、ステップ数が大きく違う正しいアルゴリズムがいくつもあることがあります。
- 手順を書く前に、入力、出力、エッジケースを書き出しましょう。
- この言葉はフワーリズミーのラテン語の名前から来ています。
このコースの出典 (11)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
- lecture notes 1 Introduction, 3 Sorting, 9 Breadth-First Search, 10 Depth-First Search (ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes) and Fall 2011 lecture 13 BFS notes (ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011)
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (MIT Press)
- with the CLRS-based Khan Academy algorithms unit by Thomas Cormen and Devin Balkcom of Dartmouth (khanacademy.org/computing/computer-science/algorithms: binary search, selection sort analysis, merge sort, quicksort overview and analysis)
- MacTutor History of Mathematics, Al-Khwarizmi (mathshistory.st-andrews.ac.uk/Biographies/Al-Khwarizmi: word algorithm from the Latin title Algoritmi de numero Indorum)
- D. E. Joyce, Euclid's Elements Book VII Propositions 1 and 2 (mathcs.clarku.edu/~djoyce/elements/bookVII)
- Wolfram MathWorld, Merge Sort (mathworld.wolfram.com/MergeSort.html: proposed by John von Neumann in 1945, after Knuth 1998 p. 159)
- Stanford CS "Tony Hoare: Quicksort" (cs.stanford.edu/people/eroberts/courses/soco/projects/2008-09/tony-hoare/quicksort.html: devised while a student at Moscow State University for Russian-English machine translation with a tape dictionary, programmed in Algol 60 and published 1961; the year 1959 from the Wikipedia Quicksort article and its cited sources)
- Bodleian Libraries, Ada Lovelace (blogs.bodleian.ox.ac.uk/adalovelace: 1843 paper, Note G Bernoulli numbers)
- Fourmilab text of Menabrea's Sketch with Lovelace's notes (fourmilab.ch/babbage/sketch.html)
- Seven Bridges of Konigsberg (Euler 1736) and Tower of Hanoi (Edouard Lucas, 1883) checked against the Wikipedia articles and their cited sources.
確認日: 2026-10-17