アルゴリズム論

システム情報科学専攻

アルゴリズム論 B04 Algorithm Theory

  • 周 暁 教授 (Prof. Xiao Zhou)
  • 伊藤 健洋 准教授 (Assoc. Prof. Takehiro Ito)
  • 鈴木 顕 助教 (Assis. Prof. Akira Suzuki)
研究キーワードアルゴリズム、回路計算量理論、グラフ理論

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

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

  1. グラフとは、点の集合と2点を結ぶ辺の集合からなるものであり、数多くの実用的な問題がグラフを用いてモデル化される。例えば、ある町の道路網をグラフでモデル化することによって、満足度の高いスクールバスの経路を求める問題を定式化できる(図1)。他にも、ネットワーク上のサーバ割当問題はグラフのフロー問題として定式化でき、スケジューリング問題はグラフの彩色問題として定式化できる。
  2. 組合せ遷移とは、現在の状態から目標の状態に段階的に遷移可能か判定する問題であり、例として15パズルが挙げられる(図2)。組合せ遷移は他にも、周波数割当や監視システムの変更など、様々な応用が知られている。

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