アルゴリズムとプログラム

アルゴリズムを語る上で，次は重要だと思ってます．

• アルゴリズムは数学的な抽象概念で，それをコンピュータ上に実現したものがプログラムである．抽象的なアルゴリズムと具体的なプログラムは分離されなくてはならない．さらに，プログラムはそれが採用するプログラミング言語に大きく依存する．
• アルゴリズムについて数学的に証明すべきことは「正当性」と「計算量」であり，それらは分離されなくてはならない．さらに，それらはアルゴリズムや問題が採用する計算モデルと計算量評価モデルに大きく依存する．

思考を明確にするためには，分離できるところをとことん分離していく立場を取ることが重要だと思います (いわゆる「分析」)．

ということを前提として，「私ごときがアルゴリズム本を書くことにした訳」にdankogaiさんからコメントをいただいたので，私見を述べます．

「裸のアルゴリズム」が正しいか否かを証明するのは、数学の証明のように結構難しい。

アルゴリズムの正しさというのが何を意味しているのか不明ですが，何かを証明するというのは常に数学的に証明することだと思います．「ように」ではなくて，そのものです．

しかしそれがプログラムの形で実装されていれば、少なくとも期待どおりの挙動を示すかどうかはそれを動かしてみるだけでわかる。そして動きがあるということは、頭だけではなく目と手でも理解できるということだ。

はい．その通りだと思います．それだから，アルゴリズムに関する多くの本でもある言語による実装が書いてあったり，多くの大学でアルゴリズムを実装するような実習が行なわれているわけです．はい．

用語の的確さ、内容の正確さは後で直していくこともできる。

一旦出版されてから直すのは大変だと思います．特に，文章の構造まで変えるのは (同一の書として刷り直すなら) ほとんど不可能でしょう．なので，出版される前に直すという意味なのでしょうね．

しかしそこにモノがなければ、それが正しいか間違っているかを判断することすら出来ない。

あら，これは正しくないですね．上に書いたことを参考にすれば，アルゴリズムの正しさと「モノ」 (この場合プログラム) の正しさは別物です．モノがなければ判断できないなら，数学的な証明は何も証明していないことになります．おそらく表現したいことと違うことが文として書かれてしまってるんじゃないでしょうか．

実際、二分検索のオーバーフローバグがわかったのだって、実際にバグが利用によって顕在化してからではないか。

これも1つ上と同様ですが，ここは表現したいことがそのまま文として書かれているような気がします．「二分検索のオーバーフローバグ」とここで呼んでいるものが本当にアルゴリズムの中にある間違いなのかどうか検討する必要があると思います．

というわけで、私は恥もコードも晒すことにしたのである。

恥をかくことは私が学生に薦めたいことですね．恥をかくことを怖がらずにいてもらいたいと思っています，学生には．