ブックタイトルGSIS_2019

概要

GSIS_2019

システム情報科学専攻Department of System Information Sciences24■研究キーワード■■KEYWORDS ■教 授准教授An example of 15-puzzle15 パズルの問題例Modeling the server supply-assignment problem for computer networksネットワーク上のサーバ割当問題のモデル化Algorithms now play a very important role for the reliability and efficiency in several social systems. Westudy and develop new algorithmic techniques from the viewpoint of theoretical computer science. Inparticular, we deal with several problems related to “graphs” and “combinatorial reconfiguration.”1. A graph consists of a set of vertices and a set of edges, each of which joins a pair of vertices. Graphscan be used to model many practical problems: For example, the server supply-assignment problemfor computer networks (see the left figure) and the scheduling problem can be formulated as thegraph flow and coloring problems, respectively.2. In combinatorial reconfiguration, we are asked to transform the current configuration into a desiredone by step-by-step operations. The 15-puzzle is one of such problems (see the right figure), andthere are many applications such as changing frequency assignments, monitoring systems, and soon.Students in our laboratory can select research topics according to their own interests. We studyalgorithms from the theoretical viewpoint, but we sometimes implement developed algorithms toevaluate them from the practical viewpoint.Developments and Applications of Algorithmsアルゴリズムは、今やあらゆるシステムに導入され、そのシステムの信頼性や高速性を握る重要な鍵となっている。本研究室では、理論計算機科学の観点から、新しいアルゴリズムの設計法や解析法を研究開発している。特に、「グラフ」を用いてモデル化される離散的な問題を解くアルゴリズムや、「組合せ遷移」と呼ばれる解と解の関係に着目した問題を解くアルゴリズムを扱っている。1. グラフとは、点の集合と２点を結ぶ辺の集合からなるものであり、数多くの実用的な問題がグラフを用いてモデル化される。例えば、ネットワーク上のサーバ割当問題はグラフのフロー問題として定式化でき（左図）、スケジューリング問題はグラフの彩色問題として定式化できる。2. 組合せ遷移とは、現在の状態から目標の状態に段階的に遷移可能か判定する問題であり、例として15 パズルが挙げられる（右図）。組合せ遷移は他にも、周波数割当や監視システムの変更など、様々な応用が知られている。本研究室に配属された学生は、それぞれの興味にあったテーマを選び、研究を進めている。研究は理論的なアルゴリズム開発がメインであるが、時にはプログラム実装による実験的評価も行っている。アルゴリズムの開発と応用Assoc. Prof.Takehiro Ito伊藤 健洋Prof.Xiao Zhou周　　暁Algorithm ／ Graph Theory ／ Combinatorial Reconfigurationアルゴリズム／グラフ理論／組合せ遷移http://www.ecei.tohoku.ac.jp/alg/Algorithm Theoryアルゴリズム論准教授（ 兼）Assoc. Prof.Akira Suzuki鈴 木 顕