离散结构大纲.docVIP

《离散结构》教学大纲 课程编号 ： 课程名称 ：离散结构/Discrete Structure 学时/学分：64/4 先修课程 ：高等数学、线性代数 适用专业 ：工科类 开课学院（部）、系(教研室)：计算机科学与技术学院 一、课程的性质与任务 离散结构以离散结构为主要研究对象，是计算机科学的理论基础，又是计算机应用必不可少的工具，是计算机应用与软件工程专业的核心基础课。本课程为计算机科学和技术的发展奠定了重要的数学基础，其基本思想、概念和方法广泛渗透到计算机科学和技术的各个领域。通过本课程的学习，要使学生获得：数理逻辑、集合论、代数系统、图论等方面的基本概念、基本理论和基本运算技能，为学习后继专业课程和进一步获得数学知识奠定必要的数学基础。 在传授知识的同时，要通过各个教学环节逐步培养学生的抽象思维能力、逻辑思维能力、数学建模能力、形式化程序设计能力以及综合归纳分析的能力，联系计算机科学理论，注重与计算机科学技术的实际问题相结合 二、课程的教学内容、基本要求及学时分配 （一）教学内容 1．数理逻辑 命题逻辑：逻辑与证明，命题和命题连接词，命题公式，命题公式的等值关系和蕴涵关系，范式，命题演算的推理理论。 谓词逻辑：谓词、个体和量词，谓词演算公式，谓词演算的永真公式，前束范式，谓词演算的推理理论。 2．集合论 集合：集合的基本概念，集合的运算，有序对与笛卡儿积，包含排斥原理。 关系：关系及其表示，关系的性质，等价关系，偏序关系。 函数：函数的概念，复合函数和逆函数，集合的特征函数，集合的基数。 3．代数结构 代数结构：二元运算及其性质，代数系统，同态和同构，同余关系。 群：半群和独异点，群的定义，群的性质，子群及其陪集，正规子群与满同态。 4．图论 图的基本概念、图的矩阵表示、图的连通性、欧拉图和哈密尔顿图、树、有向树、二部图、平面图、有向图。 （二）基本要求 要求学生熟练掌握命题推理及谓词推理的基本概念、基本原理。掌握两种推理的证明方法，会应用两种推理解决一些简单的实际推理问题。要求学生熟练掌握集合的基本概念、集合的运算、关系、关系的性质、等价关系、偏序关系、函数、数学归纳法及其应用，了解集合的基数、整数的性质；要求学生熟练掌握常见的代数系统的性质，群及格的性质，能理论证明群的有关结论。要求学生熟练掌握图的基本概念、会应用图的基本概念对实际问题建立图论模型，掌握树的概念及其在计算机科学中及其他科学中的应用。了解一些特殊的图如欧拉图和哈密尔顿图、二部图 平面图、竞赛图等的概念及其应用。能将所学知识与计算机科学技术的实际问题相结合 教学环节 课程内容 　学时 理论课 习题课 小 计 数理逻辑 14 3 17 集合论 14 3 17 代数结构 14 3 17 图论 10 3 13 合计 51 13 64 （四）课程内容的重点、难点 1．数理逻辑 重点：命题逻辑和谓词逻辑的推理 难点：命题逻辑和谓词逻辑的推理 2.集合论 重点：关系及其运算、等价关系与偏序关系、数学归纳法、容斥原理 难点：递推关系 3．代数结构 重点：代数系统的概念、群及其性质 难点：群 4．图论 重点：树及其性质 难点：Hamilton图、图的匹配问题 三、课程改革与特色 离散结构是一门研究离散结构的计算机科学的专业基础课。目前国内的教材与国际上经典的教程差距较大，如何选择教学内容，既能与国际接轨又能符合中国国情，正处于探索中，本大纲参考了ACM和IEEE/CS必威体育精装版推出的Computing Curricula 2004，以及教育部高等教育司组织评审通过的《中国计算机科学与技术学科教程2002》中制定的关于“离散”的知识结构 四、推荐教材及参考书 推荐教材： 《离散数学（修订版）》 　　 主 编：耿素云 屈婉玲 出版社：高等教育出版社 出版或修订时间：2004年 参考书： 《Discrete Mathematics and Its Applications》 主 编：Kenneth H. Rosen 出版社：机械工业出版社 出版或修订时间：2004年 《离散数学》 　　 主 编：贲可荣 出版社：清华大学出版社 出版或修订时间：2007年 《离散数学（第三版）》， 　　 主 编：耿素云 出版社：清华大学出版社 出版或修订时间：2004年 《离散数学（第六版）》， 　　 主 编：Richard Johnson baugh 出版社：电子工业出版社 出版或修订时间：2005年10月 《离散数学基础（第二版）》