TOKUTEI: algorithm Katsudou Shushi

本特定領域研究の活動主旨

新しいパラダイムとしてのアルゴリズム工学：
計算困難問題への挑戦

領域代表者　茨木俊秀 (京都大学・情報学研究科・教授)

領域代表者からの申請総額　3億2800万円
研究期間　平成10年度〜平成12年度

問題解決のため、アルゴリズムの方法論と技術を体系化し、
新しいアルゴリズムの開発と適用領域の拡大を図る

本研究領域の背景：なぜアルゴリズム工学か

社会や産業の活動には、生産計画、希少資源の最適利用、環境汚染の最小化、通信回線網の有効利用など、重要で大規模な問題が数多く含まれている。計算理論は、これらの問題の多くに、多大な時間がかかる計算困難な部分があることを明らかにしてきた。しかし、工学的見地に立つと、問題の難易にかかわらず、ある時間制約の下で、できる限り大きな規模の問題を実用上許される精度で解くようなアルゴリズムに意義があり、そのための方法論が要求されている。ハードウエア技術とソフトウエア技術は、いうまでもなく情報化社会を支える車の両輪であるが、その中でも欧米に10年以上遅れていると言われるソフトウエア技術にとって、その基盤であるアルゴリズムを進展させることはとくに重要である。さらに、インターネットや並列計算機の普及、低軌道衛星群による通信など、アルゴリズムの観点からも新しい展開を必要とする状況がある。これらの変化の結果、分散アルゴリズム、動的アルゴリズム、確率アルゴリズム、近似アルゴリズムなど新しい概念が提唱され、研究が活発化している。

アルゴリズム工学の構築を目指して

アルゴリズムを巡る上記の状況に対処するため、本特定領域研究では、アルゴリズムの技術と方法論を体系化することによって、アルゴリズム工学という新しいパラダイムの創生と構築を目指す。具体的な研究項目には、離散最適化アルゴリズム、グラフアルゴリズム、幾何アルゴリズム、並列/分散アルゴリズム、の4つを設け、25名を研究代表者として研究を遂行する。さらに、16名からなる総括班は、強力なリーダシップによってこれを組織し、目的の達成を図る。

研究内容

「離散最適化アルゴリズム」では、ネットワークフロー、マトロイド、劣モジュラ、離散凸解析などの理論的研究をベースに、メタヒューリスティクスなどに基づく実用性の高いアルゴリズムの開発を行う。「グラフアルゴリズム」では、グラフ構造をもつ問題の中から、グラフの連結度、同型性、彩色など重要な問題の近似および厳密アルゴリズムについて研究する。「幾何アルゴリズム」では、2次元あるいは3次元の幾何学問題を、グラフィックス、画像処理、建築学、交通システムへの応用などを念頭に置きつつ研究し、実用的アルゴリズムを実現する。「並列/分散アルゴリズム」では、インターネットなど、通信技術の急速な発展に対応して新しいアルゴリズムの概念を探求するとともに、分散システムの高速化や暗号技術などへも貢献する。

活動主旨の詳細

本特定領域研究の活動に興味を持たれた方は、活動趣旨をより詳しくまとめた以下の資料をぜひとも御覧下さい。

活動趣旨をまとめたPSファイル

柳浦睦憲

<最終更新作成日時 1998年9月1日 >