《離散數(shù)學(xué)》-課程教學(xué)大綱

PAGEPAGE9《離散數(shù)學(xué)》課程教學(xué)大綱英文：《DiscreteMathematics》一、課程基本信息課程代碼：16046404課程名稱：離散數(shù)學(xué)英文名稱：DiscreteMathematics課程類別：學(xué)科基礎(chǔ)學(xué)時(shí)：64學(xué)分：4適用對(duì)象:計(jì)算機(jī)實(shí)驗(yàn)班、計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程考核方式：閉卷先修課程：無(wú)二、課程簡(jiǎn)介中文簡(jiǎn)介離散數(shù)學(xué)主要介紹計(jì)算機(jī)科學(xué)與技術(shù)中的基本離散結(jié)構(gòu)，重點(diǎn)是這些結(jié)構(gòu)的數(shù)學(xué)定義、在計(jì)算機(jī)科學(xué)中廣為使用的證明方法及其應(yīng)用。課程包括的基本內(nèi)容：數(shù)理邏輯初步、證明方法、歸納、良序、集合、關(guān)系、圖論基礎(chǔ)、排列與組合、計(jì)數(shù)等。課程還包括若干可選內(nèi)容：遞歸定義與結(jié)構(gòu)歸納法、狀態(tài)機(jī)與不變式、遞歸等。英文簡(jiǎn)介Elementarydiscretemathematicsforcomputerscienceandengineering.Emphasisonmathematicaldefinitionsandproofsaswellasonapplicablemethods.Topics:formallogicnotation,proofmethods;induction,well-ordering;sets,relations;elementarygraphtheory;integercongruences;asymptoticnotationandgrowthoffunctions;permutationsandcombinations,countingprinciples;discreteprobability.Furtherselectedtopicssuchas:recursivedefinitionandstructuralinduction;statemachinesandinvariants;recurrences.三、課程性質(zhì)與教學(xué)目的離散數(shù)學(xué)是計(jì)算機(jī)類各專業(yè)的專業(yè)基礎(chǔ)課，是計(jì)算機(jī)科學(xué)的基礎(chǔ)理論，離散結(jié)構(gòu)的基礎(chǔ)知識(shí)和邏輯思維的形式化是信息技術(shù)類學(xué)生的基本功，離散數(shù)學(xué)的基本概念是理科專業(yè)學(xué)生進(jìn)行信息類課程學(xué)習(xí)的重要基礎(chǔ)。離散數(shù)學(xué)課程旨在引導(dǎo)學(xué)生掌握如何運(yùn)用數(shù)學(xué)模型和方法去分析計(jì)算機(jī)科學(xué)中的問題。重點(diǎn)培養(yǎng)學(xué)生用嚴(yán)格的邏輯分析去建模和解決計(jì)算類問題。本課程將覆蓋現(xiàn)代計(jì)算機(jī)科學(xué)中的若干重要且非常實(shí)用的知識(shí)點(diǎn)，包括證明方法、良序法則、數(shù)理邏輯、集合論、數(shù)學(xué)歸納法、組合、圖論和網(wǎng)絡(luò)算法等。每一章中都包含了若干有趣的定理、性質(zhì)、它們的詳細(xì)證明及一些相對(duì)更有挑戰(zhàn)性的問題。本課程主要為計(jì)算機(jī)科學(xué)專業(yè)學(xué)生開設(shè)，也可為理工類其它專業(yè)學(xué)生提供參考。目的是通過本課程的學(xué)習(xí)給學(xué)生未來(lái)的學(xué)習(xí)和工作奠定必要的數(shù)學(xué)素質(zhì)。課程思政教學(xué)中介紹近代數(shù)學(xué)、計(jì)算機(jī)科學(xué)上偉大科學(xué)家的事跡，提煉其偉大思想，為學(xué)生提供可以學(xué)習(xí)的思想楷模。具體見各教學(xué)章節(jié)。四、教學(xué)內(nèi)容及要求Chapter1:WhatisaProof?目的與要求教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：掌握：證明的基本方法熟悉：證明的基本概念了解：如何欣賞美的證明教學(xué)內(nèi)容1.1Propositions1.2Predicates1.3TheAxiomaticMethod1.4OurAxioms1.5ProvinganImplication1.6Provingan“IfandOnlyIf”1.7ProofbyCases1.8ProofbyContradiction1.9GoodProofsinPractice教學(xué)方法與手段教學(xué)方法及手段（請(qǐng)打√）：講授、討論、多媒體講解、模型、實(shí)物講解□、掛圖講解□、音像講解□等。Chapter2:TheWellOrderingPrinciple目的與要求教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：掌握：良序證明方法熟悉：良序集了解：良序集的應(yīng)用教學(xué)內(nèi)容2.1WellOrderingProofs2.2TemplateforWOPProofs2.3FactoringintoPrimes2.4WellOrderedSets教學(xué)方法與手段教學(xué)方法及手段（請(qǐng)打√）：講授、討論、多媒體講解、模型、實(shí)物講解□、掛圖講解□、音像講解□等。Chapter3:LogicalFormulas目的與要求教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：掌握：邏輯演算、等值演算熟悉：命題邏輯、謂詞邏輯的基本概率、常用公式了解：數(shù)理邏輯與計(jì)算機(jī)科學(xué)的關(guān)系課程思政：在數(shù)學(xué)和邏輯結(jié)合的過程中，一大批偉大的學(xué)者為了實(shí)現(xiàn)自動(dòng)推理的夢(mèng)想，窮盡一生，不惜血汗、前赴后繼方有今天信息的繁榮，其偉大事跡值得后學(xué)學(xué)習(xí)。教學(xué)內(nèi)容3.1PropositionsfromPropositions3.2PropositionalLogicinComputerPrograms3.3EquivalenceandValidity3.4TheAlgebraofPropositions3.5TheSATProblem3.6PredicateFormulas教學(xué)方法與手段教學(xué)方法及手段（請(qǐng)打√）：講授、討論、多媒體講解、模型、實(shí)物講解□、掛圖講解□、音像講解□等。Chapter4:MathematicalDataTypes目的與要求教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：掌握：集合、序列、函數(shù)、關(guān)系的基本定義與性質(zhì)熟悉：等價(jià)關(guān)系、偏序關(guān)系了解：有窮集的基數(shù)教學(xué)內(nèi)容4.1Sets4.2Sequences4.3Functions4.4BinaryRelations4.5FiniteCardinality教學(xué)方法與手段教學(xué)方法及手段（請(qǐng)打√）：講授、討論、多媒體講解、模型、實(shí)物講解□、掛圖講解□、音像講解□等。Chapter5:Induction目的與要求教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：掌握：數(shù)學(xué)歸納法、強(qiáng)數(shù)學(xué)歸納法的應(yīng)用熟悉：使用歸納法中出錯(cuò)的類型了解：歸納法與良序法則教學(xué)內(nèi)容5.1OrdinaryInduction5.2StrongInduction5.3StrongInductionvs.Inductionvs.WellOrdering教學(xué)方法與手段教學(xué)方法及手段（請(qǐng)打√）：講授、討論、多媒體講解、模型、實(shí)物講解□、掛圖講解□、音像講解□等。Chapter6:InfiniteSets目的與要求教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：掌握：有窮和無(wú)窮的區(qū)別；可數(shù)無(wú)窮的證明；不可數(shù)無(wú)窮的證明熟悉：停機(jī)問題了解：對(duì)角線方法在計(jì)算理論中的應(yīng)用課程思政：Cantor以一己之力，建立無(wú)窮和集合的理論，不僅因?yàn)橹橇μ魬?zhàn)更因?yàn)楸Ｊ貦?quán)威的打擊，可Cantor為了科學(xué)，迎面直上，雖三次精神失常，但終究為人類建立了無(wú)窮的樂園，其不屈不撓的精神足可以成為我們學(xué)習(xí)的楷模。教學(xué)內(nèi)容6.1InfiniteCardinality6.2TheHaltingProblem6.3TheLogicofSets6.4DoesAllThisReallyWork?教學(xué)方法與手段教學(xué)方法及手段（請(qǐng)打√）：講授、討論、多媒體講解、模型、實(shí)物講解□、掛圖講解□、音像講解□等。Chapter7:SimpleGraphs?目的與要求教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：掌握：二部圖、圖著色、連通、數(shù)熟悉：圖的基本概念了解：圖的同構(gòu)課程思政：歐拉的哥尼斯堡七橋問題標(biāo)志著圖論的創(chuàng)立，歐拉在失明后還口述了幾百篇論文和十幾本書，其成就值得敬仰、其直面困難、堅(jiān)持不懈的精神是我們學(xué)習(xí)的楷模。教學(xué)內(nèi)容7.1VertexAdjacencyandDegrees7.2SexualDemographicsinAmerica7.3SomeCommonGraphs7.4Isomorphism7.5BipartiteGraphs&Matchings7.6Coloring7.7WalksinSimpleGraphs7.8Connectivity7.9SpecialWalksandTours7.10k-connectedGraphs7.11Forests&Trees教學(xué)方法與手段教學(xué)方法及手段（請(qǐng)打√）：講授、討論、多媒體講解、模型、實(shí)物講解□、掛圖講解□、音像講解□等。Chapter8:PlanarGraphs?目的與要求教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：掌握：平面圖的判定定理、平面圖的著色熟悉：庫(kù)拉托夫斯基定理了解：四色定理教學(xué)內(nèi)容8.1DrawingGraphsinthePlane8.2DefinitionsofPlanarGraphs8.3Euler’sFormula8.4BoundingtheNumberofEdgesinaPlanarGraph8.5ReturningtoK5andK3;38.6ColoringPlanarGraphs8.7ClassifyingPolyhedra8.8AnotherCharacterizationforPlanarGraphs教學(xué)方法與手段教學(xué)方法及手段（請(qǐng)打√）：講授、討論、多媒體講解、模型、實(shí)物講解□、掛圖講解□、音像講解□等。五．學(xué)時(shí)分配周次教學(xué)內(nèi)容教學(xué)方式教學(xué)媒體學(xué)時(shí)課外作業(yè)及平時(shí)考核內(nèi)容課程簡(jiǎn)介網(wǎng)絡(luò)課堂1考勤數(shù)理邏輯基本概念網(wǎng)絡(luò)課堂2命題邏輯網(wǎng)絡(luò)課堂1作業(yè)1命題演算形式系統(tǒng)網(wǎng)絡(luò)課堂2作業(yè)23.謂詞邏輯及形式系統(tǒng)網(wǎng)絡(luò)課堂34集合論網(wǎng)絡(luò)課堂3作業(yè)35.集合論網(wǎng)絡(luò)課堂3作業(yè)46特殊關(guān)系及函數(shù)網(wǎng)絡(luò)課堂3作業(yè)57.證明技術(shù)課堂講授投影3作業(yè)69.良序法則課堂講授投影3作業(yè)710.數(shù)學(xué)歸納法課堂講授投影311無(wú)窮理論課堂講授投影3作業(yè)812.SimpleGraphs課堂講授投影313SimpleGraphs課堂講授投影3作業(yè)914PlanarGra