<<返回综合资料

离散数学教学大纲

Discrete Mathematics

 

【课程编号】

【学分】3.5          【参考学时】56

【编写】             【审    核】

(一)授课对象

四年制本科数学与应用数学、信息与计算科学等专业。

(二)教学内容

1.数理逻辑部分

1)命题公式(谓词公式)及表示法、联结词;(2)命题公式(谓词公式)的重言式、蕴含式、等价式。(3)命题公式的范式、谓词公式的前束范式;(4)约束变元和自由变元;(5)推理理论。

2.集合与关系部分

1)集合的概念与表示法,集合的运算;(2)序偶与笛卡尔积;(3)二元关系、关系的五大性质(4)复合关系与逆关系;(5)关系的闭包运算;(6)等价关系、划分;(7)相容关系、覆盖;(7)偏序关系、偏序集。

3.代数系统部分

1)半群;(2)群、子群;(3)阿贝尔群、循环群;(4)同态与同构,同余关系;(6)环与域的基本概念。

4.图论部分

1)图及其相关概念,图的同构;(2)路和回路、连通性;(3)图的矩阵表示;(3)欧拉图和汉密尔顿图;(4)树、生成树。

(三)主要参考书

1.左孝凌主编 《离散数学》, 上海科学技术出版社,1982年版;

2.刘光奇等编 《离散数学》, 复旦大学出版社,1988年版;

3.张锦文等编 《离散数学引论》 天津科学技术出版社,1986年版。

 

二、大纲说明

(一)本课程的性质、地位和任务

   《离散数学》课程是专业基础课。它是计算机科学中基础理论的核心课程,是现代数学的一个重要分支。离散数学是以研究离散量的结构和相互关系为主要目标,其研究对象一般地是有限个或可数个元素,因此它充分描述了计算机科学离散性的特点。离散数学是一门新兴的工具性学科,是为培养适应市场经济要求的应用型人才服务的。

    通过本课程的学习,使学生获得数理逻辑、集合论、代数系统和图论的基本常识。培养学生的分析、推理能力,增强学生用具体与抽象相结合的方法处理问题和解决问题的能力。为下一步学习计算机方面的有关课程打好基础。

(二)课程教学的基本要求

   通过本课程的学习,学生应达到如下要求:能判断命题(谓词),熟悉五种常见联结词的作用,了解其余联结词;理解命题公式(谓词公式),会作命题公式的真值表,掌握重言式,矛盾式;掌握命题公式(谓词公式)的等价关系,熟练置换与代入规则;掌握命题公式(谓词公式)的蕴含关系及其证明;会求合取与析取范式,会求主合取与主析取范式,会求谓词公式的前束范式;掌握命题演算(谓词公式)的推理规则,并能运用。理解集合及其相关概念,掌握集合的表示方法;熟悉集合的并、交、补、差等运算并掌握集合的基本运算律;

能证明一些简单的集合恒等式;理解序偶与笛卡尔积;理解二元关系及有关概念;熟练掌握关系矩阵及关系图;关系的五大性质:自反、对称、传递、反自反、反对称性并了解其矩阵及图表示与特征;会求复合关系、逆关系;会求关系的闭包;理解等价关系、等价类、商集、划分等概念;理解相容关系、相容类与最大相容类;能判断偏序集的最大、最小、极大、极小元与界;理解二元运算的概念,理解二元运算的封闭性、交换律、结合律、分配律,了解幂等律、吸收律;理解半群、独异点,理解并能判断幺元、零元和逆元;理解群与子群的概念、理解循环群、阿贝尔群的概念;知道群的基本判定定理,了解群同态与同构;知道环与域的基本概念。掌握图、简单图、多重图、赋权图、子图、生成子图、完成图等概念;了解图的同构;理解路、回路、图的连通性,理解欧拉图,了解哈密尔顿图;理解邻接矩阵及可达性矩阵并能简单应用;理解树及其相关基本概念,会求加权图的最小生成树。

(三)本课程与其他课程的联系与分工

    离散数学是计算机科学知识的基础。它自成体系。对后续课程如数据结构、操作系统、编译理论、算法分析、逻辑设计、系统结构等的学习可以打下坚实的理论基础。

(四)重点与难点

   重点:翻译,范式,推理。关系的概念,关系的五大性质及其判断,等价关系与偏序关系。半群、群的概念及其判断,幺元、零元与逆元的判断。图的概念、树的概念,图的矩阵表示。

   难点:谓词的翻译,蕴含式,量词作用域的扩张与收缩。等价类,相容类。 群的性质,同态。有向图的连通性,欧拉图。

(五)习题、实验及上机要求

   1.习题要求:结合各章节的内容,注重基本知识和基本技能的掌握。布置一些习题,习题量适中即可。

   2.实验及上机要求:

1)数理逻辑指导简单逻辑电路设计。

2)欧拉图理论指导学生计算机鼓轮机的设计。

(六)学时分配

章节

序号

     

学时

分配

   

讲授

习题课

实验

上机

其它

1

数理逻辑

16

12

4

 

 

 

2

集合与关系

20

16

4

 

 

 

3

代数系统

8

6

2

 

 

 

4

图论

12

10

2

 

 

 

 

 

 

 

 

 

 

 

    

56

44

12

 

 

 

 

 

 

 

 

                                         上一篇 :

                                         瀚海网(http://hanhai.org)