离散数学教学大纲.docx

《离散数学教学大纲.docx》由会员分享，可在线阅读，更多相关《离散数学教学大纲.docx（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、离散数学教学大纲（2011年2月修订）课程名离散数学课号311019040类型必修所属学科软件工程领域方向离散数学学时68+20学分4+1教师冯伟森、栾新成、何坤、林兰先修课程线性代数、高等数学同修课程无基本目的让学生学习并掌握离散数学基本理论知识， 培养学生的数学涵养和抽象思维能力；为学生在进一步学习专业课程或解决实际问题时所需要的离散数学知识奠定坚实的基础，并受惠长远。学习收获1掌握命题逻辑和谓词逻辑的体系构造、表达实现和有效推理的方法与技术。 2掌握二元关系的理论，特别是关系的性质和运算，熟悉典型的二元关系；掌握函数的性质和运算以利于构造其他的数学模型。3掌握图论的基本知识和解决有关图论

2、问题的基本技能，熟悉各种典型图类性质特征及相关算法的应用技巧、了解应用背景。 4掌握格和布尔代数的相关知识以及在计算机科学中的应用。5. 掌握形式语言和有限状态自动机的相关知识，为以后学习相关专业课程打下基础。6. 了解代数系统的基本知识。教学方式课堂讲授，每周讲授4学时。教材离散数学，冯伟森、栾新成、石兵编（机械工业出版社 2011.2） 参考书目1、离散数学及其应用（原书第5版）（Discrete Mathematical and Its Applications），Kenneth.Rosen 著， 袁崇义 屈婉玲 等译 机械工业出版社（2007.6） 2、离散数学（修订版）耿素云、屈婉玲

3、 高等教育出版社 （20044）3、离散数学学习指导与习题解析 耿素云、屈婉玲 高等教育出版社 200534、应用离散数学，方景龙 王毅刚 编著 人民邮电出版社（2005.8）5、离散数学常见题型解析及模拟题，傅彦，西北工业大学出版社 （2004）考试方式笔试成绩评定作业和半期考试、到课情况等综合占30%，期末考试占70%。助教需求每个大班安排1一2名助教负责作业批改和答疑。实验条件需求内容提要第1章 命题逻辑（12个学时）1 命题、真值、逻辑联结词、合适公式及真值表、重言式、矛盾式、可满足公式。2 命题公式的等价、基本等价式、等价的性质、对偶式、联结词的完备集、命题公式的范式构造。3 命题公

4、式的蕴含、基本蕴含式、蕴含的性质。4 命题逻辑的推理方法、规则、过程、消解原理的应用。第2章 一阶谓词逻辑（8个学时）1 个体域、量词、谓词合适公式及其解释。2 谓词公式的等价、基本等价式、前束范式、Skolem范式构造。3 谓词公式的蕴含、基本蕴含式。4 谓词逻辑的推理方法和规则、消解法应用。第3章 集合代数集合间的并、交、差、补、对称差等运算，以及幂集、笛卡尔集的构造及相关的证明方法。（该章主要靠学生自学，课堂上只讲述幂集、笛卡尔集的定义，建议放到第4章讲述，因此未单独安排学时）第4章 二元关系（4个学时）1. 二元关系的定义、以及关系的集合、矩阵和关系图表示。2. 二元关系的自反、反自反

5、、对称、反对称、传递等性质。3. 关系的并、交、补、复合及逆运算、以及闭包运算。第5章 特殊关系（6个学时）1. 等价关系、等价类、集合的划分与等价关系。2. 偏序关系、偏序集、哈斯图。3. 全序集与良序集、全序关系与拓扑排序。第6章 函数（4个学时）1. 函数的定义、单射、满射和双射、函数的运算，以及函数的递归定义。2. 集合的基数、可数集与不可数集、Cantor定理。第8章 基本计数方法（2个学时）1. 容斥原理、鸽巢原理。第10章 图的基本概念（6个学时）1. 无向图与有向图基本概念、图论基本定理、特殊图类、子图和补图、图的同构问题。2. 图的道路、回路、连通性问题、连通度定理。3. 图

6、的邻接矩阵、关联矩阵、回路矩阵问题。第11章 树及其应用（4个学时）1. 树、生成树的概念、最小生成树算法。2. 根树、最优树与编码。第12章 平面图及其应用（6个学时）1. 平面图、欧拉公式、对偶图问题。2. 平面图的点着色与图的着色第13章 欧拉图与哈密顿图（6个学时）1. 欧拉图及其应用。2. 哈密顿图及其应用。第14章 代数系统（2个学时）1. 二元运算及其性质。2. 代数系统。第15章 半群与群（2个学时） 1. 几个典型代数系统。 2. 同态与同构。第17章 格与布尔代数（8个学时）1 格的定义及性质、子格与格同态。2 分配格、有补格、Demorgan律。3 布尔代数。4. 布尔表

7、达式。第18章 应用（10个学时） 1. 串和语言。 2. 形式文法。 3. 有限状态自动机。 4. 有限状态机与正则语言。进度安排1、本期教学内容共计安排了80个学时（含习题课），考虑到清明、端午及“5.1”放假和半期考试、总复习需占用46个学时，老师们可根据自己的实际情况进行适当调整；2、第三章关于集合的内容，由于学生在中学阶段的学习中大部分内容已学习过，因此主要安排学生自学，笛卡尔集和幂集的内容可以放到第4章和关系一起讲述；3、由于离散数学作为一门数学课程，习题训练是个重要环节，但由于该书的部分习题较难，请大家在布置习题时注意；4、由于学生普遍反映对习题不知道怎样下手，因此在主要章节讲授完成后，我们安排了一次习题课（共计有7次），大家可利用此时间对前面的主要内容进行总结，同时向学生讲解一些典型例题和习题以指导学生；5、实验：可在数理逻辑、关系、图论及布尔代数部分各布置一次实验；6、习题课进度安排：1）第1章结束后（命题逻辑）2）第2章结束后（谓词逻辑）3）第4章结束后（关系的概念及关系的闭包）4）第5、6章结束后（特殊关系和函数）5）第10章结束后（图的基本概念和表示）6）第11、12、13章结束后（特殊图）7）第17章结束后（格与布尔代数）5