离散数学课程教学大纲.doc

离散数学课程教学大纲

课程名称：离散数学/ Discrete Mathematics
学时/学分：60学时/4学分（其中课内教学60学时，上机实验0学时）
先修课程：数学分析、高等代数
适用专业：信息与计算科学
开课院系：数学与计算机科学学院
一、课程的性质与任务
离散数学是现代数学的一个重要分支,是信息与计算科学专业的专业主干课之一，课程结合信息与计算科学的特点研究离散对象及相互关系，对提高学生的抽象思维与逻辑推理能力有重要作用.它以研究离散量的结构和相互间的关系为主要目标,在信息与计算科学中的数据结构、操作系统等有广泛的应用。
二、课程内容、基本要求与学时分配
介绍本课程的现状及其相关知识,介绍本课程的教学安排和学习方法,介绍本课程的主要内容等。
（一）命题逻辑 10学时
1.理解命题的概念，掌握常用的命题联结词。
2.理解命题的合式公式概念，会用真值表来判别公式的真假。
3.知道公式的等价关系和蕴含关系,会利用真值表和常用的基本等值式作等值演算。
4.会用真值表法及等值演算求合式公式的主析取范式和主合取范式。
5.知道命题演算的推理理论，掌握直接证明、条件证明、反证法，能进行一些简单推理。
重点：求合式公式的主析取范式和主合取范式。
难点：利用基本等值作等值演算。
（二）谓词逻辑 6学时
1.熟悉一阶谓词逻辑的谓词、量词等概念。知道谓词公式的概念。
2.知道谓词演算中关于量词的等值式。
2.熟悉常见谓词演算的基本规则；掌握谓词演算的推理理论。
重点：谓词演算的基本规则。
难点：谓词演算中关于量词的等值式。
（三）集合的基本概念 2学时
1.理解集合的概念，掌握集合和元素间的关系。
2.熟悉集合与集合之间的关系（相等、包含）。
3.熟练掌握集合之间的运算及基本运算规律。
4.掌握幂集及笛卡尔积的计算。
重点：集合之间的运算及基本运算规律。
难点：幂集及笛卡尔积的计算。
（四）关系与函数 8学时
1.理解关系的基本概念，掌握关系的图及其矩阵表示方法。
2.掌握关系的运算，理解关系的几种特性。
3.掌握关系的闭包运算。
4.理解等价关系、等价类、商集、偏序关系的概念，会用哈斯图表示偏序关系，会根据等价关系求等价类,理解并掌握等价关系与集合划分之间的重要关系会求出等价关系所产生的一个集合的划分。
5.了解函数的基本概念，掌握复合函数、逆函数的计算。
重点：关系的几种特性、关系的闭包运算。
难点：哈斯图表示偏序关系、商集。
（五）代数结构的基本概念 6学时
1.理解代数系统的概念及性质。
2.掌握同态与同构.
重点：同态与同构的概念。
难点：同态像与同态核。
（六）半群与群 8学时
1.了解半群和独异点的概念和性质
2.掌握群的概念和性质,掌握循环群和置换群的基本特性,理解子群与陪集的概念,掌握群的同态与同构。
重点：循环群和置换群的基本特性。
难点：子群与陪集。
（七）格与布尔代数 2学时
1.掌握格的概念和初等性质，知道格与代数系统的对应关系。
2.了解一些特殊格的概念（有界格、分配格）。
3.掌握布尔代数的概念及布尔表达式。
重点：特殊格的概念。
难点：布尔表达式。
(八)图的基本概念及其矩阵表示 4学时
1.掌握有关图的基本概念。
2.掌握通路和回路的概念。
3.掌握图的矩阵表示法（邻接矩阵、关联矩阵）。
重点：图的概念及其矩阵表示。
难点：通路与回路。
（九）图的连通性 8学时
1. 理解图的连通性，掌握连通性的判别方法，对简单有向图会判断强连通、单向连通还是弱连通。能熟练地求图的点割集、边割集，割点、割边。
2. 理解欧拉图、欧拉通路、欧拉回路的概念，知道哈密顿图的概念及哈密顿图与欧拉图的区别，掌握相关的重要结论，会判断一个图是否是欧拉图或哈密顿图。
3.理解二分图的概念,会求最大匹配.
重点：点割集、边割集及欧拉图。
难点：哈密顿图的判定及最大匹配。
(十) 树 4学时
1.理解有向树、生成树、最小生成树的概念，会由连通图来寻找生成树,掌握最小生成树的构造方法。
2.理解带权树、位置二元树等概念，掌握Huffman算法，熟悉前缀码及其应用。
重点：最小生成树及Huffman树。
难点：位置二元树。
(十一)平面图 2学时
1.了解平面图的基本概念，掌握欧拉公式，了解相关的重要结论。
2.了解平面图的点着色, 了解四色定理。
重点：欧拉公式及其应用、平面图着色的韦尔齐.鲍威尔算法。
难点：四色定理的证明。
三、推荐教材和主要参考书
1．推荐教材：
（1）蔡英，刘均梅.离散数学，西安：西安电子科技大学出版社，2003.6。
（2）耿素云等，离散数学，北京：高等教育出版社，1998。
2．推荐参考书：
（1）左孝凌等，离散数学，上海：上海科学技术文献出版社，1982.9 。
（2）尹宝林等，离散数学，北京，高等教育出版社，1998。
（3）李盘林等，离散数学，北京：高等教育出版社，1999。
（4）徐洁磐，离散数学导论，北京：高等教育出版社，1982。

　　　　　大纲制订者：冯天祥
大纲审定者：王绍恒