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