![[美] 多西《离散数学》](http://oss.shudanhao.com/caiji/chazidian/2023/33549.jpg)
[美] 多西《离散数学》
书刊介绍
内容简介
本书是一本优秀的离散数学入门教材，主要内容包括集合、关系、函数、编码理论、图、树、匹配、网络流、计数技术、递推关系与生成函数、组合电路和有限状态机等。
本书充分考虑到了初学者的需要，叙述浅显易懂，内容、例题、习题都作了精心的挑选和组织，讲解细致，循序渐进。
本书可作为高等院校计算机专业或其他相关专业的离散数学教材或教学参考书，也可作为自学者的参考书。
作品目录
离散数学纪年表
译者序
译者简介
前言
致学生
离散数学纪年表
第1章 组合问题与组合技术引论 1
1.1 工程完成时间的问题 1
1.1.1 问题 1
1.1.2 分析 2
1.1.3 关键路径分析 3
1.1.4 一个建筑的例子 4
1.2 匹配问题 7
1.2.1 问题 7
1.2.2 分析 7
1.2.3 排列 8
1.2.4 航空公司问题解决方案的实用性 9
1.3 背包问题 11
1.3.1 问题 11
1.3.2 分析 12
1.3.3 回顾实验问题 14
1.4 算法及其效率 15
1.4.1 算法的比较 15
1.4.2 多项式求值 16
1.4.3 子集生成算法 19
1.4.4 冒泡排序 21
历史注记 24
补充习题 25
计算机题 27
推荐读物 27
第2章 集合、关系和函数 28
2.1 集合运算 28
2.2 等价关系 32
*2.3 偏序关系 37
2.3.1 偏序和全序 37
2.3.2 哈斯图 40
2.3.3 拓扑排序 41
2.4 函数 44
2.5 数学归纳法 52
2.6 应用 58
历史注记 65
补充习题 66
计算机题 69
推荐读物 69
第3章 编码理论 70
3.1 同余 70
3.2 欧几里得算法 75
3.2.1 最大公约数 75
3.2.2 欧几里得算法 75
3.2.3 欧几里得算法的效率 77
3.2.4 扩展的欧几里得算法 77
3.3 RSA方法 79
3.3.1 指数取模 80
3.3.2 RSA方法的解密 83
3.3.3 RSA方法的可行性 85
3.4 检错码和纠错码 86
3.5 矩阵码 93
3.5.1 矩阵码 93
3.5.2 编码的校验矩阵 94
3.6 单纠错矩阵码 99
3.6.1 校验矩阵行译码法 100
3.6.2 汉明码 101
历史注记 105
补充习题 106
计算机题 109
推荐读物 109
第4章 图 110
4.1 图及其表示 110
4.1.1 图的概念和表示 110
4.1.2 图的其他表示 112
4.1.3 同构 113
4.2 通路和回路 117
4.2.1 多重图、通路和回路 117
4.2.2 欧拉回路和欧拉通路 119
4.2.3 哈密顿回路和哈密顿通路 122
4.3 最短通路和距离 129
4.3.1 广度优先搜索算法 129
4.3.2 带权图 131
4.3.3 通路的数目 134
4.4 图着色 138
4.5 有向图和有向多重图 144
4.5.1 有向图 145
4.5.2 有向图的表示 145
4.5.3 有向多重图 146
4.5.4 有向欧拉回路和有向欧拉通路 148
4.5.5 有向哈密顿回路和有向哈密顿
通路 149
历史注记 155
补充习题 156
计算机题 160
推荐读物 161
第5章 树 162
5.1 树的性质 162
5.2 生成树 168
5.2.1 生成树 169
5.2.2 广度优先搜索法 169
5.2.3 最小生成树和最大生成树 171
5.2.4 普里姆算法的证明 174
5.3 深度优先搜索 179
5.3.1 深度优先搜索法 179
5.3.2 回溯 183
5.4 根树 188
5.5 二叉树和遍历 193
5.5.1 表达式树 193
5.5.2 前序遍历 195
5.5.3 后序遍历 197
5.5.4 中序遍历 199
5.6 最优二叉树和二叉搜索树 202
5.6.1 最优二叉树 202
5.6.2 二叉搜索树 208
历史注记 215
补充习题 216
计算机题 219
推荐读物 220
第6章 匹配 221
6.1 相异代表系 221
6.1.1 相异代表系 221
6.1.2 霍尔定理 222
6.2 图中的匹配 225
6.2.1 匹配 225
6.2.2 偶图的矩阵 227
6.2.3 覆盖 227
6.3 匹配算法 231
6.3.1 独立集算法的应用示例 231
6.3.2 将算法运用于最大独立集 233
6.3.3 独立集算法 234
6.3.4 课程分配 235
6.4 算法的应用 239
6.4.1 柯尼希定理 240
6.4.2 霍尔定理的证明 241
6.4.3 瓶颈问题 242
6.5 匈牙利方法 245
6.5.1 匈牙利算法 245
6.5.2 匈牙利算法的证明 247
6.5.3 不是方阵的矩阵 248
6.5.4 最大和独立集 249
历史注记 250
补充习题 251
计算机题 252
推荐读物 253
第7章 网络流 254
7.1 流和割 254
7.2 流增广算法 261
7.3 最大流最小割定理 269
7.4 流和匹配 274
历史注记 280
补充习题 280
计算机题 283
推荐读物 283
第8章 计数技术 284
8.1 帕斯卡三角形和二项式定理 284
8.2 3个基本原理 287
8.3 排列和组合 293
8.4 允许重复的排列和组合 297
8.5 概率 302
*8.6 容斥原理 306
*8.7 排列和r组合的生成 315
8.7.1 排列的词典序枚举 315
8.7.2 r组合的词典序枚举 317
历史注记 320
补充习题 321
计算机题 323
推荐读物 324
第9章 递推关系与生成函数 325
9.1 递推关系 325
9.2 迭代法 333
9.3 常系数线性差分方程 341
9.3.1 一阶常系数线性差分方程 341
9.3.2 二阶线性齐次差分方程 344
*9.4 用递推关系分析算法的效率 350
9.4.1 顺序查找算法和冒泡排序算法
的效率… 350
9.4.2 分治算法的效率 352
9.4.3 排序算法的效率 357
9.5 用生成函数计数 359
9.5.1 生成函数 360
9.5.2 形式幂级数 361
9.6 生成函数的代数 365
历史注记 372
补充习题 373
计算机题 375
推荐读物 376
第10章 组合电路和有限状态机 377
10.1 逻辑门 377
10.2 构造组合电路 383
10.3 卡诺图 388
10.4 有限状态机 397
10.4.1 奇偶校验机 398
10.4.2 有限状态机 399
10.4.3 带输出的有限状态机 400
历史注记 404
补充习题 405
计算机题 407
推荐读物 408
附录A 逻辑和证明简介 409
附录B 矩阵 425
附录C 本书中的算法 432
参考文献 436
奇数号习题答案 440
相关推荐
-
罗宾汉-文学名著英汉双语读物-第一级
罗宾汉-文学名著英汉双语读物-第一级 本书特色 十三世纪的英格兰，王位争夺、权贵倾轧，百姓生活苦不堪言。年轻气盛的罗宾汉与人打赌而误杀了国王的鹿，并因为自卫而射...
-
问题出在4年级
问题出在4年级 本书特色 进入四年级，孩子的成长发生了很大的变化。在这个时期父母和孩子对亲子关系、家庭教育等很多方面的看法存在一定的差异，亲子之间的理解沟通存在...
-
概率统计及其应用
概率统计及其应用 内容简介 为使初学者尽快熟悉这种独特的思维方法，很好地掌握概率论与数理统计的基本概念、基本理论、基本运算以及处理随机数据的基本思想和方法，培养...
-
萧萐父选集
萧萐父选集 本书特色 萧萐父先生是著名的哲学工作者，长期从事中国哲学的教学与研究。《萧萐父选集》选录了他一生中较有影响的文章若干，辑为一册，涉及儒释道研究的中国...
-
聚合物结构与性能-(结构篇)
聚合物结构与性能-(结构篇) 本书特色 马德柱编著的《聚合物结构与性能》为国家精品课程配套教材。全书由二十章组成，分为结构篇和性能篇两册。结构篇包括聚合...
-
一年级(下册)-人教课标版-整合集训口算速算天天练-培优版
一年级(下册)-人教课标版-整合集训口算速算天天练-培优版 本书特色 口算方法指导，速算方法指导不是本书的重点，但绝对是本书的闪光点。一年级(下册)-人教课标版...
-
一年级数学卷-陪孩子读到三年级
一年级数学卷-陪孩子读到三年级 本书特色 一年级的孩子要经历许许多多的人生“**次”，父母陪伴孩子学习，可以减少孩子的孤独、恐慌和无助，在这一阶段，父母引导孩子...
-
公共关系学
公共关系学 内容简介 高等职业教育人才培养创新教材出版工程·高职高专公共选修课教材系列。本书可作为各高职高专院校公共选修课教材，也可供有关部门管理人员以及企业管...
-
萱草.郁金香.百合-自然博物馆-彩图版
萱草.郁金香.百合-自然博物馆-彩图版 本书特色 《自然博物馆：萱草·郁金香·百合（彩图版）》从青少年的阅读心理特点出发，对图书结构进行了精心设计。全书采用板块...
-
西方传统.经典与解释 德语美学文选(上下册)
西方传统.经典与解释德语美学文选(上下册) 内容简介 本书由刘小枫选编，2006年重新编排出版。书中选编了近四百年来的德意志美学的著名论作，包括了鲍姆伽通、席勒...
-
李成章|黄玉民《数学分析(上下)(第二版)》
本书是南开大学数学系老师在多年教学经验的基础上编写而成的，是一本大学数学系基础课程的教材。.本书分上、下两册，介绍了数学分
-
电影性教育读本
《电影性教育读本》内容简介：80部人们耳熟能详的经典电影，性教育专家从性教育的角度对其情节进行分析与解读，编写成方便教师进行
-
我心光明：《道德经》与心理健康
《我心光明：《道德经》与心理健康》内容简介：在本书中，作者认为，道法自然、不折腾才是好的养生策略。养生贵在养心，心静如水才
-
普通化学
普通化学 本书特色 全书共11章，内容包括原子结构与元素周期律、化学键与分子结构、化学热力学基础、反应速率及化学平衡、水溶液化学、配位化合物及配位平衡、电化学、...
-
英语学习漫谈-像婴儿一样学英语
英语学习漫谈-像婴儿一样学英语 本书特色 语言幽默生动，睿智脱俗轻松突破口语障碍，单词记忆障碍，语法障碍快速提高英语水平，扫清传统学习方式的困扰发现学习乐趣，找...
-
海底的秘密
无字图画书的独到之处在于它既激活读者的想象力，也挑战读者的理解力。在阅读大卫·威斯纳的无字图画书《海底的秘密》时，每个读者的阐释能力也同样会受到考验。一个充满好...
-
中学生英语作文3日通
中学生英语作文3日通 内容简介 英语作文有无规律可循呢？能否在短期之内提高自己的写作水平呢？这是广大中学生热切关注的问题。为此，我们特编写了这本《中学生·英语作...
-
小狗的小房子:无障碍精读版
小狗的小房子:无障碍精读版 本书特色 在中国的童话界，孙幼军是年轻作家的一个典范。孙幼军非常自然娴熟地使用讲童话故事的高招，轻快的几笔就勾勒出了童话人物的形象，...
-
政治学概论-(行政管理专业)(专科)(2008年版)(附政治学概论自学考试大纲)
政治学概论-(行政管理专业)(专科)(2008年版)(附政治学概论自学考试大纲) 内容简介 《政治学概论》作为我国高等教育组成部分的自学考试，其职责就是在高等教...
-
土木工程概论-第3版
土木工程概论-第3版 本书特色 本书内容涵盖了大土木工程的主要研究领域，力求构建大土木的知识体系，尽可能多地反映现代土木工程的新技术、新方法、新工艺和新成就，突...
