アルゴリズム論

システム情報科学専攻

アルゴリズム論 B04 Algorithm Theory

周暁教授（Prof. Xiao Zhou）
鈴木顕准教授（Assoc. Prof. Akira Suzuki）
田村祐馬助教（Assis. Prof. Yuma Tamura）

研究キーワードアルゴリズム、グラフ理論、組合せ遷移

アルゴリズムの開発と応用

アルゴリズムは、今やあらゆるシステムに導入され、そのシステムの信頼性や高速性を握る重要な鍵となっている。本研究室では、理論計算機科学の観点から、新しいアルゴリズムの設計法や解析法を研究開発している。特に、「グラフ」を用いてモデル化される離散的な問題を解くアルゴリズムや、「組合せ遷移」と呼ばれる解と解の関係に着目した問題を解くアルゴリズムを扱っている。

1. グラフとは、点の集合と２点を結ぶ辺の集合からなるものであり、数多くの実用的な問題がグラフを用いてモデル化される。例えば、ネットワークをモデル化することによって、データの通信経路を求める問題を定式化できる（図1）。他にも、スケジューリング問題はグラフの彩色問題として定式化できる。

2. 組合せ遷移とは、現在の状態から目標の状態に段階的に遷移可能か判定する問題であり、例として15パズルが挙げられる（図2）。組合せ遷移は他にも、周波数割当や監視システムの変更など、様々な応用が知られている。

本研究室に配属された学生は、それぞれの興味にあったテーマを選び、研究を進めている。研究は理論的なアルゴリズム開発がメインであるが、時にはプログラム実装による実験的評価も行っている。

ネットワーク上のデータ通信
15パズルの問題例