アルゴリズムに関する研究の基本姿勢

　アルゴリズムは理論計算機科学の中でも最も基礎的でしかも重要な研究分野です．アルゴリズムの研究というと，高速化が主要なテーマのように思われがちですが，研究の醍醐味は別にあります．高速化というのは，他人が考案したアルゴリズムを改良することでしかありません．もっと大事なことは，まったくどのようにして解けばよいかが分からなかった問題に対して新たな解法，すなわちアルゴリズムを考案することです．このとき，幾つかの例題に対してうまく行くというだけでは不十分で，どんな入力に対しても必ず解が求まることを証明できなければなりません．また，実行時間と作業領域（メモリ量）の解析も重要です．アルゴリズムの解析は難しいことが多いのですが，ここをしっかりとしておかないとアルゴリズムに説得力がなくなります．
　アルゴリズムの解析では最悪の場合を考えることが多いのですが，これは決してアルゴリズム研究者に悲観論者が多いからではありません．最悪の場合の実行時間さえ解析できていれば，最大どれだけの時間だけ待てば計算が終わるか分かるからです．いつ終わるか分からずに待つのは辛いことです．本当は平均的な実行時間も求めたいのですが，これは数学的に難しいので，アルゴリズム研究者と言えども敬遠していることが多いようです．