數(shù)學與泛型編程：高效編程的奧秘

目　　錄
譯者序
致謝
作者簡介
作者附言
第1章　內(nèi)容提要 1
1.1　編程與數(shù)學 1
1.2　從歷史的角度來講解 2
1.3　閱讀準備 3
1.4　各章概述 3
第2章　算法初談 5
2.1　埃及乘法算法 6
2.2　改進該算法 9
2.3　本章要點 12
第3章　古希臘的數(shù)論 13
3.1　整數(shù)的幾何屬性 13
3.2　篩選素數(shù) 15
3.3　實現(xiàn)該算法并優(yōu)化其代碼 18
3.4　完美數(shù) 23
3.5　畢達哥拉斯學派的構(gòu)想 26
3.6　畢氏構(gòu)想中的嚴重缺陷 28
3.7　本章要點 31
第4章　歐幾里得算法 33
4.1　雅典與亞歷山大 33
4.2　歐幾里得的最大公度量算法 36
4.3　缺乏數(shù)學成就的一千年 40
4.4　奇怪的0 42
4.5　求余及求商算法 44
4.6　用同一份代碼來實現(xiàn)求余及求商 47
4.7　對最大公約數(shù)算法進行驗證 49
4.8　本章要點 51
第5章　現(xiàn)代數(shù)論的興起 52
5.1　梅森素數(shù)與費馬素數(shù) 52
5.2　費馬小定理 57
5.3　消去 59
5.4　證明費馬小定理 63
5.5　歐拉定理 65
5.6　模運算的應用 69
5.7　本章要點 69
第6章　數(shù)學中的抽象 71
6.1　群 71
6.2　幺半群與半群 74
6.3　與群有關(guān)的定理 77
6.4　子群及循環(huán)群 80
6.5　拉格朗日定理 82
6.6　理論與模型 86
6.7　舉例說明范疇理論與非范疇理論 89
6.8　本章要點 92
第7章　推導泛型算法 94
7.1　厘清算法所應滿足的要求 94
7.2　對模板參數(shù)A提出要求 95
7.3　對模板參數(shù)N提出要求 98
7.4　提出新的要求 100
7.5　將乘法算法改編為冪算法 102
7.6　對運算本身加以泛化 103
7.7　計算斐波那契數(shù) 106
7.8　本章要點 109
第8章　更多代數(shù)結(jié)構(gòu) 110
8.1　斯蒂文、多項式及最大公約數(shù) 110
8.2　哥廷根與德國數(shù)學 115
8.3　埃米·諾特與抽象代數(shù)的誕生 120
8.4　環(huán) 121
8.5　矩陣乘法與半環(huán) 124
8.6　半環(huán)的運用：社交網(wǎng)絡與最短路徑 125
8.7　歐幾里得整環(huán) 127
8.8　域及其他的代數(shù)結(jié)構(gòu) 128
8.9　本章要點 129
第9章　整理數(shù)學知識 132
9.1　證明 132
9.2　數(shù)學史上的第一個定理 135
9.3　歐幾里得與公理化方法 137
9.4　與歐氏幾何并立的其他幾何學 139
9.5　希爾伯特的形式化方法 141
9.6　皮亞諾與他的公理 144
9.7　用皮亞諾公理來構(gòu)建算術(shù)體系 147
9.8　本章要點 149
第10章　編程的基本概念 150
10.1　亞里士多德與抽象 150
10.2　值與類型 152
10.3　concept 153
10.4　迭代器 156
10.5　迭代器的種類、所支持的操作及所具備的特性 157
10.6　區(qū)間 160
10.7　線性搜索 162
10.8　二分搜索 163
10.9　本章要點 167
第11章　置換算法 169
11.1　置換與換位 169
11.2　交換兩個區(qū)間內(nèi)的元素 172
11.3　旋轉(zhuǎn) 175
11.4　利用循環(huán)來執(zhí)行旋轉(zhuǎn) 178
11.5　倒置 182
11.6　空間復雜度 186
11.7　內(nèi)存自適應算法 187
11.8　本章要點 188
第12章　再論最大公約數(shù)算法 189
12.1　硬件的限制催生出更為高效的算法 189
12.2　Stein 算法的推廣 192
12.3　貝祖等式 194
12.4　擴展最大公約數(shù)算法 198
12.5　最大公約數(shù)算法的運用 202
12.6　本章要點 203
第13章　實際運用 204
13.1　密碼學 204
13.2　素數(shù)測試 206
13.3　米勒–拉賓素數(shù)測試 209
13.4　RSA算法的步驟及原理 211
13.5　本章要點 214
第14章　全書總結(jié) 215
延伸閱讀 217
附錄A　記法 222
附錄B　常用的證明辦法 225
附錄C　寫給非 C++ 程序員看的C++ 知識 228
參考文獻 237
中英文詞匯對照表 241