研究

研究内容

「超高速アルゴリズム技術と人工知能・知識処理への応用」 (湊)

アルゴリズムとは, 計算機のプログラムに書かれた計算手順・戦略のことです. 様々な計算を行うときに, アルゴリズムを工夫するだけで計算時間を何十倍, 何百倍も短縮できる場合があります. 多くのプログラムでは, 集合・論理・証明・グラフ・順列・組合せ・確率などの基本的な数学構造を扱いますが, これらを総称して「離散構造」と呼んでいます. 離散構造に関するアルゴリズム技術は応用範囲が広く, 波及効果が大きな重要な基盤技術となっています. 具体的にはハードウェア・ソフトウェアの設計, 大規模システム故障解析, 制約充足問題, データマイニングと知識発見, 機械学習と自動分類, バイオインフォマティクス, ウェブ情報解析など, 現代の情報化社会を支える様々な分野で必要とされている技術です.

当分野の湊が考案・命名した, ZDD (zero-suppressed binary decision diagram, ゼロサプレス型二分決定グラフ)と呼ばれるアルゴリズム技術は, 大規模な離散構造データを, 意味を変えずに小さく圧縮して索引化し, 高速に演算処理する技法として広く使われています. ZDDを用いた技法は, アルゴリズムのバイブルと呼ばれる世界的教科書「The Art of Computer Programming Vol. 4-1」(D. E. Knuth著)の中で, 日本人の研究成果として初めて, 独立項目として数十ページにわたって詳しく掲載され, 情報科学分野の研究者の注目を集めました.

ZDDに関する研究成果は, 日本科学未来館の展示「フカシギの数え方」 (2012年8月~2013年4月)でも取り上げられ, 組合せ爆発のすごさとアルゴリズム技術の重要性を, 青少年や一般市民に分かりやすく解説しています. その展示作品の1つとして湊が監修したアニメ動画は, YouTubeで180万ビューを超える大ヒットとなっています. 高校や大学の授業などで使われることも多く, 現在でも再生回数は増え続けています.

研究事例

  • 論理関数のBDD/ZDD表現による知識処理
  • 組合せ列挙・最適化に基づくデータマイニング
  • 様々な離散構造を扱う代数処理系の研究開発
  • 一票の格差が小さい選挙区割りの列挙・索引化
  • 災害時の避難所割り当て問題の列挙・索引化
  • 高速な確率推論を行うための圧縮データ構造
  • 組合せ列挙に基づく高精度な統計検定アルゴリズム
  • スマートグリッド電力網の最適組合せ構成計算

アルゴリズム計算の理論」 (ルガル・玉置・湊)

情報処理の基礎を支える理論 (数学), 特に, アルゴリズムの設計と解析, 計算複雑性理論および量子計算, の研究を行っています. 得られた成果は STOCFOCS (理論計算機科学分野ではNature, Science誌のような発表媒体), CCC (計算複雑性理論の頂上会議), SODA (離散アルゴリズムの頂上会議) を含む一流国際会議・雑誌に採択されています.

1. アルゴリズムの設計と解析
幅広い種類のアルゴリズムに取り組んでいます. 主要な興味の1つに代数的問題, 特に行列の乗法があります. 行列乗法は数学と計算機科学における最も基本的な処理の1つです. 過去5年間にいくつかの大きな進歩が起こり, 特に行列乗法に対するより高速なアルゴリズムが発見されています (20年以上最良であった行列乗法の初めての改良). 我々はこのような最近の発展に積極的な貢献をしています. 他の話題として, グラフ理論的な問題や分散計算における問題に対するアルゴリズム, ストリーミングアルゴリズム性質検査にも注目しています.

2. 計算複雑性理論
計算複雑性理論には2つの主要な目標, つまり, 計算問題を困難性 (解くために必要な資源量) に応じて分類すること, 及び, 計算模型の能力を解析すること, があります. 我々は多くの模型 (有限オートマトン, 非決定性Turing機械やさらに強力な計算模型など) や様々な資源 (時間複雑性, 領域複雑性, 通信複雑性など) に取り組んで来ました. 計算複雑性理論の分野は, 有名なP対NP問題のような手強い未解決問題で良く知られていますが, 適切な道具を用いて研究することで進展が見込まれる興味深い問題も多数存在します.

3. 量子計算
量子計算は量子力学の法則に基づく新しい計算パラダイムです. 量子計算の有名な成功例として, 完璧に安全な暗号系 (量子鍵配送) の開発, 及び, 素因数分解や他の数論的計算問題に対する, 現在最良のアルゴリズムより高速な量子アルゴリズムの設計があります. 我々の主な研究分野は, 量子アルゴリズム (量子計算機のためのアルゴリズムの研究) と量子計算複雑性理論 (量子計算機が伝統的な計算機より強力である理由の解明) です.


発表論文


学位論文


プロジェクト