新書推薦：
《
深度学习详解
》
售價：HK$
114.8
《
李白传（20世纪文史学家李长之经典传记）
》
售價：HK$
45.8
《
津轻：日本无赖派文学代表太宰治自传性随笔集
》
售價：HK$
66.7
《
河流之齿
》
售價：HK$
59.8
《
新经济史革命：计量学派与新制度学派
》
售價：HK$
89.7
《
盗墓笔记之秦岭神树4
》
售價：HK$
57.3
《
战胜人格障碍
》
售價：HK$
66.7
《
逃不开的科技创新战争
》
售價：HK$
103.3
|
| 內容簡介： |
|
本书选取了计算机科学专业的学生需要掌握的离散数学基础知识和核心理论进行系统的介绍，以利用计算机解决问题为主要目标，将理论与实践结合起来，使学生充分认识抽象的重要性。全书选材适当、结构清晰、叙述简明、推理严谨，适合作为高校计算机专业离散数学课程的教材，也适合从事计算机软件开发工作的技术人员学习。
|
| 目錄：
|
出版者的话
译者序
前言
第1章 算法、数和机器1
1.1 什么是算法3
1.2 整数算法和复杂度6
1.2.1 素数测试7
1.2.2 实数8
1.2.3 改进素数测试算法9
1.2.4 素数分解11
1.2.5 对数12
1.2.6 最大公约数14
1.3 数的机器表示16
1.3.1 近似误差17
1.3.2 二进制、八进制和十六进制19
1.4 数值求解25
1.4.1 牛顿的平方根求解方法26
1.4.2 二分法27
习题30
第2章 集合、序列和计数32
2.1 朴素集合论32
2.1.1 可恶的图书管理员34
2.1.2 集合运算和基数34
2.1.3 鸽巢原理36
2.2 序列37
2.2.1 子集的特征序列38
2.3 计数39
2.3.1 n元集合上的k元序列数40
2.3.2 n元集合的子集数40
2.3.3 n元集合上的k元排列数40
2.3.4 n的阶乘41
2.3.5 n元集合上的k元子集数42
2.3.6 Pascal三角形44
2.3.7 非公式的计数策略46
2.4 无限序列和复杂度函数49
2.4.1 汉诺塔51
2.4.2 差的复杂度函数53
习题54
第3章 布尔表达式、逻辑和证明56
3.1 贪心算法和饼干选择问题56
3.1.1 贪心算法56
3.2 布尔表达式和真值表60
3.2.1 否算子60
3.2.2 合取算子60
3.2.3 析取算子60
3.2.4 条件算子62
3.2.5 双向条件算子63
3.3 谓词和量词64
3.4 有效推理65
3.5 证明实例68
3.5.1 直接证明70
3.5.2 间接证明71
3.5.3 Cantor的对角线方法73
3.6 数学归纳法75
3.6.1 强归纳法82
3.7 第1章的待证明结论83
3.7.1 RPM的正确性证明83
3.7.2 切蛋糕难题的正确性证明85
3.7.3 舍九法的正确性证明87
3.7.4 GCD欧几里得算法的正确性证明88
3.8 第2章的待证明结论90
习题92
第4章 查找和排序95
4.1 查找95
4.1.1 查找任意列表95
4.1.2 查找有序列表96
4.2 分支图100
4.2.1 二分查找的第二个版本101
4.3 排序106
4.3.1 选择排序106
4.3.2 交换排序108
4.4 至少有n!个叶子的二叉树113
4.5 划分排序120
4.6 排序算法比较129
4.6.1 时间和运算的计数130
习题131
第5章 图和树134
5.1 引言134
5.1.1 度137
5.1.2 欧拉图138
5.1.3 哈密顿图139
5.2 路径、回路和多边形139
5.2.1 路径确定的子图140
5.3 树142
5.3.1 遍历142
5.4 边带权图153
5.4.1 最短路径157
5.5 有向图157
5.5.1 有向路径158
5.5.2 距离函数159
5.5.3 Dijkstra算法159
5.5.4 Floyd-Warshall算法165
习题169
第6章 关系：特别是整数序列上的关系171
6.1 关系和表示171
6.1.1 矩阵表示171
6.1.2 有向图表示172
6.1.3 关系的性质172
6.2 等价关系173
6.2.1 等价关系的矩阵和有向图表示174
6.3 序关系176
6.3.1 偏序的矩阵和有向图表示177
6.3.2 极小元和极大元178
6.4 有限序列上的关系180
6.4.1 支配180
6.4.2 字典序182
6.5 无限序列上的关系184
6.5.1 渐近支配和大O表示法185
6.5.2 渐近等价和大Θ表示189
6.5.3 渐近排序191
6.5.4 强渐近支配和小o表示192
习题194
第7章 序列和级数197
7.1 递推方程实例197
7.2 求解一阶线性递推方程202
7.3 Fibonacci序列206
7.3.1 Fibonacci序列算法208
7.3.2 黄金比例210
7.3.3 Fibonacci序列和黄金比例210
7.3.4 Fibonacci序列的阶213
7.3.5 GCD的欧几里得算法的复杂度213
7.4 求解二阶线性递推方程216
7.5 无限级数221
7.5.1 芝诺悖论221
7.5.2 序列和级数收敛的形式化定义222
习题227
第8章 生成序列和子集231
8.1 以字典序生成序列232
8.2 生成{1..n}的所有k元序列234
8.2.1 平均情况复杂度235
8.3 生成{1..n}的升序序列子集237
8.4 按字典序生成全排列244
8.4.1 按字典序生成{1..n}的所有k元排列251
习题254
第9章 离散概率和平均情况复杂度260
9.1 概率模型260
9.1.1 采样空间260
9.1.2 概率函数261
9.1.3 特例：等概率输出262
9.2 条件概率264
9.2.1 组合事件265
9.2.2 条件概率265
9.2.3 独立事件266
9.2.4 互斥事件266
9.3 随机变量和期望值270
9.3.1 期望频率270
9.3.2 期望值271
9.3.3 概率分布272
9.4 标准分布及其期望值273
9.4.1 均匀分布273
9.4.2 二项分布276
9.4.3 几何分布277
9.5 条件期望值279
9.5.1 条件期望282
9.6 平均情况复杂度284
9.6.1 将期望应用于线性查找284
9.6.2 将期望应用于QuickSort285
习题289
第10章 图灵机293
10.1 什么是算法293
10.1.1 Church-Turing理论299
10.1.2 通用图灵机：计算模型299
10.1.3 停机问题300
习题302
索引304
|
| 內容試閱：
|
本书面向计算机科学相关专业学生，以学生可接受的形式和提高编程竞争力的方式介绍离散数学基础，内容主要聚焦在与计算机科学直接相关的主题上。
大多数章节都通过例子逐步说明要介绍的内容。第1章介绍整本书的内容框架：如何设计标准计算问题的求解算法？对每一个合适的输入，如何知道算法是否工作正确？算法需要多长时间生成输出？
从我们的观点来看，教学本身远比内容展示要多得多，我们已经将本书作为“目标导向的学生实践能力设计”教程。人类习惯于给信息添加标签，表示从实践中获取的重要性。书中用这些实践作为正面引导。
本书旨在促使学生努力思考，培养他们的问题求解能力，并结合理论和应用，认识抽象的重要性。书中通过一些难忘的具有激励作用的例子来吸引学生，这些例子中的新想法、新方法和思考深度会给学生带来挑战。希望本书比其他离散数学教材更吸引学生。
书中介绍了很多计算机科学文化以及计算机科学家分享的常识（不包括程序设计）。许多是计算机科学家都知道的基础问题的基本求解方法：如何查找特定目标列表；如何按自然数序列对列表排序以方便查找；如何生成所有对象、子集或以某种次序排列的序列；如何遍历图的所有顶点；特别是，如何比较算法的效率并验证算法的正确性。但介绍的数学知识与计算机科学相关。
本书最突出的特点是非形式化描述和交互特性。算法的详细遍历过程贯穿始终。为了将材料介绍得生动一些，会插入一些挑战性的问题和评论。我们试图像在课堂上一样与读者交流，这与其他传统的数学教材有所区别。书中用符号“”表示注释，也表示旁白（特别是数学讨论的扩展和解释），用以标识将要介绍的内容和希望读者能够自然而然想到的问题。从这点出发，本书尽可能保持（单词、句子和段落）简洁。
但这是一本数学书。我们试图用正确的数学语言和思想扩展学生的直觉。尽管到第3章才开始给出详细的证明，但已经解释和保持了数学证明的基本特性，重复应用即可证明算法的正确性。本书的一个目标是提供一个计算机科学中标准问题有效求解算法的工具箱，另一个目标是介绍一些计算机科学中不可或缺的概念。
致谢
感谢朋友和家人在本书的长期策划过程中给予的支持和鼓励，特别感谢Eleanor、Glenys、Janice和Flora。感谢Brock大学数学系和计算机科学系20多年来一直坚持本项目形式和内容方面的“课堂测试”实践。最后感谢Eric R.Muler率先在Brock大学开设了相关的原型课程。
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
