ブログ

2024年4月号「研究室からこんにちは」(藤戸 敏弘)

研究室からこんにちは(短期大学)
皆さん、こんにちは。
4月に着任しました、藤戸敏弘と申します。元々関西エリアで生まれ育った私ですが、仕事の関係で1999年に名古屋へ移って以来25年間名古屋に住み着いております。一時民間企業に勤めたこともありますが、それ以外は大学教員を生業としており、本校が4校目(愛知県内で3校目)の勤め先となります。

大学教員をしているということで、何を専門にしているのかといいますと、アルゴリズムの研究をしております。アルゴリズムというバズワードも、今でこそメディアでもよく使われるようになり、ある程度市民権を得てきたよう思われますが、少し前までは「アルゴリズムって何?」、「アルゴリズム体操のこと?」というのが一般の反応だった気がします。アルゴリズム=計算手順、と説明されることが多いようで、それはその通りなのですが、実際には「計算」に限らず、何らかの目的を達成するための手順であればアルゴリズムと言え、例えば「チャーハンのレシピ」もチャーハンを作るためのアルゴリズムと言えます。
とはいえ、「アルゴリズムの研究」ではチャーハンの作り方なども研究しているわけではなく、殆どの場合、プログラムとしてコンピュータ上で走らせることができるアルゴリズムについて研究しています。つまり、どうやってコンピュータに処理させるか・動作させるか、について考えているのです。

では、「アルゴリズムについて何を研究しているのか」ということになりますが、「良い」アルゴリズムを考案(設計)し「良さ」を証明する(解析する)、もしくは、それができない(つまり、「良い」アルゴリズムは作れない)ことを証明する、というのが主な内容となります。何をもって良し悪しを言うのかというと、色々な基準が考えられるのですが、代表的なものがスピード(効率性)になります。では、アルゴリズムのスピードは、どのように測るのでしょうか?イメージしやすいのは、アルゴリズムをプログラムとして実際にコンピュータ上で走らせ、その実行にかかる時間を測るやり方です。ただ、この方法だと、使用するコンピュータによって測定される時間も違ってきますし、理論展開する上で普遍性に欠ける等の難点があります。そこでこの分野では、アルゴリズムを走らせたときに実行される「演算の回数」により、アルゴリズムの速度を考えます。ちょっと難しそうになってきたので、ガウス(高名なドイツの数学者)のよく知られた逸話で説明いたします。ガウスが7歳の時、算数の授業で教師が生徒たちに「1から100までの数字すべてを足す」という問題を出しました。これでしばらく休憩できるだろう、と教師は考えたのですが、ガウスはわずか数秒で「5050」という正解を導きだし教師を驚かせた、という逸話です。ガウスがどのような手を使ったかというと、最初と最後、2番目と最後から2番目、3番目と最後から3番目、というように、2つの数を足し合わせると、1+100=101、2+99=101、…、50+51=101というように、どれも同じ101となりますし、このように101となるペアは50個できるため、101×50=5050が答えだとガウスは見抜いたのでした。つまり、普通の小学生なら1+2=3、3+3=6、6+4=10、…、と計算して行く(これを「小学生アルゴリズム」と呼びましょう)ところ、ガウスは(1➕100)✖️(100➗2)と計算したのです。このように、同じ計算問題を解くにも、異なるやり方(アルゴリズム)が考えられるのですが、今の場合、小学生アルゴリズムとガウスのアルゴリズムのどちらが優れていると言えるでしょうか?何となくガウスの方が「賢い」やり方に思えますし、実際により素早く計算できるので、優れているように見えますよね?実はその通り、ガウスのアルゴリズムの方がより「良い」と言えます。なぜかというと、それぞれのアルゴリズムで実行される演算の回数(今の場合、四則演算の回数)を比べてみましょう。小学生アルゴリズムでは、99回の足し算(➕)を行って答えを出します。それに対しガウスのアルゴリズムでは、1回の足し算、1回の掛け算(✖️)、そして1回の割り算(➗)の計3回の演算だけで答えが得られます。だから、ガウスの方がより高速なアルゴリズムと言えるのです。この事は、より一般化した次の問題を考えると、より明確になります。いま、「1からnまでの数字すべてを足す」という問題を考えてみましょう(ここでnは任意の正整数を表します)。すると、小学生アルゴリズムではn-1回の演算(➕)を実行する必要がある(例えば、n=1億の場合、1億―1回)のに対し、ガウスの方ではどれだけnを大きくしても常に3回で済むのです。そのため、小学生アルゴリズムの速度はn-1、ガウス・アルゴリズムの速度は3ということになり、一部例外(nが4以下の場合)を除き、ガウス・アルゴリズムの方が速いと客観的・定量的に言えることになります。アルゴリズムの分野では、様々な計算問題に対し、ガウス・アルゴリズムの様な優れたアルゴリズムを考案することを主な研究活動にしています。

以上、拙い説明でしたが、「アルゴリズムの研究」についての紹介でした。