離散數學(原書第5版)(典藏版)/(美)約翰.A.多西
作 者: [美]約翰·A.多西（JohnA.Dossey）阿爾伯特·D.奧托（Albert 著 章炯民 王新偉 曹立 譯
定 價: 89
出?版?社: 機械工業出版社
出版日期: 2017年12月01日
頁 數: 477
裝 幀: 平裝
ISBN: 9787111640455
●出版者的話 譯者序 前言 致學生 離散數學紀年表 章 組合問題與組合技術引論 1 1.1 工程完成時間的問題 1 1.1.1 問題 1 1.1.2 分析 2 1.1.3 關鍵路徑分析 3 1.1.4 一個建築的例子 4 1.2 匹配問題 7 1.2.1 問題 7 1.2.2 分析 7 1.2.3 排列 8 1.2.4 航空公司問題解決方案的實用性 9 1.3 背包問題 11 1.3.1 問題 11 1.3.2 分析 12 1.3.3 回顧實驗問題 14 1.4 算法及其效率 15 1.4.1 算法的比較 15 1.4.2 多項式求值 16 1.4.3 子集生成算法 19 1.4.4 冒泡排序 21 歷史注記 24 補充習題 25 計算機題 27 推薦讀物 27 第2章 集合、關繫和函數 28 2.1 集合運算 28 2.2 等價關繫 32 *2.3 偏序關繫 37 2.3.1 偏序和全序 37 2.3.2 哈斯圖 40 2.3.3 拓撲排序 41 2.4 函數 44 2.5 數學歸納法 52 2.6 應用 58 歷史注記 65 補充習題 66 計算機題 69 推薦讀物 69 第3章 編碼理論 70 3.1 同餘 70 3.2 歐幾裡得算法 75 3.2.1 優選公約數 75 3.2.2 歐幾裡得算法 75 3.2.3 歐幾裡得算法的效率 77 3.2.4 擴展的歐幾裡得算法 77 3.3 RSA方法 79 3.3.1 指數取模 80 3.3.2 RSA方法的解密 83 3.3.3 RSA方法的可行性 85 3.4 檢錯碼和糾錯碼 86 3.5 矩陣碼 93 3.5.1 矩陣碼 93 3.5.2 編碼的校驗矩陣 94 3.6 單糾錯矩陣碼 99 3.6.1 校驗矩陣行譯碼法 100 3.6.2 漢明碼 101 歷史注記 105 補充習題 106 計算機題 109 推薦讀物 109 第4章 圖 110 4.1 圖及其表示 110 4.1.1 圖的概念和表示 110 4.1.2 圖的其他表示 112 4.1.3 同構 113 4.2 通路和回路 117 4.2.1 多重圖、通路和回路 117 4.2.2 歐拉回路和歐拉通路 119 4.2.3 哈密頓回路和哈密頓通路 122 4.3 最短通路和距離 129 4.3.1 廣度優先搜索算法 129 4.3.2 帶權圖 131 4.3.3 通路的數目 134 4.4 圖著色 138 4.5 有向圖和有向多重圖 144 4.5.1 有向圖 145 4.5.2 有向圖的表示 145 4.5.3 有向多重圖 146 4.5.4 有向歐拉回路和有向歐拉通路 148 4.5.5 有向哈密頓回路和有向哈密頓通路 149 歷史注記 155 補充習題 156 計算機題 160 推薦讀物 161 第5章 樹 162 5.1 樹的性質 162 5.2 生成樹 168 5.2.1 生成樹 169 5.2.2 廣度優先搜索法 169 5.2.3 最小生成樹和優選生成樹 171 5.2.4 普裡姆算法的證明 174 5.3 深度優先搜索 179 5.3.1 深度優先搜索法 179 5.3.2 回溯 183 5.4 根樹 188 5.5 二叉樹和遍歷 193 5.5.1 表達式樹 193 5.5.2 前序遍歷 195 5.5.3 後序遍歷 197 5.5.4 中序遍歷 199 5.6 最優二叉樹和二叉搜索樹 202 5.6.1 最優二叉樹 202 5.6.2 二叉搜索樹 208 歷史注記 215 補充習題 216 計算機題 219 推薦讀物 220 第6章 匹配 221 6.1 相異代表繫 221 6.1.1 相異代表繫 221 6.1.2 霍爾定理 222 6.2 圖中的匹配 225 6.2.1 匹配 225 6.2.2 偶圖的矩陣 227 6.2.3 覆蓋 227 6.3 匹配算法 231 6.3.1 獨立集算法的應用示例 231 6.3.2 將算法運用於優選獨立集 233 6.3.3 獨立集算法 234 6.3.4 課程分配 235 6.4 算法的應用 239 6.4.1 柯尼希定理 240 6.4.2 霍爾定理的證明 241 6.4.3 瓶頸問題 242 6.5 匈牙利方法 245 6.5.1 匈牙利算法 245 6.5.2 匈牙利算法的證明 247 6.5.3 不是方陣的矩陣 248 6.5.4 優選和獨立集 249 歷史注記 250 補充習題 251 計算機題 252 推薦讀物 253 第7章 網絡流 254 7.1 流和割 254 7.2 流增廣算法 261 7.3 優選流最小割定理 269 7.4 流和匹配 274 歷史注記 280 補充習題 280 計算機題 283 推薦讀物 283 第8章 計數技術 284 8.1 帕斯卡三角形和二項式定理 284 8.2 3個基本原理 287 8.3 排列和組合 293 8.4 允許重復的排列和組合 297 8.5 概率 302 *8.6 容斥原理 306 *8.7 排列和r組合的生成 315 8.7.1 排列的詞典序枚舉 315 8.7.2 r組合的詞典序枚舉 317 歷史注記 320 補充習題 321 計算機題 323 推薦讀物 324 第9章 遞推關繫與生成函數 325 9.1 遞推關繫 325 9.2 迭代法 333 9.3 常繫數線性差分方程 341 9.3.1 一階常繫數線性差分方程 341 9.3.2 二階線性齊次差分方程 344 *9.4 用遞推關繫分析算法的效率 350 9.4.1 順序查找算法和冒泡排序算法的效率… 350 9.4.2 分治算法的效率 352 9.4.3 排序算法的效率 357 9.5 用生成函數計數 359 9.5.1 生成函數 360 9.5.2 形式冪級數 361 9.6 生成函數的代數 365 歷史注記 372 補充習題 373 計算機題 375 推薦讀物 376 0章 組合電路和有限狀態機 377 10.1 邏輯門 377 10.2 構造組合電路 383 10.3 卡諾圖 388 10.4 有限狀態機 397 10.4.1 奇偶校驗機 398 10.4.2 有限狀態機 399 10.4.3 帶輸出的有限狀態機 400 歷史注記 404 補充習題 405 計算機題 407 推薦讀物 408 附錄A 邏輯和證明簡介 409 附錄B 矩陣 425 附錄C 本書中的算法 432 參考文獻 436 奇數號習題答案 440
內容簡介
本書是一本很好的離散數學入門教材，主要內容包括集合、關繫、函數、編碼理論、圖、樹、匹配、網絡流、計數技術、遞推關繫與生成函數、組合電路和有限狀態機等。 本書充分考慮到了初學者的需要，敘述淺顯易懂，內容、例題、習題都進行了精心的挑選和組織，講解細致，循序漸進。 本書可作為高等院校計算機專業或其他相關專業的離散數學教材或教學參考書，也可作為自學者的參考書。
譯 者 序 Discrete Mathematics, Fifth Edition 計算機從其誕生至今短短的幾十年間，得到了令人矚目的飛速發展，它在很多方面都深刻地改變了人類的活動方式和思維習慣。然而，現代數字計算機的理論模型依然是20世紀30年代提出的圖靈機，這是一種“離散”的機器，可用來處理“離散”的對像。當然，正如大多數計算機的早期應用那樣，通過近似計算等手段，計算機也可以處理“連續”的對像，但本質上，現代的數字計算機仍然是一種“離散”的機器。事實上，目前計算機已經越來越多地用於處理各種“離散”的對像。 離散數學研究離散對像的數量和空間關繫，它包括多個數學分支，如本書所涉及的集合論、圖論、組合數學、經典概率、自動機理論等，是計算機科學的理論基礎，也是計算機應用的有力工具。18世紀以前的數學基本上都屬於離散數學的範疇，之後，天文學、物理學等的發展極大地推動了連續數學（如微......
"
