《計算機科學中的數學：信息與智慧型時代的必修課》是電子工業出版社出版的圖書，作者是埃里克·雷曼、F.湯姆森·萊頓、艾伯特·R.邁耶。
基本介紹
- 書名：計算機科學中的數學：信息與智慧型時代的必修課
- 作者：【美】埃里克•雷曼【美】F.湯姆森•萊頓【美】艾伯特•R.邁耶
- 譯者：唐李洋等
- ISBN：978-7-121-35533-2
- 頁數：832
- 定價：168
- 出版社：電子工業出版社
- 出版時間：2018-04
- 裝幀：平裝
- 開本：16
內容提要,目錄,作者簡介,
內容提要
《計算機科學中的數學：信息與智慧型時代的必修課》是麻省理工學院計算機科學與工程專業本科生的初等離散數學課程講義。本書涵蓋了國外計算機科學專業涉及的基礎數學知識，內容涉及形式邏輯符號、數學證明、歸納、集合與關係、圖論基礎、排列與組合、計數原理、離散機率、遞歸等，特彆強調數學定義、證明及其套用方法。
《計算機科學中的數學：信息與智慧型時代的必修課》適用於計算機相關專業學生及從業人員的數學入門，亦可作為統計、機器學習、數據挖掘等課程的初學資源。
目錄
第I部分 數學證明
引言 3
0.1 參考文獻 4
第1章 什麼是證明 5
1.1 命題 5
1.2 謂詞 8
1.3 公理化方法 8
1.4 我們的公理 9
1.4.1 邏輯推理 9
1.4.2 證明的模式 10
1.5 證明蘊涵 10
1.5.1 方法#1 11
1.5.2 方法#2：證明逆反命題 12
1.6 證明“若且唯若” 13
1.6.1 方法#1：證明兩個語句相互蘊涵 13
1.6.2 方法#2：構建iff鏈 13
1.7 案例證明法 14
1.8 反證法 15
1.9 數學證明的優秀實踐 16
1.10 參考文獻 18
1.1節習題 18
1.5節習題 21
1.7節習題 21
1.8節習題 23
第2章 良序原理 26
2.1 良序證明 26
2.2 良序證明模板 27
2.2.1 整數求和 27
2.3 質因數分解 29
2.4 良序集合 29
2.4.1 不一樣的良序集合（選學） 30
2.2節習題 31
2.4節習題 38
第3章 邏輯公式 40
3.1 命題的命題 41
3.1.1 NOT，AND和OR 41
3.1.2 若且唯若 42
3.1.3 IMPLIES 42
3.2 電腦程式的命題邏輯 44
3.2.1 真值表計算 45
3.2.2 符號表示 46
3.3 等價性和有效性 47
3.3.1 蘊涵和逆否 47
3.3.2 永真性和可滿足性 48
3.4 命題代數 49
3.4.1 命題範式 49
3.4.2 等價性證明 50
3.5 SAT問題 53
3.6 謂詞公式 54
3.6.1 量詞 54
3.6.2 混合量詞 55
3.6.3 量詞的順序 56
3.6.4 變數與域 56
3.6.5 否定量詞 57
3.6.6 謂詞公式的永真性 57
3.7 參考文獻 58
3.1節習題 59
3.2節習題 61
3.3節習題 65
3.4節習題 68
3.5節習題 69
3.6節習題 71
第4章 數學數據類型 79
4.1 集合 79
4.1.1 常用集合 80
4.1.2 集合的比較和組合 80
4.1.3 冪集 81
4.1.4 集合構造器標記 82
4.1.5 證明集合相等 82
4.2 序列 83
4.3 函式 84
4.3.1 域和像 84
4.3.2 函式複合 86
4.4 二元關係 86
4.4.1 關係圖 87
4.4.2 關係的像 89
4.5 有限基數 90
4.5.1 有限集有多少個子集 91
4.1節習題 92
4.2節習題 96
4.4節習題 97
4.5節習題 105
第5章 歸納法 107
5.1 一般歸納法 107
5.1.1 一般歸納法的規則 108
5.1.2 舉例說明 108
5.1.3 歸納法證明的模板 109
5.1.4 一般歸納法的簡潔寫法 110
5.1.5 更複雜的例子 111
5.1.6 錯誤的歸納證明 113
5.2 強歸納法 115
5.2.1 強歸納法的規則 115
5.2.2 斐波那契數列 116
5.2.3 質數的乘積 117
5.2.4 找零問題 118
5.2.5 堆盒子遊戲 119
5.3 強歸納法、一般歸納法和良序法的比較 120
5.1節習題 121
5.2節習題 131
第6章 狀態機 136
6.1 狀態和轉移 136
6.2 不變性原理 137
6.2.1 沿對角線移動的機器人 137
6.2.2 不變性原理的定義 139
6.2.3 示例：《虎膽龍威》 141
6.3 偏序正確性和終止性 143
6.3.1 快速求冪 143
6.3.2 派生變數 145
6.3.3 基於良序集合的終止性（選學） 146
6.3.4 東南方向跳躍的機器人（選學） 146
6.4 穩定的婚姻 147
6.4.1 配對儀式 148
6.4.2 我們結婚吧 150
6.4.3 他們從此幸福地生活在一起 150
6.4.4 竟然是男性…… 151
6.4.5 套用 152
6.3節習題 153
6.4節習題 165
第7章 遞歸數據類型 172
7.1 遞歸定義和結構歸納法 172
7.1.1 結構歸納法 174
7.2 匹配帶括弧的字元串 175
7.3 非負整數上的遞歸函式 179
7.3.1 N上的一些標準遞歸函式 179
7.3.2 不規範的函式定義 179
7.4 算術表達式 181
7.4.1 Aexp的替換和求值 181
7.5 計算機科學中的歸納 185
7.1節習題 185
7.2節習題 193
7.3節習題 201
7.4節習題 202
第8章 無限集 206
8.1 無限基數集 206
8.1.1 不同之處 209
8.1.2 可數集 209
8.1.3 冪集的勢嚴格大於原集合 211
8.1.4 對角線證明 213
8.2 停止問題 214
8.3 集合邏輯 217
8.3.1 羅素悖論 217
8.3.2 集合的ZFC公理系統 218
8.3.3 避免羅素悖論 220
8.4 這些真的有效嗎 220
8.4.1 計算機科學中的無窮大 221
8.1節習題 221
8.2節習題 228
8.3節習題 233
8.4節習題 236
第Ⅱ部分 結構
引言 241
第9章 數論 242
9.1 整除 242
9.1.1 整除的性質 243
9.1.2 不可整除問題 244
9.1.3 虎膽龍威 245
9.2 最大公約數 247
9.2.1 歐幾里得算法 247
9.2.2 粉碎機 249
9.2.3 水壺問題的通解 251
9.2.4 最大公約數的性質 252
9.3 質數的奧秘 253
9.4 算術基本定理 255
9.4.1 唯一分解定理的證明 256
9.5 阿蘭·圖靈 257
9.5.1 圖靈編碼（1.0版） 258
9.5.2 破解圖靈編碼（1.0版） 260
9.6 模運算 260
9.7 余運算 262
9.7.1 環Z_n 264
9.8 圖靈編碼（2.0版） 265
9.9 倒數與約去 266
9.9.1 互質 267
9.9.2 約去 268
9.9.3 解密（2.0版） 268
9.9.4 破解圖靈編碼（2.0版） 269
9.9.5 圖靈後記 269
9.10 歐拉定理 271
9.10.1 計算歐拉ϕ函式 273
9.11 RSA公鑰加密 274
9.12 SAT與RSA有什麼關係 276
9.13 參考文獻 277
9.1節習題 277
9.2節習題 278
9.3節習題 285
9.4節習題 285
9.6節習題 287
9.7節習題 288
9.8節習題 293
9.9節習題 293
9.10節習題 295
9.11節習題 303
第10章 有向圖和偏序 309
10.1 頂點的度 311
10.2 路和通路 311
10.2.1 查找通路 313
10.3 鄰接矩陣 314
10.3.1 最短路徑 315
10.4 路關係 316
10.4.1 複合關係 316
10.5 有向無環圖&調度 317
10.5.1 調度 318
10.5.2 並行任務調度 320
10.5.3 Dilworth引理 322
10.6 偏序 323
10.6.1 DAG中路關係的性質 323
10.6.2 嚴格偏序 324
10.6.3 弱偏序 325
10.7 用集合包含表示偏序 326
10.8 線性序 327
10.9 乘積序 327
10.10 等價關係 328
10.10.1 等價類 328
10.11 關係性質的總結 329
10.1節習題 330
10.2節習題 331
10.3節習題 334
10.4節習題 335
10.5節習題 338
10.6節習題 344
10.7節習題 347
10.8節習題 349
10.9節習題 352
10.10節習題 354
第11章 通信網路 357
11.1 路由 357
11.1.1 完全二叉樹 357
11.1.2 路由問題 358
11.2 路由的評價指標 358
11.2.1 網路直徑 358
11.2.2 交換機的數量 359
11.2.3 網路時延 359
11.2.4 擁塞 360
11.3 網路設計 361
11.3.1 二維陣列 361
11.3.2 蝶形網路 362
11.3.3 Benes ̌網路 363
11.2節習題 368
11.3節習題 368
第12章 簡單圖 373
12.1 頂點鄰接和度 373
12.2 美國異性伴侶統計 375
12.2.1 握手引理 376
12.3 一些常見的圖 377
12.4 同構 378
12.5 二分圖與匹配 380
12.5.1 二分匹配問題 380
12.5.2 匹配條件 381
12.6 著色 384
12.6.1 一個考試安排問題 384
12.6.2 一些著色邊界 386
12.6.3 為什麼著色 387
12.7 簡單路 388
12.7.1 簡單圖中的路、通路和圈 388
12.7.2 圈作為子圖 389
12.8 連通性 390
12.8.1 連通分量 390
12.8.2 奇數長度的圈和2-著色性 391
12.8.3 k–連通圖 392
12.8.4 連通圖的最小邊數 393
12.9 森林和樹 394
12.9.1 葉子、父母和孩子 394
12.9.2 性質 395
12.9.3 生成樹 397
12.9.4 最小生成樹 397
12.10 參考文獻 401
12.2節習題 402
12.4節習題 403
12.5節習題 406
12.6節習題 411
12.7節習題 418
12.8節習題 420
12.9節習題 424
第13章 平面圖 431
13.1 在平面上繪製圖形 431
13.2 平面圖的定義 433
13.2.1 面 434
13.2.2 平面嵌入的遞歸定義 436
13.2.3 這個定義行嗎 438
13.2.4 外表面在哪裡呢 438
13.3 歐拉公式 439
13.4 平面圖中邊的數量限制 440
13.5 返回到K_5和K_3,3 441
13.6 平面圖的著色 442
13.7 多面體的分類 443
13.8 平面圖的另一個特徵 445
13.2節習題 446
13.8節習題 447
第Ⅲ部分 計數
引言 455
第14章 求和與漸近性 457
14.1 年金的值 458
14.1.1 錢未來的價值 458
14.1.2 擾動法 459
14.1.3 年金價值的閉型 460
14.1.4 無限長的等比數列 460
14.1.5 示例 461
14.1.6 等比數列求和的變化 462
14.2 冪和 463
14.3 估算求和式子 465
14.4 超出邊界 468
14.4.1 問題陳述 468
14.4.2 調和數 471
14.4.3 漸近等式 473
14.5 乘積 474
14.5.1 斯特林公式 475
14.6 雙倍的麻煩 477
14.7 漸近符號 479
14.7.1 小o 479
14.7.2 大O 479
14.7.3 θ 481
14.7.4 漸近符號的誤區 482
14.7.5 Ω（選學） 484
14.1節習題 484
14.2節習題 486
14.3節習題 486
14.4節習題 488
14.7節習題 490
第15章 基數法則 499
15.1 通過其他計數來計算當前計數 499
15.1.1 雙射規則 499
15.2 序列計數 500
15.2.1 乘積法則 501
15.2.2 n-元素集合的子集 501
15.2.3 加和法則 502
15.2.4 密碼計數 502
15.3 廣義乘積法則 503
15.3.1 有缺陷的美元鈔票 504
15.3.2 一個象棋問題 505
15.3.3 排列 505
15.4 除法法則 506
15.4.1 另一個象棋問題 506
15.4.2 圓桌騎士 507
15.5 子集計數 508
15.5.1 子集法則 509
15.5.2 比特序列 510
15.6 重複序列 510
15.6.1 子集序列 510
15.6.2 Bookkeeper法則 511
15.6.3 二項式定理 512
15.7 計數練習：撲克手牌 513
15.7.1 四條相同點數的手牌 514
15.7.2 葫蘆手牌 514
15.7.3 兩個對子的手牌 515
15.7.4 花色齊全的手牌 517
15.8 鴿子洞原理 517
15.8.1 頭上的頭髮 518
15.8.2 具有相同和的子集 519
15.8.3 魔術 521
15.8.4 秘密 521
15.8.5 真正的秘密 523
15.8.6 如果是4張牌呢 524
15.9 容斥原理 525
15.9.1 兩個集合的並集 525
15.9.2 三個集合的並集 525
15.9.3 42序列、04序列或60序列 526
15.9.4 n個集合的並集 527
15.9.5 計算歐拉函式 529
15.10 組合證明 530
15.10.1 帕斯卡三角恆等式 530
15.10.2 給出組合證明 531
15.10.3 有趣的組合證明 532
15.11 參考文獻 533
15.2節習題 534
15.4節習題 537
15.5節習題 538
15.6節習題 544
15.7節習題 548
15.8節習題 550
15.9節習題 554
15.10節習題 561
第16章 母函式 566
16.1 無窮級數 566
16.1.1 不收斂性 567
16.2 使用母函式計數 568
16.2.1 蘋果和香蕉 568
16.2.2 母函式的積 569
16.2.3 卷積法則 570
16.2.4 利用卷積法則數甜甜圈 570
16.2.5 卷積法則中的二項式定理 571
16.2.6 一個荒唐的計數問題 572
16.3 部分分式 573
16.3.1 帶有重根的部分分式 575
16.4 求解線性遞推 575
16.4.1 斐波那契數的母函式 575
16.4.2 漢諾塔 576
16.4.3 求解一般線性遞推 580
16.5 形式冪級數 580
16.5.1 發散母函式 580
16.5.2 冪級數環 581
16.6 參考文獻 583
16.1節習題 583
16.2節習題 583
16.3節習題 586
16.4節習題 588
16.5節習題 595
第Ⅳ部分 機率論
引言 599
第17章 事件和機率空間 601
17.1 做個交易吧 601
17.1.1 理清問題 601
17.2 四步法 602
17.2.1 步驟一：找到樣本空間 602
17.2.2 步驟二：確定目標事件 605
17.2.3 步驟三：確定結果的機率 606
17.2.4 步驟四：計算事件的機率 608
17.2.5 蒙特霍爾問題的另一種解釋 609
17.3 奇怪的骰子 609
17.3.1 骰子A vs. 骰子B 610
17.3.2 骰子A vs. 骰子C 612
17.3.3 骰子B vs. 骰子C 612
17.3.4 擲兩次 613
17.4 生日原理 615
17.4.1 匹配機率的確切公式 615
17.5 集合論和機率 616
17.5.1 機率空間 616
17.5.2 集合論的機率法則 617
17.5.3 均勻機率空間 618
17.5.4 無窮機率空間 619
17.6 參考文獻 620
17.2節習題 620
17.5節習題 623
第18章 條件機率 626
18.1 蒙特霍爾困惑 626
18.1.1 帷幕之後 627
18.2 定義和標記 627
18.2.1 問題所在 628
18.3 條件機率四步法 629
18.4 為什麼樹狀圖有效 630
18.4.1 大小為k的子集的機率 631
18.4.2 醫學檢測 632
18.4.3 四步分析法 633
18.4.4 固有頻率 634
18.4.5 後驗機率 634
18.4.6 機率的哲學 635
18.5 全機率定理 637
18.5.1 以單一事件為條件 637
18.6 辛普森悖論 638
18.7 獨立性 640
18.7.1 另一個公式 640
18.7.2 獨立性是一種假設 641
18.8 相互獨立性 641
18.8.1 DNA檢測 642
18.8.2 兩兩獨立 643
18.9 機率vs. 置信度 645
18.9.1 肺結核測試 645
18.9.2 可能性修正 646
18.9.3 很可能正確的事實 648
18.9.4 極端事件 648
18.9.5 下一次拋擲的置信度 649
18.4節習題 650
18.5節習題 650
18.6節習題 660
18.7節習題 661
18.8節習題 663
18.9節習題 666
第19章 隨機變數 667
19.1 隨機變數示例 667
19.1.1 指示器隨機變數 668
19.1.2 隨機變數和事件 668
19.2 獨立性 669
19.3 分布函式 670
19.3.1 伯努利分布 672
19.3.2 均勻分布 672
19.3.3 數字遊戲 673
19.3.4 二項分布 675
19.4 期望 677
19.4.1 均勻隨機變數的期望值 677
19.4.2 隨機變數的倒數的期望 678
19.4.3 指示器隨機變數的期望值 678
19.4.4 期望的另一種定義 678
19.4.5 條件期望 679
19.4.6 平均故障時間 680
19.4.7 賭博遊戲的預期收益 682
19.5 期望的線性性質 686
19.5.1 兩枚骰子的期望 687
19.5.2 指示器隨機變數的和 687
19.5.3 二項分布的期望 688
19.5.4 贈券收集問題 689
19.5.5 無限和 691
19.5.6 賭博悖論 691
19.5.7 悖論的解答 692
19.5.8 乘積的期望 693
19.2節習題 694
19.3節習題 696
19.4節習題 698
19.5節習題 702
第20章 離差 712
20.1 馬爾可夫定理 712
20.1.1 套用馬爾可夫定理 714
20.1.2 有界變數的馬爾可夫定理 714
20.2 切比雪夫定理 715
20.2.1 兩個賭博遊戲的方差 716
20.2.2 標準差 717
20.3 方差的性質 718
20.3.1 方差公式 719
20.3.2 故障時間的方差 719
20.3.3 常數的處理 720
20.3.4 和的方差 721
20.3.5 生日匹配 722
20.4 隨機抽樣估計 723
20.4.1 選民投票 723
20.4.2 兩兩獨立採樣 725
20.5 估計的置信度 726
20.6 隨機變數的和 728
20.6.1 引例 728
20.6.2 切諾夫界 729
20.6.3 二項式尾的切諾夫界 729
20.6.4 彩票遊戲的切諾夫界 730
20.6.5 隨機負載均衡 731
20.6.6 切諾夫界的證明 732
20.6.7 邊界的比較 734
20.6.8 墨菲定律 735
20.7 大期望 736
20.7.1 重複你自己 736
20.1節習題 737
20.2節習題 738
20.3節習題 739
20.5節習題 746
20.6節習題 750
20.7節習題 753
第21章 隨機遊走 755
21.1 賭徒破產 755
21.1.1 避免破產的機率 757
21.1.2 獲勝機率遞推 758
21.1.3 有偏情形的簡單解釋 759
21.1.4 步長多長 761
21.1.5 贏了就退出 762
21.2 圖的隨機遊走 763
21.2.1 網頁排名初探 764
21.2.2 網頁圖的隨機遊走 765
21.2.3 平穩分布與網頁排名 766
21.1節習題 768
21.2節習題 769
第Ⅴ部分 遞推
引言 779
第22章 遞推 780
22.1 漢諾塔 780
22.1.1 上界陷阱 781
22.1.2 擴充-化簡法 781
22.2 歸併排序 783
22.2.1 尋找遞推 784
22.2.2 求解遞推 784
22.3 線性遞推 786
22.3.1 爬樓梯 786
22.3.2 求解齊次線性遞推 789
22.3.3 求解一般線性遞推 790
22.3.4 如何猜測特解 792
22.4 分治遞推 793
22.4.1 Akra-Bazzi公式 794
22.4.2 兩個技術問題 795
22.4.3 Akra-Bazzi定理 796
22.4.4 主定理 797
22.5 進一步探索 797
22.4節習題 799
參考文獻 802
符號表 806
作者簡介
唐李洋
女，博士，畢業於合肥工業大學管理科學與工程系。現就職於中國電子科技集團公司第三十八研究所，數據挖掘與大數據分析研究經驗頗豐，在相關領域重要國際期刊及會議發表論文數篇。
