斎藤 寿樹准教授

准教授

斎藤 寿樹

研究紹介一覧に戻る研究室ホームページ

研究概要

本研究室では主に以下の3つの課題に注目し,研究を進めています.

1.省領域アルゴリズムの研究

2.列挙アルゴリズムの研究

3.実問題に対する計算複雑性やシステム開発

これらの研究を通じて,アルゴリズムの開発やその解析技術を学ぶだけでなく,どのように実問題を離散的な構造への定式化していくのか,またどのようにアルゴリズムを実装するのか,といった方法についても学んでいきます.

省領域アルゴリズムの研究

近年のデータの巨大化により,効率的にビッグデータを処理するアルゴリズムが求められています.しかし,ビッグデータはそのデータの巨大さゆえ,データのすべてを一度にメモリに載せることはできません.これまでのアルゴリズム理論において,多項式時間・多項式領域のアルゴリズムが効率的であるとされてきましたが,それらのアルゴリズムはビッグデータの前では実行することができません.そこで,入力のデータサイズよりも計算領域が小さい省領域アルゴリズムが求められています.

本テーマでは省領域計算モデル上で動作する効率的な省領域アルゴリズムを開発し,そのアルゴリズムに対する理論的な解析を与えています.また,それらのアルゴリズムを実装し,ビッグデータに対してアルゴリズムが耐性を持つかを検証を行います.

sublinear_space.png

列挙アルゴリズムの研究
列挙問題とは,入力データの中からある特徴をオブジェクトをすべて抽出する問題です.例えば,クリーク列挙であれば,グラフからクリークをすべて抽出する問題で,ネットワーク中からコミュニティをすべて発見する,という問題を意味します.こうした列挙アルゴリズムを適用することで,データから偏りのなくある特徴を満たすデータを抽出できたり,データ全体の傾向や特徴を求めることができます.列挙アルゴリズムにおける手法として,逆探索法やZDDと呼ばれるデータ構造を用いた手法が知られています.特に,データ構造 ZDD は列挙自体を効率的に行えるというだけでなく,列挙されたオブジェクトから最適なものを抽出したり,ランダム生成を行うことができるなど,近年,非常に注目を集めています.
本研究では,これらの手法を用いた効率的な列挙アルゴリズムの開発するとともに,列挙アルゴリズムを実装し,アルゴリズムの効率性を実験的に評価します.

zdd_path.png

実問題に対するアルゴリズムと計算複雑性

組合せゲーム・パズルに関する研究

本研究では,組合せ的なゲームやパズルに対する計算複雑性を証明したり,パズルを解く高速なアルゴリズムの開発を行っています.また,列挙アルゴリズムの研究で得られた手法を応用し,パズルの解の列挙や例題生成アルゴリズムを行い,パズル作成システムの開発を目指しています.

slither_link.png

たんぱく質の機能解明に関する研究
たんぱく質の立体構造は X線結晶解析や NMR によって実験的に得られます.しかし,NMR から得られる立体構造は現時点ではあまり信頼されておらず,実際の応用ではあまり使われていません.一方で,近年,組合せ剛性理論を用いたアルゴリズムにより,立体構造の剛性を組合せ的に判定することができるようになりました.本研究では,組合せ剛性理論を用いた剛性判定アルゴリズムを用いて,NMR によって生成されたモデルを検証システムの開発を行っています.

斎藤寿樹研究室

斎藤研究室
本研究室では,効率的なアルゴリズムを開発および解析をするとともに,そのアルゴリズムを実装して現実的に効率的かどうかを確かめることで,アルゴリズムの理論と実践の両方を学んでいきます.研究室の活動としては,アルゴリズムグループでセミナーを行っていたり,週一回お茶会を開催しています.128GB のメモリを搭載した計算サーバーでガシガシと計算するだけでなく,コーヒーサーバーでリラックスしながら,楽しく研究を進めていきます.

 

前ページに戻る