《离散数学》课程教学大纲Word文档格式.docx

1、二、课程简介中文简介 离散数学主要介绍计算机科学与技术中的基本离散结构，重点是这些结构的数学定义、在计算机科学中广为使用的证明方法及其应用。课程包括的基本内容：数理逻辑初步、证明方法、归纳、良序、集合、关系、图论基础、排列与组合、计数等。课程还包括若干可选内容：递归定义与结构归纳法、状态机与不变式、递归等。英文简介 Elementary discrete mathematics for computer science and engineering. Emphasis on mathematical definitions and proofs as well as on applicabl

2、e methods. Topics: formal logic notation, proof methods; induction, well-ordering; sets, relations; elementary graph theory; integer congruences; asymptotic notation and growth of functions; permutations and combinations, counting principles; discrete probability. Further selected topics such as: re

3、cursive definition and structural induction; state machines and invariants; recurrences. 三、课程性质与教学目的离散数学是计算机类各专业的专业基础课，是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。离散数学课程旨在引导学生掌握如何运用数学模型和方法去分析计算机科学中的问题。重点培养学生用严格的逻辑分析去建模和解决计算类问题。本课程将覆盖现代计算机科学中的若干重要且非常实用的知识点，包括证明方法、良序法则、数理

4、逻辑、集合论、数学归纳法、组合、图论和网络算法等。每一章中都包含了若干有趣的定理、性质、它们的详细证明及一些相对更有挑战性的问题。本课程主要为计算机科学专业学生开设，也可为理工类其它专业学生提供参考。目的是通过本课程的学习给学生未来的学习和工作奠定必要的数学素质。课程思政教学中介绍近代数学、计算机科学上伟大科学家的事迹，提炼其伟大思想，为学生提供可以学习的思想楷模。具体见各教学章节。四、教学内容及要求 Chapter 1: What is a Proof?（一）目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握： 证明的基本方法熟悉： 证明的基本概念了解： 如何欣赏美的证明（二）教学

5、内容1.1 Propositions 1.2 Predicates 1.3 The Axiomatic Method 1.4 Our Axioms 1.5 Proving an Implication 1.6 Proving an “If and Only If” 1.7 Proof by Cases 1.8 Proof by Contradiction 1.9 Good Proofs in Practice （三）教学方法与手段教学方法及手段（请打）：讲授 、讨论 、多媒体讲解 、模型、实物讲解、挂图讲解、音像讲解等。 Chapter 2: The Well Ordering Princip

6、le良序证明方法 良序集 良序集的应用2.1 Well Ordering Proofs 2.2 Template for WOP Proofs 2.3 Factoring into Primes 2.4 Well Ordered Sets Chapter 3: Logical Formulas 逻辑演算、等值演算 命题逻辑、谓词逻辑的基本概率、常用公式 数理逻辑与计算机科学的关系课程思政：在数学和逻辑结合的过程中，一大批伟大的学者为了实现自动推理的梦想，穷尽一生，不惜血汗、前赴后继方有今天信息的繁荣，其伟大事迹值得后学学习。3.1 Propositions from Propositions

7、3.2 Propositional Logic in Computer Programs 3.3 Equivalence and Validity 3.4 The Algebra of Propositions 3.5 The SAT Problem 3.6 Predicate Formulas Chapter 4: Mathematical Data Types 集合、序列、函数、关系的基本定义与性质 等价关系、偏序关系 有穷集的基数4.1 Sets 4.2 Sequences 4.3 Functions 4.4 Binary Relations 4.5 Finite Cardinality

8、Chapter 5: Induction 数学归纳法、强数学归纳法的应用 使用归纳法中出错的类型 归纳法与良序法则5.1 Ordinary Induction 5.2 Strong Induction 5.3 Strong Induction vs. Induction vs. Well Ordering Chapter 6: Infinite Sets 有穷和无穷的区别；可数无穷的证明；不可数无穷的证明 停机问题 对角线方法在计算理论中的应用Cantor以一己之力，建立无穷和集合的理论，不仅因为智力挑战更因为保守权威的打击，可Cantor为了科学，迎面直上，虽三次精神失常，但终究为人类建立了

9、无穷的乐园，其不屈不挠的精神足可以成为我们学习的楷模。6.1Infinite Cardinality 6.2 The Halting Problem 6.3 The Logic of Sets 6.4 Does All This Really Work?Chapter 7: Simple Graphs? 二部图、图着色、连通、数 图的基本概念 图的同构欧拉的哥尼斯堡七桥问题标志着图论的创立，欧拉在失明后还口述了几百篇论文和十几本书，其成就值得敬仰、其直面困难、坚持不懈的精神是我们学习的楷模。7.1Vertex Adjacency and Degrees 7.2 Sexual Demograph

10、ics in America 7.3 Some Common Graphs 7.4 Isomorphism 7.5 Bipartite Graphs & Matchings 7.6 Coloring 7.7 Walks in Simple Graphs 7.8 Connectivity 7.9 Special Walks and Tours 7.10 k-connected Graphs 7.11 Forests & Trees Chapter 8: Planar Graphs? 平面图的判定定理、平面图的着色 库拉托夫斯基定理 四色定理8.1 Drawing Graphs in the Pl

11、ane 8.2 Definitions of Planar Graphs 8.3 Eulers Formula 8.4 Bounding the Number of Edges in a Planar Graph 8.5 Returning to K5 and K3;3 8.6 Coloring Planar Graphs 8.7 Classifying Polyhedra 8.8 Another Characterization for Planar Graphs 五学时分配周次教学内容教学方式教学媒体学时课外作业及平时考核内容1. 课程简介网络课堂1考勤 数理逻辑基本概念23. 命题逻辑作

12、业1命题演算形式系统作业2谓词逻辑及形式系统34集合论作业35.作业46特殊关系及函数作业57.证明技术课堂讲授投影作业69.良序法则作业710. 数学归纳法11无穷理论作业812.Simple Graphs13作业914Planar Graphs作业1015习题课16复习 答疑六课程考核闭卷集中考试七推荐教材和教学参考资源1. Lehman, Leighton, and Meyer Mathematics for Computer Science MIT 20182. L.Lovasz J.pelikan K.Vesztergombi Discrete Mathematics:Elementary and Beyond Springer 2003