集合论与图论

1、.,1,集合论与图论Set Theory and Graph Theory,主讲： 姜守旭 博士/教授/教学带头人/博导 办公室：综合楼411 手机email： 课程网站： 空间： 答疑地点：？ 答疑时间：？,School of Computer Science & Technology Harbin Institute of Technology,.,2,2020/7/7,2,主要内容,1. 认识教育 2. 理解专业 3. 了解课程 4. 寄语,.,3,1. 认识教育,1.1 教育的目的 1.2 教育的本质 1.3 教育的方法 1.4 教育的动力 1.5 教育的灵魂

2、,.,4,1.1 教育的目的,明德亲民，修身治世 “天命之谓性，率性之谓道，修道之谓教”中庸 “玉不琢，不成器；人不学，不知道。是故古之王者建国君民，教学为先”学记 “大学之道，在明明德，在亲民，在止于至善”“古之欲明明德于天下者，先治其国。欲治其国者，先齐其家。欲齐其家者，先修其身。欲修其身者，先正其心。欲正其心者，先诚其意”大学 “好学近乎知，力行近乎仁，知耻近乎勇。知斯三者，则知所以修身；知所以修身，则知所以治人；知所以治人，则知所以治天下国家矣”。中庸 以正确的方式认识世界（由直观到概念）叔本华,Computing CurriculaACM/IEEE-CS CC1991/CC2001/

3、CC2005 CS2008/CS2013 SE2003/SE2014 计算机科学与技术专业发展战略研究报告暨专业规范(CCC2006)教育部计算机教指委 知识、能力、素质,.,5,1.2 教育的本质,“教育就是当你把所学的东西都忘掉后，最终剩下的东西！ ”英国哲学家怀特海德 “能忘掉在学校学的东西，剩下的才是教育”爱因斯坦 “教育无非是一切已学过的东西都遗忘掉的时候所剩下的东西”美国物理学家劳厄 “最终剩下的东西就是一个人的创新意识和学习能力。”美国教育家布鲁纳,.,6,1.2 教育的本质,创新意识 人类知识的创造、科学的进展都有前因后果，来龙去脉。 故勤奋学习，全面掌握文献，积累深厚基础，加

4、上追根到底，万事必问为什么的好奇心，就是创新的源泉。 前者是学，后者是问。学而不问则殆，问而不学则罔（孔子曰：学而不思则罔，思而不学则殆）。 学而问，问而思，思而行，行而果，这就是创新 徐光宪院士,.,7,1.2 教育的本质,创新意识 关键是怀疑与发问 哥伦比亚大学教育学院的林晓东教授就“中国学生常会遇到哪些问题？建议他们提高哪些技能？” 请教了35位美国大学教授 良好的写作能力 提出问题并批判性思考问题的能力 良好的表达和沟通能力，特别是跟教授和同学 问题驱动的教学与学习方法,每一个知识点的介绍、每一种方法的引出、每一个定理的证明都应该首先弄清其背景，为什么要学？是为了解决什么问题？当初是怎

5、么想出来的？为什么是正确的/有效的？怎么证明？还有更好的方法吗？,.,8,1.2 教育的本质,学习能力 关键是资料的获取 要快、要会甄别、要有选择 除了教材之外，为学生提供一些相关的辅助资料，关键要教会学生如何获取资料（google/baidu） 经典的图书 校图书馆的电子资源：相关的会议与刊物 相关的研究群体的个人主页 ,.,9,1.3 教育的方法,引导示范 “务学不如务求师。师者，人之模范也” 扬子法言-学行 重复实践 “只要功夫深，铁杵磨成针”“熟能生巧” 纸上得来终觉浅，绝知此事要躬行 人格绝不是靠所听到的和所说出来的言语而是靠劳动和行动来形成的。因此，最重要的教育方法总是鼓励学生去实

6、际行动。 爱因斯坦,.,10,1.4 教育的动力,面向需求 目标驱动、学习成效驱动 关键：了解需求、理解需求、定位需求 持续改进 “不断地提高教育质量是教育的永恒主题” 关键因素 质量要求 全员参与 自愿改变 沟通交流,.,11,1.5 教育的灵魂,独立精神 “没有自由思想，没有独立精神，即不能发扬真理，即不能研究学术” 陈寅恪 “学校的目标应当是培养独立工作和独立思考的人，这些人把为社会服务看作自己最高的人生问题” 爱因斯坦 自由思想 “囊括大典，网罗众家；思想自由，兼容并包” 蔡元培 “没有思想自由，就不可能有学术创新”周海中 “科学同思想自由是不可分离的” 张岱年,.,12,2020/7

7、/7,12,主要内容,1. 认识教育 2. 理解专业 3. 了解课程 4. 寄语,.,13,2. 理解专业,2.1 专业性质 2.2 专业特征 2.3 培养目标 2.4 毕业要求 2.5 课程体系,2020/7/7,.,14,2.1 专业性质-新工科对专业的影响,以新工科推动办学模式变革 由学科导向转向需求导向 由专业分割转向跨界融合 由适应服务转向支撑引领 以新工科推动理念变革 坚持学生中心、坚持结果导向、坚持持续改进 以新工科推动专业变革 实现人才培养结构与国家需求相匹配 学科专业体系与产业链、创新链、人才链相衔接,2020/7/7,.,15,2.1 专业性质-新工科对专业的影响,以新工科

8、推动培养模式变革 完善多主体协同育人 探索多学科交叉融合 探索个性化培养模式 打破传统教育的时空界限和学校围墙 以新工科推动组织变革 推进建设现代产业学院 探索建设未来技术学院,2020/7/7,.,16,2.1 专业性质-以计算机专业为例,计算学科是一门基础技术学科 在科技发展中占有重要地位 计算机技术是信息化建设的核心技术 信息化建设需要大量人才 计算机技术是一种广泛应用的技术 在人类的生产和生活中占有重要地位,2020/7/7,.,17,2.1 专业性质-以计算机专业为例,内涵 通过在计算机上建立模型和系统，模拟实际过程进行科学调查和研究 通过数据搜集、存储、传输与处理等进行问题求解 包

9、括科学、工程、技术和应用。 根本问题 “什么能、且如何被有效地实现自动计算”,.,18,2.2 专业特征-计算机相关专业,学科形态,绑定、大问题复杂性、概念和形式模型 一致性和完备性、效率、演化、抽象层次 按空间排序、重用、安全性、折衷与决策 按时间排序,核心概念,基本知识体系,知识领域,计算机科学与技术/软件工程/网络空间与安全/物联网工程/生物信息技术/数据科学与数据技术/人工智能,基 本 技 术、基 本 工 具、新 技 术、新 工 具,技 术,.,19,2.2 专业特征-计算机专业,核心是抽象思维与逻辑思维能力的训练 本学科的基本教育原理抽象第一 抽象思维能力的培养比较难，需要反复训练，

10、其目的是学会表示事物，关键是离散化、符号化、形式化、模型化的训练 逻辑思维能力的培养相对简单一些，其目的是学会描述各种处理流程，关键是编程的训练，目前学生中有相当一部分存在编程障碍 典型代表：图灵机模型(有穷自动机),.,20,工程教育专业认证-用标准引导,工程教育专业认证 是国际通行的工程教育质量保证制度，也是实现工程教育国际互认和工程师资格国际互认的重要基础。 要求专业从培养目标到毕业要求，再到课程体系，最后到教学落实、评价与反馈，进行系统的设计与实施。 工程教育专业认证倡导的教育理念 以学生为中心 产出导向（OBE） 持续改进 工程教育专业认证标准的基本内容 分通用标准和专业补充标准 通

11、用标准：学生、培养目标、毕业要求、持续改进、课程体系、师资队伍、支持条件,.,21,OBE的关键要素,三个目标 培养目标、毕业要求、课程目标 三个支撑 毕业要求支撑培养目标 课程体系支撑毕业要求 课程目标支撑毕业要求指标点 三个机制 培养目标的评价机制 毕业要求的评价机制 合理性？ 达成情况？ 课程目标的评价机制,.,22,认证对培养目标的要求,有公开的、符合学校定位的、适应社会经济发展需要的培养目标。 内涵 是对毕业生毕业后5年左右能够达成的职业和专业成就的总体描述。 根据内外部需求和条件（学校定位、专业具备的资源条件、社会需求、利益相关者的期望） 通过各种方式使利益相关者（特别是教师）了解

12、和参与培养目标的制定过程 有明确的公开渠道公布和解读培养目标,.,23,认证对培养目标的要求,定期评价培养目标的合理性并根据评价结果对培养目标进行修订，评价与修订过程有行业或企业专家参与。 内涵 对培养目标进行合理性评价是修订培养目标的基础工作。 合理性是指专业培养目标与学校定位、专业具备的资源条件、社会需求和利益相关者的期望等内外需求和条件的符合度。 要求企业或行业专家参与评价修订工作，是为了保证评价和修订工作能更好地反映行业的人才需求，使专业的人才培养工作更加符合行业的需求,2020/7/7,.,24,力求培养在教育/研究/工业/社会服务等领域 能够引领社会发展的未来领军型人才，毕业生 （

13、1）具有正确的世界观、人生观与价值观，具有环保/经济意识； （2）熟悉本专业国内外现状和发展趋势； （3）具备计算思维能力，能够综合运用所学知识，独立解决与计算相关的复杂工程技术问题； （4）能够设计与实现大型计算机软硬件系统； （5）能够建立或应用新型计算模式并能设计相关算法以解决复杂的计算问题； （6）培养学生将基本原理与技术应用于计算学科研究以及计算系统设计、开发与应用等工作的能力。（国标）,2.3 培养目标制定-以计算机专业为例,.,25,认证对毕业要求的要求,专业必须有明确、公开的毕业要求, 毕业要求应能支撑培养目标的达成。专业应通过评价证明毕业要求的达成。专业制定的毕业要求应完全覆

14、盖以下内容： 依据：1.合理分解毕业要求到可衡量的若干指标点；2.明确指出下列每一项要求及指标点是通过什么样的教学活动来实施的；3.能够提出依据说明每一个这样的活动有合理的评价方式，对每一个学生给出是否达到要求的评价结论。,复杂工程问题的特征： （1）必须运用深入的工程原理经过分析才可能得到解决； （2）需求涉及多方面的技术、工程和其它因素，并可能相互有一定冲突； （3）需要通过建立合适的抽象模型才能解决，在建模过程中需要体现出创造性； （4）不是仅靠常用方法就可以完全解决的； （5）问题中涉及的因素可能没有完全包含在专业标准和规范中； （6）问题相关各方利益不完全一致； （7）具有较高的综合

15、性，包含多个相互关联的子问题。,.,26,认证对毕业要求的要求,1. 工程知识：能够将数学、自然科学、工程基础和专业知识用于解决复杂工程问题。 2. 问题分析：能够应用数学、自然科学和工程科学的基本原理，识别、表达、并通过文献研究分析复杂工程问题，以获得有效结论。 3. 设计/开发解决方案：能够设计针对复杂工程问题的解决方案，设计满足特定需求的系统、单元（部件）或工艺流程，并能够在设计环节中体现创新意识，考虑社会、健康、安全、法律、文化以及环境等因素。,掌握解决复杂工程问题所需要的数学、自然科学、工程基础和专业知识 掌握的程度要达到能够用于解决复杂工程问题 计算机科学与技术专业 能够设计与实现

16、大型计算机软硬件系统 能够建立或应用新型计算模式并能设计相关算法以解决复杂的计算问题,.,27,认证对毕业要求的要求,4.研究：能够基于科学原理并采用科学方法对复杂工程问题进行研究，包括设计实验、分析与解释数据、并通过信息综合得到合理有效的结论。 5.使用现代工具：能够针对复杂工程问题，开发、选择与使用恰当的技术、资源、现代工程工具和信息技术工具，包括对复杂工程问题的预测与模拟，并能够理解其局限性。 6.工程与社会：能够基于工程相关背景知识进行合理分析，评价专业工程实践和复杂工程问题解决方案对社会、健康、安全、法律以及文化的影响，并理解应承担的责任。,.,28,认证对毕业要求的要求,7.环境和

17、可持续发展：能够理解和评价针对复杂工程问题的工程实践对环境、社会可持续发展的影响。 8.职业规范：具有人文社会科学素养、社会责任感，能够在工程实践中理解并遵守工程职业道德和规范，履行责任。 9.个人和团队：能够在多学科背景下的团队中承担个体、团队成员以及负责人的角色。,.,29,认证对毕业要求的要求,10.沟通：能够就复杂工程问题与业界同行及社会公众进行有效沟通和交流，包括撰写报告和设计文稿、陈述发言、清晰表达或回应指令。并具备一定的国际视野，能够在跨文化背景下进行沟通和交流。 11.项目管理：理解并掌握工程管理原理与经济决策方法，并能在多学科环境中应用。 12.终身学习：具有自主学习和终身学

18、习的意识，有不断学习和适应发展的能力。,毕业时必须达成的能力要求 需要分解到课程体系的相应教学活动中去落实 “复杂工程问题”在8条中出现了9次 “多学科背景下”、“跨文化背景下”、“多学科环境中”,2020/7/7,.,30,知识结构 程序设计基础、离散结构、算法与复杂度、计算机体系结构与组织、操作系统、软件工程、网络及其计算、信息管理、计算机科学与数值方法、社会与职业问题、理论与专业基础知识。 能力结构 科学思维与理论分析能力、系统分析与设计能力、运用知识求解问题能力、系统开发与调试能力、组织、协调与项目管理能力、表达与沟通能力、英语理解与沟通能力、自学能力、独立思考与创新能力、实践动手能力

19、。 综合素质 研究素质、个性素质、文化素质、社会素质、精英素质、身心素质、工程素质,2.4 毕业要求(HIT-CS 2008),2020/7/7,.,31,研究素质 具有良好的科学思维和科学态度，对未知世界有强烈的好奇心和研究兴趣 个性素质 培养协同意识，塑造利他精神，健全人格；挖掘自己的潜力和爱好，对待事物有独立见解；具有理性批判、自主学习和终身学习的意识和习惯 文化素质 具有一定的文学艺术修养，及法律、经济、管理等方面的知识,2.4 毕业要求(HIT-CS 2008),2020/7/7,.,32,社会素质 爱国敬业，具有科学的世界观、人生观、价值观，具有团队合作精神，自觉遵守社会公德和职业

20、道德，具有诚信意识和宽容的心态 精英素质 有高度的历史和社会责任感，有一定的领导意识，有国际视野及跨文化交流能力 身心素质 养成良好的健身习惯，具有乐观向上的生活态度，掌握调节心态的方式和方法，有较强的抗挫折能力 工程素质 具有工程观念，能用工程的思想与方法分析和解决实际问题,2.4 毕业要求(HIT-CS 2008),.,33,认证对课程体系的要求,课程设置能支持毕业要求的达成，课程体系设计有企业或行业专家参与。 内涵：专业的课程设置能够“支持”毕业要求的达成。 （1）整个课程体系能够支撑全部毕业要求，即在课程矩阵中，每项毕业要求指标点都有合适的课程支撑，并且对支撑关系能够进行合理的解释；

21、（2）每门课程能够实现其在课程体系中的作用，即课程大纲中明确建立了课程目标与相关毕业要求指标点的对应关系，课程内容与教学方式能够有效实现课程目标，课程考核的方式、内容和评分标准能够针对课程目标设计，考核结果能够证明课程目标的达成情况。 （3）要求企业或行业专家参与课程体系设计过程的目的是保证课程内容及时更新，与行业实际发展相适应。,.,34,认证对课程体系的要求,课程设置能支持毕业要求的达成，课程体系设计有企业或行业专家参与。 内涵：专业的课程设置能够“支持”毕业要求的达成。 （4）支持毕业要求的所有课程都应该将 “解决复杂工程问题”的能力培养作为教学的背景目标，各类课程应各司其责，共同支撑该

22、能力的达成。 重点强调： （1）课程体系需要系统设计，勿忽视对非技术性能力的支撑。 （2）课程矩阵需要合理布局，每项毕业要求指标点应该设置高支撑课程，既要避免支撑的密集重叠，也要避免支撑不足。 （3）课程需要合理承担毕业要求指标点，课程内容和教学方法需要与所支撑的毕业要求指标点相匹配，形成有效支撑。,.,35,课程体系的构建原则,课程设置能支持毕业要求的达成，课程体系设计有企业或行业专家参与。课程体系必须包括： 1与本专业毕业要求相适应的数学与自然科学类课程（至少占总学分的15%）。 使学生掌握理论和实验方法，为表述工程问题、选择恰当的数学模型、进行分析推理奠定基础 2符合本专业毕业要求的工程

23、基础类课程、专业基础类课程与专业类课程（至少占总学分的30%）。 工程基础类课程和专业基础类课程能体现数学和自然科学在本专业应用能力培养，专业类课程能体现系统设计和实现能力的培养。,.,36,认证对课程体系的要求,3.工程实践与毕业设计（论文）（至少占总学分的20%）。 设置完善的实践教学体系，并与企业合作，开展实习、实训，培养学生的实践能力和创新能力。毕业设计（论文）选题要结合本专业的工程实际问题，培养学生的工程意识、协作精神以及综合应用所学知识解决实际问题的能力。对毕业设计（论文）的指导和考核有企业或行业专家参与。 4.人文社会科学类通识教育课程（至少占总学分的15%） 使学生在从事工程设

24、计时能够考虑经济、环境、法律、伦理等各种制约因素。,实验课程 课程设计 至少完成两个有一定规模和复杂度的系统的设计与开发 实习与实训 建立实习基地，使学生认识和参与生产实践 毕业设计（论文）,.,37,课程的分类及其定位,基础课 数学、自然科学、工程基础 培养识别、表达和分析复杂工程问题的能力 专业核心课 专业知识 培养分析/设计/研究的能力 综合性实践课 专业知识 培养综合运用知识解决实际问题的能力,.,38,2020/7/7,38,主要内容,1. 认识教育 2. 理解专业 3. 了解课程 4. 寄语,.,39,3. 了解课程,3.1 课程性质 3.2 在计算机专业中的意义 3.3 课程目标

25、 3.4 教学目的 3.5 课程的基本思想 3.6 课程特点 3.7 课程主要内容 3.8 教学要求 3.9 考试要求 3.10 教学与学习方式 3.11 教学方法 3.12 学习方法 3.13 教材及主要参考书,.,40,2020/7/7,40,3.1 课程性质,48+16学时 是一门专业基础课，本专业最重要的课程之一 需要一些工科数学分析、线性代数的知识 是数学(离散数学)的一部分，数学首先是一些工具，其次是一门语言，最后还是一种素养,.,41,集合论与图论是数学的一部分,“对于大自然这本奥秘无穷的书，我读不懂” 莎士比亚安东尼和克里奥帕特拉 （15641616） “如果不理解它的语言，没

26、有人能读懂宇宙这本伟大的书，它的语言就是数学” 伽里略（15641642） “在任何特定的理论中，只有其中包含数学的部分才是真正的科学” 康德（17241804）,.,42,集合论与图论是数学的一部分,“一门科学，只有当它能够运用数学时，才算真正发展了。” 马克思（18181883） 数学不专属自然科学，也不专属社会科学，更不专属于文学艺术。它是一种宇宙语言，为一切文明生物共有、共享。,.,43,2020/7/7,43,3.1 课程性质,为描述现实世界中的各种现象和过程提供工具 （1）简单的数学工具（集合、映射） （2）复杂一些的数学工具（关系、图） （3）数学模型（自动机、图灵机） （4）代

27、数系统（集合+运算） 格与布尔代数硬件设计和通讯系统设计的工具 半群自动机和形式语言 关系代数关系数据库的理论模型 有限域编码理论的数学基础 ,.,44,3.2 在计算机专业中的意义,能形式化就能自动化。 对计算机专业而言，形式化尤为重要。利用形式化描述给程序设计提供了方便，从而实现了自动化。,.,45,3.2 在计算机专业中的意义,集合论可以看成一种通用语言，一切必要的数据结构都可以由集合这个原始的数据结构而构造出来。 实际上，数学发展的历史可以看成是一个煞费苦心或精心制成的数据结构。首先，我们有整数，然后有有理数、代数数，在经过一阵斗争以后，我们有实数、复数、函数的一般概念等等。最后，人们

28、终于明白开头所说的思想，计算机科学家或许可以利用这个经历。 其次，19世纪后半期，数学家把函数定义为笛儿乘积的子集，从而把函数视为集合，这是严格的。但对计算机科学家是不合适宜的，他们更喜欢用规则来定义函数。,.,46,3.2 在计算机专业中的意义,集合论是数学的基础，也是计算机科学的基础。集合论和图论是算法与数据结构、形式语言与自动机、数据库原理、计算的复杂性理论等课的先修课。而图论的基本知识则将始终陪伴我们，直到。 数学要教会人如何进行逻辑推理，如何进行正确的抽象思维，如何在纷繁的事物中抓住主要的联系，并如何使用明确的概念，等等。这对计算机技术及应用也是至关重要的，在其他任何领域同样重要。,

29、.,47,计算机系统,硬件,软件,组成原理,电子技术,体系结构,数字逻辑电路,电路原理,大学物理,计算机网络,接口与通讯技术,通讯概论,安全与保密,程序设计语言,汇编语言,高级语言,编译原理,计算理论,C、C、JAVA、PB、VB,系统软件,操作系统,DOS、Windows 、UNIX,数据库,Access、Sybase 、Oracle,数据结构,人工智能,应用软件开发,离散数学：,软件工程,算法设计与分析,集合,函数,代数结构,格与布尔代数,图论,形式语言与自动机,数理逻辑,二元关系,.,48,3.3 课程目标,本课程的目标是通过理论学习，为计算机科学与技术专业的后继课及将来的科学研究提供必

30、要的相关数学知识，提供建立离散系统的数学模型的数学描述工具；使学生正确地理解概念，正确地使用概念进行推理，养成一个好的思维习惯，理解理论与实践的关系；引导学生观察生活、社会和大自然，分析事物间的联系，建立系统的模型，提出和解决其中的科学问题或应用问题。,.,49,3.3 课程目标,1.掌握集合论与图论的基本概念、基本原理、基本方法等基本知识，培养形式化、模型化的抽象思维能力，使学生能够利用集合论与图论的概念、理论与方法识别、表达计算相关的复杂工程问题，逐步学会为计算类复杂工程问题建立数学模型 2.掌握直接证明法、反证法、数学归纳法、构造法等常用的证明方法，培养机械化、自动化的逻辑推理能力，使学

31、生能够利用集合论与图论的概念、理论与方法并通过文献研究分析复杂工程问题，并能获得有效的结论，理解并逐步设计求解这些问题的算法基本思想,2020/7/7,49,.,50,3.4 教学目的,该课程的设置主要是为了培养学生的抽象思维和逻辑推理能力，提高学生分析问题和解决问题的能力，提高学生的数学修养及计算机科学素质。 本课程为后继的专业基础课及专业课提供必要的数学工具，为描述离散模型提供数学语言。 要想用计算机解决问题就要为它建立数学模型，即描述研究对象及对象与对象之间的联系，并通过事物之间的联系找出事物的运动规律。 集合论与图论为此提供了强有力的描述工具与推理理论。,2020/7/7,50,.,5

32、1,3.5 课程的基本思想,我们从“集合”这个基本概念开始建立集合理论。就某种观点来看，“集合”与“性质”是同义词，是基本概念之一。 集合用来描述事物的性质我们的研究对象， 映射用来描述事物之间的联系运算、关系，从而为集合建立了结构。 于是，为建立系统的数学模型提供了数学描述语言工具，代数系统就是引入运算以后的集合。,.,52,3.5 课程的基本思想,集合论又提供了研究数学模型的性质，发现新联系的推理方法，从而找出事物的运动规律。 图论是上述思想的一个具体应用，事实上，图论为任何一个包含了一种二元关系的系统提供了一个数学模型；部分地，也因为使用了图解式表示方法，图就具有一种直观的和符合美学的外

33、形。 在图论中，许多结果是初等的，但也有大量的十分复杂的问题可以难倒最老练的数学家。,.,53,3.6 课程特点,自给自足，不需要预先的知识准备。学习本课的前提实在仅仅是不可捉摸的所谓“数学上的成熟”。 概念多，但都有实在的具体的实物背景，最后要落实到抽象的定义上，概念是第一位的。,.,54,3.6 课程特点,作为一门数学课，与以往不同的是以证明为主而不是以计算为主。因此，要学会证明技术，学会分析问题和解决问题的思想方法。它能培养你诚实！ 与计算机科学/技术联系紧密，是最常用、最有用的数学内容之一。 没有什么公式要你背。需要的仅是智力上的成熟并乐意进行独立思考！,.,55,2020/7/7,5

34、5,3.7 课程主要内容,工大80年开始将离散数学分成三门课：集合论与图论、近世代数、数理逻辑 集合论 集合及其运算、映射及其合成、关系及其运算、无穷集合及其基数。 图论 图的一些基本概念、一些特殊的图、树及其性质、割点和桥、连通度、平面图、图的着色、有向图。,.,56,2020/7/7,56,3.8 教学要求,掌握集合论与图论的基本概念、基本原理、基本方法等基本知识，并且对其具有比较全面、系统的认识和正确的理解； 掌握运用基本知识进行推理的初步能力，并能将其应用到计算机科学领域内，分析和处理一些基本问题； 掌握常用的证明方法：直接证明法、反证法、数学归纳法、构造法等，具有一定的抽象思维和逻辑

35、思维能力，达到知识、能力、素质的协调发展。,.,57,3.9 考试要求,题型 选择、填空、判断、简答、证明、论述、设计、计算等 重点和难点 会在各章的开始点明 考试权重 平时成绩10%、作业占10% 期末考试占80% 考前答疑 考试前两天 保证课程目标的达成,2020/7/7,57,2020/7/7,.,58,3.10 教学方式与学习方式,教学方式 课前：明确课程在整个课程体系中的地位、作用、目的和要求；做好课程设计；准备好教案 课中：注重启发、问题驱动、案例教学、交互式 课后：批改作业、答疑 课外：科学研究、教学研究、教学法讨论 学习方式 课前：了解课程体系、课程大纲、准备课程学习资料 课中

36、：认真听讲、积极思考、发问互动 课后：主动答疑、完成作业、实验、大作业 课外：积极参加俱乐部、科技竞赛、讲座、论坛,.,59,3.11 教学方法,证明为主 要学会证明技术，学会分析问题和解决问题的思想方法 强调抽象 本课程的特点是概念多，但都有实在的、具体的实物背景，最后要落实到抽象的定义上，没有抽象就没有科学。 发现解法 已知的事物和要求的事、已知量和未知量、假设和结论，这些都是一些隔开的事物和想法，解题的过程就是要在这原先隔开的事物或想法之间找出联系。 瞻前顾后 站在新的概念、理论、方法和观点看已学过的知识有时会更清楚，显得简单，理解会更深刻 随时指出本课的内容在计算机专业中的应用,202

37、0/7/7,59,.,60,3.12 学习方法,基于问题的学习（What-Why-hoW） 学习要以思考为基础 一般的学习只是一种模仿，而没有任何创用 思考由怀疑和答案组成，学习便是经常怀疑，经常随时发问。怀疑是智慧的大门，知道得越多，就越会发问，而问题就越多。所以，发问使人进步，发问和答案一样重要。 基础知识是研究的工具 在独立思考之前，必须先有基础知识。所谓“获得基础知识”并不是形式上读过某门课程，而是将学过的东西完全弄懂(什么叫做精通C语言？)。 学习中，概念是第一位的，概念的背景（直观原型）、抽象定义的内涵和外延要准确，应用时才能自如。,2020/7/7,60,.,61,3.12 学习

38、方法,要敢于犯错误 学习的一种方法，经常还是唯一的方法，就在于首先犯错误。我们在学习，多数时间在通过犯错误学习。 教学、学习是一个过程 是毛毛雨，需不断地滋润 教师在传授知识和技术的过程中，偶尔会传授教训， 但这种教训如果没有经过你的亲身体验，不会变成有用的经验。 知识没有教训作为根基，只能是纸上谈兵。 上课、读书、复习、做作业、讨论、做实验、自己编程序、上机调试排错是绝对必要的 那种抄别人作业、考试作弊、不上课不看书，是没有希望的。一个作弊的民族怎么可能进步和强大呢？ 提倡学习中互相讨论、辩论、提出不同的方法。,2020/7/7,61,.,62,3.12 学习方法,记住，数学以及其他理论学科

39、的书，不能读得太快，也不能期望读一遍就全弄懂。 生活的根基不仅包括我们得到的所有的答案，而且还应该包括我们提出的所有问题。,2020/7/7,62,.,63,3.12 学习方法,辅导答疑 这是任课教师与学生直接交流、沟通思想的时间。对学生一视同仁应当是教师的基本心理，而善待每个学生是教师应当坚持的教育原则。 充分利用好答疑时间，是与老师交流的机会，会获得意想不到的东西 教师为你解答经你努力尚未弄懂的问题。没有经你思考的习题、问题最好暂时不问，否则收获不大 教师不要立即暴露你的全部秘密让学生在你说出来之前先去猜尽量让他们自己去找出来。你可以给一些提示，创造一个稍好的环境，让学生自己去发现！增强学

40、生的信心。 把老师看成朋友或者长者，这时除谈业务外，谈理想、人生、道德、责任、如何做人,2020/7/7,63,.,64,2020/7/7,64,3.13 教材及主要参考书,王义和, 离散数学引论, 哈尔滨工业大学出版社, 2000.3. Kenneth.Rosen著,袁崇义, 屈婉玲等译,离散数学及其应用,机械工业出版社,2007.6. 曲婉玲，耿素云，张立昂，离散数学(第2版)，清华大学出版社，2008.2.,.,65,2020/7/7,65,主要内容,1. 认识教育 2. 理解专业 3. 了解课程 4. 寄语,.,66,4. 寄语,要主动学习 不要苛求课程、老师和环境，他/她/它们只是资

41、源 目标确定后要善于利用各种资源 注重对自己能力的培养 学会做人,乐于助人,多为别人着想,可以获取友谊 朋友是资源，可以终生受益 学会安排自己的时间 时间就像海绵里的水，只要肯挤，总会有的。贵在恒。 学会利用各种资源提高自己 学校的、家庭的、社会的 上学期间利用资源的唯一目的就是提高自己 不要沉迷于网络聊天与游戏,2020/7/7,66,.,67,第一篇 集合论,德国数学家康托 于1874年建立，是现代数学的基础 当今数学中的每个对象本质上都是集合。数学的各个分支在本质上都是研究这种或那种对象的集合。例如： 几何学是研究点、线、面的集合； 数学分析是研究连续函数的集合； 代数学是研究数的集合以

42、及在此集合上定义的有关运算的集合等。 因此，把集合论作为现代各种数学的基础是有道理的、合适的。 集合论也是计算机科学的重要工具。集合论在程序设计、数据结构、形式语言、操作系统等计算机科学中，都有重要应用，成为计算机科学工作者必不可少的基础知识。,2020/7/7,67,.,68,第一篇 集合论,集合论主要有以下几个特点： 它所研究的对象十分广泛。例如数、图形或其它任何客体都可作为研究的对象。 因为它研究的对象是如此广泛，为了便于研究，就必须寻找对象的共性。而要做到这一点，就必须进行抽象。 在抽象化的基础上，可以用统一的方法来研究和处理集合论中的各种问题。 集合论的主要特点是研究对象的广泛性，分析思考问题的抽象性和处理问题的统一性。正是这些特点，使得我们便于用它来描述和研究离散对象及其关系。,2020/7/7,68,.,69,第一章 集合及其运算,重点： 概念 ：集合、差、对称差、笛卡儿乘积、有穷集合的基数。 方法 ：证明两个集合相等的方法必考，必须掌握；基本的计数法则及容斥原理在古典概率论中的应用。 应用 ：古典概率模型、跳舞问题的数学模型。 难点： 容斥原理在古典概率论中的应用。,2020/7/7,69,.,70,第二章 映射,重点： 概念：映射、单（满、双）射、合成运算、置换、逆映射、特征函数 方法：置换的循环置换分解 应用：