単語記事: アルゴリズム

編集

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

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

概要

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

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

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

例1

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

1に2を足したら3、3に3を足して6、6に4を足して……と99回の足し算を手作業でがんばる人もいるかもしれない。実際、昔の人はそうやって足し算していた。しかし、この問題は、等差数列の和の公式を使えば(1+100)*100/2 = 5050と四則演算をたった3回するだけで答えが出る。

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

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

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

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

実用例1: 動画再生

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

実用例2: 暗号

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

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

アルゴリズムの評価方法

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

たとえば、上記例1においてnまでの総和をめるために、地に足し算する場合の足し算の回数はn-1で、和の公式を用いる方法なら四則演算の回数は常に3である。

別の例をとると、nチームで優勝者を決める場合、総当たり戦なら試合数はn(n-1)/2であり(優勝決定戦が必要になる可性を除く)、トーナメント戦であれば試合数はn-1(優勝者以外は必ず1敗するため)である。

このようにn, n2, n3,...など、計算や手順の実施回数が、対となるnのべき乗の和(多項式)で表せるものを、多項式時間で解けるアルゴリズムと表現し、多項式時間(より短い時間)で解けるアルゴリズムが存在する問題を、多項式時間で解ける問題と表現する。

それに対して、計算回数が2nなど、nが大きくなると多項式時間より大きくなる式(指数関数など)で表される場合は、多項式時間で解けないということになる。

逆(逆関数的)に計算回数がlog(n)に例するアルゴリズムは、かなり優秀なアルゴリズムであると言える。

条件により計算回数が一定しない場合は、計算回数の期待値や、最大値、最頻値のようなもので評価する場合もある。

関連動画

関連記事


【スポンサーリンク】

携帯版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 リビジョン番号: 2078566
読み:アルゴリズム
初版作成日: 14/08/14 22:48 ◆ 最終更新日: 14/08/30 23:19
編集内容についての説明/コメント: 関連項目
記事編集 / 編集履歴を閲覧

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

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

1 : ななしのよっしん :2014/11/22(土) 18:57:57 ID: LNHsjOd+K7
動画から飛んで来たけど勉強になった
この記事のこと、お姉さんに…教えてあげたい…
2 : ななしのよっしん :2014/11/27(木) 17:47:31 ID: oMRmNNQDmY
アルゴリズムの大切さを解く動画を見てて思うんだが、意味が不明瞭なカタカナを捨てて素直に解き方と呼べば、みんながアルゴリズムを考えるようになると思った。
グニャラくんの本が出ました!
  JASRAC許諾番号: 9011622001Y31015