基礎情報分野 離散アルゴリズム研究室

コンピュータやスマートフォンは便利ですよね。高速に、正確に、さまざまなことを計算してくれます。例えば「検索」や「乗り換え案内」も計算の結果です。では、このような計算はどのように行われているのでしょうか？効率よく計算する方法あるでしょうか？また、計算機はあらゆることを計算できるのでしょうか？私の研究室では、効率良い計算の方法について、理論的な側面から研究を行います。

図のようにSからGまでの道順の場合の数を求める問題を考えてみましょう。最短経路だけでしたらその公式は高校生で学びます。では、同じ道を通ってはいけないが遠回りを許した道順を数える問題はどうでしょう。実は公式は知られていません。ひとつずつ数えるとなると、組合せ爆発を起こし、答えを得るまでに天文学的な時間がかかります。しかし、例えばZDDと呼ばれる最先端の手法を利用すると驚くほど高速に数え上げてくれます。コンピュータは人間の能力では到底敵わない速度で計算してくれますが、上手に扱わないとその能力を十分に発揮できません。一方で、効率よく計算する方法が存在しないかもしれない問題もあります。例に挙げた遠回りを許した道順の数え上げもそのような問題だと考えられています。そういった問題が持つ難しさの本質も研究の対象になります。計算手順に関する理論的な成果は、実際のコンピュータで計算する際にも利用されています。本研究室では、コンピュータを効率よく利用するための理論的背景を学び、実際の問題を効率良く解く方法を見つけ出す直感を養います。