研究紹介 (斎藤研究室)
研究内容
本研究室では主に以下の３つの課題に注目し，研究を進めています．
- 省領域アルゴリズムの研究
- 列挙アルゴリズムの研究
- 実問題に対する計算複雑性やシステム開発
これらの研究を通じて，アルゴリズムの開発やその解析技術を学ぶだけでなく，どのように実問題を離散的な構造への定式化していくのか，またどのようにアルゴリズムを実装するのか，といった方法についても学んでいきます．
省領域アルゴリズムの研究
近年のデータの巨大化により，効率的にビッグデータを処理するアルゴリズムが求められています．しかし，ビッグデータはそのデータの巨大さゆえ，データのすべてを一度にメモリに載せることはできません．これまでのアルゴリズム理論において，多項式時間・多項式領域のアルゴリズムが効率的であるとされてきましたが，それらのアルゴリズムはビッグデータの前では実行することができません．そこで，入力のデータサイズよりも計算領域が小さい省領域アルゴリズムが求められています．
本テーマでは省領域計算モデル上で動作する効率的な省領域アルゴリズムを開発し，そのアルゴリズムに対する理論的な解析を与えています．また，それらのアルゴリズムを実装し，ビッグデータに対してアルゴリズムが耐性を持つかを検証を行います．
列挙アルゴリズムの研究
列挙問題とは，入力データの中からある特徴をオブジェクトをすべて抽出する問題です．例えば，クリーク列挙であれば，グラフからクリークをすべて抽出する問題で，ネットワーク中からコミュニティをすべて発見する，という問題を意味します．こうした列挙アルゴリズムを適用することで，データから偏りのなくある特徴を満たすデータを抽出できたり，データ全体の傾向や特徴を求めることができます．列挙アルゴリズムにおける手法として，逆探索法やZDDと呼ばれるデータ構造を用いた手法が知られています．特に，データ構造 ZDD は列挙自体を効率的に行えるというだけでなく，列挙されたオブジェクトから最適なものを抽出したり，ランダム生成を行うことができるなど，近年，非常に注目を集めています．
本研究では，これらの手法を用いた効率的な列挙アルゴリズムの開発するとともに，列挙アルゴリズムを実装し，アルゴリズムの効率性を実験的に評価します．
実問題に対するアルゴリズムと計算複雑性
組合せゲーム・パズルに関する研究
本研究では，組合せ的なゲームやパズルに対する計算複雑性を証明したり，パズルを解く高速なアルゴリズムの開発を行っています．また，列挙アルゴリズムの研究で得られた手法を応用し，パズルの解の列挙や例題生成アルゴリズムを行い，パズル作成システムの開発を目指しています．
たんぱく質の機能解明に関する研究
たんぱく質の立体構造は X線結晶解析や NMR によって実験的に得られます．しかし，NMR から得られる立体構造は現時点ではあまり信頼されておらず，実際の応用ではあまり使われていません．一方で，近年，組合せ剛性理論を用いたアルゴリズムにより，立体構造の剛性を組合せ的に判定することができるようになりました．本研究では，組合せ剛性理論を用いた剛性判定アルゴリズムを用いて，NMR によって生成されたモデルを検証システムの開発を行っています．