离散数学及其在计算机科学中的应用 英文版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