滿額折
商品簡介
序
目次
商品簡介
本書選取了計算機科學專業的學生需要掌握的離散數學基礎知識和核心理論進行系統的介紹，以利用計算機解決問題為主要目標，將理論與實踐結合起來，使學生充分認識抽象的重要性。全書選材適當、結構清晰、敘述簡明、推理嚴謹，適合作為高校計算機專業離散數學課程的教材，也適合從事計算機軟件發展工作的技術人員學習。
序
本書面向計算機科學相關專業學生，以學生可接受的形式和提高程序設計競爭力的方式介紹離散數學基礎，內容主要聚焦在與計算機科學直接相關的主題上。
大多數章節都通過例子逐步說明要介紹的內容。第1章介紹整本書的內容框架：如何設計標準計算問題的求解算法？對每一個合適的輸入，如何知道算法是否工作正確？算法需要多長時間生成輸出？
從我們的觀點來看，教學本身遠比內容展示要多得多，我們已經將本書作為“目標導向的學生實踐能力設計”教程。人類習慣於給信息添加標籤，表示從實踐中獲取的重要性。書中用這些實踐作為正面引導。
本書旨在促使學生努力思考，培養他們的問題求解能力，並結合理論和應用，認識抽象的重要性。書中通過一些難忘的具有激勵作用的例子來吸引學生，這些例子中的新想法、新方法和思考深度會給學生帶來挑戰。希望本書比其他離散數學教材更吸引學生。
書中介紹了很多計算機科學文化以及計算機科學家分享的常識（不包括程序設計）。許多是計算機科學家都知道的基礎問題的基本求解方法：如何查找特定目標清單；如何按自然數序列對列表排序以方便查找；如何生成所有物件、子集或以某種次序排列的序列；如何遍歷圖的所有頂點；特別是，如何比較算法的效率並驗證算法的正確性。但介紹的數學知識與計算機科學相關。
本書最突出的特點是非形式化描述和交互特性。算法的詳細遍歷過程貫穿始終。為了將材料介紹得生動一些，會插入一些挑戰性的問題和評論。我們試圖像在課堂上一樣與讀者交流，這與其他傳統的數學教材有所區別。書中用符號“//”表示注釋，也表示旁白（特別是數學討論的擴展和解釋），用以標識將要介紹的內容和希望讀者能夠自然而然想到的問題。從這點出發，本書盡可能保持（單詞、句子和段落）簡潔。
但這是一本數學書。我們試圖用正確的數學語言和思想擴展學生的直覺。儘管到第3章才開始給出詳細的證明，但已經解釋和保持了數學證明的基本特性，重複應用即可證明算法的正確性。本書的一個目標是提供一個計算機科學中標準問題有效求解算法的工具箱，另一個目標是介紹一些計算機科學中不可或缺的概念。
致謝
感謝朋友和家人在本書的長期策劃過程中給予的支持和鼓勵，特別感謝Eleanor、Glenys、Janice和Flora。感謝Brock大學數學系和計算機科學系20多年來一直堅持本項目形式和內容方面的“課堂測試”實踐。最後感謝Eric R.Muler率先在Brock大學開設了相關的原型課程。
大多數章節都通過例子逐步說明要介紹的內容。第1章介紹整本書的內容框架：如何設計標準計算問題的求解算法？對每一個合適的輸入，如何知道算法是否工作正確？算法需要多長時間生成輸出？
從我們的觀點來看，教學本身遠比內容展示要多得多，我們已經將本書作為“目標導向的學生實踐能力設計”教程。人類習慣於給信息添加標籤，表示從實踐中獲取的重要性。書中用這些實踐作為正面引導。
本書旨在促使學生努力思考，培養他們的問題求解能力，並結合理論和應用，認識抽象的重要性。書中通過一些難忘的具有激勵作用的例子來吸引學生，這些例子中的新想法、新方法和思考深度會給學生帶來挑戰。希望本書比其他離散數學教材更吸引學生。
書中介紹了很多計算機科學文化以及計算機科學家分享的常識（不包括程序設計）。許多是計算機科學家都知道的基礎問題的基本求解方法：如何查找特定目標清單；如何按自然數序列對列表排序以方便查找；如何生成所有物件、子集或以某種次序排列的序列；如何遍歷圖的所有頂點；特別是，如何比較算法的效率並驗證算法的正確性。但介紹的數學知識與計算機科學相關。
本書最突出的特點是非形式化描述和交互特性。算法的詳細遍歷過程貫穿始終。為了將材料介紹得生動一些，會插入一些挑戰性的問題和評論。我們試圖像在課堂上一樣與讀者交流，這與其他傳統的數學教材有所區別。書中用符號“//”表示注釋，也表示旁白（特別是數學討論的擴展和解釋），用以標識將要介紹的內容和希望讀者能夠自然而然想到的問題。從這點出發，本書盡可能保持（單詞、句子和段落）簡潔。
但這是一本數學書。我們試圖用正確的數學語言和思想擴展學生的直覺。儘管到第3章才開始給出詳細的證明，但已經解釋和保持了數學證明的基本特性，重複應用即可證明算法的正確性。本書的一個目標是提供一個計算機科學中標準問題有效求解算法的工具箱，另一個目標是介紹一些計算機科學中不可或缺的概念。
致謝
感謝朋友和家人在本書的長期策劃過程中給予的支持和鼓勵，特別感謝Eleanor、Glenys、Janice和Flora。感謝Brock大學數學系和計算機科學系20多年來一直堅持本項目形式和內容方面的“課堂測試”實踐。最後感謝Eric R.Muler率先在Brock大學開設了相關的原型課程。
目次
出版者的話
譯者序
前言
第1章 算法、數和機器1
1.1 什麼是算法3
1.2 整數算法和複雜度6
1.2.1 素數測試7
1.2.2 實數8
1.2.3 改進素數測試算法9
1.2.4 素數分解11
1.2.5 對數12
1.2.6 最大公約數14
1.3 數的機器表示16
1.3.1 近似誤差17
1.3.2 二進位、八進制和十六進位19
1.4 數值求解25
1.4.1 牛頓的平方根求解方法26
1.4.2 二分法27
習題30
第2章 集合、序列和計數32
2.1 樸素集合論32
2.1.1 可惡的圖書管理員34
2.1.2 集合運算和基數34
2.1.3 鴿巢原理36
2.2 序列37
2.2.1 子集的特徵序列38
2.3 計數39
2.3.1 n元集合上的k元序列數40
2.3.2 n元集合的子集數40
2.3.3 n元集合上的k元排列數40
2.3.4 n的階乘41
2.3.5 n元集合上的k元子集數42
2.3.6 Pascal三角形44
2.3.7 非公式的計數策略46
2.4 無限序列和複雜度函數49
2.4.1 漢諾塔51
2.4.2 差的複雜度函數53
習題54
第3章 布林運算式、邏輯和證明56
3.1 貪心算法和餅乾選擇問題56
3.1.1 貪心算法56
3.2 布林運算式和真值表60
3.2.1 否操作數60
3.2.2 合取操作數60
3.2.3 析取操作數60
3.2.4 條件操作數62
3.2.5 雙向條件操作數63
3.3 謂詞和量詞64
3.4 有效推理65
3.5 證明實例68
3.5.1 直接證明70
3.5.2 間接證明71
3.5.3 Cantor的對角線方法73
3.6 數學歸納法75
3.6.1 強歸納法82
3.7 第1章的待證明結論83
3.7.1 RPM的正確性證明83
3.7.2 切蛋糕難題的正確性證明85
3.7.3 舍九法的正確性證明87
3.7.4 GCD歐幾裡得算法的正確性證明88
3.8 第2章的待證明結論90
習題92
第4章 查找和排序95
4.1 查找95
4.1.1 查找任意列表95
4.1.2 查找有序列表96
4.2 分支圖100
4.2.1 二分查找的第二個版本101
4.3 排序106
4.3.1 選擇排序106
4.3.2 交換排序108
4.4 至少有n!個葉子的二叉樹113
4.5 劃分排序120
4.6 排序算法比較129
4.6.1 時間和運算的計數130
習題131
第5章 圖和樹134
5.1 引言134
5.1.1 度137
5.1.2 歐拉圖138
5.1.3 哈密頓圖139
5.2 路徑、回路和多邊形139
5.2.1 路徑確定的子圖140
5.3 樹142
5.3.1 遍歷142
5.4 邊帶權圖153
5.4.1 最短路徑157
5.5 有向圖157
5.5.1 有向路徑158
5.5.2 距離函數159
5.5.3 Dijkstra算法159
5.5.4 Floyd-Warshall算法165
習題169
第6章 關係：特別是(整數)序列上的關係171
6.1 關係和表示171
6.1.1 矩陣表示171
6.1.2 有向圖表示172
6.1.3 關係的性質172
6.2 等價關係173
6.2.1 等價關係的矩陣和有向圖表示174
6.3 序關係176
6.3.1 偏序的矩陣和有向圖表示177
6.3.2 極小元和極大元178
6.4 有限序列上的關係180
6.4.1 支配180
6.4.2 字典序182
6.5 無限序列上的關係184
6.5.1 漸近支配和大O標記法185
6.5.2 漸近等價和大Θ表示189
6.5.3 漸近排序191
6.5.4 強漸近支配和小o表示192
習題194
第7章 序列和級數197
7.1 遞推方程實例197
7.2 求解一階線性遞推方程202
7.3 Fibonacci序列206
7.3.1 Fibonacci序列算法208
7.3.2 黃金比例210
7.3.3 Fibonacci序列和黃金比例210
7.3.4 Fibonacci序列的階213
7.3.5 GCD的歐幾裡得算法的複雜度213
7.4 求解二階線性遞推方程216
7.5 無限級數221
7.5.1 芝諾悖論221
7.5.2 序列和級數收斂的形式化定義222
習題227
第8章 生成序列和子集231
8.1 以字典序生成序列232
8.2 生成{1..n}的所有k元序列234
8.2.1 平均情況複雜度235
8.3 生成{1..n}的昇冪序列子集237
8.4 按字典序生成全排列244
8.4.1 按字典序生成{1..n}的所有k元排列251
習題254
第9章 離散概率和平均情況複雜度260
9.1 概率模型260
9.1.1 採樣空間260
9.1.2 概率函數261
9.1.3 特例：等概率輸出262
9.2 條件概率264
9.2.1 組合事件265
9.2.2 條件概率265
9.2.3 獨立事件266
9.2.4 互斥事件266
9.3 隨機變數和期望值270
9.3.1 期望頻率270
9.3.2 期望值271
9.3.3 概率分佈272
9.4 標準分佈及其期望值273
9.4.1 均勻分佈273
9.4.2 二項分佈276
9.4.3 幾何分佈277
9.5 條件期望值279
9.5.1 條件期望282
9.6 平均情況複雜度284
9.6.1 將期望應用於線性查找284
9.6.2 將期望應用於QuickSort285
習題289
第10章 圖靈機293
10.1 什麼是算法293
10.1.1 Church-Turing理論299
10.1.2 通用圖靈機：計算模型299
10.1.3 停機問題300
習題302
索引304
譯者序
前言
第1章 算法、數和機器1
1.1 什麼是算法3
1.2 整數算法和複雜度6
1.2.1 素數測試7
1.2.2 實數8
1.2.3 改進素數測試算法9
1.2.4 素數分解11
1.2.5 對數12
1.2.6 最大公約數14
1.3 數的機器表示16
1.3.1 近似誤差17
1.3.2 二進位、八進制和十六進位19
1.4 數值求解25
1.4.1 牛頓的平方根求解方法26
1.4.2 二分法27
習題30
第2章 集合、序列和計數32
2.1 樸素集合論32
2.1.1 可惡的圖書管理員34
2.1.2 集合運算和基數34
2.1.3 鴿巢原理36
2.2 序列37
2.2.1 子集的特徵序列38
2.3 計數39
2.3.1 n元集合上的k元序列數40
2.3.2 n元集合的子集數40
2.3.3 n元集合上的k元排列數40
2.3.4 n的階乘41
2.3.5 n元集合上的k元子集數42
2.3.6 Pascal三角形44
2.3.7 非公式的計數策略46
2.4 無限序列和複雜度函數49
2.4.1 漢諾塔51
2.4.2 差的複雜度函數53
習題54
第3章 布林運算式、邏輯和證明56
3.1 貪心算法和餅乾選擇問題56
3.1.1 貪心算法56
3.2 布林運算式和真值表60
3.2.1 否操作數60
3.2.2 合取操作數60
3.2.3 析取操作數60
3.2.4 條件操作數62
3.2.5 雙向條件操作數63
3.3 謂詞和量詞64
3.4 有效推理65
3.5 證明實例68
3.5.1 直接證明70
3.5.2 間接證明71
3.5.3 Cantor的對角線方法73
3.6 數學歸納法75
3.6.1 強歸納法82
3.7 第1章的待證明結論83
3.7.1 RPM的正確性證明83
3.7.2 切蛋糕難題的正確性證明85
3.7.3 舍九法的正確性證明87
3.7.4 GCD歐幾裡得算法的正確性證明88
3.8 第2章的待證明結論90
習題92
第4章 查找和排序95
4.1 查找95
4.1.1 查找任意列表95
4.1.2 查找有序列表96
4.2 分支圖100
4.2.1 二分查找的第二個版本101
4.3 排序106
4.3.1 選擇排序106
4.3.2 交換排序108
4.4 至少有n!個葉子的二叉樹113
4.5 劃分排序120
4.6 排序算法比較129
4.6.1 時間和運算的計數130
習題131
第5章 圖和樹134
5.1 引言134
5.1.1 度137
5.1.2 歐拉圖138
5.1.3 哈密頓圖139
5.2 路徑、回路和多邊形139
5.2.1 路徑確定的子圖140
5.3 樹142
5.3.1 遍歷142
5.4 邊帶權圖153
5.4.1 最短路徑157
5.5 有向圖157
5.5.1 有向路徑158
5.5.2 距離函數159
5.5.3 Dijkstra算法159
5.5.4 Floyd-Warshall算法165
習題169
第6章 關係：特別是(整數)序列上的關係171
6.1 關係和表示171
6.1.1 矩陣表示171
6.1.2 有向圖表示172
6.1.3 關係的性質172
6.2 等價關係173
6.2.1 等價關係的矩陣和有向圖表示174
6.3 序關係176
6.3.1 偏序的矩陣和有向圖表示177
6.3.2 極小元和極大元178
6.4 有限序列上的關係180
6.4.1 支配180
6.4.2 字典序182
6.5 無限序列上的關係184
6.5.1 漸近支配和大O標記法185
6.5.2 漸近等價和大Θ表示189
6.5.3 漸近排序191
6.5.4 強漸近支配和小o表示192
習題194
第7章 序列和級數197
7.1 遞推方程實例197
7.2 求解一階線性遞推方程202
7.3 Fibonacci序列206
7.3.1 Fibonacci序列算法208
7.3.2 黃金比例210
7.3.3 Fibonacci序列和黃金比例210
7.3.4 Fibonacci序列的階213
7.3.5 GCD的歐幾裡得算法的複雜度213
7.4 求解二階線性遞推方程216
7.5 無限級數221
7.5.1 芝諾悖論221
7.5.2 序列和級數收斂的形式化定義222
習題227
第8章 生成序列和子集231
8.1 以字典序生成序列232
8.2 生成{1..n}的所有k元序列234
8.2.1 平均情況複雜度235
8.3 生成{1..n}的昇冪序列子集237
8.4 按字典序生成全排列244
8.4.1 按字典序生成{1..n}的所有k元排列251
習題254
第9章 離散概率和平均情況複雜度260
9.1 概率模型260
9.1.1 採樣空間260
9.1.2 概率函數261
9.1.3 特例：等概率輸出262
9.2 條件概率264
9.2.1 組合事件265
9.2.2 條件概率265
9.2.3 獨立事件266
9.2.4 互斥事件266
9.3 隨機變數和期望值270
9.3.1 期望頻率270
9.3.2 期望值271
9.3.3 概率分佈272
9.4 標準分佈及其期望值273
9.4.1 均勻分佈273
9.4.2 二項分佈276
9.4.3 幾何分佈277
9.5 條件期望值279
9.5.1 條件期望282
9.6 平均情況複雜度284
9.6.1 將期望應用於線性查找284
9.6.2 將期望應用於QuickSort285
習題289
第10章 圖靈機293
10.1 什麼是算法293
10.1.1 Church-Turing理論299
10.1.2 通用圖靈機：計算模型299
10.1.3 停機問題300
習題302
索引304
購物須知
大陸出版品因裝訂品質及貨運條件與台灣出版品落差甚大，除封面破損、內頁脫落等較嚴重的狀態，其餘商品將正常出貨。
特別提醒：部分書籍附贈之內容(如音頻mp3或影片dvd等)已無實體光碟提供，需以QR CODE 連結至當地網站註冊“並通過驗證程序”，方可下載使用。
無現貨庫存之簡體書，將向海外調貨：
海外有庫存之書籍，等候約45個工作天;
海外無庫存之書籍，平均作業時間約60個工作天，然不保證確定可調到貨，尚請見諒。
為了保護您的權益，「三民網路書店」提供會員七日商品鑑賞期(收到商品為起始日)。
若要辦理退貨，請在商品鑑賞期內寄回，且商品必須是全新狀態與完整包裝(商品、附件、發票、隨貨贈品等)否則恕不接受退貨。