离散数学及其应用PDF|Epub|txt|kindle电子书版本网盘下载

离散数学及其应用PDF格式电子书版下载

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

专家指导委员会1

译者序1

前言1

第1章 基础：逻辑、集合和函数1

1.1 逻辑1

1.1.1 引言1

1.1.2 命题1

出版者的话1

1.1.3 翻译语言的句子6

1.1.4 布尔检索7

1.1.5 逻辑运算和位运算7

练习9

1.2.2 逻辑等价15

1.2 命题等价15

1.2.1 引言15

练习19

1.3 谓词和量词22

1.3.1 引言22

1.3.2 量词23

1.3.3 翻译语句为逻辑表达式26

1.3.4 选自Lewis Carroll的例子(选读)27

1.3.5 绑定变量28

1.3.6 否定31

练习31

1.4 集合39

1.4.1 引言39

1.4.3 笛卡儿积43

1.4.2 幂集合43

练习45

1.5 集合运算47

1.5.1 引言47

1.5.2 集合相等49

1.5.3 扩展的并集和交集51

1.5.4 集合的计算机表示52

练习53

1.6 函数57

1.6.1 引言57

1.6.2 一对一函数和映上函数59

1.6.3 反函数和函数组合61

1.6.4 函数的图像63

1.6.5 几个重要的函数64

练习65

1.7 序列和求和70

1.7.1 引言70

1.7.2 序列70

1.7.3 特殊的整数序列71

1.7.4 求和72

1.7.5 基数(选读)75

练习76

1.8 函数增长80

1.8.1 引言80

1.8.2 大O符号80

1.8.3 函数组合的增长84

1.8.4 大Ω和θ符号86

练习88

关键术语和结果92

复习题94

补充练习95

计算机题目98

计算和研究98

写作题目98

第2章 基础：算法、整数和矩阵100

2.1 算法100

2.1.1 引言100

2.1.2 搜索算法102

练习104

2.2 算法的复杂性106

2.2.1 引言106

练习109

2.3.2 除法112

2.3.1 引言112

2.3 整数和除法112

2.3.3 素数113

2.3.4 除法算法115

2.3.5 最大公约数和最小公倍数115

2.3.6 模运算117

2.3.7 同余应用118

2.3.8 密码学120

练习121

2.4 整数和算法124

2.4.1 引言124

2.4.2 欧几里德算法125

2.4.3 整数表示127

2.4.4 整数运算算法128

练习131

2.5 数论应用134

2.5.1 引言134

2.5.2 若干有用的结果134

2.5.3 线性同余136

2.5.4 中国余数定理137

2.5.5 大整数的计算机算术运算138

2.5.6 伪素数140

2.5.7 公钥密码学141

2.5.8 RSA加密141

2.5.9 RSA解密142

2.5.10 用RSA作公钥系统143

练习143

2.6.1 引言146

2.6 矩阵146

2.6.2 矩阵运算147

2.6.3 矩阵乘法运算148

2.6.4 矩阵的转置和幂149

2.6.5 0-1矩阵150

练习153

关键术语和结果156

复习题158

补充练习159

计算机题目161

计算和研究161

写作题目162

第3章 数学推理163

3.1 证明方法163

3.1.1 引言163

3.1.2 推理规则164

3.1.3 谬误167

3.1.4 带量词命题的推理规则168

3.1.5 证明定理的方法169

3.1.6 定理与量词172

3.1.7 停机问题174

3.1.8 关于证明的一些评注175

练习175

3.2 数学归纳法181

3.2.1 引言181

3.2.2 良序性181

3.2.3 数学归纳法181

3.2.4 数学归纳法证明的例子183

3.2.5 数学归纳法的第二原理189

练习191

3.3 递归定义195

3.3.1 引言195

3.3.2 递归地定义函数196

3.3.3 递归地定义集合199

练习201

3.4 递归算法208

3.4.1 引言208

3.4.2 递归与迭代209

练习211

3.5 程序正确性211

3.5.1 引言212

3.5.2 程序验证213

3.5.4 条件语句214

3.5.3 推理规则214

3.5.5 循环不变量215

练习217

关键术语和结果219

复习题219

补充练习221

计算机题目224

计算和研究225

写作题目225

第4章 计数227

4.1 计数的基础227

4.1.1 引言227

4.1.2 基本的计数原则227

4.1.3 容斥原理232

4.1.4 树图233

练习234

4.2 鸽巢原理238

4.2.1 引言238

4.2.2 推广的鸽巢原理239

4.2.3 巧妙使用鸽巢原理240

练习242

4.3 排列与组合244

4.3.1 引言244

4.3.2 排列244

4.3.3 组合245

4.3.4 二项式系数246

4.3.5 二项式定理248

练习250

4.4.1 引言254

4.4 离散概率254

4.4.2 有限概率255

4.4.3 事件组合的概率256

4.4.4 概述的推理257

练习258

4.5 概率论260

4.5.1 引言260

4.5.2 概率赋值260

4.5.3 事件的组合262

4.5.4 条件概率262

4.5.5 独立性263

4.5.6 伯努利实验与二项式分布264

4.5.7 随机变量266

4.5.8 期望值267

4.5.9 独立随机变量269

4.5.10 方差270

4.5.11 切比雪夫不等式272

4.5.12 平均状态下的计算复杂性273

练习274

4.6 一般性的排列和组合277

4.6.1 引言277

4.6.2 有重复的排列277

4.6.3 有重复的组合278

4.6.4 具有不可区别物体的集合的排列281

4.6.5 把物体放入盒子282

练习282

4.7.1 引言283

4.7.2 生成排列286

4.7 生成排列和组合286

4.7.3 生成组合288

练习289

关键术语和结果290

复习题292

补充练习294

计算机题目298

计算和研究298

写作题目299

第五章 高级计数技术300

5.1 递推关系300

5.1.1 引言300

5.1.2 递推关系300

5.1.3 用递推关系构造模型301

练习306

5.2 求解递推关系312

5.2.1 引言312

5.2.2 求解常系数线性齐次递推关系313

5.2.3 常系数线性非齐次的递推关系317

练习318

练习321

5.3 分而治之关系325

5.3.1 引言325

5.3.2 分而治之关系326

练习329

5.4 生成函数330

5.4.1 引言330

5.4.2 关于幂级数的有用的事实331

5.4.3 计数问题与生成函数335

5.4.4 使用生成函数求解递推关系338

5.4.5 使用生成函数证明恒等式340

练习340

5.5.1 引言347

5.5.2 容斥原理347

5.5 容斥347

练习352

5.6 容斥原理的应用353

5.6.1 引言353

5.6.2 容斥原理的另一种形式354

5.6.3 伊拉脱森筛355

5.6.4 映上函数的个数356

5.6.5 错位排列357

练习359

关键术语和结果360

复习题361

补充练习362

计算机题目365

计算和研究366

写作题目366

第6章 关系368

6.1 关系及其性质368

6.1.1 引言368

6.1.2 函数作为关系369

6.1.3 集合上的关系369

6.1.4 关系的性质370

6.1.5 关系的组合372

练习374

6.2.3 数据库和关系377

6.2.2 n元关系377

6.2.1 引言377

6.2 n元关系及其应用377

6.3 关系的表示382

6.3.1 引言382

6.3.2 用矩阵表示关系382

6.3.3 用图表示关系384

练习386

6.4 关系的闭包387

6.4.1 引言387

6.4.2 闭包388

6.4.3 有向图的路径389

6.4.4 传递闭包390

6.4.5 沃舍尔算法393

练习396

6.5 等价关系398

6.5.1 引言398

6.5.2 等价关系398

6.5.3 等价类399

6.5.4 等价类与划分400

练习402

6.6 偏序405

6.6.1 引言405

6.6.2 字典顺序406

6.6.3 哈斯图408

6.6.4 极大元素与极小元素409

6.6.5 格411

6.6.6 拓扑排序412

练习414

关键术语和结果419

复习题420

补充练习422

计算机题目426

计算和研究426

写作题目427

第7章 图428

7.1 图的介绍428

7.1.1 图的种类428

7.1.2 图模型431

练习432

7.2.1 引言434

7.2.2 基本术语434

7.2 图的术语434

7.2.3 一些特殊的简单图436

7.2.4 偶图437

7.2.5 特殊类型的图的一些应用438

7.2.6 从旧图到新图440

练习441

7.3 图的表示和图的同构443

7.3.1 引言443

7.3.2 图的表示443

7.3.3 相邻矩阵444

7.3.4 关联矩阵445

7.3.5 图的同构446

练习449

7.4.2 通路454

7.4.1 引言454

7.4 连通性454

7.4.3 无向图连通性455

7.4.4 有向图中的连通性456

7.4.5 通路与同构456

7.4.6 统计顶点之间的通路457

练习458

7.5 欧拉通路与哈密顿通路461

7.5.1 引言461

7.5.2 欧拉回路和欧拉通路的充要条件462

7.5.3 哈密顿通路和回路465

练习468

7.6 最短通路问题473

7.6.1 引言473

7.6.2 一个最短通路算法475

7.6.3 旅行推销员问题479

练习480

7.7 平面性图484

7.7.1 引言484

7.7.2 欧拉公式485

7.7.3 库拉图斯基定理488

练习489

7.8 图着色491

7.8.1 引言491

7.8.2 图着色的应用495

练习496

关键术语和结果499

复习题501

补充练习502

计算和研究507

计算机题目507

写作题目508

第8章 树510

8.1 介绍树510

8.1.1 树作为模型514

8.1.2 树的性质516

练习518

8.2 树的应用521

8.2.1 引言521

8.2.2 二叉搜索树521

8.2.3 决策树524

8.2.4 前辍码524

练习525

8.3.1 引言526

8.3 树的遍历526

8.3.2 通用地址系统527

8.3.3 遍历算法527

8.3.4 中缀、前缀和后缀记法533

练习536

8.4 树与排序538

8.4.1 引言538

8.4.2 排序的复杂性539

8.4.3 冒泡排序539

8.4.4 归并排序541

练习544

8.5 生成树545

8.5.1 引言545

8.5.2 一些构造生成树的算法547

8.5.3 回溯549

练习551

8.6 最小生成树554

8.6.1 引言554

8.6.2 最小生成树算法554

练习558

关键术语和结果560

复习题561

补充练习562

计算机题目566

计算和研究566

写作题目567

9.1.1 引言568

9.1 布尔函数568

第9章 布尔代数568

9.1.2 布尔表达式和布尔函数569

9.1.3 布尔代数中的恒等式570

9.1.4 对偶性571

9.1.5 布尔代数和抽象定义572

练习573

9.2 布尔函数的表示574

9.2.1 积之和展开式574

9.2.2 函数完备性575

练习576

9.3 逻辑门电路577

9.3.1 引言577

9.3.2 门的组合578

9.3.3 电路的例子579

9.3.4 加法器581

9.4 电路的极小化583

9.4.1 引言583

练习583

9.4.2 卡诺图584

9.4.3 无需在意条件588

9.4.4 奎因-莫可拉斯基方法588

练习592

关键术语和结果594

复习题595

补充练习596

计算机题目598

计算和研究598

写作题目598

10.1.1 引言600

第10章 计算模型600

10.1 语言和文法600

10.1.2 短语结构文法601

10.1.3 短语结构文法的类型604

10.1.4 派生树605

10.1.5 巴科斯-诺尔范式605

练习607

10.2 带输出的有限状态机609

10.2.1 引言609

10.2.2 带输出的有限状态机610

10.3 不带输出的有限状态机612

练习614

10.3.1 引言616

10.3.2 串的集合616

10.3.3 有限状态自动机617

练习621

10.4 语言的识别623

10.4.1 引言623

10.4.2 正则集合623

10.4.3 克莱因定理624

10.4.4 正则集合和正则文法627

10.4.5 一个不能由有限状态自动机识别的语言629

10.4.6 一些更强大的机器630

练习631

10.5 图灵机632

10.5.1 引言632

10.5.2 图灵机的定义633

10.5.3 用图灵机识别集合634

10.5.4 用图灵机计算函数636

10.5.5 不同类型的图灵机637

10.5.6 丘奇-图灵论题637

练习637

关键术语和结果639

复习题640

补充练习641

计算机题目644

计算和研究644

写作题目644

附录A 指数函数和对数函数646

附录B 伪代码649

奇数练习题答案654

推荐读物790

参考文献794