magazine.gif その数式、プログラムできますか?

謝辞
著者紹介
まえがき

第1章 本書の内容

  • プログラミングと数学
  • 歴史的観点
  • 本書の前提条件
  • ロードマップ

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

  • エジプト乗法
  • アルゴリズムの改良
  • まとめ

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

  • 整数の幾何学的特性
  • 素数のシフト
  • コードの実装と最適化
  • 完全数
  • ピタゴラス派の目論
  • ピタゴラス派の目論の致命的な欠陥
  • まとめ

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

  • アテナイとアレクサンドリア
  • ユークリッドの最大公約数アルゴリズム
  • 数学の空白の千年
  • ゼロの不思議な歴史
  • 剰余と商のアルゴリズム
  • コードの共有
  • アルゴリズムの検証
  • まとめ

第5章 近代数論の誕生

  • メルセンヌ素数とフェルマー素数
  • フェルマーの小定理
  • 簡約
  • フェルマーの小定理の証明
  • オイラーの定理
  • 合同算術の応用
  • まとめ

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

  • モノイドと半群
  • 群に関する定理
  • 部分群と巡回群
  • ラグランジェの定理
  • 理論とモデル
  • 圏論と非圏論の例
  • まとめ

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

  • アルゴリズムの要件を整理する
  • Aの要件
  • Nの要件
  • 新しい要件
  • 乗算をべき乗に交換する
  • 演算の一般化
  • フィボナッチ数列の計算
  • まとめ

第8章 その他の代数構造

  • ステヴィン、多項式、最大公約数
  • ゲッティンゲンとドイツの数学
  • ネーターと抽象代数学の誕生
  • 行列の乗算と半環
  • 応用:ソーシャルネットワークと最短経路
  • ユークリッド整域
  • 体とその他の代数構造
  • まとめ

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

  • 証明
  • 最初の定理
  • ユークリッドと公理的方法
  • ユークリッド幾何学に代わるもの
  • ヒルベルトの形式主義アプローチ
  • ペアノとペアノの公理
  • 算術の構築
  • まとめ

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

  • アリストテレスと抽象化
  • 値と型
  • コンセプト
  • イテレータ
  • イテレータカテゴリー、演算、トレイト
  • 区間
  • 線形探索
  • 二分探索
  • まとめ

第11章 置換アルゴリズム

  • 置換と移項
  • 区間の交換
  • 回転
  • 巡回の使用
  • 反転
  • 空間的コスト
  • メモリ適応アルゴリズム
  • まとめ 

第12章 GCD の拡張

  • ハードウェアの制約とより効果的なアルゴリズム
  • ステインのアルゴリズムの一般化
  • ベズーの等式
  • 拡張GCD
  • GCDの応用
  • まとめ

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

  • 暗号学
  • 素数判定
  • ミラー・ラビンテスト
  • RSAアルゴリズムの仕組み
  • まとめ

第14章 最後に

  • 深く理解するために

付録A 数学表記

  • 記号
  • 合意と対偶

付録B 一般的な証明法

  • 背理法による証明
  • 帰納法による証明
  • 鳩の巣原理

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

  • テンプレート関数
  • コンセプト
  • 宣言の構文と定数の型指定
  • 関数オブジェクト
  • 事前条件、事後条件、アサーション
  • STLのアルゴリズムとデータ構造
  • イテレータと区間
  • C++11のusingを使った型エイリアスと型関数
  • C++11のイニシャライザリスト
  • C++11のラムダ関数
  • inlineに関する注記

付録D 参考文献
索引