北京航空航天大学离散数学ChapterPPT课件.pptx

DiscreteMathematicsandItsApplications IntroductoryLecture 3 21 2020 1 Instructor Dr Jin XingHAOOffice RoomA906 NewMainBuildingOfficeHour ByemailappointmentEmail hao 3 21 2020 2 CourseOverview CourseName DiscreteMathematicsCourseHourandCredit 40 2 5 3 21 2020 3 TextbookandReferences Textbook罗森著 袁崇义等译 离散数学及其应用 原书第6版 本科教学版 机械工业出版社 2011 11ReferencesRosen K H DiscreteMathematicsandItsApplications 7Edition McGrawHill 2013 离散数学 耿素云 屈婉玲编著 清华大学出版社 2005离散数学 左孝凌等编著 上海科学技术文献出版社 1982O 3 21 2020 4 CourseOverview TeachingApproachLecturesCasesLabs Afterclass GradingAttendanceandonline offlineparticipation10 QuizandAssignments30 FinalExamination60 3 21 2020 5 CourseSchedule 3 21 2020 6 WhatisDiscreteMathematics Discretemathematicsisthepartofmathematicsdevotedtothestudyofdiscrete asopposedtocontinuous objects Calculusdealswithcontinuousobjectsandisnotpartofdiscretemathematics Examplesofdiscreteobjects integers stepstakenbyacomputerprogram distinctpathstotravelfrompointAtopointBonamapalongaroadnetwork waystopickawinningsetofnumbersinalottery Acourseindiscretemathematicsprovidesthemathematicalbackgroundneededforallsubsequentcoursesincomputerscienceandforallsubsequentcoursesinthemanybranchesofdiscretemathematics 3 21 2020 7 KindsofProblemsSolvedUsingDiscreteMathematics Howmanywayscanapasswordbechosenfollowingspecificrules HowmanyvalidInternetaddressesarethere Whatistheprobabilityofwinningaparticularlottery Istherealinkbetweentwocomputersinanetwork HowcanIidentifyspamemailmessages HowcanIencryptamessagesothatnounintendedrecipientcanreadit Howcanwebuildacircuitthataddstwointegers 3 21 2020 8 KindsofProblemsSolvedUsingDiscreteMathematics Whatistheshortestpathbetweentwocitiesusingatransportationsystem Findtheshortesttourthatvisitseachofagroupofcitiesonlyonceandthenendsinthestartingcity HowcanwerepresentEnglishsentencessothatacomputercanreasonwiththem Howcanweprovethatthereareinfinitelymanyprimenumbers Howcanalistofintegersbesortedsothattheintegersareinincreasingorder Howmanystepsarerequiredtodosuchasorting Howcanitbeprovedthatasortingalgorithmalwayscorrectlysortsalist 3 21 2020 9 GoalsofaCourseinDiscreteMathematics MathematicalReasoning Abilitytoread understand andconstructmathematicalargumentsandproofs CombinatorialAnalysis Techniquesforcountingobjectsofdifferentkinds DiscreteStructures Abstractmathematicalstructuresthatrepresentobjectsandtherelationshipsbetweenthem Examplesaresets permutations relations graphs trees andfinitestatemachines 3 21 2020 10 GoalsofaCourseinDiscreteMathematics AlgorithmicThinking Onewaytosolvemanyproblemsistospecifyanalgorithm Analgorithmisasequenceofstepsthatcanbefollowedtosolveanyinstanceofaparticularproblem Algorithmicthinkinginvolvesspecifyingalgorithms analyzingthememoryandtimerequiredbyanexecutionofthealgorithm andverifyingthatthealgorithmwillproducethecorrectanswer ApplicationsandModeling Itisimportanttoappreciateandunderstandthewiderangeofapplicationsofthetopicsindiscretemathematicsanddeveloptheabilitytodevelopnewmodelsinvariousdomains Conceptsfromdiscretemathematicshavenotonlybeenusedtoaddressproblemsincomputing buthavebeenappliedtosolveproblemsinmanyareassuchaschemistry biology linguistics geography business etc 3 21 2020 11 DiscreteMathematicsisaGatewayCourse Topicsindiscretemathematicswillbeimportantinmanycoursesthatyouwilltakeinthefuture ComputerScience ComputerArchitecture DataStructures Algorithms ProgrammingLanguages Compilers ComputerSecurity Databases ArtificialIntelligence Networking Graphics GameDesign TheoryofComputation etc Mathematics Logic SetTheory Probability NumberTheory AbstractAlgebra Combinatorics GraphThe