离散数学及其在计算机科学中的应用 英文版PDF|Epub|txt|kindle电子书版本网盘下载

离散数学及其在计算机科学中的应用 英文版PDF格式电子书版下载

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

第1章 计数31

1.1 基本计数31

求和原理31

抽象化33

连续整数求和33

乘积原理34

二元素子集36

重要概念、公式和定理37

习题38

1.2 序列、排列和子集40

使用求和与乘积原理40

序列和函数42

双射原理44

集合的k元素排列45

集合子集的计数46

重要概念、公式和定理48

习题50

1.3 二项式系数52

帕斯卡三角形52

使用求和原理的一个证明54

二项式定理56

标记与三项式系数58

重要概念、公式和定理59

习题60

1.4 关系62

什么是关系62

函数作为关系63

关系的性质63

等价关系66

偏序和全序69

重要概念、公式和定理71

习题72

1.5 在计数中运用等价关系73

对称原理73

等价关系75

商原理76

等价类计数76

多重集78

书柜安排问题80

n元集合的k元多重集的数目81

使用商原理解释商数82

重要概念、公式和定理83

习题84

第2章 密码学与数论89

2.1 密码学和模算法89

密码学导论89

私钥密码学90

公钥密码体制93

模n算术95

使用模n加法的密码学98

使用模n乘法的密码学99

重要概念、公式和定理101

习题102

2.2 逆元和最大公因子105

方程的解和模n的逆元105

模n的逆元106

转化模方程为普通方程109

最大公因子110

欧几里得除法定理111

欧几里得最大公因子算法114

广义最大公因子算法115

计算逆元118

重要概念、公式和定理119

习题120

2.3 RSA密码体制123

模n的指数运算123

指数运算的规则123

费马小定理126

RSA密码体制127

中国剩余定理131

重要概念、公式和定理132

习题134

2.4 RSA加密体制的细节136

模n指数运算的实用性136

使用RSA算法会花费多长时间139

因式分解有多难140

找大素数140

重要概念、公式和定理143

习题144

第3章 关于逻辑与证明的思考147

3.1 等价和蕴含147

语句的等价147

真值表150

德摩根律153

蕴含155

当且仅当156

重要概念、公式和定理159

习题161

3.2 变元和量词163

变元和论域163

量词164

量词化的标准记号166

关于变元的语句168

重写语句以包含更大的论域168

证明量词语句的真假169

量词语句的否定170

隐式量词化173

量词语句的证明174

重要概念、公式和定理175

习题177

3.3 推理179

直接推理（演绎推理）和证明179

直接证明的推理规则181

推理的逆否（对换）规则183

反证法185

重要概念、公式和定理188

习题189

第4章 归纳法、递归和递推式191

4.1 数学归纳法191

最小反例191

数学归纳法原理195

强归纳法199

归纳法的一般形式201

从递归视角看归纳法203

结构归纳法206

重要概念、公式和定理208

习题210

4.2 递归、递推式和归纳法213

递归213

一阶线性递推的实例215

遍历递推式217

等比数列218

一阶线性递推式221

重要概念、公式和定理225

习题227

4.3 递推式解的增长率228

分治算法228

递归树231

三种不同的行为239

重要概念、公式和定理240

习题242

4.4 主定理244

主定理及其证明244

求解更一般的递推式247

扩展主定理248

重要概念、公式和定理250

习题251

4.5 更一般的递推式252

递推不等式252

不等式主定理253

归纳法的一个窍门255

归纳证明的更多窍门257

处理nc以外的函数260

重要概念、公式和定理262

习题263

4.6 递推式和选择265

选择的理念265

一种递归选择算法266

中位数未知情况下的选择267

一种从中间一半中查找元素的算法269

对修改后的选择算法的分析272

不均匀划分274

重要概念、公式和定理276

习题277

第5章 概率279

5.1 概率导论279

为什么要学习概率279

概率计算举例282

互补概率283

概率和散列284

均匀概率分布286

重要概念、公式和定理289

习题290

5.2 并集和交集292

并集事件的概率292

概率的容斥原理295

计数的容斥原理301

重要概念、公式和定理303

习题304

5.3 条件概率和独立性306

条件概率306

贝叶斯法则310

独立性310

独立连续过程312

树形图314

素数测试318

重要概念、公式和定理319

习题320

5.4 随机变量322

什么是随机变量322

二项式概率323

体验生成函数325

期望值326

期望值的加法和数值乘法329

指示器随机变量332

第一次成功的尝试次数334

重要概念、公式和定理336

习题337

5.5 散列中的概率计算340

每个位置元素的期望个数340

空位置的期望个数341

冲突的期望个数342

元素在哈希表一个位置的最大期望个数345

重要概念、公式和定理350

习题351

5.6 条件期望、递归和算法355

什么时候运算时间不止取决于输入的大小355

条件期望值357

随机算法359

重温选择算法361

快速排序363

更详细的随机选取的分析366

重要概念、公式和定理369

习题370

5.7 概率分布和方差373

随机变量的分布373

方差376

重要概念、公式和定理384

习题385

第6章 图论389

6.1 图389

顶点的度393

连通性395

环397

树398

树的其他性质398

重要概念、公式和定理401

习题403

6.2 生成树和有根树405

生成树405

宽度优先搜索407

有根树412

重要概念、公式和定理416

习题417

6.3 欧拉图和哈密顿图419

欧拉回路与路径419

寻找欧拉回路424

哈密顿路径和环425

P完全问题431

证明问题是NP完全的433

重要概念、公式和定理436

习题437

6.4 匹配定理440

匹配的概念440

让匹配更大444

二部图的匹配447

二部图增广道路的搜索447

增广覆盖算法450

高效的算法456

重要概念、公式和定理457

习题458

6.5 染色和平面性460

染色的概念460

区间图463

平面性465

平面化的面467

五色定理471

重要概念、公式和定理474

习题475

附录A 更一般的主定理的推导479

更一般的递推式479

对一般n的递推式481

去掉下取整和上取整482

更强版本主定理中的下取整和上取整483

定理的证明483

重要概念、公式和定理487

习题488

附录B 节选习题答案与提示491

参考文献507