その数式プログラミングできますか?

その数式プログラミングできますか?

「その数式プログラミングできますか?」より。

この本のテーマはプログラミングだが、ほとんどのプログラミング本と異なり、アルゴリズムやコードに加えて、数学証明や、古代から現代までの数学上の発見に関する歴史的経緯が含まれている。

もう少し具体的に言うと、テーマはジェネリックプログラミング(generic programming)となる。ジェネリックプログラミングは1980年台に登場したプログラミングの手法であり、1990年代にC++のTL(Standard Template Library)が開発された。ここで、ジェネリックプログラミングとは、アルゴリズムとデータ構造を設計することに焦点を合わせ、効率を低下させることなく、それらを最も一般的な環境で動作させるためのプログラミング手法となる。

ジェネリックプログラミングは、STLに代表される特定のツールの集まりというよりは、プログラミングに対する姿勢に近いものとなる。

ジェネリックプログラミングの原点は数学であり、更に具体的にいうと、抽象代数学(abstract algebra)と呼ばれる数学の一分野に端を発している。この手法を理解するのに役立つように、この本では、オブジェクトをそれらに対する操作の対象という観点から推論する、という手法に焦点を合わせて抽象代数学について述べられている。

実際に、このプログラミング基本的な考え方の多くは数学からきている。そうした考え方がどのようにして生まれ、どのようにして発展したかを学ぶことは、ソフトウェアデザインを学ぶ上で重要な要素となる。例えば2000年以上前に書かれたユークリッドの「原論」(Elements)は、今なお理解しやすい小さな要素から複雑なシステムを構築する方法を最も効果的に示す手本の一つとなっている。

ジェネリックプログラミングの中心にあるのは抽象性だが、抽象性は最初から完全な形で存在しているわけではない。何かを法則化する方法を理解するには、具体的なものから始める必要がある。具体的に言うと、抽象性を正しく捉えるには、特定の分野を具体的に理解している必要がある。

抽象代数学に登場する抽象性は、主に、最も古くからある数学の一部である数論(number theory)の具体的な研究結果に基づいている。そこでこの図書では、整数の性質、特に可分性に関する数論の基本的な考え方についても紹介されている。

これらの数学を理解するための思考プロセスは、プログラミングスキルを向上させるだけでなく様々なアルゴルズムを構築するためのヒントになる。

この図書の中に記載されている内容としては
第1章では、ジェネリックプログラミングの概要
第2章では、古代の乗数アルゴリズムに関するエピソードとその改良方法
第3章では、数字の性質に関する初期の見解と、素数を求めるアルゴリズムの効率的な実装
第4章では、最大公約数を求めるアルゴリズム(抽象概念やアプリケーションの基礎)
第5章では、重要な役割を果たす定理を2つ説明
第6章では、ジェネリックプログラミングの中心にある抽象数学
第7章では、数学的な概念を一般化することで、単純な催術の枠を超えて、情報アルゴリズムを実践的なプログラミングに応用
第8章では、新しい抽象的な数学構造の紹介
第9章では、公理系、理論、モデル(ジェネリックプログラミングの構成要素)を説明
第10章では、ジェネリックプログにミングを構成する概念を紹介し、単純に思えるプロミングタスクに含まれる微妙な問題を提示
第11章では、基本的なプログラミングタスクの検証を通して、問題に対する理論的な知識を現場の実装にどう応用できるかを提示
第12章では、ハードウェアの制約が古いアルゴリズムに対する新しいアプローチに繋がることを提示
第13章では、数学的な結果とアルゴリズム的な結果を組み合わせた暗号アプリケーションの構築
第14章では、まとめに
となっている。

それらの目次としては以下のようになる。

CHAPTER1 本書の内容
1.1 プログラミングと数学
1.2 歴史的観点
1.3 本書の前提条件
1.4 ロードマップ

CHAPTER2 最初のアルゴリズム
2.1 エジプト乗法
2.2 アルゴリズムの改良
2.3 まとめ

CHAPTER3 古代ギリシャの数論
3.1 整数の幾何学的特性
3.2 素数のシフト
3.3 コードの実装と最適化
3.4 完全数
3.5 ピタゴラス派の目論見
3.6 ピタゴラス派の目論見の致命的な欠陥
3.7 まとめ

CHAPTER4 ユークリッドの互除法
4.1 アテナイとアレクサンドリア
4.2 ユークリッドの最大公約数アルゴリズム
4.3 数学の空白の千年
4.4 ゼロの不思議な歴史
4.5 剰余と商のアルゴリズム
4.6 コードの共有
4.7 アルゴリズムの検証
4.8 まとめ

CAHPTER5 近代数論の誕生
5.1 メルセンヌ素数とフェルマー素数
5.2 フェルマーの小定理
5.3 簡約
5.4 フェルマーの小定理の証明
5.5 オイラーの定理
5.6 合同算術の応用
5.7 まとめ

CHAPTER6 数学における抽象性
6.1 群
6.2 モノイドと半群
6.3 群に関する定理
6.4 部分群と巡回群
6.5 ラグランジェの定理
6.6 理論とモデル
6.7 圏論と非圏論の例
6.8 まとめ

CHAPTER7 アルゴリズムの一般化
7.1 アルゴリズムの要件を整理する
7.2 Aの要件
7.3 Nの要件
7.4 新しい要件
7.5 乗算をべき乗に変換する
7.6 演算の一般化
7.7 フィナボッチ数列の計算
7.8 まとめ

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

CHAPTER9 数学知識の体系化
9.1 証明
9.2 最初の定理
9.3 ユークリッドと公理的方法
9.4 ユークリッド幾何学に代わるもの
9.5 ヒルベルトの形式主義アプローチ
9.6 ペアノとペアノの公理
9.7 算術の構築
9.8 まとめ

CHAPTER10 プログラミングの基礎概念
10.3 コンセプト
10.4 イテレータ
10.5 イテレータカテゴリー、演算、トレイト
10.6 区間
10.7 線型探索
10.8 二分探索
10.9 まとめ

CHAPTER11 置換アルゴリズム
11.1 置換と移項
11.2 区間の交換
11.3 回転
11.4 巡回の使用
11.5 反転
11.6 空間的コスト
11.7 メモリ適用アルゴリズム
11.8 まとめ

CHAPTER12 GCDの拡張
12.1 ハードウェアの制約とより効率的なアルゴリズム
12.2 ステインのアルゴリズムの一般化
12.3 ベズーの等式
12.4 拡張GCD
12.5 GCDの応用
12.6 まとめ

CHAPTER13 現実の世界での応用
13.1 暗号学
13.2 素数判定
13.3 ミラー・ラピンテスト
13.4 RSAアルゴリズムの仕組み
13.5 まとめ