イントロダクション: アルゴリズムとは何か
アルゴリズムの定義
広い意味でいえば、アルゴリズムは「問題解決のための手順」のことです。料理のレシピなどもアルゴリズムといえるでしょう。
狭い意味での、つまり数学やコンピュータサイエンスの分野におけるアルゴリズムとは、以下を満たす手順のことです。
- コンピュータなどの命令で実行できるほど具体的に定められている
- 有限回数で終わる(いつかは停止する)
つまり簡単にまとめてしまえば、これもやはり「問題を解決するために用いられる具体的な手順」のことといえます。
もう少し詳細に説明しましょう。
「具体的に定められる」というのはどういうことか
アルゴリズムは、計算やデータの処理などをどの様に行うのかを、不明瞭な点がないように定めます。
例えば、「 a に b を足すのを 10 回行う」というのもアルゴリズムです。 a と b というものが決まっていれば、足し算という決まった演算を特定の回数繰り返すので、不明確な部分がありません。
つまり、違うコンピュータや人間であっても、同じアルゴリズムに(間違うことなく)従えば同じ結果が得られるのです。（ランダム性を含むアルゴリズムはこの限りではないのですが、本質ではないので詳しい説明は省きます。）
もし、実行するたびに違う結果になってしまう場合は、アルゴリズムが正しく無いか、実行する側が間違えている可能性があります。
「有限回数」で終わるとは
有限回数で終わるというのも重要な条件です。「停止性」などと言われることもあります。
手順通りに実行していても、もし終わらなければ永遠に問題を解決することはできません。アルゴリズムはあくまで課題解決のための方法なので、問題を解くことができなければ意味がなくなってしまいます。
有限回で終わらないものといえば、無限ループなどがあります。プログラミングをしていると時々陥ってしまいますが、これは終了することがないのでアルゴリズムとは言えません。
アルゴリズムの具体例: 除算
もうすこし具体的に説明しましょう。アルゴリズムというのは、紀元前から存在しています。私達がよく知っているであろう除算、つまり割り算もその一つです(Division algorithm)
2つの自然数 \(n, d\) (ただし \(n \leq d\) ) を受け取って、商 \(q\) と余りを求めるというのは、以下の手順（アルゴリズム）で実行することができます。
- \(q\) を \(0\) として手順2へ
- \(n\) が \(d\) 以上なら手順３を実行し、違うなら終了する
- \(n\) から \(d\) を引いて、\(q\) を 1 増やし、手順2に戻る
最終的に残った \(q\) が商となり、\(n\) が余りとなります。
具体的な値を入れて確かめて見ましょう。(何事も具体化してみると状況が良く掴めるということはよくあります。)
今回は \(n=10\)、\(d=3\)、つまり \(10 \div 3\) をアルゴリズムにそって計算してみましょう。
① \(q\) を \(0\) として手順2へ
② \(n (=10)\) が \(3\) 以上なので手順３へ
③ \(n (=10)\) から \(3\) を引いて、\(q (=0)\) を1増やし、手順2に戻る
② \(n (=7)\) が \(3\) 以上なので手順３へ
③ \(n (=7)\) から \(3\) を引いて、\(q (=1)\) を1増やし、手順2に戻る
② \(n (=4)\) が \(3\) 以上なので手順３へ
③ \(n (=4)\) から \(3\) を引いて、\(q (=2)\) を1増やし、手順2に戻る
② \(n(=1)\) が \(3\) 以上ではないので終了
これで終了しました。ここでの商は \(q\) で \(3\)、余りは \(n\) で \(1\) になっています。これは今まで頭の中でやっていた「割り算」というものを、誤解のないほど具体的に行っており、有限回の手順で終了します。
実はアルゴリズムというのは、気がついていないだけでかなり身近なものなのです。