研究室公開
OPEN LABORATORY
先進マルチメディア情報知能システム
情報工学コース
05
アルゴリズムの知られざるチカラ
君は最強のアルゴリズムに勝てるか！？
|
周・鈴木研究室 |
EXHIBIT
オープンキャンパスでの展示
アルゴリズムのすごさを体感しよう
数学の問題の答えは１つですが，解く方法は１つとは限りません．問題の解き方によって，簡単に解けたり，すごく時間がかかったりします．コンピュータが問題を解く方法を決めるのが「アルゴリズム」です．なので，アルゴリズムが変われば問題を解決する時間が変わります．パソコンやスマホがサクサク動くかどうかもアルゴリズム次第．アルゴリズムは，今やあらゆるシステムに導入され，システムの信頼性や高速性を握る重要な鍵となっています．
アルゴリズムに挑戦！！
最近「人間vsコンピュータ」という話題を良く見るようになりました．将棋や囲碁で，コンピュータがプロに勝利してニュースにもなりました．何億何兆という候補の中から，より良い答えを見つけるのもアルゴリズムの仕事．今回の展示では「陣取りパズル」で様々なアルゴリズムと対戦できます．陣取りパズルは単なるパズルゲームではなく，伝染病等の拡がりを予測するシミュレーション等にも応用できます．アルゴリズムの世界で盛んに研究されている陣取りパズル．皆さんも，なるべく多くの陣地を奪えるよう挑戦してみてください．
私たちの研究
LABORATORY
より良いアルゴリズムの開発を
15人全員に，電話を使って，情報を伝えたいとしましょう．図に示すように電話連絡の仕方は様々で，それらは情報伝達のアルゴリズムとみなせます．どちらのアルゴリズムも，全員に情報が伝わるという点で正しいアルゴリズムですが，情報伝達にかかる時間には大きな差があります．同じことをやってくれるのならば，もちろん速い方がいいですよね．
私たちの研究室では，正確さを保証しつつも，いかにアルゴリズムを高速化できるか，その限界を研究しています．
身近にあるアルゴリズム
皆さんが使っているインターネットの世界にも，アルゴリズムがたくさん隠れています．例えばデータ通信するときに，みんなが一斉に同じ回線を使おうとしたら，その回線はパンクしてしまいます．そのようなことが起こらないように，うまく通信経路を分散させられるかどうかは，アルゴリズム次第．
こんな風に，皆さんに直接は見えないところで働いているアルゴリズムは，社会基盤を支える縁の下の力持ちなのです．
恋愛にもアルゴリズム！？
L.S. Shapleyは，1962年にD. Galeと一緒に「安定結婚問題」を解くアルゴリズムを考案し，2012年にノーベル経済学賞を受賞しました．安定結婚とは，結婚した後でお互いに「本当はあなたの方が良かった」というペアが生じないカップリングのことです．（もしそんなペアがいたら，駆け落ちの危険がありますね．）
実はこのアルゴリズム，結婚相手を見つけるだけでなく，研修医の配属先病院を決めるプログラムにも使われています．他にも，大学の研究室配属など，様々なマッチングに応用できる，正にノーベル賞級にすごいアルゴリズムなのです．
