计算机科学中的数学 信息与智能时代的必修课【2025|PDF下载-Epub版本|mobi电子书|kindle百度云盘下载】

计算机科学中的数学 信息与智能时代的必修课PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第Ⅰ部分 数学证明3

引言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 方法#111

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和OR41

3.1.2 当且仅当42

3.1.3 IMPLIES42

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

引言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 环Zn264

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 Bene？网络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 返回到K5和K3,3441

13.6 平面图的着色442

13.7 多面体的分类443

13.8 平面图的另一个特征445

13.2 节习题446

13.8 节习题447

第Ⅲ部分 计数455

引言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 小o479

14.7.2 大O479

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

引言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.骰子B610

17.3.2 骰子A vs.骰子C612

17.3.3 骰子B vs.骰子C612

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

引言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