本书由计算机和数学领域的三位教授联合撰写，旨在满足计算机专业对离散数学课程的需求。针对这门课程的困境初入学的本科生不理解为何要学习高深的数学，以及授课教师难以向毫无编程经验的学生讲授繁杂的算法程序本书明确了为何学和有何用，打破了传统的课程顺序和教学方法，不仅清晰呈现了计算机专业学生必需的数学知识，而且通过实践和应用激发学生对后续课程的学习兴趣。
主要内容：涵盖计数、密码编码学与数论、逻辑与证明、归纳、递归、概率以及图论，推导严谨、代码清晰、练习丰富。
教学模式：提倡参与式教学，鼓励学生加入小组讨论，主动探索，通过提问、讨论和报告来掌握概念，找到解决方案。
课程建议：建议学生掌握微积分知识，了解递归。
动机与目标
很多大学都开设离散数学课程。上该课程的学生来自多个专业，其中多的是来自计算机科学专业的学生。在国家科学基金会一的支持下，作为达特茅斯（Dartmouth）学院跨学科数学项目的一部分，我们提出开设一门离散数学课程来满足计算机科学专业学生的需求。在分析想让计算机科学专业的学生了解哪些离散数学主题，以及为什么想让他们了解这些主题时，我们得到两个结论。
，我们认为一些主题对于计算机科学专业很重要，但是没有被充分地纳入传统的离散数学课程中。这些主题包括递归树和解决递推关系的主定理，计算平均运行时间和分析随机算法的概率理论，以及强归纳法和结构归纳法。
第二，我们认为对于计算机科学专业学生很重要的每个离散数学主题，在计算机科学里都有一个很有启发性的主题，上述门或者第二门计算机科学入门课程的学生可以理解这些主题。我们感觉这样安排就能回答在应用数学课程中学生经常会问的问题：为什么我们必须学习这些？因此，我们决定写一本针对计算机科学专业学生的教科书，目标是为计算机科学专业学生提供必要的数学基础，并且通过学生在计算机科学学习的开始阶段就能够理解的计算机科学问题来启发他们学习这本教科书。
一基金资助号为DUE-9552462。
二我们的大多数学生已经学习过微积分。在一些地方我们会使用初级的导数，并且在概率部分的选修小节中，我们使用自然对数、指数函数和初级的幂级数。如果忽略少数使用导数的证明和问题，以及概率部分的选修小节，教师可以不涉及微积分。
在许多高校的计算机科学系，离散数学是学生的专业必修课之一，甚至是门计算机科学课程的先修课。在这种情况下，教师面临一种困境讲授纯数学的概念，很少或者完全没有显式的计算机应用，或者讲授计算机科学的例子来营造一种针对计算机科学专业学生的语境。对于种讲课方式，学生会抱怨在学习门计算机科学课程之前被迫学习太多不相干的数学知识。对于第二种讲课方式，教师（通常是数学家）要尝试给可能从来没有写过程序的学生解释相当高级的计算机科学主题，比如散列、二叉树和递归程序等。即使在好的情况下，这种方式也明显降低了数学的深度。基于我们的分析，产生了一种不同的讲课方式，即开设一门学生稍后学习的课程。尽管我们没有明确假定学生已经学过微积分，但是假定学生了解并且能够熟练使用求和符号、对数和指数函数。因此，熟悉微积分知识是很有帮助的二。这意味着学生要在计算机科学的入门课中见过递归程序之后再学习这门课。这门课好和数据结构课程同时学习或者在其之后学习，不过我们会通过例子解释所使用的数据结构。因此，数据结构课程不是这门课的先导课程。
我们觉得这样安排离散数学课程有很多优势，例如：
?学生已经有了较为深入的问题解决、算法和编程的经验。
?学生已经学习或者准备学习一些重要的计算机科学概念，比如散列、递归、排序和搜索，以及基本的数据结构。
?学生对计算机科学有足够的了解，已经知道一些启发性例子，或者这些例子对于他们而言足够简单易懂。例如：
a散列可以用于启发概率的学习。a分析递归程序，比如归并和快速排序，可以启发学习递推关系和相应的解决方法。
a分析在一个寻找线性表中小元素的程序中，我们期望多久找到一个新的小值，可以启发学习期望的线性性质和调和数。
a二叉树可以用于教授结构递归法，也可以作为图的特例启发树的学习。
根据我们自己的授课经验，离散数学课程是算法课的先导课程，学生经常在结束离散数学课程不久后就开始学习算法。这样，他们会发现自己可以直接使用刚学过的离散数学知识。
教学理念
这本教科书是以教学活动为驱动，以练习的形式体现的。教学内容通过说明和教学活动的延伸来形象地呈现。对于学生，使用这本书的有效方法是认真参与教学活动，而不是只阅读那些教学活动后面的解释。这些教学活动在课堂中以小组的形式完成。因此，我们建议学生形成小组，一起解决安排在课外进行的教学活动。我们希望通过这种设计来帮助学生培养数学思维。通过了解关于本科生怎样学习数学，我们得出以下几个结论。
?那些主动发现自己所学内容的学生（从而参与到所谓的主动学习中）比那些不主动学习的学生记住概念的时间要长得多，他们也更有可能在课堂之外运用这些概念。
?当学生在一个小组和同学一起学习，而不是在一个有导师的更大的班级中学习时，他们更有可能提出问题，直到他们理解一个主题。（然而，情况并非如此。很多学生需要适应他们的小组之后再提出问题，因为他们担心会拖慢其他人的进度。我们尝试提高舒适度，允许学生选择学习小组，并且根据出席情况允许或者要求学生更换不同的小组。）
?后，通过为他人解释概念来帮助学生进一步理解概念，并且让学生熟悉数学语言。
这本书的内容可用于一门四个学期的课程。在达特茅斯学院，我们使用这本书的课程节奏比较快，一周上三天且仅仅上九周，却涵盖了本书除了后几节和一部分带星号的内容之外的所有内容。
证明的作
克利福德·斯坦（Clifford Stein）
著名计算机科学家，名作《算法导论》的作者之一。现为哥伦比亚大学计算机科学系和工业工程与运筹学系教授。
罗伯特·L. 戴斯得尔（Robert L. Drysdale）
达特茅斯学院计算机科学系教授，曾任该系系主任8年，是算法和计算几何学领域的知名学者。
肯尼斯·博加特（Kenneth Bogart）
生前是达特茅斯学院数学系教授，一生致力于数学研究和教学工作，2005年由于自行车事故不幸去世。
译者序
前言
第1章 计数 1
1.1 基本计数 1
1.1.1 加法原理 1
1.1.2 抽象化 2
1.1.3 连续整数求和 3
1.1.4 乘法原理 3
1.1.5 二元子集 5
重要概念、公式和定理 5
习题 6
1.2 序列、排列和子集 7
1.2.1 使用加法和乘法原理 7
1.2.2 序列和函数 9
1.2.3 双射原理 10
1.2.4 集合的 k 元素排列 11
1.2.5 集合子集的计数 12
重要概念、公式和定理 14
习题 15
1.3 二项式系数 16
1.3.1 帕斯卡三角形 16
1.3.2 使用加法原理的证明 18
1.3.3 二项式定理 19
1.3.4 标记与三项式系数 21
重要概念、公式和定理 22
习题 22
1.4 关系 24
1.4.1 什么是关系 24
1.4.2 函数关系 24
1.4.3 关系的性质 25
1.4.4 等价关系 27
1.4.5 偏序和全序 29
重要概念、公式和定理 30
习题 31
1.5 在计数中运用等价关系 32
1.5.1 对称原理 32
1.5.2 等价关系 34
1.5.3 商原理 34
1.5.4 等价类计数 35
1.5.5 多重集 36
1.5.6 书柜安排问题 37
1.5.7 n 元集合的 k 元多重集的数目 38
1.5.8 使用商原理解释商 39
重要概念、公式和定理 39
习题 40
第2章 密码编码学与数论 43
2.1 密码编码学和模算法 43
2.1.1 密码编码学导论 43
2.1.2 私钥密码 43
2.1.3 公钥密码体制 46
2.1.4 模 n 算术 47
2.1.5 使用模 n 加法的密码编码 49
2.1.6 使用模 n 乘法的密码编码 50
重要概念、公式和定理 51
习题 52
2.2 逆元和公因子 54
2.2.1 方程的解和模 n 的逆元 54
2.2.2 模 n 的逆元 55
2.2.3 将模方程转化为普通方程 57
2.2.4 公因子 58
2.2.5 欧几里得除法定理 59
2.2.6 欧几里得公因子算法 61
2.2.7 广义公因子算法 62
2.2.8 计算逆元 64
重要概念、公式和定理 65
习题 66
2.3 RSA 密码体制 67
2.3.1 模 n 的指数运算 67
2.3.2 指数运算的规则 68
2.3.3 费马小定理 70
2.3.4 RSA 密码体制 71
2.3.5 中国剩余定理 74
重要概念、公式和定理 75
习题 76
2.4 RSA 加密体制的细节 78
2.4.1 模 n 指数运算的实用性 78
2.4.2 使用 RSA 算法会花费多长时间 79
2.4.3 因式分解有多难 80
2.4.4 找大素数 80
重要概念、公式和定理 83
习题 83
第3章 关于逻辑与证明的思考 85
3.1 等价和蕴含 85
3.1.1 语句的等价 85
3.1.2 真值表 87
3.1.3 德摩根律 89
3.1.4 蕴含 90
3.1.5 当且仅当 91
重要概念、公式和定理 93
习题 94
3.2 变元和量词 95
3.2.1 变元和论域 95
3.2.2 量词
当前图书最新荐购
