平成１０年１０月から２年半の計画で、特定領域研究(B)「新しい パラダイムとしてのアルゴリズム工学：計算困難問題への挑戦」 が始まることになりました。４つの研究班「離散最適化アルゴリズム」、 「グラフアルゴリズム」、「幾何アルゴリズム」、「並列/分散アル ゴリズム」に加え、それらを統括する「総括班」の下に、２５の研究 課題が進められます。

この研究テーマが採択されるにあたっては、文部省科学研究費の枠組みで、 我々にとってはちょうど適当な規模である特定領域研究(B)(ミニ重点とも 呼ばれる)という制度が始まったこと、その他いくつかのタイミングが うまく合ったことがあります。しかし、最大のポイントは「アルゴリズム 工学」の重要性が認識され、今これを開始しないと、とくに欧米に対して著しく 立ち遅れてしまうという主張が支持されたのだと信じています。 実際、特定領域研究の審査委員の先生方の間でも、この研究テーマに対する 評価はかなり高かったと漏れ聞いております。これまで、情報科学の 分野で、今回のような基礎的なテーマが選ばれたことはありませんでした。 これが刺激となって、アルゴリズムの基礎研究 に目が向けられることになれば大変幸いです。しかし、それだけに、我々の 側には、この大きな期待に答える責任があります。

一体「アルゴリズム工学」とは何か、またそれは新しいパラダイムとなり 得るのでしょうか。以前、皆様にお配りした申請書には、「アルゴリズム 工学」の一応の解釈と主張が書いてあります。1. 現実社会で解決を 迫られている問題は広範囲にわたり、しかも困難な問題が多いため、 これらの解決にはアルゴリズムの進歩が不可欠である、2. 応用を指向した実用的に 役立つアルゴリズムという観点に立てば、アルゴリズムの評価法が従来の 理論的評価法と異なり、その結果として新しいタイプのアルゴリズムが生みださ れる可能性がある、3. アルゴリズム研究の対象となる分野も情報化技術の進歩 によって拡大しており、それらの特定と定式化から始めて解決法を考えていく 必要がある、などが主なところです。要は、アルゴリズムにとって新しい状況が あり、それを新しい視点に立って眺めよう、ということになるかと思います。 しかし、このような「アルゴリズム工学」が果たして存在し得る のかどうか、さらにその具体的内容はどのようになるのか、これらの点 については、これから共に研究して行かなければなりません。

大事なことですが、特定領域研究は個々の独立した研究の単なる 集合ではなくて、テーマとして掲げられた目標に向かって全員が協力して 研究を進めることが要求されています。この研究では、「アルゴリズム工学」 が掲げるところでありますが、一つの具体的な成果として、開発された アルゴリズムを、データベースの形で取りまとめ、外部の人々にも使えるような 形で提供することを考えています。このデータベースの具体的な内容に付いても さらに検討して行きたいと存じます。

最後に、この特定領域研究の２年半の研究期間を通じて、皆様方の絶大なご協力を お願いいたしますと共に、この研究の成果が、新しい分野である「アルゴリズム 工学」の創設のきっかけとなって、次世代の研究へ継承していくことを念じ ています。

この度，特定領域研究（Ｂ）「新しいパラダイムとしてのアルゴリズム工学：計算困難問題への挑戦」が発足することになり誠に喜ばしく存じます．

本研究の申請書の中に，次のように述べられています．「ＮＰ−困難問題を含む、大規模で困難な最適化問題を現実的に解くための方法論は、その重要さが認識されるにしたがって、世界的に集中的な研究が始まり、急速に進歩している．これら工学的視点に立つアプローチには、近似アルゴリズム、確率的アルゴリズム、オンラインアルゴリズム、メタヒューリスティックス、進化的アルゴリズム、並列／分散アルゴリズムなど様々な提案があり、最適に十分近い解を短時間で求め得るという意味で、今まで解けなかったようなな大規模な計算困難問題を実用的に解き得ることが、数多くの研究成果によって確認されつつある．しかし、これらの新しい方法論はようやく検討段階に入ったばかりであって、それらを包括するような新しい工学体系の姿はまだ雲の彼方に隠されている．本特定領域研究の目的は、工学的技術としてのアルゴリズムという立場を重視し，今日の産業界が抱えている多様な大規模最適化問題を実用的な時間で現実的に解く具体的なアルゴリズムを生み出すととともに、そのための方法論を含めた新しいパラダイムであるアルゴリズム工学を建築することである．」と．!

　この趣旨にはまったく賛成で，雲の彼方に隠されている体系を明らかにして新しいアルゴリズム工学をこの特定領域研究の推進を通して構築されることを望みます． 　解決を待ち望まれている個別問題はたくさんあります．個々の問題を解くアルゴリズムの開発の重要性を否定するつもりはまったくありませんが，しかし、かといって少しずつ条件やパラメータを変えながらアルゴリズムの動物園を作ることも考えものです．アルゴリズム工学の確立に昇華してほしいと思います． 　アルゴリズム工学として何を想起したらよいでしょう．種々のレベルがあると思います．具体的な現実世界の諸問題，それらを抽象して論理的な形で定式化された問題，論理的なレベルで問題をデータ構造として表現し解法を明らかにする問題，さらに計算機，もちろん並列／分散／その他の新しい計算機構も含めて，の中でそれをどのように表現し，どのように計算をするかを明らかにすること、さらに得られた結果を現実の具体的な課題の解決に適用し現実の具体に戻ること，そうして，それぞれの問題を解決して行く方法論，アルゴリズム開発のプロセス，また，アルゴリズムの良さをどのように評価するか，そのパラメータとしてはどのよななものが考えられるか，計算速度，計算スペース，計算精度，近似の良さ，分かりやすさ，簡潔さ，透明性，さらには，アルゴリズムの応用における柔軟性などなど．そうしてそれらをトータルとして体系化すること． 　いろいろと言葉が浮かびますが，アルゴリズム工学とはどんなものであるかということは，何も一致した見解があるわけではないと思います．まさにこの研究プロジェクトから生まれて来るものと思います． 　真に新しいアルゴリズム工学の誕生を期待しています．

First of all, I would like to congratulate you all on your successful application for the new category of Monbusho Scientific Research Grant, which I am sure was very highly competitive. I cannot agree with you more regarding the necessity and urgency of the establishment in Japan of "Algorithm Engineering", which you so eloquently expound in Section 1 of your application.

I am personally involved in a few practical research projects, which require the development of new types of algorithms that must run orders of magnitude faster than is currently feasible. One of them concerns cell scheduling in ATM networks. At the OC3 speed (155Mbps), the next cell (53-byte packet) to depart on a particular output link of a switching node must be determined every 2.8 microseconds, and at the OC12 speed (622Mbps), the scheduler has only 0.7microseconds to do so. What's more, the link transmission speed is likely to increase to over 100Gbps in the not-so-distant future.

Another project of mine is Chinese character font generation. In a computerized font, each character is described mathematically by a set of splines. Since there are 23,000 Chinese characters in the Unicode standard, designing each character of a new font manually is too labor-intensive to be practical. One approach would be to first design basic strokes and then let an algorithm compose each character out of those basic strokes. This is easier said than done. The big challenge is to come up with a set of transformations to modify the basic strokes to suit the particular character, and also to compose them in an aesthetically pleasing layout.

I believe that the above are typical of many practical problems. In the first problem, the objective function is well-defined, but the best known algorithm takes too long, while in the second problem, even the objective function is rather fuzzy. Many of the research topics you propose are even more challenging than the above examples.

Getting funded is just the first step. It reflects the trust the granting agency has in your team, and their great expectations. The real work begins now! I believe that an important aspect of your joint effort is to work towards the common goal. In this vein, may I suggest that you, from time to time, reread Section 1 of your application, in order not to lose sight of the "big picture"? I wish you success.

アルゴリズム工学の研究が特定領域研究として取り上げられたことをお喜び申し上げます。この機会に日本におけるこの方面の研究がさらに大きく発展する事をお祈りいたします。２年半という期間は本当にあっという間に過ぎてしまいます（というのは、現在特定をやってすでに２年半たってしまったものの実感です）。理論家は自由人が多いので、まとめられるのは大変だと思いますが、精鋭ぞろいですので世界に誇れる結果が出ると信じております。アメリカに於ける理論研究のありかたに関する論争にみられるように、現在は理論に対する考え方が変わりつつある重要な時期だと考えております。

私の大学院生時代はソフトウェアをやっている人は論文も書けず博士号が取れないといわれた時代で、当然のことながらコンピュータサイエンス研究に占める理論の比重は非常に大きなものがありました。現在では、コンピュータ研究の領域が大きく広がり相対的に理論の比重は下がってはいますが、適切な理論は非常に重要であると考えられます。特に変化の激しい時代ですので、むしろ表面的な変化にとらわれない基礎が重要となっていると思います。

データベースの分野は、６０年代中ごろから実用システムができ、そこから生じた問題を解決するために理論の必要性が生じ、７０年代後半から８０年代前半は理論と実際がうまく連動した理想的な時期となりました。私もそのころデータベースに興味を持ったのですが、UllmanやAho、Ginsburgといった人達もデータベース理論に入り込んでいました。最近大学を退官したGinsburgはデータベースに専門を変えた理由を、「アルゴリズム理論では、最後に決着をつけた論文しかあとに残らない。多くの中間段階の論文は努力しても忘れられてしまうのでむなしい。」といっていたようです。応用分野は最初に概念を出せば評価されますし、アルゴリズムも究極のものでなくても実用性があれば評価されるといったことをいったのだと思います。その後、データベース分野も多様化したことと、理論が中心であった平行処理制御と演繹データベースの分野で多数の論文が出たにも係わらずあまり実用化できなかったことから、現在は理論への信頼性がすこし薄らいだ状況となっております。しかし、今後また理論的に解決するべきことが増えてくると信じております。

現在はネットワークの発展でコンピュータの応用分野が大きく広がり、それらから生じた問題を解決するためにも理論が必要となってきています。新しい情報通信革命に対応した研究課題は非常に多くあり、学生にもこういった分野は人気があります。しかし、応用研究分野では思いつきに終わってしまうような論文も多くあり、理論的思考による積み重ねは非常に重要と考えます。このアルゴリズム工学の特定領域研究で、是非ともコンピュータの新しい応用分野を対象とした理論を開拓していただければと思います。７０年代後半のデータベース理論のように基礎としての理論が応用の可能性を開いていったということが可能となればと願っております。また、この機会に次世代の研究者の養成にも力をそそいでいただけたらと思っております。

特定領域研究(B)「新しいパラダイムとしてのアルゴリズム工学：計算困難問題 への挑戦」が，研究代表者の茨木俊秀先生他，日本の錚々たるメンバーで開始さ れることになり，生み出されるであろう成果に胸をわくわくさせて期待しており ます．

従来のアルゴリズムの研究がややもすると理論に片寄り過ぎて，計算時間のオー ダをほんの少々改善するのに血眼になって，オーダはちょっと下がっても，オー ダの前の係数が膨大になってしまったり，実用的ではないが解き易い問題だけを 選んでアルゴリズムを与えたりしていた過去を反省し，真に「使える」アルゴリ ズムのための「工学」を打立てようとしているものと理解しております．

アルゴリズムは，まず“並の”プログラマーでインプレメントできないといけな い．次に“並の”ワークステーションのメモリーとスピードで対処できるもので ないと普通はいけない．また，“並の”大きさの問題に対して有効でないといけ ない．更に数値データを扱うものならば，“並の”数値誤差があっても“ころば ない”ものでなければならない．このような基準で考えれば，アルゴリズム工学 の枠組(パラダイム)は自ずと決まるのではないでしょうか．

日本には過去にもそうのような立場で研究されてきた研究者が少ないながらもい らっしゃいましたし，今回のメンバーにも入られているので，必ずや優れた成果 がでるものと期待してます．

ただ学問の常ですが，「実用的でない」と“現在”思われている問題がずっと将 来も実用的でないとは限らないことです．例を２つあげよう．20年前以上も前に 浅野孝夫先生等と一緒に4連結(極大)平面グラフのハミルトン閉路を求めるアル ゴリズムを研究していたときには，本人も含め誰も実用になるとは期待していな かったが，最近は幾何データの圧縮に利用されている．また15年位前に，グラフ を“きれいに”描画するアルゴリズムを国内の某学会論文誌に投稿したら，“応 用がない”という理由で見事に不採録になった．(これが今までにその論文誌に 投稿して不採録になった唯一の原稿です．尚Acta Informatica には採録になり ました．念のため．)しかし，いまやグラフ描画の分野は毎年ワークショップが 開催されるまで活発になっている．

別に上の２つの例がよい研究の模範例だと主張するつもりはありません．たまた まそうなっただけです．言いたいことは，現在応用があろうとなかろうと，いい ものはいいのです．こういうと，今回のメンバーのかなりの方々が「開き直られ て」しまうのが恐い．

ともかく２年半という研究期間は短いので，奮闘されることを期待します．