《离散数学》课程教学大纲英文：《Discrete Mathematics》一、课程基本信息课程代码：16046404课程名称：离散数学英文名称：Discrete Mathematics课程类别：学科基础学时：64学分： 4适用对象: 计算机实验班、计算机科学与技术、软件工程考核方式：闭卷先修课程：无二、课程简介中文简介离散数学主要介绍计算机科学与技术中的基本离散结构，重点是这些结构的数学定义、在计算机科学中广为使用的证明方法及其应用。
课程包括的基本内容：数理逻辑初步、证明方法、归纳、良序、集合、关系、图论基础、排列与组合、计数等。
课程还包括若干可选内容：递归定义与结构归纳法、状态机与不变式、递归等。
英文简介Elementary discrete mathematics for computer science and engineering. Emphasis on mathematical definitions and proofs as well as on applicable 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: recursive definition and structural induction; state machines and invariants; recurrences.三、课程性质与教学目的离散数学是计算机类各专业的专业基础课，是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。
离散数学课程旨在引导学生掌握如何运用数学模型和方法去分析计算机科学中的问题。
重点培养学生用严格的逻辑分析去建模和解决计算类问题。
本课程将覆盖现代计算机科学中的若干重要且非常实用的知识点，包括证明方法、良序法则、数理逻辑、集合论、数学归纳法、组合、图论和网络算法等。
每一章中都包含了若干有趣的定理、性质、它们的详细证明及一些相对更有挑战性的问题。
本课程主要为计算机科学专业学生开设，也可为理工类其它专业学生提供参考。
目的是通过本课程的学习给学生未来的学习和工作奠定必要的数学素质。
课程思政教学中介绍近代数学、计算机科学上伟大科学家的事迹，提炼其伟大思想，为学生提供可以学习的思想楷模。
具体见各教学章节。
四、教学内容及要求Chapter 1: What is a Proof?（一）目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：证明的基本方法熟悉：证明的基本概念了解：如何欣赏美的证明（二）教学内容1.1 Propositions1.2 Predicates1.3 The Axiomatic Method1.4 Our Axioms1.5 Proving an Implication1.6 Proving an “If and Only If”1.7 Proof by Cases1.8 Proof by Contradiction1.9 Good Proofs in Practice（三）教学方法与手段教学方法及手段（请打√）：讲授 、讨论 、多媒体讲解 、模型、实物讲解□、挂图讲解□、音像讲解□等。
Chapter 2: The Well Ordering Principle（一）目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：良序证明方法熟悉：良序集了解：良序集的应用（二）教学内容2.1 Well Ordering Proofs2.2 Template for WOP Proofs2.3 Factoring into Primes2.4 Well Ordered Sets（三）教学方法与手段教学方法及手段（请打√）：讲授 、讨论 、多媒体讲解 、模型、实物讲解□、挂图讲解□、音像讲解□等。
Chapter 3: Logical Formulas（一）目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：逻辑演算、等值演算熟悉：命题逻辑、谓词逻辑的基本概率、常用公式了解：数理逻辑与计算机科学的关系课程思政：在数学和逻辑结合的过程中，一大批伟大的学者为了实现自动推理的梦想，穷尽一生，不惜血汗、前赴后继方有今天信息的繁荣，其伟大事迹值得后学学习。
（二）教学内容3.1 Propositions from Propositions3.2 Propositional Logic in Computer Programs3.3 Equivalence and Validity3.4 The Algebra of Propositions3.5 The SAT Problem3.6 Predicate Formulas（三）教学方法与手段教学方法及手段（请打√）：讲授 、讨论 、多媒体讲解 、模型、实物讲解□、挂图讲解□、音像讲解□等。
Chapter 4: Mathematical Data Types（一）目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：集合、序列、函数、关系的基本定义与性质熟悉：等价关系、偏序关系了解：有穷集的基数（二）教学内容4.1 Sets4.2 Sequences4.3 Functions4.4 Binary Relations4.5 Finite Cardinality（三）教学方法与手段教学方法及手段（请打√）：讲授 、讨论 、多媒体讲解 、模型、实物讲解□、挂图讲解□、音像讲解□等。
Chapter 5: Induction（一）目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：数学归纳法、强数学归纳法的应用熟悉：使用归纳法中出错的类型了解：归纳法与良序法则（二）教学内容5.1 Ordinary Induction5.2 Strong Induction5.3 Strong Induction vs. Induction vs. Well Ordering（三）教学方法与手段教学方法及手段（请打√）：讲授 、讨论 、多媒体讲解 、模型、实物讲解□、挂图讲解□、音像讲解□等。
Chapter 6: Infinite Sets（一）目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：有穷和无穷的区别；可数无穷的证明；不可数无穷的证明熟悉：停机问题了解：对角线方法在计算理论中的应用课程思政：Cantor以一己之力，建立无穷和集合的理论，不仅因为智力挑战更因为保守权威的打击，可Cantor为了科学，迎面直上，虽三次精神失常，但终究为人类建立了无穷的乐园，其不屈不挠的精神足可以成为我们学习的楷模。
（二）教学内容6.1Infinite Cardinality6.2 The Halting Problem6.3 The Logic of Sets6.4 Does All This Really Work?（三）教学方法与手段教学方法及手段（请打√）：讲授 、讨论 、多媒体讲解 、模型、实物讲解□、挂图讲解□、音像讲解□等。
Chapter 7: Simple Graphs?（一）目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：二部图、图着色、连通、数熟悉：图的基本概念了解：图的同构课程思政：欧拉的哥尼斯堡七桥问题标志着图论的创立，欧拉在失明后还口述了几百篇论文和十几本书，其成就值得敬仰、其直面困难、坚持不懈的精神是我们学习的楷模。
（二）教学内容7.1Vertex Adjacency and Degrees7.2 Sexual Demographics in America7.3 Some Common Graphs7.4 Isomorphism7.5 Bipartite Graphs & Matchings7.6 Coloring7.7 Walks in Simple Graphs7.8 Connectivity7.9 Special Walks and Tours7.10 k-connected Graphs7.11 Forests & Trees（三）教学方法与手段教学方法及手段（请打√）：讲授 、讨论 、多媒体讲解 、模型、实物讲解□、挂图讲解□、音像讲解□等。
Chapter 8: Planar Graphs?（一）目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：平面图的判定定理、平面图的着色熟悉：库拉托夫斯基定理了解：四色定理（二）教学内容8.1 Drawing Graphs in the Plane8.2 Definitions of Planar Graphs8.3 Euler’s Formula8.4 Bounding the Number of Edges in a Planar Graph8.5 Returning to K5 and K3;38.6 Coloring Planar Graphs8.7 Classifying Polyhedra8.8 Another Characterization for Planar Graphs（三）教学方法与手段教学方法及手段（请打√）：讲授 、讨论 、多媒体讲解 、模型、实物讲解□、挂图讲解□、音像讲解□等。
六．课程考核闭卷集中考试七．推荐教材和教学参考资源1. Lehman, Leighton, and Meyer Mathematics for Computer Science MIT 20182. L.Lovasz J.pelikan K.Vesztergombi Discrete Mathematics:Elementary and BeyondSpringer 2003。