中山大學(xué)本科教學(xué)大綱UndergraduateCourseSyllabus學(xué)院（系）：數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院School(Department)：SchoolofDataandComputerScience課程名稱：離散數(shù)學(xué)基礎(chǔ)CourseTitle：DiscreteMathematics二〇二〇年離散數(shù)學(xué)教學(xué)大綱CourseSyllabus:DiscreateMathematics（編寫日期：2020年12月）(Date:19/12/2020)一、課程基本說明I.BasicInformation課程名稱：（中文）離散數(shù)學(xué)基礎(chǔ)（英文）DiscreteMathematicsCourseTitle:ChineseEnglish課程性質(zhì)CourseType必修RequiredCourse課程編碼CourseCodeDCS106學(xué)分Credits4授課學(xué)時(shí)ClassHours72主講教師（職稱）Instructor(Title)開課單位OfferedBy數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院SDCS面向?qū)I(yè)TargetStudents計(jì)算機(jī)科學(xué)與技術(shù)ComputerScienceandTechnology/信息安全I(xiàn)nformationSecurity/智能科學(xué)與技術(shù)IntelligenceScienceandTechnology/軟件工程SoftwareEngineering/信息與計(jì)算科學(xué)InformationandComputingScience授課年級YearofStudents一年級Freshman先修課程PrerequisiteCourse(s)無None課程目的與教學(xué)基本要求CourseObjectiveandRequirements課程的主要目的包括：(1)讓學(xué)生掌握離散數(shù)學(xué)的核心內(nèi)容，并具備使用離散數(shù)學(xué)語言對問題建模的能力；(2)為后續(xù)計(jì)算機(jī)學(xué)科課程構(gòu)建離散數(shù)學(xué)基礎(chǔ)；(3)提高學(xué)生數(shù)學(xué)素養(yǎng)，增強(qiáng)學(xué)生的邏輯思維、關(guān)系思維、量化思維、計(jì)算思維和遞歸思維能力，培養(yǎng)學(xué)生的離散化、模塊化、層次化、系統(tǒng)化、公理化專業(yè)意識(shí)。具體來說，本課程教學(xué)應(yīng)使得學(xué)生熟練掌握有關(guān)集合、函數(shù)、關(guān)系、圖、樹和代數(shù)系統(tǒng)等離散結(jié)構(gòu)基本知識(shí)，掌握有關(guān)邏輯和證明的基本技巧和方法，掌握有關(guān)計(jì)數(shù)的基本知識(shí)，理解并能初步運(yùn)用離散結(jié)構(gòu)進(jìn)行問題建模和求解，了解算法及其分析的基本方法。Thecourseaimstohelpstudents:(1)tolearnthefundamentalmathematicalconceptsandresultsindiscretemathematics;(2)tolaythemathematicalfoundationsforsuccessivecomputersciencecourses;and(3)tounderstandinglogical,relational,quantificational,computationalandrecursivethinking,andtodevelopprofessionalawarenessondiscretization,modularization,abstractlayer,systematizionandaxiomatization.Indetail,afterstudyingthecourse,studentsshould:(1)masterfundamentaldefinitionsandresultsonsets,relations,graphsandtrees;(2)understandpropositionalandpredicatelogics,knowthebasicskillsofmathematicreasoning;(3)graspthebasicknowledgeoncountingtechniques;(4)knowhowtousediscretestructurestomodellingapplicationproblems;and(5)knowhowtowriteandanalysissimplealgorithms.二、課程基本內(nèi)容II.CourseContent（一）課程內(nèi)容i.CourseContent1、 邏輯與證明（22學(xué)時(shí)）LogicandProofs(22hours) 1.1 命題邏輯的語法和語義(4學(xué)時(shí))PropositionalLogic(4hours) 命題的概念、命題邏輯聯(lián)結(jié)詞和復(fù)合命題，命題的真值表和命題運(yùn)算的優(yōu)先級，自然語言命題的符號化 PropositionalLogic,logicoperators(negation,conjunction,disjunction,implication,bicondition),compoundpropositions,truthtable,translatingsentencesintologicexpressions 1.2 命題公式等值演算(2學(xué)時(shí))LogicalEquivalences(2hours) 命題之間的關(guān)系、邏輯等值和邏輯蘊(yùn)含，基本等值式，等值演算 Logicalequivalence,basiclawsoflogicalequivalences,constructingnewlogicalequivalences 1.3 命題邏輯的推理理論（2學(xué)時(shí)）論斷模式，論斷的有效性及其證明，推理規(guī)則，命題邏輯中的基本推理規(guī)則（假言推理、假言易位、假言三段論、析取三段論、附加律、化簡律、合取律）,構(gòu)造推理有效性的形式證明方法Argumentforms,validityofarguments,inferencerules,formalproofs1.4謂詞邏輯的語法和語義(4學(xué)時(shí))PredicatesandQuantifiers(4hours) 命題邏輯的局限，個(gè)體與謂詞、量詞、全程量詞與存在量詞，自由變量與約束變量，謂詞公式的真值，帶量詞的自然語言命題的符號化 Limitationsofpropositionallogic,individualsandpredicates,quantifiers,theuniversalquantificationandconjunction,theexistentialquantificationanddisjunction,freevariablesandboundvariables,logicequivalencesinvolvingquantifiers,translatingsentencesintoquantifiedexpressions. 1.4 謂詞公式等值演算(2學(xué)時(shí))NestedQuantifiers(2hours) 謂詞公式之間的邏輯蘊(yùn)含與邏輯等值，帶嵌套量詞的自然語言命題的符號化，嵌套量詞與邏輯等值 Understandingstatementsinvolvingnestedquantifiers,theorderofquantifiers,translatingsentencesintologicalexpressionsinvolvingnestedquantifiers,logicalequivalencesinvolvingnestedquantifiers. 1.5謂詞邏輯的推理規(guī)則和有效推理(4學(xué)時(shí))RulesofInference(4hours) 證明的基本含和證明的形式結(jié)構(gòu)，帶量詞公式的推理規(guī)則（全程量詞實(shí)例化、全程量詞一般化、存在量詞實(shí)例化、存在量詞一般化），證明的構(gòu)造 Arguments,argumentforms,validityofarguments,rulesofinferenceforpropositionallogic(modusponens,modustollens,hypotheticalsyllogism,disjunctivesyllogism,addition,simplication,conjunction),usingrulesofinferencetobuildarguments,rulesofinferenceforquantifiedstatements(universalinstantiation,universalgeneralization,existentialinstantiation,existentialgeneralization) 1.6 數(shù)學(xué)證明簡介(2學(xué)時(shí))IntroductiontoProofs(2hours) 數(shù)學(xué)證明的相關(guān)術(shù)語、直接證明、通過逆反命題證明、反證法、證明中常見的錯(cuò)誤 Terminologyofproofs,directproofs,proofbycontraposition,proofbycontradiction,mistakesinproofs 1.7 數(shù)學(xué)證明方法與策略初步(2學(xué)時(shí))ProofMethodsandStrategy(2hours) 窮舉法、分情況證明、存在命題的證明、證明策略（前向與后向推理） Exhaustiveproof,proofbycases,existenceproofs,proofstrategies(forwardandbackwardreasoning)2、集合、函數(shù)和關(guān)系（18學(xué)時(shí)）Sets,FunctionsandRelations(18hours) 2.1 集合及其運(yùn)算(3學(xué)時(shí))Sets(3hours) 集合與元素、集合的表示、集合相等、文氏圖、子集、冪集、笛卡爾積 Setanditselements,setrepresentations,setidentities,Venndiagrams,subsets,powersets,Cartesianproducts. 集合基本運(yùn)算（并、交、補(bǔ)）、廣義并與廣義交、集合基本恒等式 Unions,intersections,differences,complements,generalizedunionsandintersections,basiclawsforsetidentities. 2.2函數(shù)(3學(xué)時(shí))Functions(3hours) 函數(shù)的定義、域和共域、像和原像、函數(shù)相等、單函數(shù)與滿函數(shù)、函數(shù)逆與函數(shù)復(fù)合、函數(shù)圖像 Functions,domainsandcodomains,imagesandpre-images,functionidentity,one-to-oneandontofunctions,inversefunctionsandcompositionsoffunctions. 2.3.集合的基數(shù)（1學(xué)時(shí)）集合等勢、有窮集、無窮集、可數(shù)集和不可數(shù)集Setequinumerous,finiteset,infiniteset,countableset,uncountableset.2.4集合的歸納定義、歸納法和遞歸（3學(xué)時(shí)）Inductivesets,inductionsandrecursions(3hours)自然數(shù)的歸納定義，自然數(shù)上的歸納法和遞歸函數(shù)； 數(shù)學(xué)歸納法（第一數(shù)學(xué)歸納法）及應(yīng)用舉例、強(qiáng)歸納法（第二數(shù)學(xué)歸納法）及應(yīng)用舉例；集合一般歸納定義模式、結(jié)構(gòu)歸納法和遞歸函數(shù)。Inductivedefinitionofthenaturalnumbers,inductionandrecursiononnaturalnumbers,inductivelydefinedsets,structuralinductionandrecursion.2.5關(guān)系及其性質(zhì)(3學(xué)時(shí))RelationsandTheirProperties(2hours) 關(guān)系的定義、自反性、對稱性、傳遞性、關(guān)系復(fù)合、關(guān)系的逆、關(guān)系的矩陣表示、關(guān)系的有向圖表示 Relations,reflexiverelations,symmetricrelations,transitiverelations,inverserelationsandcompositionsofrelations,representingrelationsusingmatrices,representingrelationsusingdigraphs 2.6 關(guān)系閉包(3學(xué)時(shí))ClosuresofRelations(2hours) 關(guān)系的自反閉包、關(guān)系的對稱閉包、關(guān)系的傳遞閉包、傳遞閉包與有向圖中的路徑、Warshall算法 Reflexive,symmetricandtransitiveclosuresofrelations,transitiveclosuresandpathsindirectedgraphs,Warshall’sAlgorithms 2.7 等價(jià)關(guān)系(2學(xué)時(shí))EquivalenceRelations(2hours) 等價(jià)關(guān)系、等價(jià)類與劃分，等價(jià)關(guān)系基本定理 Equivalencerelations,equivalenceclassesandpartitions 2.8 偏序關(guān)系(2學(xué)時(shí))PartialOrderings(2hours) 偏序關(guān)系、哈塞圖、極大元與極小元、最大元與最小元、上下界與上下確界、良序集與良序原理 Partialorderings,Hasse-diagrams,maximalandminimalelements,greatestandleastelements,theupperandlowerboundofaset,theleastupperandgreatestlowerboundofaset3、算法及其分析（4學(xué)時(shí)）Algorithms（4hours） 3.1 算法與算法復(fù)雜度(2學(xué)時(shí))AlgorithmsandtheComplexityofAlgorithms(2hours) 算法的概念和算法的基本特征，算法的偽代碼表示，大O記號及其重要性質(zhì)、大記號、大記號、算法復(fù)雜度、最壞情況復(fù)雜度和平均復(fù)雜度 Propertiesofalgorithms,simpleexamplesofalgorithms,big-Onotation,big-omegaandbig-thetanotation,thecomplexityofalgorithms,worst-casecomplexity,average-casecomplexity,thecomplexityofsomesimplealgorithms,thecomplexityofalgorithmsandthecomputertimeusedbyalgorithms 3.2 遞歸算法(2學(xué)時(shí))RecursiveAlgorithms(2hours) 遞歸算法及其執(zhí)行過程、使用歸納法證明遞歸算法的正確性 Recursivealgorithms,provingrecursivealgorithmscorrect4、計(jì)數(shù)基礎(chǔ)（8學(xué)時(shí)）Counting(8hours) 4.1 基本計(jì)數(shù)原理(2學(xué)時(shí))TheBasicsofCounting（2hours） 乘法原理、加法原理、容斥原理、鴿籠原理 Theproductrule,thesumrule,theprincipleofinclusion-exclusion,thepigeonholeprinciple 4.2 排列、組合與二項(xiàng)式定理(4學(xué)時(shí))Permutations,CombinationsandBinomialIdentities(4hours) 排列、組合、二項(xiàng)式定理、二項(xiàng)式系數(shù)的基本性質(zhì)，允許重復(fù)時(shí)的排列與組合、排列的生成、組合的生成算法 Permutations,combinations,thebinomialtheorem,binomialcoefficientsandidentities Permutationswithrepetition,combinationswithrepetition,generatingpermutations,generatingcombinations 4.3遞推關(guān)系（2學(xué)時(shí)） 計(jì)數(shù)問題的遞推式，線性遞推關(guān)系式的解，分治算法及其遞推式求解Countingbyusingrecurrencerelation,solvinglinearrecurrencerelations,divide-and-conquerandtheresultingrecurrencerelation5、圖和樹（12學(xué)時(shí)）Graphs(12hours) 5.1 圖的基本概念(2學(xué)時(shí))TheBasicsofGraphs(2hours) 圖的基本概念（頂點(diǎn)、邊、多重邊、簡單圖）、常見問題的圖模型、頂點(diǎn)度數(shù)、握手定理、特殊的圖（完全圖、環(huán)、輪圖、方體圖、正則圖）、二部圖、子圖、圖矩陣表示（鄰接矩陣與關(guān)聯(lián)矩陣）、圖的同構(gòu) Basicdefinitionsofgraphs(vertices,edges,multipleedges,simplegraphs),graphmodels,degreesofvertices,theHandshakingTheorem,somespecialsimplegraphs,bipartitegraphs,sub-graphs,representinggraphsusingmatrices 5.2 圖的連通性(2學(xué)時(shí))ConnectivityofGraphs(2hours) 路徑、無向圖的連通性、有向圖的連通性、頂點(diǎn)之間路徑數(shù)的計(jì)算、帶權(quán)圖、最短路徑問題 Paths,connectednessinundirectedgraphs,connectednessindirectedgraphs,countingpathsbetweenvertices,weightedgraphs,short-pathproblems 5.3 一些特殊的圖(2學(xué)時(shí))SomeSpecialGraphs(2hours) 歐拉圖、哈密爾頓圖、平面圖與歐拉公式 Eulerpathsandcircuit,Hamiltonpathsandcircuits,planargraphs,Euler’sformulaforplanargraphs 5.4樹的基本概念(2學(xué)時(shí))TheBasicsofTrees(2hours) 無向樹的定義、根樹的定義、常見問題的樹模型、樹的基本性質(zhì)、樹的遍歷、表達(dá)式的語法樹 Introductiontotrees,rootedtrees,treemodels,propertiesoftrees,treetraversal,syntaxtreesofexpressions 5.5樹的應(yīng)用(4學(xué)時(shí))ApplicationsofTrees(4hours) 哈夫曼算法及前綴碼、生成樹與最小生成樹算法 Binarysearchtrees,decisiontrees,Huffmantreesandprefixcodes,Spanningtreesandminimumspanningtrees6、代數(shù)結(jié)構(gòu)（8學(xué)時(shí)）AlgebraStructures(8hours)6.1代數(shù)系統(tǒng)一般概念（4學(xué)時(shí)）BasicConceptsofAlgebraStructures(4hours)運(yùn)算的定義和性質(zhì)，零元、單位元和逆元，代數(shù)、子代數(shù)、商代數(shù)、代數(shù)同態(tài)Operationanditsproperties,zeroelement,identityandinverse,algebra,sub-algebra,quotientalgebra,algebrahomomorphism6.2代數(shù)系統(tǒng)實(shí)例（4學(xué)時(shí)）InstancesofAlgebraStructures(4hours)群的基本概念、群元素的階、子群、陪集、正規(guī)子群、商群、格、分配格、布爾代數(shù)Group,groupelementorder,sub-group,coset,normalgroup,quotientgroup,lattice,distributivelattice,booleanalgebra（二）教學(xué)環(huán)節(jié)安排ii.TheOrganizationoftheCourse 所有講課內(nèi)容都安排相應(yīng)的習(xí)題課時(shí)： Alllectureshavecorrespondingtutorialhours,andtotal18tutorialhours:1、 邏輯與證明部分習(xí)題課（4學(xué)時(shí)） 命題邏輯安排一次2學(xué)時(shí)習(xí)題課，謂詞邏輯應(yīng)安排一次2學(xué)時(shí)的習(xí)題課。2、 集合、函數(shù)和函數(shù)部分習(xí)題課（4學(xué)時(shí)） 集合和函數(shù)安排一次2學(xué)時(shí)習(xí)題課，關(guān)系部分安排2學(xué)時(shí)習(xí)題課3、算法部分習(xí)題課（2學(xué)時(shí)4、 計(jì)數(shù)基礎(chǔ)部分習(xí)題課（2學(xué)時(shí)）5、圖和樹習(xí)題課（4學(xué)時(shí)）6、代數(shù)部分習(xí)題課（2學(xué)時(shí)（三）教學(xué)方法iii.TeachingMethodology教師在講課主要注意如下兩點(diǎn)：(1)多講解例題、習(xí)題，并注意解釋解題思路；(2)多解釋離散數(shù)學(xué)與計(jì)算機(jī)學(xué)科其他課程之間的聯(lián)系。Suggestinstructorsshould:(1)showstudentsmoreexamplesandexercises,especiallygivemoreinsightsintohowtosolveproblemsinthecourse;(2)explaintherelationshipsbetweenkeyresultsindiscretemath