計算機程序設計藝術 卷4B：組合算法（二）（英文版）
[美] 高德納（Donald E. Knuth）
- 出版商: 人民郵電
- 出版日期: 2025-05-01
- 售價: $1,799
- 語言: 簡體中文
- 頁數: 673
- ISBN: 7115667608
- ISBN-13: 9787115667601
-
相關分類:
英文 English
已絕版
相關主題
商品描述
《計算機程序設計藝術》系列是圖靈獎得主高德納傾盡心血進行的一項巨大的寫作計劃，這套書被公認為計算機科學領域的權威之作，深入闡述了程序設計和算法理論，對計算機領域的發展有著極為深遠的影響。高德納是算法和程序設計領域的先驅者，對計算機科學發展史也有著深入的研究，書中在介紹眾多理論的同時，也給出了相關的歷史和發展進程，成為本書的一大特色。本書是該系列的卷4B，以7.2.2節開篇，討論回溯編程，內容包括舞蹈鏈、精準覆蓋問題、算法謎題、可滿足性問題等。
作者簡介
高德納（Donald E. Knuth）
1974年圖靈獎得主，斯坦福大學計算機系榮休教授，美國國家科學院院士，美國工程院院士。
著名計算機科學家，算法與程序設計技術的先驅者、計算機排版系統TEX和METAFONT字體系統的發明人，因諸多成就以及大量富於創造力和具有深遠影響的著作（19部書，160篇論文）而譽滿全球。
近些年，他將精力全部投入到“計算機程序設計藝術”七卷集的史詩般創作中。
Knuth教授獲得過許多獎項和榮譽，包括美國國家科學獎章、計算機先鋒獎、美國數學學會的斯蒂爾獎、IEEE馮·諾依曼獎，以及因發明先進技術於1996年榮獲的京都獎。1996年，Donald E. Knuth獎設立，授予那些為計算機科學基礎做出傑出貢獻的人。
目錄大綱
重溫預備數學知識 1
不等式 3
鞅 6
從鞅得到的尾部不等式 8
應用 9
幾乎必然和確乎必然的陳述 11
習題 12
第7 章組合查找 [4A.1]
7.2 生成所有可能的組合對象 [4A.281]
7.2.1 生成基本組合模式 [4A.281]
7.2.2 回溯編程 30
數據結構 32
沃克方法 33
排列與蘭福德對 34
單詞矩形 36
無逗點碼 37
選擇的動態排序 38
重溫順序分配 39
無逗點碼問題的列表 41
行動和撤銷的一般機制 43
無逗點碼的回溯 44
運行時間估計 46
*估計解的個數 49
分解問題 52
歷史註記 53
習題 55
7.2.2.1 舞蹈鏈 65
精確覆蓋問題 66
副項 70
進度報告 73
數獨 74
多聯骨牌 79
多聯立方 82
分解精確覆蓋問題 83
受限顏色覆蓋 87
引入重數 92
*新的舞步 95
*分析算法X 98
*分析匹配問題 102
*保持適當的專註 104
利用局部等價性 106
*預處理選項 108
最小成本解 111
*實現最小成本截斷 116
*使用ZDD 的舞蹈鏈 119
總結 122
歷史註記 123
習題（第 1 組） 124
習題（第 2 組） 156
習題（第3 組） 174
7.2.2.2 可滿足性 185
一個簡單的例子 188
精確覆蓋 189
圖著色 190
因式分解整數 192
故障測試 194
學習布爾函數 198
有界模型檢測 200
互斥中的應用 204
數字體層成像 208
SAT 實例——總結 210
回溯求解可滿足性問題 211
惰性數據結構 214
從單元子句強制移動 215
算法的比較 218
*通過更加努力地工作來獲得提速 219
*通過前瞻來獲得提速 223
*更進一步的前瞻 229
隨機可滿足性問題 231
分析隨機2SAT問題 235
歸結法 238
*一般歸結法的下界 241
使用歸結的SAT 求解 244
由沖突驅動的子句學習 246
不可滿足性證書 253
*清除無用的子句 255
*刷新文字並重新開始 259
蒙特卡羅算法. . . . . . . . . . . . . . . . . . . . . . 261
局部引理 265
跡與板塊 267
跡上的算術 269
*跡與局部引理 271
*消息傳遞 274
*預處理子句 279
將約束編碼為子句 281
單元傳播與強制 287
對稱性破缺 289
保可滿足性的映射 291
100 個測試樣例 297
調整參數 308
利用並行化 312
簡史 313
習題 317
習題答案 370
附錄A 數值表 656
附錄B 記號索引 660
附錄C 算法、定理、引理、推論和程序索引 666
附錄D 組合問題索引 667
附錄E 習題解答中謎題的答案 671
