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

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