単語記事: アルゴリズム

編集

もしかして? → アルゴリズムたいそう / アルゴリズムこうしん

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

概要

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

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

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

例1

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

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

  1. めるもの「1 + 2 + 3 + ... + 99 + 100」をもう一組用意する。
  2. 一つの順番を逆にして「100 + 99 + 98 + ... + 2 + 1」とし、「1 + 2 + 3 + ... + 99 + 100」と上下に並べる(下表)。
  3. 上下に並んだ数字を足すと常に1 + 100 = 2 + 99 = 3 + 98 = ... = 101になる。
  4. める値の2倍は上記101100個あるのだから(1+100)*100である。
  5. つまりめる値は、(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やらがやってきて、映画マーキュリー・ライジング」の登場人物のような運命が待っているのだろうか。とにかく世界が震撼するのは間違いない。

アルゴリズムの評価方法

上述のように、計算量が少ないアルゴリズムが優秀なアルゴリズムということになるが、それだけでは較しにくい。そこで、較の際には計算回数(手順)がアルゴリズムで取り扱う対の数の増加に合わせてどのような増え方をするかで評価を行う。

関連動画

関連記事


【スポンサーリンク】

携帯版URL:
http://dic.nicomoba.jp/k/a/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
ページ番号: 5259361 リビジョン番号: 2070320
読み:アルゴリズム
初版作成日: 14/08/14 22:48 ◆ 最終更新日: 14/08/15 09:11
編集内容についての説明/コメント: とりあえずここまで
記事編集 / 編集履歴を閲覧

アルゴリズムについて語るスレ


まだ掲示板に書き込みがありません… 以下のようなことを書き込んでもらえると嬉しいでーす!

  • 記事を編集した人の応援(応援されると喜びます)
  • 記事に追加して欲しい動画・商品・記述についての情報提供(具体的だと嬉しいです)
  • アルゴリズムについての雑談(ダラダラとゆるい感じで)

書き込みを行うには、niconicoのアカウントが必要です!


  JASRAC許諾番号: 9011622001Y31015