その数式、プログラムできますか? 読書ノート

著者の一人は STL の設計者か。

著者:Alexander A. Stepanov, Daniel E. Rose
訳者:株式会社クイープ
出版社:翔泳社
発行年:2015 年
ISBN:978-4-7981-4110-7
関連 URL:あり

第 1 章 本書の内容

<抽象性を理解するためには、そのもとになっている数学を理解している必要がある> (p. 5)

第 2 章 最初のアルゴリズム

  • エジプト乗法 a.k.a. ロシア農民のアルゴリズム
  • 末尾再帰の優秀性をもっと強調して欲しい。

第 3 章 古代ギリシャの数論

この本は数学史、有力数学者の伝記に紙幅を割いていてひじょうに良い。

  • ピタゴラスの四科=天文学、幾何学、数論、音楽。
  • 文中に「シフト」という用語が出てくるが、これは英語の動詞 sift (separate by passing through a sieve or other) をそのまま片仮名で書いただけらしい。と思ったら p. 28 のコード中にズバリ sift とあった。

第 4 章 ユークリッドの互除法

互除法の章。この本は最大公約数の話題を繰り返し取り上げている。相当重要と考えているようだ。

  • そろばんが存在するのに「ゼロ」がないのは不思議 (p. 54) という指摘はなるほど。
  • C/C++ には商と剰余の演算子が別々に用意されている (p. 61) というから、両者が一度に欲しいときでも、C/C++ コードは損をするハメになる。 Win32 API の DivMod 的なものを別途利用しないと。

第 5 章 近代数論の誕生

この章ではフェルマーの小定理、ウィルソンの定理、オイラーの定理を紹介している。

  • 必要なのは概念であって、表記ではない (p. 81) by ガウス。

第 6 章 数学における抽象性

この章では群論の公理系からラグランジュの定理まで説明する。

  • 面白いのは 6.6, 6.7 の議論の組み立て方。準同型の概念を定義しないで、代わりに圏論の話を持ち出してから同型の定義をする。
  • まとめの p.121 の図 6-1 は数学科専攻の代数のノートにありそうな内容だ。

第 7 章 アルゴリズムの一般化

  • C++ のテンプレートの typename の仕様が私の承知しているそれよりも随分と高級になっているようだ。記述が丁寧なので、読者は所見でも理解できるだろう。
  • フィボナッチ数列の一般項を与えている (p. 141) が、プログラムコードとしてもこの形式で計算するのが望ましいのだろうか。つまり、この行列の乗算を素直に実装するのだろうか。

第 8 章 その他の代数構造

この章の話題は、多項式、最大公約数、可換環、体という流れになっている。

  • <トロピカル (tropical) または {min, +} 半環によって> (p. 166) 「または」の部分は原文では or とあったと思われるが、こういうのは「すなわち」「つまり」と訳して欲しい。
  • まとめ (pp. 170-172) 部分は数学科専攻の代数のノートにありそうな内容だ。

第 9 章 数学的知識の体系化

体系化、平行線公準、ペアノなど。

  • ヒルベルトの引用(テーブル、椅子、ジョッキ)が実に良い。
  • <数(正の整数)を定義することはできない> (p.195) by ペアノ。

第 10 章 プログラミングの基本概念

  • データ、値、値型、オブジェクトの定義は役に立つ。
  • リモートパーツという概念は知らなかったが、確かにこういう状況はよくある。
  • コンセプトとは。10.3 節はすごく重要。
  • 10.6 節の区間の議論。有界区間と算入区間という言葉は知らなんだ。言葉は知らなくても、読者はそこに書かれている概念には馴染んでいるはずだ。

第 11 章 置換アルゴリズム

順列(置換)。

  • <swap がいかに基本的な演算であるか> (p. 228) は同感。
  • 用語 polylog space (p. 248) がわからない。
  • ミニコラム get_temporary_buffer のエピソード (p. 250) は既視感がある。

第 12 章 GCD の拡張

最大公約数、環論。

これまで見てきたことは、整数や多項式や代数的整数には最大公約数という概念があるということだった。これを逆方向に考えて、最大公約数が存在するという「コンセプト」をユークリッド整域ということにする、という議論なのだろう。

  • そういうわけで、p. 257 のコードが関数テンプレート gcd の本質的な最終形となる。

第 13 章 現実の世界での応用

この章では暗号、素数、RSA を議論する。興味がほとんどないのでパス。

第 14 章 最後に

最初の章と最後の章とでロジャー・ベーコンを引用するのは何か意図がある?

付録 C 非 C++ プログラマーための C++

C++ の知識が古い C++ プログラマーは、むしろこの付録を先に読むべきだった。

  • 特に C.2 節のコンセプトの説明は必読。
  • 関数テンプレート std::partition_point は知らなんだ。
  • 予約語 using も不思議な方向に進化している。

付録 D 参考文献

参考文献が多いので、何かの役に立ちそうだ。