 |
 |
群馬大学
 |
群馬大学工学研究科 博士後期課程 電子情報工学専攻1年 岡下 綾 |
 |
当研究トップへ | |
| 1. | はじめに | |
| 2. | アルゴリズムとは何か？  |
|
| 3. | 難しい問題を解くためには | |
| 4. | 中野先生の研究について | |
| 5. | 中野先生について | |
| 6. | おわりに | |
 |
群馬大学工学部 情報工学科 中野 眞一 助教授 |
| ２．アルゴリズムとは何か？ アルゴリズムとはコンピュータで問題を解決するためのおおまかな手順です。何か物事を行うときの「やり方」と考えてもいいでしょう。よってアルゴリズムの研究とは、問題を解くためのより良い方法を考えようという作業であるといえます。 例えば、1から100までの数の和を求めたいとします。単純に、1＋2＋3＋…と足し算をしていくと100回の足し算を行わなければなりません。しかし、1＋100＝101，2＋99＝101，3＋98＝101…というふうに、左からi番目の数と右からi番目の数を足すと101になることに気がつけば、101が50個集まったものが解になることが分かるので、101×50=5050を計算すれば解が求まります。1から100までなら、なんとか単純に足し算をして解を求めることはできますが、1から100万までの数の和は？と問題の数が大きくなると、単純な方法では解を求めるのに膨大な時間がかかってしまいます。 もう一つの例として、300万円を年利4％で複利で25年間借りると、元利合計はいくらになるか？という問題を考えます。ちなみに、答えは7997509円です。今、二つのアルゴリズムを比較します。
アルゴリズム1では25回除算を行うのに対して、アルゴリズム２では7回の除算で済みます。借りる年数をnとすると、アルゴリズム1で実行する乗算の回数はちょうどnですが、アルゴリズム2では2log n程度となっています。これはどの程度の違いがあるのかを表1に示します。
コンピュータを使って問題を解くために、例えばCPUなどのハードウェアの性能を上げれば2倍や3倍ほどの速さを実現できるかもしれません。しかし、アルゴリズムを変えることによって、1000倍や10000倍もの劇的な速さで問題を解ける場合があります。データがn個の問題を解くのに2種類のアルゴリズムがあり、アルゴリズムAは2のn乗回の演算を用いて問題を解き、アルゴリズムBはnの5乗の1000倍回の演算を用いて問題を解くとします。もし、1秒に1回の演算をする計算機を使うと、問題を解くために必要な時間は表2のようになります。
表2からも分かるように、データの数が大きくなるような問題でアルゴリズムAを適用すると、計算が終了するまでの時間は天文学的な数字になってしまいます。ソフトウェアを作るときには、きちんとアルゴリズムを検討して、ソフトウェアの実行時間やデータの数はどの程度になるのかを見積もる作業はとても重要です。 アルゴリズムに関する知識がなくても、ソフトウェアを組むことはできますが、知らないと効率が悪いだけではなくバグのできやすいソフトウェアを作ってしまいます。例えるならば、建築学を知らなくても犬小屋くらいは作れますが、知らないと高層建築を作ることができないようなものです。アルゴリズムはソフトウェアを高速に実行するための技術なのです。 |
|||||||||||||||||||||||||||||||||||||||||||||||
