《离散数学》-课程教学大纲

PAGEPAGE9《离散数学》课程教学大纲英文：《DiscreteMathematics》一、课程基本信息课程代码：16046404课程名称：离散数学英文名称：DiscreteMathematics课程类别：学科基础学时：64学分：4适用对象:计算机实验班、计算机科学与技术、软件工程考核方式：闭卷先修课程：无二、课程简介中文简介离散数学主要介绍计算机科学与技术中的基本离散结构，重点是这些结构的数学定义、在计算机科学中广为使用的证明方法及其应用。课程包括的基本内容：数理逻辑初步、证明方法、归纳、良序、集合、关系、图论基础、排列与组合、计数等。课程还包括若干可选内容：递归定义与结构归纳法、状态机与不变式、递归等。英文简介Elementarydiscretemathematicsforcomputerscienceandengineering.Emphasisonmathematicaldefinitionsandproofsaswellasonapplicablemethods.Topics:formallogicnotation,proofmethods;induction,well-ordering;sets,relations;elementarygraphtheory;integercongruences;asymptoticnotationandgrowthoffunctions;permutationsandcombinations,countingprinciples;discreteprobability.Furtherselectedtopicssuchas:recursivedefinitionandstructuralinduction;statemachinesandinvariants;recurrences.三、课程性质与教学目的离散数学是计算机类各专业的专业基础课，是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。离散数学课程旨在引导学生掌握如何运用数学模型和方法去分析计算机科学中的问题。重点培养学生用严格的逻辑分析去建模和解决计算类问题。本课程将覆盖现代计算机科学中的若干重要且非常实用的知识点，包括证明方法、良序法则、数理逻辑、集合论、数学归纳法、组合、图论和网络算法等。每一章中都包含了若干有趣的定理、性质、它们的详细证明及一些相对更有挑战性的问题。本课程主要为计算机科学专业学生开设，也可为理工类其它专业学生提供参考。目的是通过本课程的学习给学生未来的学习和工作奠定必要的数学素质。课程思政教学中介绍近代数学、计算机科学上伟大科学家的事迹，提炼其伟大思想，为学生提供可以学习的思想楷模。具体见各教学章节。四、教学内容及要求Chapter1:WhatisaProof?目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：证明的基本方法熟悉：证明的基本概念了解：如何欣赏美的证明教学内容1.1Propositions1.2Predicates1.3TheAxiomaticMethod1.4OurAxioms1.5ProvinganImplication1.6Provingan“IfandOnlyIf”1.7ProofbyCases1.8ProofbyContradiction1.9GoodProofsinPractice教学方法与手段教学方法及手段（请打√）：讲授、讨论、多媒体讲解、模型、实物讲解□、挂图讲解□、音像讲解□等。Chapter2:TheWellOrderingPrinciple目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：良序证明方法熟悉：良序集了解：良序集的应用教学内容2.1WellOrderingProofs2.2TemplateforWOPProofs2.3FactoringintoPrimes2.4WellOrderedSets教学方法与手段教学方法及手段（请打√）：讲授、讨论、多媒体讲解、模型、实物讲解□、挂图讲解□、音像讲解□等。Chapter3:LogicalFormulas目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：逻辑演算、等值演算熟悉：命题逻辑、谓词逻辑的基本概率、常用公式了解：数理逻辑与计算机科学的关系课程思政：在数学和逻辑结合的过程中，一大批伟大的学者为了实现自动推理的梦想，穷尽一生，不惜血汗、前赴后继方有今天信息的繁荣，其伟大事迹值得后学学习。教学内容3.1PropositionsfromPropositions3.2PropositionalLogicinComputerPrograms3.3EquivalenceandValidity3.4TheAlgebraofPropositions3.5TheSATProblem3.6PredicateFormulas教学方法与手段教学方法及手段（请打√）：讲授、讨论、多媒体讲解、模型、实物讲解□、挂图讲解□、音像讲解□等。Chapter4:MathematicalDataTypes目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：集合、序列、函数、关系的基本定义与性质熟悉：等价关系、偏序关系了解：有穷集的基数教学内容4.1Sets4.2Sequences4.3Functions4.4BinaryRelations4.5FiniteCardinality教学方法与手段教学方法及手段（请打√）：讲授、讨论、多媒体讲解、模型、实物讲解□、挂图讲解□、音像讲解□等。Chapter5:Induction目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：数学归纳法、强数学归纳法的应用熟悉：使用归纳法中出错的类型了解：归纳法与良序法则教学内容5.1OrdinaryInduction5.2StrongInduction5.3StrongInductionvs.Inductionvs.WellOrdering教学方法与手段教学方法及手段（请打√）：讲授、讨论、多媒体讲解、模型、实物讲解□、挂图讲解□、音像讲解□等。Chapter6:InfiniteSets目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：有穷和无穷的区别；可数无穷的证明；不可数无穷的证明熟悉：停机问题了解：对角线方法在计算理论中的应用课程思政：Cantor以一己之力，建立无穷和集合的理论，不仅因为智力挑战更因为保守权威的打击，可Cantor为了科学，迎面直上，虽三次精神失常，但终究为人类建立了无穷的乐园，其不屈不挠的精神足可以成为我们学习的楷模。教学内容6.1InfiniteCardinality6.2TheHaltingProblem6.3TheLogicofSets6.4DoesAllThisReallyWork?教学方法与手段教学方法及手段（请打√）：讲授、讨论、多媒体讲解、模型、实物讲解□、挂图讲解□、音像讲解□等。Chapter7:SimpleGraphs?目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：二部图、图着色、连通、数熟悉：图的基本概念了解：图的同构课程思政：欧拉的哥尼斯堡七桥问题标志着图论的创立，欧拉在失明后还口述了几百篇论文和十几本书，其成就值得敬仰、其直面困难、坚持不懈的精神是我们学习的楷模。教学内容7.1VertexAdjacencyandDegrees7.2SexualDemographicsinAmerica7.3SomeCommonGraphs7.4Isomorphism7.5BipartiteGraphs&Matchings7.6Coloring7.7WalksinSimpleGraphs7.8Connectivity7.9SpecialWalksandTours7.10k-connectedGraphs7.11Forests&Trees教学方法与手段教学方法及手段（请打√）：讲授、讨论、多媒体讲解、模型、实物讲解□、挂图讲解□、音像讲解□等。Chapter8:PlanarGraphs?目的与要求教学目的、要求（分掌握、熟悉、了解三个层次）：掌握：平面图的判定定理、平面图的着色熟悉：库拉托夫斯基定理了解：四色定理教学内容8.1DrawingGraphsinthePlane8.2DefinitionsofPlanarGraphs8.3Euler’sFormula8.4BoundingtheNumberofEdgesinaPlanarGraph8.5ReturningtoK5andK3;38.6ColoringPlanarGraphs8.7ClassifyingPolyhedra8.8AnotherCharacterizationforPlanarGraphs教学方法与手段教学方法及手段（请打√）：讲授、讨论、多媒体讲解、模型、实物讲解□、挂图讲解□、音像讲解□等。五．学时分配周次教学内容教学方式教学媒体学时课外作业及平时考核内容课程简介网络课堂1考勤数理逻辑基本概念网络课堂2命题逻辑网络课堂1作业1命题演算形式系统网络课堂2作业23.谓词逻辑及形式系统网络课堂34集合论网络课堂3作业35.集合论网络课堂3作业46特殊关系及函数网络课堂3作业57.证明技术课堂讲授投影3作业69.良序法则课堂讲授投影3作业710.数学归纳法课堂讲授投影311无穷理论课堂讲授投影3作业812.SimpleGraphs课堂讲授投影313SimpleGraphs课堂讲授投影3作业914PlanarGra