《离散数学》课程教学大纲
|
一、课程的地位与作用
当前应用计算机技术已成为科学技术现代化的一个重要标志。计算机科学的发展和应用需要以现代数学的理论和方法作为其工具，离散数学是掌握和应用这一工具的基础，是计算机科学中基础理论的核心课程。 | |||||||||||
|
二、课程的教学目标与基本要求
通过离散数学的教学，一方面使同学掌握本课程所涉及的数学内容的基本术语、基本概念、基本定理、基本方法，为学习或应用计算机的各专业知识打下较坚实的数学基础；另一方面使学生的抽象思维能力和逻辑推理能力得到进一步的提高。
三、课程内容
1 集合1．1 集合的基本概念①集合；②子集合；③空集合；④集合的相等。
1．2 集合的基本运算①集合的运算；②集合的交；③集合的并；④集合的差；⑤集合的对称差；⑥集合的广义交；
⑦集合的广义并；⑧幂集合。
1．3 全集和集合的补①全集；②集合的补；③德·摩根定律。
1．4 自然数与自然数集①自然数；②自然数集；③数学归纳法；④集合的归纳定义。
1．5 包含与排斥原理①有限集；②包含与排斥原理。
2 关系2．1 集合的笛卡尔积集①有序对；②集合的笛卡尔积集；③有序n(n 2)元组；④n重(n 2)笛卡尔积集。
2．2 二元关系的基本概念①二元关系；②二元关系的表示；③二元关系的图形表示；④二元关系的矩表示；⑤二元关系的运算；⑥二元关系的复合运算；⑦二元关系的逆关系。
2．3 二元关系的性质①二元关系的性质；②自反的二元关系；③反自反的二元关系 ；④对称的二元关系；⑤反对称的二元关系；⑥传递的二元关系。
2．4 二元关系的闭包运算①二元关系的闭包运算；②自反闭包；③对称闭包；④传递闭包。
2．5 等价关系与集合的划分①等价关系；②等价类；③集合的划分；④商集合。
2．6 偏序关系和格①偏序关系；②偏序集；③极大元；④极小元；⑤最大元；⑥最小元； ⑦最小上界；⑧最大下界；⑨可比；⑩覆盖；⑾有序集；⑿良序集；⒀格。
2．7 链与反链①链；②反链。
3 函数与集合的势3．1 函数的基本概念①函数（映射）；②定义域；③陪域；④值域；⑤象集；⑥原象集；⑦单射函数；⑧满射函数；⑨双射函数。
3．2 函数的复合与可逆函数①函数的复合；②左可逆函数；③右可逆函数；④可逆函数。
3．3 无限集①集合的势；②无限集；③集合的势相等；④可数无限集；⑤不可数无限集； ⑥集合势大小的比较。
4 图论4．1 图的基本概念①有向图；②无向图；③顶点集；④边集；⑤自环；⑥孤立点；⑦多重边；⑧简单图；⑨完全图；⑩关联；⑾邻接；⑿图的同构；⒀子图；⒁生成子图；⒂补图；⒃图的顶点度数（次数）；⒄图的顶点度数和与边数关系。
4．2 图中的通路、图的连通性与图的矩阵表示①图中的通路；②简单通路；③初等通路；④回路；⑤简单回路；⑥初等回路（圈）；⑦连通图；⑧有向连通图；⑨有向单侧连通图；⑩有向强连通图；⑾ 图的邻接矩阵；⑿图的关联矩阵；⒀图的可达矩阵。
4．3 带权图与带权图中最短通路①带权图；②带权图的最短通路；③狄克斯瑞（Dijkstra）算法。
4．4 欧拉图①欧拉图；②欧拉通路；③欧拉回路；④欧拉定理。
4．5 哈密尔顿图与货郎担问题①哈密尔顿通路；②哈密尔顿回路（圈）；③哈密尔顿图；④哈密尔顿图的必要条件；⑤哈密尔顿图的充分条件；⑥货郎担问题；⑦最邻近算法。
4．6 二部图①二部图（偶图）；②二部图的充要条件；③二部图的匹配；④二部图的极大匹配；⑤二部图的完美匹配。
4．7 平面图①平面图；②平面图的欧拉定理；③平面图的必要条件；④平面图的区域着色。
5 树5．1 树的基本概念①树；②树中顶点与边关系公式；③树的等价定义。
5．2 连通图的生成树与带权图的最小生成树①连通图的生成树；②割集；③割集与生成树的关系；④带权图最小生成树的算法。
5．3 有序树①有向树；②根树；③有序树；④有序n (n 2)分树；⑤正则有序n (n 2) 分树。
5．4 前缀码和最优二分树①前缀码；②带权图的最优二分树；③霍夫曼（Huffman）算法。
6 群和环6．1 代数运算的基本概念①二元运算；②封闭的二元运算；③可结合的二元运算；④可交换的二元运算；⑤n元运算
6．2 代数系统和半群①代数系统；②左么元；③右么元；④么元；⑤半群；⑥含么半群（独异点）；⑦半群的同态；⑧子半群；⑨子含么半群。
6．3 群的基本概念①左逆元；②右逆元；③逆元；④群；⑤有限群；⑥交换群；⑦群同态；⑧群同构；⑨群中元素的阶。
6．4 变换群和置换群①变换含么半群；②变换群；③置换群；④n个文字对称群。
6．5 循环群①循环群。
6．6 子群、群的子集生成的群①子群。
6．7 子群的陪集①子群的陪集；②子群在群中的指数；③群中拉格朗日定理。
6．8 正规子群、商群、群同态①正规子群；②商群；③群的同态基本定理。
6．9 环和域①零元；②负元；③环；④整环；⑤可除环；⑥域；⑦有限域。
7 格与布尔代数7．1 格定义的代数系统①幂等律；②吸收律；③对偶原理。
7．2 格的代数定义①格的代数定义。
7．3 一些特殊的格①分配格；②泛上界；③泛下界；④补元；⑤有补格；⑥布尔格；⑦子格； ⑧格同态；⑨狄·摩根定理；⑩有限布尔格的唯一性定理。 | |||||||||||
|
四、时间分配 | |||||||||||
|
课程分
段标识 |
序号 |
教 学 内 容 |
教学环节（学时） | ||||||||
|
讲
课 |
习
题 |
实
验 |
上
机 |
课
外 |
小
计 | ||||||
|
Ⅳ |
1 |
集合 |
6 |
|
|
|
|
6 | |||
|
2 |
关系 |
10 |
|
|
|
|
10 | ||||
|
3 |
函数和集合的势 |
6 |
|
|
|
|
6 | ||||
|
4 |
图 |
12 |
|
|
|
|
12 | ||||
|
5 |
树 |
8 |
|
|
|
|
8 | ||||
|
6 |
群和环 |
16 |
|
|
|
|
16 | ||||
|
7 |
格与布尔代数 |
6 |
|
|
|
|
6 | ||||
|
8 |
|
|
|
|
|
|
| ||||
|
9 |
|
|
|
|
|
|
| ||||
|
10 |
|
|
|
|
|
|
| ||||
|
11 |
|
|
|
|
|
|
| ||||
|
12 |
|
|
|
|
|
|
| ||||
|
13 |
|
|
|
|
|
|
| ||||
|
14 |
|
|
|
|
|
|
| ||||
|
15 |
|
|
|
|
|
|
| ||||
|
16 |
|
|
|
|
|
|
| ||||
|
总 计 |
64 |
|
|
|
|
64 | |||||
|
五、课程说明 | |||||||||||
|
课程英文名称 |
Discrete Mathematics | ||||||||||
|
主要先修课程 |
线性代数 | ||||||||||
|
适用专业类别 |
计算机科学与技术、计算机通讯 | ||||||||||
|
主要教材（作者、教材名称、出版社） |
离散数学 叶有培 兵器工业出版社 1995
离散数学 左孝陵 上海科技出版社 1987 | ||||||||||
|
考核方式 |
考试 | ||||||||||
|
课程简介 |
离散数学是计算机科学与技术系的一门核心必修课程，它是计算机科学重要的理论基础。它以集合、代数系统、图与树为研究对象。修学该课程必须掌握线性代数的基本理论，具有较好的逻辑思维的能力。课程的教学目标是提高学生抽象思维与逻辑思维的能力，为培养计算机系统设计、算法设计等人才方面打下良好的基础。本课程坚持理论和应用相结合的原则，理论上主要叙述集合的运算、二元关系、代数系统、图与树等基本理论及其应用。学习成绩的评定将通过理论考试及作业的表述和表达水平来综合评定。 | ||||||||||
|
必 开
实 验
项 目 |
序号 |
项 目 名 称 |
学时 | ||||||||
|
1 |
|
| |||||||||
|
2 |
|
| |||||||||
|
3 |
|
| |||||||||
|
4 |
|
| |||||||||
|
5 |
|
| |||||||||
|
6 |
|
| |||||||||
|
7 |
|
| |||||||||
|
8 |
|
| |||||||||