next up previous
: I. 研究業績 : cv0210a : 略歴

研究業績概要

今井博士は,コンピュータ科学における効率的アルゴリズムの新パラダイムに よる設計(特に計算幾何・最適化)と,計算の観点から対象問題の構造を解析す る代数的・幾何的理論に関するものを軸に,新たなコンピューティングパラダ イム(量子計算等)の展開を推進して,コンピュータ科学において新展開をもた らす研究を行ってきた.以下では,多岐に渡る研究を(1) 計算幾何, (2) 最適化・ 離散システム論, (3) 量子計算等の新開拓分野, の3つについて概要を記述す.


1 計算幾何

計算幾何は,幾何構造を有する問題を計算機で処理するアルゴリズムの設計と 解析を計算量の立場から統一的に行なう分野で,2,3次元の図形処理の問題か ら,一般次元の普遍的幾何モデルまで対象にしている.研究初期では幾何の 接続関係に関する問題を,グラフアルゴリズムを援用しながら,グラフを明 示的に構成することなく幾何構造上で効率よく計算する方法論を開発した [1,4,7,11,12,15,17]. 動的な点に対するVoronoi図などパラメトリック問題を解決 する一連の研究 [21,22,23,28,29,33,49,83,85,94],低 次元線形計画関連の点集合直線近似など最適化アルゴリズムの研究 [16,24,25,26,34,44,45] がある.これらの成果に対して日本IBM科学賞が授与されている.

近年の幾何クラスタリングに関する研究では,幾何構造を活用して 計算量を格段と下げるとともに,幾何表現モデルを情報幾何空間に拡張して 特徴空間でのクラスタリングを高次幾何アルゴリズムの観点から統一的に 扱う理論を展開している [38,47,54,64,69,74,76,86,87,88,106,110,112]. 3角形分割の研究 [63,65,70,77,89,101]を通した計算幾何 の計算代数・計算位相との橋渡しの研究を追求している. このように,計算幾何の研究では,普遍モデルとしての幾何構造の種々 の有用な側面をアルゴリズム設計・問題解決への適用する研究方法を確立した.


2 最適化・離散システム論

最適化研究の初期では,最大流・最短路問題といったネットワー ク基本問題のアルゴリズムの実際的効率の実験的検証を行なった [2,5].これは 90年代後半に展開されるアルゴリズム工学的立場の先駆的な研究である. 理論研究では,ネットワーク技法 でマトロイド解析を実現する独自の方法の開発[3,6]と,線形 計画法における内点法について乗法的罰金関数法 を一連の研究[14,18,20,40]で 設計・解析し,内点法研究初期に収束性な ど多大な貢献をした.また,幾何的構造も用いて,広く 線形計画パラダイムの強力さを示した [30,48,8,10,11,13].

2分決定グラフ(BDD)という論理関数表現データ構造で, VLSI CAD, AIにおいて注目されているものについて,新理論的解析技 法を与え,離散システムを対象問題としたときのアルゴリズム面からのブレー クスルーをもたらした [55,59,62,66,67,73,78,81,82,95,18,21]. この研究は,ネットワーク信頼度や結び目のJones多項式の実用的計算に発展 し,計算位相幾何学の確立に貢献した.


3 量子計算等の新開拓分野

コンピュータ科学における新分野開拓においても,量子計算などで先導的 役目を果たしてきた. 計算生物学においては,アルゴリズムと計算の複雑さの理論を背景に, 複数アラインメント問題での従来スケールを完全に凌駕する厳密 および近似解法の開発 [43,51,52,60,68,72,79,84,90,92], さらに生物ゲノム実験におけるコンピュータ科学のCADに関する研究を行った [80,102,103,111,114,115].

近年,量子力学原理を計算に導入した量子計算の分野において,従来から 計算幾何学で展開してきた確率化アルゴリズムでの成果と,情報幾何からの情 報理論的アプローチを融合した量子計算機構・量子セキュリティの研究を ERATOプロジェクトで提唱している.計算量の観点から古典確率と量子確率が どのような計算能力差をもたらすかについて,量子オートマトンなどを軸に研 究を進めている[136,113].量子計算が素因数分解の多項 式解法をもたらすことによる現在の暗号系へのインパクトを現在の技術で評価 し,また確率的側面のシミュレーションを目的に,量子計算シミュレーション システムの開発を進め,次世代の量子アルゴリズム設計の研究を推進している [120,23,25,26,27].



IMAI Hiroshi 平成14年10月17日