[ Japanese / English ]

プロジェクト概要

 計算機が誕生して半世紀以上が経ちました. 従来計算機では「正確な計算」が出来るのは当たり前, 問題はそれをいかに速く実現するかでした. この面でアルゴリズムの貢献は非常に大きなものがありました. 例えば米国ライス大学の Bixby 教授によれば, 計算機の代表的応用例である線形計画法が初めて計算機上で実行されたときに比べて, 現在では実に 1,900,000 倍ものスピードアップが達成されています. 重要なことは,この間にアルゴリズムの改良によって 2,400 倍弱の高速化が達成され, これは同じ期間におけるハードウェアの高速化の 800 倍を凌駕しているのです.

 しかし, 前世紀の終わり頃から革命とも言っても良いくらいの大きな変化が現れて来ました. 従来の金科玉条であった「正確な計算」の実行を, 場合によっては放棄しようという動きが出て来たのです.最大の理由は 従来「計算機には向かない(計算困難)」と言われていた分野に 計算機が堂々と進出して来たことです. 例えば列車ダイヤの線引きとかコンビニの配送計画等, 従来いわゆる職人芸の世界でしたが, 最近では質の良い近似解を計算機が瞬時に出してくれます. また為替取引やオークションと言った経済活動では, 将来の入力変動や他人の行動が分かりませんから 正確な計算はそもそも不可能なのですが, それでも与えられた条件下で出来るだけ良いアルゴリズムを設計することが 出来るようになってきました.こうした応用において最も重要なのは 計算機が出してくる解答がいかに我々の要望にかなっているかです. つまり,アルゴリズムの目指すものが, 速度から解の品質に大きく変化して来たのです.

 我々は,この重要な変化の時期にあって, こうした広い意味での計算困難問題に対して, 実用性の高いアルゴリズムの品質・性能保証がいかにあるべきかを議論します. 具体的技術と方法論を含めた, 新時代における「アルゴリズムの設計と解析」の体系を 作り上げることが出来れば良いと考えています. 特に重視したいのが「社会的評価基準」です. 数学的に興味深いだけで終わらず, 分かりやすさと実用性も備えた成果を出すことが,我々の目標です.

概略図

領域代表者

評価委員