離散數(shù)學(xué)及其應(yīng)用：原書第4版

第l章  基礎(chǔ)：邏輯. 集合和函數(shù)                  
 1. 1  邏輯                  
 1. 1. 1  引言                  
 1. 1. 2  命題                  
 1. 1. 3  翻譯語言的句子                  
 1. 1. 4  布爾檢索                  
 l. 1. 5  邏輯運(yùn)算和位運(yùn)算練習(xí)                  
 1. 2  命題等價(jià)                  
 1. 2. 1  引言                  
 1. 2. 2  邏輯等價(jià)練習(xí)                  
 1. 3  謂詞和量詞                  
 1. 3. 1  引言                  
 1. 3. 2  量詞                  
 1. 3. 3  翻譯語句為邏輯表達(dá)式                  
 1. 3. 4  選自Lewis Carroll的例子(選讀)                  
 1. 3. 5  綁定變量                  
 1. 3. 6  否定練習(xí)                  
 1. 4  集合                  
 1. 4. 1  引言                  
 1. 4. 2  冪集合                  
 1. 4. 3  笛卡兒積練習(xí)                  
 1. 5  集合運(yùn)算                  
 1. 5. 1  引言                  
 1. 5. 2  集合相等                  
 1. 5. 3  擴(kuò)展的并集和交集                  
 1. 5. 4  集合的計(jì)算機(jī)表示練習(xí)                  
 1. 6  函數(shù)                  
 1. 6. 1  引言                  
 1. 6. 2  一對(duì)一函數(shù)和映上函數(shù)                  
 1. 6. 3  反函數(shù)和函數(shù)組合                  
 1. 6. 4  函數(shù)的圖像                  
 1. 6. 5  幾個(gè)重要的函數(shù)練習(xí)                  
 1. 7  序列與求和                  
 1. 7. 1  引言                  
 1. 7. 2  序列                  
 1. 7. 3  特殊的整數(shù)序列                  
 1. 7. 4  求和                  
 1. 7. 5  基數(shù)(選讀)練習(xí)                  
 1. 8  函數(shù)增長(zhǎng)                  
 1. 8. 1  引言                  
 1. 8. 2  大O符號(hào)                  
 1. 8. 3  函數(shù)組合的增長(zhǎng)                  
 1. 8. 4  大Ω和大Ξ符號(hào)                  
 練習(xí)                  
 關(guān)鍵術(shù)語和結(jié)果                  
 復(fù)習(xí)題                  
 補(bǔ)充練習(xí)                  
 計(jì)算機(jī)題目                  
 計(jì)算和研究                  
 寫作題目                  
 第2章  基礎(chǔ)：算法. 整數(shù)和矩陣                  
 2. 1  算法                  
 2. 1. 1  引言                  
 2. 1. 2  搜索算法練習(xí)                  
 2. 2  算法的復(fù)雜性                  
 2. 2. 1  引言練習(xí)                  
 2. 3  整數(shù)和除法                  
 2. 3. 1  引言                  
 2. 3. 2  除法                  
 2. 3. 3  素?cái)?shù)                  
 2. 3. 4  除法算法                  
 2. 3. 5  最大公約數(shù)和最小公倍數(shù)                  
 2. 3. 6  模運(yùn)算                  
 2. 3. 7  同余應(yīng)用                  
 2. 3. 8  密碼學(xué)練習(xí)                  
 2. 4  整數(shù)和算法                  
 2. 4. 1  引言                  
 2. 4. 2  歐幾里德算法                  
 2. 4. 3  整數(shù)表示                  
 2. 4. 4  整數(shù)運(yùn)算算法練習(xí)                  
 2. 5  數(shù)論應(yīng)用                  
 2. 5. 1  引言                  
 2. 5. 2  若干有用的結(jié)果                  
 2. 5. 3  線性同余                  
 2. 5. 4  中國余數(shù)定理                  
 2. 5. 5  大整數(shù)的計(jì)算機(jī)算術(shù)運(yùn)算                  
 2. 5. 6  偽素?cái)?shù)                  
 2. 5. 7  公鑰密碼學(xué)                  
 2. 5. 8  RSA加密                  
 2. 5. 9  RSA解密                  
 2. 5. 10  用RSA作公鑰系統(tǒng)練習(xí)                  
 2. 6  矩陣                  
 2. 6. 1  引言                  
 2. 6. 2  矩陣運(yùn)算                  
 2. 6. 3  矩陣乘法運(yùn)算                  
 2. 6. 4  矩陣的轉(zhuǎn)置和冪                  
 2. 6. 5  0-1矩陣練習(xí)                  
 關(guān)鍵術(shù)語和結(jié)果                  
 復(fù)習(xí)題                  
 補(bǔ)充練習(xí)                  
 計(jì)算機(jī)題目                  
 計(jì)算和研究                  
 寫作題目                  
 第3章  數(shù)學(xué)推理                  
 3. 1  證明方法                  
 3. 1. 1  引言                  
 3. 1. 2　推理規(guī)則                  
 3. 1. 3  謬誤                  
 3. 1. 4  帶量詞命題的推理規(guī)則                  
 3. 1. 5  證明定理的方法                  
 3. 1. 6  定理與量詞                  
 3. 1. 7  停機(jī)問題                  
 3. 1. 8  關(guān)于證明的一些評(píng)注練習(xí)                  
 3. 2  數(shù)學(xué)歸納法                  
 3. 2. 1  引言                  
 3. 2. 2  良序性                  
 3. 2. 3  數(shù)學(xué)歸納法                  
 3. 2. 4  數(shù)學(xué)歸納法證明的例子                  
 3. 2. 5  數(shù)學(xué)歸納法的第二原理練習(xí)                  
 3. 3  遞歸定義                  
 3. 3. 1  引言                  
 3. 3. 2  遞歸地定義函數(shù)                  
 3. 3. 3  遞歸地定義集合練習(xí)                  
 3. 4  遞歸算法                  
 3. 4. 1  引言                  
 3. 4. 2  遞歸與迭代練習(xí)                  
 3. 5  程序正確性                  
 3. 5. 1  引言                  
 3. 5. 2  程序驗(yàn)證                  
 3. 5. 3  推理規(guī)則                  
 3. 5. 4  條件語句                  
 3. 5. 5  循環(huán)不變量                  
 練習(xí)                  
 關(guān)鍵術(shù)語和結(jié)果                  
 復(fù)習(xí)題                  
 補(bǔ)充練習(xí)                  
 計(jì)算機(jī)題目                  
 計(jì)算和研究                  
 寫作題目                  
 第4章  計(jì)數(shù)                  
 4. 1  計(jì)數(shù)的基礎(chǔ)                  
 4. 1. 1  引言                  
 4. 1. 2  基本的計(jì)數(shù)原則                  
 4. 1. 3  容斥原理                  
 4. 1. 4  樹圖練習(xí)                  
 4. 2  鴿巢原理                  
 4. 2. 1  引言                  
 4. 2. 2  推廣的鴿巢原理                  
 4. 2. 3  巧妙使用鴿巢原理練習(xí)                  
 4. 3  排列與組合                  
 4. 3. 1  引言                  
 4. 3. 2  排列                  
 4. 3. 3  組合                  
 4. 3. 4  二項(xiàng)式系數(shù)                  
 4. 3. 5  二項(xiàng)式定理練習(xí)                  
 4. 4  離散概率                  
 4. 4. 1  引言                  
 4. 4. 2  有限概率                  
 4. 4. 3  事件組合的概率                  
 4. 4. 4  概率的推理練習(xí)                  
 4. 5  概率論                  
 4. 5. 1  引言                  
 4. 5. 2  概率賦值                  
 4. 5. 3  事件的組合                  
 4. 5. 4  條件概率                  
 4. 5. 5  獨(dú)立性                  
 4. 5. 6  伯努利實(shí)驗(yàn)與二項(xiàng)式分布                  
 4. 5. 7  隨機(jī)變量                  
 4. 5. 8  期望值                  
 4. 5. 9  獨(dú)立隨機(jī)變量                  
 4. 5. 10  方差                  
 4. 5. 11  切比雪夫不等式                  
 4. 5. 12  平均狀態(tài)下的計(jì)算復(fù)雜性練習(xí)                  
 4. 6  一般性的排列和組合                  
 4. 6. 1  引言                  
 4. 6. 2  有重復(fù)的排列                  
 4. 6. 3  有重復(fù)的組合                  
 4. 6. 4  具有不可區(qū)別物體的集合的排列                  
 4. 6. 5  把物體放入盒子練習(xí)                  
 4. 7  生成排列和組合                  
 4. 7. 1  引言                  
 4. 7. 2  生成排列                  
 4. 7. 3  生成組合                  
 練習(xí)                  
 關(guān)鍵術(shù)語和結(jié)果                  
 復(fù)習(xí)題                  
 補(bǔ)充練習(xí)                  
 計(jì)算機(jī)題目                  
 計(jì)算和研究                  
 寫作題目                  
 第5章  高級(jí)計(jì)數(shù)技術(shù)                  
 5. 1  遞推關(guān)系                  
 5. 1. 1  引言                  
 5. 1. 2  遞推關(guān)系                  
 5. 1. 3  用遞推關(guān)系構(gòu)造模型練習(xí)                  
 5. 2　求解遞推關(guān)系                  
 5. 2. 1  引言                  
 5. 2. 2  求解常系數(shù)線性齊次遞推關(guān)系                  
 5. 2. 3  常系數(shù)線性非齊次的遞推關(guān)系練習(xí)                  
 5. 3　分而治之關(guān)系                  
 5. 3. 1  引言                  
 5. 3. 2  分而治之關(guān)系練習(xí)                  
 5. 4  生成函數(shù)                  
 5. 4. 1  引言                  
 5. 4. 2  關(guān)于冪級(jí)數(shù)的有用的事實(shí)                  
 5. 4. 3  計(jì)數(shù)問題與生成函數(shù)                  
 5. 4. 4  使用生成函數(shù)求解遞推關(guān)系                  
 5. 4. 5  使用生成函數(shù)證明恒等式練習(xí)                  
 5. 5  容斥                  
 5. 5. 1  引言                  
 5. 5. 2  容斥原理練習(xí)                  
 5. 6  容斥原理的應(yīng)用                  
 5. 6. 1  引言                  
 5. 6. 2  容斥原理的另一種形式                  
 5. 6. 3　伊拉脫森篩                  
 5. 6. 4  映上函數(shù)的個(gè)數(shù)                  
 5. 6. 5  錯(cuò)位排列                  
 練習(xí)                  
 關(guān)鍵術(shù)語和結(jié)果                  
 復(fù)習(xí)題                  
 補(bǔ)充練習(xí)                  
 計(jì)算機(jī)題目                  
 計(jì)算和研究                  
 寫作題目                  
 第6章  關(guān)系                  
 6. 1  關(guān)系及其性質(zhì)                  
 6. 1. 1  引言                  
 6. 1. 2  函數(shù)作為關(guān)系                  
 6. 1. 3  集合上的關(guān)系                  
 6. 1. 4  關(guān)系的性質(zhì)                  
 6. 1. 5  關(guān)系的組合練習(xí)                  
 6. 2  n元關(guān)系及其應(yīng)用                  
 6. 2. 1  引言                  
 6. 2. 2  n元關(guān)系                  
 6. 2. 3  數(shù)據(jù)庫和關(guān)系練習(xí)                  
 6. 3  關(guān)系的表示                  
 6. 3. 1  引言                  
 6. 3. 2  用矩陣表示關(guān)系                  
 6. 3. 3  用圖表示關(guān)系練習(xí)                  
 6. 4  關(guān)系的閉包                  
 6. 4. 1  引言                  
 6. 4. 2  閉包                  
 6. 4. 3  有向圖的路徑                  
 6. 4. 4  傳遞閉包                  
 6. 4. 5  沃舍爾算法練習(xí)                  
 6. 5  等價(jià)關(guān)系                  
 6. 5. 1  引言                  
 6. 5. 2  等價(jià)關(guān)系                  
 6. 5. 3  等價(jià)類                  
 6. 5. 4  等價(jià)類與劃分練習(xí)                  
 6. 6  偏序                  
 6. 6. 1  引言                  
 6. 6. 2  字典順序                  
 6. 6. 3  哈斯圖                  
 6. 6. 4  極大元素與極小元素                  
 6. 6. 5  格                  
 6. 6. 6  拓?fù)渑判?nbsp;                 
 練習(xí)                  
 關(guān)鍵術(shù)語和結(jié)果                  
 復(fù)習(xí)題                  
 補(bǔ)充練習(xí)                  
 計(jì)算機(jī)題目                  
 計(jì)算和研究                  
 寫作題目                  
 第7章  圖                  
 7. 1  圖的介紹                  
 7. 1. 1  圖的種類                  
 7. 1. 2  圖模型練習(xí)                  
 7. 2  圖的術(shù)語                  
 7. 2. 1  引言                  
 7. 2. 2  基本術(shù)語                  
 7. 2. 3  一些特殊的簡(jiǎn)單圖                  
 7. 2. 4  偶圖                  
 7. 2. 5  特殊類型的圖的一些應(yīng)用                  
 7. 2. 6  從舊圖到新圖練習(xí)                  
 7. 3  圖的表示和圖的同構(gòu)                  
 7. 3. 1  引言                  
 7. 3. 2  圖的表示                  
 7. 3. 3  相鄰矩陣                  
 7. 3. 4  關(guān)聯(lián)矩陣                  
 7. 3. 5  圖的同構(gòu)練習(xí)                  
 7. 4  連通性                  
 7. 4. 1  引言                  
 7. 4. 2  通路                  
 7. 4. 3  無向圖連通性                  
 7. 4. 4  有向圖中的連通性                  
 7. 4. 5  通路與同構(gòu)                  
 7. 4. 6  統(tǒng)計(jì)頂點(diǎn)之間的通路練習(xí)                  
 7. 5  歐拉通路與哈密頓通路                  
 7. 5. 1  引言                  
 7. 5. 2  歐拉回路和歐拉通路的充要條件                  
 7. 5. 3  哈密頓通路和回路練習(xí)                  
 7. 6  最短通路問題                  
 7. 6. 1  引言                  
 7. 6. 2  一個(gè)最短通路算法                  
 7. 6. 3  旅行推銷員問題練習(xí)                  
 7. 7  平面性圖                  
 7. 7. 1  引言                  
 7. 7. 2  歐拉公式                  
 7. 7. 3  庫拉圖斯基定理練習(xí)                  
 7. 8  圖著色                  
 7. 8. 1  引言                  
 7. 8. 2  圖著色的應(yīng)用                  
 練習(xí)                  
 關(guān)鍵術(shù)語和結(jié)果                  
 復(fù)習(xí)題                  
 補(bǔ)充練習(xí)                  
 計(jì)算機(jī)題目                  
 計(jì)算和研究                  
 寫作題目                  
 第8章  樹                  
 8. 1  介紹樹                  
 8. 1. 1  樹作為模型                  
 8. 1. 2  樹的性質(zhì)練習(xí)                  
 8. 2  樹的應(yīng)用                  
 8. 2. 1  引言                  
 8. 2. 2  二叉搜索樹                  
 8. 2. 3  決策樹                  
 8. 2. 4  前綴碼練習(xí)                  
 8. 3  樹的遍歷                  
 8. 3. 1  引言                  
 8. 3. 2  通用地址系統(tǒng)                  
 8. 3. 3  遍歷算法                  
 8. 3. 4  中綴. 前綴和后綴記法練習(xí)                  
 8. 4  樹與排序                  
 8. 4. 1  引言                  
 8. 4. 2  排序的復(fù)雜性                  
 8. 4. 3  冒泡排序                  
 8. 4. 4  歸并排序練習(xí)                  
 8. 5  生成樹                  
 8. 5. 1  引言                  
 8. 5. 2  一些構(gòu)造生成樹的算法                  
 8. 5. 3  回溯練習(xí)                  
 8. 6  最小生成樹                  
 8. 6. 1  引言                  
 8. 6. 2  最小生成樹算法                  
 練習(xí)                  
 關(guān)鍵術(shù)語和結(jié)果                  
 復(fù)習(xí)題                  
 補(bǔ)充練習(xí)                  
 計(jì)算機(jī)題目                  
 計(jì)算和研究                  
 寫作題目                  
 第9章  布爾代數(shù)                  
 9. 1  布爾函數(shù)                  
 9. 1. 1  引言                  
 9. 1. 2  布爾表達(dá)式和布爾函數(shù)                  
 9. 1. 3  布爾代數(shù)中的恒等式                  
 9. 1. 4  對(duì)偶性                  
 9. 1. 5  布爾代數(shù)的抽象定義練習(xí)                  
 9. 2  布爾函數(shù)的表示                  
 9. 2. 1  積之和展開式                  
 9. 2. 2  函數(shù)完備性練習(xí)                  
 9. 3  邏輯門電路                  
 9. 3. 1  引言                  
 9. 3. 2  門的組合                  
 9. 3. 3  電路的例子                  
 9. 3. 4  加法器練習(xí)                  
 9. 4  電路的極小化                  
 9. 4. 1  引言                  
 9. 4. 2  卡諾圖                  
 9. 4. 3  無需在意條件                  
 9. 4. 4  奎因-莫可拉斯基方法                  
 練習(xí)                  
 關(guān)鍵術(shù)語和結(jié)果                  
 復(fù)習(xí)題                  
 補(bǔ)充練習(xí)                  
 計(jì)算機(jī)題目                  
 計(jì)算和研究                  
 寫作題目                  
 第10章  計(jì)算模型                  
 10. 1  語言和文法                  
 10. 1. 1  引言                  
 10. 1. 2  短語結(jié)構(gòu)文法                  
 10. 1. 3  短語結(jié)構(gòu)文法的類型                  
 10. 1. 4  派生樹                  
 10. 1. 5  巴科斯-諾爾范式練習(xí)                  
 10. 2  帶輸出的有限狀態(tài)機(jī)                  
 10. 2. 1  引言                  
 10. 2. 2  帶輸出的有限狀態(tài)機(jī)練習(xí)                  
 10. 3  不帶輸出的有限狀態(tài)機(jī)                  
 10. 3. 1  引言                  
 10. 3. 2  串的集合                  
 10. 3. 3  有限狀態(tài)自動(dòng)機(jī)練習(xí)                  
 10. 4  語言的識(shí)別                  
 10. 4. 1  引言                  
 10. 4. 2  正則集合                  
 10. 4. 3  克萊因定理                  
 10. 4. 4  正則集合和正則文法                  
 10. 4. 5  一個(gè)不能由有限狀態(tài)自動(dòng)機(jī)識(shí)別語言                  
 10. 4. 6  一些更強(qiáng)大的機(jī)器練習(xí)                  
 10. 5  圖靈機(jī)                  
 10. 5. 1  引言                  
 10. 5. 2  圖靈機(jī)的定義                  
 10. 5. 3  用圖靈機(jī)識(shí)別集合                  
 10. 5. 4  用圖靈機(jī)計(jì)算函數(shù)                  
 10. 5. 5  不同類型的圖靈機(jī)                  
 10. 5. 6  丘奇-圖靈論題                  
 練習(xí)                  
 關(guān)鍵術(shù)語和結(jié)果                  
 復(fù)習(xí)題                  
 補(bǔ)充練習(xí)                  
 計(jì)算機(jī)題目                  
 計(jì)算和研究                  
 寫作題目                  
 附錄A  指數(shù)函數(shù)和對(duì)數(shù)函數(shù)                  
 附錄B  偽代碼                  
 奇數(shù)練習(xí)題答案                  
 推薦讀物                  
 參考文獻(xiàn)