陳　致中

陳　致中 (Zhi-Zhong Chen)

Date of birth: (秘密)

1：経歴

専門分野

アルゴリズムと計算量の理論（Theory of Algorithms and Complexity）

学歴

工学学士：西北電訊工程学院（現西安電子科技大学）(1985年)

工学修士：電気通信大学（1989年）

博士（工学）：電気通信大学（1992年）

職歴

1992年 4月	-	1994年 3月	三重大学工学部情報工学科	助手
1994年 4月	-	1997年 9月	東京電機大学理工学部数理学科	専任講師
1997年 10月	-	2006年3月	東京電機大学理工学部数理科学科	助教授
2006年 4月	-	2008年３月	東京電機大学理工学部数理科学科	教授
2008年 4月	-	現在	東京電機大学理工学部情報システムデザイン学系	教授

2：海外研究歴

1996年9月	～	1997年8月	University of California at Berkeley客員研究員（C. H. Papadimitriouと共同研究）
2000年7月	～	2000年9月	University of California at Riverside客員研究員（T. Jiangと共同研究）

3：褒賞

平成10年度山下記念研究賞（情報処理学会）
第2回LA/EATCS-Japan発表論文賞（2003年）

4：所属学会

Journal of Applied Mathematics: Editor
LAシンポジウム会員

5：代表的な論文

Reducing Randomness via Irrational Numbers,
SIAM Journal on Computing, Vol. 29, No. 4, pp. 1247-1256, 2000.
この論文で多項式等価性判定問題（2つの多変数多項式P(x,y,...,z)と Q(x,y,...,z)が与えられて，PとQの値が変数x,y,...,zの値に依存せずいつも同じか否かを判定する問題）を考える．この問題で，PとQは必ずしも展開形で与えられなく，むしろ変数行列の行列式などの形で与えられる．この問題は他の問題に応用が多いが，効率的な解法がまだ知られていない．一方，この問題を解く効率的な確率アルゴリズムが古くから知られてきた．本論文で，多項式等価性判定問題を解く新しい確率アルゴリズムを提案し，それの使う乱数の桁数が従来のより遥かに小さいことを示す．この論文の斬新なアイディアは無理数の近似をうまく使い，無理数の近似をよくすればするほど正しい判定を下す確率を上げることができるところにある．
［補足：本論文の発表後，他の研究者はこの論文の成果に刺激されて，素数判定問題を解く多項式時間アルゴリズムの設計に成功してビッグニュースになった.］

Map Graphs, Journal of the ACM, Vol. 49, No. 2, pp. 127-138, 2002.
地理情報システムの理論研究でトポロジカル推論問題が研究されてきた．この問題において，2次元図形間のトポロジカル関係（たとえば，「包含関係」とか「隣接関係」）が与えられて，これらの図形とその間の関係を実現する地図を作成できるか否かを決定しなければならない．この問題を解くアルゴリズムが存在するか否かですら分かっていなかった．本論文で，普通の地図で一番よく見られる「隣接関係」と「非隣接関係」に着目し，この2つの関係しか許さない場合を考え，この特別な場合を解くアルゴリズムが存在することを示す．
［補足：本論文の発表後，他の研究者はこの論文の成果に刺激されて，トポロジカル推論問題を解くアルゴリズムが存在することを示した．］

Finding Double Euler Tours of Planar Graphs in Linear Time,
SIAM Journal on Computing, Vol. 31, No. 4, pp. 1255-1285, 2002.
本論文で，CMOS（相補型金属酸化物半導体）VLSI回路の設計に関連した基本的な問題である平面グラフの二重双対オイラー路問題を考える．この問題において，平面グラフGが与えられて，いかにしてGを平面に埋め込み，埋め込んだあとのGとその双対グラフG'にそれぞれオイラー路 PとP'が存在してPとP'が互いに双対であるようにするかを決定しなければならない．この問題を解く多項式時間アルゴリズムが存在するか否かは未解決であった．本論文で，平面グラフ上で定義された2つの演算の深い代数的性質を解明して更にそれを活用することによって，この問題を解く最適なアルゴリズムを提案する．

6：現在の研究テーマ

バイオインフォマティクス（Bioinformatics):
生物学における計算困難な問題を，数学とコンピュータの知識を使って解こうとする．具体的に現在は，生物系統樹の構築およびDNAとタンパク質の解析で現れる計算困難な問題の効率的なアルゴリズムの開発に興味を持っている．設計したアルゴリズムを数学的に解析してその良さを理論的に評価するだけではなく，実際にプログラミング言語でプログラムに実装してから実際のデータを与えてその性能を計測して評価する．

離散アルゴリズム（Discrete Algorithms):
離散的な構造を持つ問題（たとえば，グラフや文字列などの上で定義された問題）を解くためのアルゴリズムのこと．その設計で，対象となる問題の深い構造を見出したり，最適なデータ構造を使ったりするのがポイント．

近似アルゴリズム（Approximation Algorithms):
世の中に役立つ問題の多くは最適化問題（optimization problems)．最適化問題において，多数の可能な解（feasible solutions）の中から最適な解（optimal solutions）を1つ求める必要がある．しかし残念ながら，ほとんどの最適化問題において，最適解を求める効率的な方法が存在しそうにない（理論的な根拠がある)．近似アルゴリズムは，（必ずしも最適ではないが）最適に近い解（近似解という）を効率よく求めるアルゴリズムのこと．速く解けることが分かっている問題をうまく利用して，速く解けそうにない問題の近似解を速く計算することが近似アルゴリズムの設計のポイント．

確率アルゴリズム（Randomized Algorithms):
その実行中で乱数（random numbers）を生成できてかつ乱数の出方に依存して異なる計算を進められるアルゴリズムのこと．確率アルゴリズムが実行毎に違う解を出したり，正しくない解を出したりする可能性がある．しかし，よい確率アルゴリズムは1に近い確率で正しい解を出す．従来のアルゴリズムで速く解けるか否かまだ分かっていない問題で，確率アルゴリズムで素早く解けてしまう問題がたくさん知られている．これらの確率アルゴリズムは大抵シンプルでコーディングしやすい．一方，確率アルゴリズムの解析には高度な数学の知識が必要．

並列アルゴリズム（Parallel Algorithms):
複数個のプロセッサを持つ計算機（いわゆる並列計算機）上で実行されるアルゴリズムのこと．1個のプロセッサを持つ計算機上で t時間かかる問題を，並列計算機上で遥かにより速く（たとえば， log t 時間で）解きたいのが目的．解きたい問題をいかにしていくつかの互いに独立したほぼ同じサイズの部分問題に分割するかは並列アルゴリズムの設計のポイント．

構造的計算量（Structural Complexity):
計算問題をその計算量に基づいていくつかのクラスに分類して，クラス間の関係や各クラスの性質と構造などについて研究する．解きやすい問題はなぜ解きやすいのか，解きにくい問題はなぜ解きにくいのか，．．．などの理論的根拠を与えるのが目的．