离散数学：面向计算机科学专业

动机与目标 
很多大学都开设离散数学课程。上该课程的学生来自多个专业，其中多的是来自计算机科学专业的学生。在国家科学基金会一的支持下，作为达特茅斯（Dartmouth）学院跨学科数学项目的一部分，我们提出开设一门离散数学课程来满足计算机科学专业学生的需求。在分析想让计算机科学专业的学生了解哪些离散数学主题，以及为什么想让他们了解这些主题时，我们得到两个结论。
，我们认为一些主题对于计算机科学专业很重要，但是没有被充分地纳入传统的离散数学课程中。这些主题包括递归树和解决递推关系的主定理，计算平均运行时间和分析随机算法的概率理论，以及强归纳法和结构归纳法。
第二，我们认为对于计算机科学专业学生很重要的每个离散数学主题，在计算机科学里都有一个很有启发性的主题，上述门或者第二门计算机科学入门课程的学生可以理解这些主题。我们感觉这样安排就能回答在应用数学课程中学生经常会问的问题：“为什么我们必须学习这些？”因此，我们决定写一本针对计算机科学专业学生的教科书，目标是为计算机科学专业学生提供必要的数学基础，并且通过学生在计算机科学学习的开始阶段就能够理解的计算机科学问题来启发他们学习这本教科书。
一基金资助号为DUE-9552462。
二我们的大多数学生已经学习过微积分。在一些地方我们会使用初级的导数，并且在概率部分的选修小节中，我们使用自然对数、指数函数和初级的幂级数。如果忽略少数使用导数的证明和问题，以及概率部分的选修小节，教师可以不涉及微积分。

在许多高校的计算机科学系，离散数学是学生的专业必修课之一，甚至是门计算机科学课程的先修课。在这种情况下，教师面临一种困境——讲授纯数学的概念，很少或者完全没有显式的计算机应用，或者讲授计算机科学的例子来营造一种针对计算机科学专业学生的语境。对于种讲课方式，学生会抱怨在学习门计算机科学课程之前被迫学习太多“不相干的”数学知识。对于第二种讲课方式，教师（通常是数学家）要尝试给可能从来没有写过程序的学生解释相当高级的计算机科学主题，比如散列、二叉树和递归程序等。即使在好的情况下，这种方式也明显降低了数学的深度。基于我们的分析，产生了一种不同的讲课方式，即开设一门学生稍后学习的课程。尽管我们没有明确假定学生已经学过微积分，但是假定学生了解并且能够熟练使用求和符号、对数和指数函数。因此，熟悉微积分知识是很有帮助的二。这意味着学生要在计算机科学的入门课中见过递归程序之后再学习这门课。这门课好和数据结构课程同时学习或者在其之后学习，不过我们会通过例子解释所使用的数据结构。因此，数据结构课程不是这门课的先导课程。
我们觉得这样安排离散数学课程有很多优势，例如：
?学生已经有了较为深入的问题解决、算法和编程的经验。
?学生已经学习或者准备学习一些重要的计算机科学概念，比如散列、递归、排序和搜索，以及基本的数据结构。
?学生对计算机科学有足够的了解，已经知道一些启发性例子，或者这些例子对于他们而言足够简单易懂。例如：
a散列可以用于启发概率的学习。a分析递归程序，比如归并和快速排序，可以启发学习递推关系和相应的解决方法。
a分析在一个寻找线性表中小元素的程序中，我们期望多久找到一个新的小值，可以启发学习期望的线性性质和调和数。
a二叉树可以用于教授结构递归法，也可以作为图的特例启发树的学习。
根据我们自己的授课经验，离散数学课程是算法课的先导课程，学生经常在结束离散数学课程不久后就开始学习算法。这样，他们会发现自己可以直接使用刚学过的离散数学知识。
教学理念
这本教科书是以教学活动为驱动，以练习的形式体现的。教学内容通过说明和教学活动的延伸来形象地呈现。对于学生，使用这本书的有效方法是认真参与教学活动，而不是只阅读那些教学活动后面的解释。这些教学活动在课堂中以小组的形式完成。因此，我们建议学生形成小组，一起解决安排在课外进行的教学活动。我们希望通过这种设计来帮助学生培养数学思维。通过了解关于本科生怎样学习数学，我们得出以下几个结论。
?那些主动发现自己所学内容的学生（从而参与到所谓的“主动学习”中）比那些不主动学习的学生记住概念的时间要长得多，他们也更有可能在课堂之外运用这些概念。
?当学生在一个小组和同学一起学习，而不是在一个有导师的更大的班级中学习时，他们更有可能提出问题，直到他们理解一个主题。（然而，情况并非如此。很多学生需要适应他们的小组之后再提出问题，因为他们担心会拖慢其他人的进度。我们尝试提高舒适度，允许学生选择学习小组，并且根据出席情况允许或者要求学生更换不同的小组。）
?后，通过为他人解释概念来帮助学生进一步理解概念，并且让学生熟悉数学语言。
这本书的内容可用于一门四个学期的课程。在达特茅斯学院，我们使用这本书的课程节奏比较快，一周上三天且仅仅上九周，却涵盖了本书除了后几节和一部分带星号的内容之外的所有内容。
证明的作

本书由计算机和数学领域的三位教授联合撰写，旨在满足计算机专业对离散数学课程的需求。针对这门课程的困境——初入学的本科生不理解为何要学习高深的数学，以及授课教师难以向毫无编程经验的学生讲授繁杂的算法程序——本书明确了“为何学”和“有何用”，打破了传统的课程顺序和教学方法，不仅清晰呈现了计算机专业学生必需的数学知识，而且通过实践和应用激发学生对后续课程的学习兴趣。
主要内容：涵盖计数、密码编码学与数论、逻辑与证明、归纳、递归、概率以及图论，推导严谨、代码清晰、练习丰富。
教学模式：提倡参与式教学，鼓励学生加入小组讨论，主动探索，通过提问、讨论和报告来掌握概念，找到解决方案。
课程建议：建议学生掌握微积分知识，了解递归。