アルゴリズムで斬る！ 数学vs.情報科学

小学校の算数では、やたらとアルゴリズムを習う。計算の仕方はアルゴリズムの一種だからだ。その後も、中学くらいまでは、アルゴリズムの比重が大きい。大学（数学科）に来ると、講義ではアルゴリズムらしいことをあまりやらなくなる（皆無ではないが）。

私が、自分の意識の中で数学とアルゴリズムの間にはっきりした線を引いたのは、不定方程式の解の存在証明だった。
今、a,bを整数のペアだとしよう。このとき、1次の不定方程式：



を満たす整数x,yが存在することを証明するにはどうすればよいか？　ここで、(a,b)は最大公約数で、情報系の人は、gcd(a,b)と書くことが多いようだ。具体的な解を求めるアルゴリズムは、拡張ユークリッド互除法と呼ばれるもので、計算機で求める場合には非常に効率的な方法だ。これは普通の発想で考えればわかる（高校生くらいのレベル？）。

群論的な証明の筋はまるで違う。

1) 巡回群の部分群は巡回群である。
2) は加法に関して巡回群になる。その部分群は、の形のものしかないことを示す。
3) がの部分群であることを示す。
4) 2), 3)から、となるmが存在する。
5) を示す。

この証明は、x, yを求める手順について直接的には何も語っていない。

こういう証明はいかにも数学的だと感ずる。

数学では、類似の”アルゴリズムの分からない存在証明”が頻出する。

ブラウアーの不動点定理なんかもそうだ。これは標準的には写像度（ホモトピー不変量）を使うが、ゴリゴリの解析的証明もできるような気がする（知らないが、考えればできそうな感じ）。いずれにしても、どうやって解を構成するかはわからない（不動点定理でも縮小写像の原理（バナッハの不動点定理）は構成的な証明で、雰囲気がだいぶ違うが）。

一方、情報科学では、存在は明らかだが「効率的な」アルゴリズムがわからない、というものが頻出する。例えば最短ベクトル探索問題は、有限集合の問題だから、最短ベクトルの存在は明らかだ。問題はアルゴリズムである。

別に何学でも面白ければそれでいいのだが、こういうことには「相性」があるような気がする。それが理解できるということと、面白いと思うかは別問題だからだ。数学好きの高校生は、流行りで情報系を選ぶかもしれないが、その理論に限っても相性がいいとは限らない。理解できてかつ面白いと思える学問を選んで欲しい、と切に願う。