アルゴリズムとは (アルゴリズムとは) [単語記事]

アルゴリズムとは、「問題を解くための手順」である。

概要

アルゴリズムとは、「問題を解く手順(解き方)」のことである。

現代ではもっぱら「コンピューターの計算手順の最適化」を指すが、たとえば「ニコニコ大百科の読者が、一覧の一覧の編集履歴から、元素の一覧が追加された日を調べる手順」のように、コンピューター以外のものが処理できる手順についてもアルゴリズムと呼ぶことができる。

「いかに問題の解き方を工夫するか」というのが、アルゴリズムの研究と言ってほぼ間違いない。

例1

たとえば、1から100まで足し算することを考えてみよう。

1に2を足したら3、3に3を足して6、6に4を足して……と手作業でがんばる人もいるかもしれない。実際、昔の人はそうやって足し算していた。しかし、この問題は、以下の手順で簡単に解くことができる。

求めるもの「1 + 2 + 3 + ... + 99 + 100」をもう一組用意する。
一つの順番を逆にして「100 + 99 + 98 + ... + 2 + 1」とし、「1 + 2 + 3 + ... + 99 + 100」と上下に並べる(下表)。
上下に並んだ数字を足すと常に1 + 100 = 2 + 99 = 3 + 98 = ... = 101になる。
求める値の2倍は上記101が100個あるのだから(1+100)*100である。
つまり求める値は、(1+100)*100/2 = 5050である。

1	+	2	+	3	+	...	+	99	+	100
100	+	99	+	98	+	...	+	2	+	1

このように、1から100まで足しあわせるのにも、愚直にがんばるという方式と、反転させてくっつけて2で割るという方法で少なくとも二通りがあることがわかる。後者の方が計算量が少ないのは明らかだろう。

で、結局アルゴリズムって何の役に立つの？

つまり、アルゴリズムが優秀であれば、計算量を減らすことができるのだ。

ただし、手順が異なるだけであり、同じ問題を解決するのであるから、アルゴリズムの優劣によらず答えは一致している必要がある。

答えが同じなのに計算量を減らすのが何の役に立つって？と思われるかもしれないが、これは非常に重要な問題で、第二次大戦以前からずーーーーっと脈々と研究が続けられてきた。なぜなら、計算する量が少なければ少ないほど、コンピュータが短い時間で答えを出せるからだ。

実用例1: 動画再生

たとえば、古いパソコンでニコニコを見ているとき、動画がカクカクしてイラッとしたことはないだろうか？これも、コンピュータの処理能力が、計算量より低かったから生じる問題だ。つまり、ニコニコ動画が使っている「アルゴリズム」がさらにパワーアップすれば、古いパソコンでもヌルヌル字幕を動かせたりすることができるのだ。

実用例2: 暗号

それだけではない。たとえば現在広く使われているRSA暗号は、「コンピュータに解読させようとすると、あまりに時間がかかりすぎる」という理由で安全性が保たれている。 → P≠NP予想

つまり、「どんなRSA暗号でも速く解読するアルゴリズムを手に入れたぜ！」と宣言し、しかもそれが正しいと認められたなら、莫大な富と尊敬を得られる……かもしれない。いやむしろ、真っ先にFBIやらインターポールやらペンタゴンやらMI6やらがやってきて、映画「マーキュリー・ライジング」の登場人物のような運命が待っているのだろうか。とにかく全世界が震撼するのは間違いない。