常用下载   /  加入收藏  
 
 
    欢迎访问!今天是2018年02月20日  星期二  正月初五      
更多»公告
    当前位置: 首页 » 本科生教育 » 教学大纲 » 信息与计算科学 »  《离散数学》教学大纲
 上一篇:《高等代数2》教学大纲
 下一篇:《算法与程序设计》教学大纲
《离散数学》教学大纲
作者:管理员  来源:本站原创  发布时间:2016年5月11日  点击次数:348

《离散数学》教学大纲

Discrete Mathematics

 

课程编码:09A03010      学分: 5         课程类别:专业基础必修课

计划学时:80            其中讲课:80     实验或实践:0        上机:0

适用专业:信息与计算科学

推荐教材:左孝凌等著,离散数学[M],上海:上海科学技术文献出版社,1999

参考书目:邓辉文编著,离散数学[M],北京:清华大学出版社,2006

耿素云等编著,离散数学[M],北京:清华大学出版社,2013

 

课程的教学目的与任务

离散数学是信息与计算科学专业的核心课程之一,是现代数学的重要分支,是计算机科学中基础理论的核心课程。离散数学课程的主要内容为数理逻辑、集合论、代数结构和图论。本课程学习的目的与任务,是使学生掌握数理逻辑、集合论、代数结构和图论的基本概念与基本理论,了解这些学科的发展历史与现状,熟悉这些学科与其他相关学科特别是计算机科学的关系。该课程的授课重在培养学生严密的抽象思维和缜密概括能力,提高学生的认识水平,为后续课程如数据结构、操作系统、模糊数学、现代密码学等专业课程的学习作好准备。

 

课程的基本要求

1、要求学生掌握数理逻辑、集合论、代数结构和图论的基本概念与基本理论。

2、要求通过本课程的学习,使学生了解逻辑学、集合论、代数学以及图论发展的历史与现状;了解这些学科与其他相关学科关系;了解它们对其他相关学科,特别是计算机科学的作用。

3、通过本课程的学习,提高学生抽象思维和慎密概括能力,提高学生认识问题的高度,提高学生解决问题的能力。

 

 

各章节授课内容、教学方法及学时分配建议(含课内实验)

 

第一章:命题逻辑                          建议学时:12

[教学目的与要求] 掌握有关命题的概念,熟练认识9种联结词及其关系;会将自然语言表示为命题公式;会熟练求合式公式的主合取范式与主析取范式;会利用真值表法及等价推证证明等价式;会利用各种方法证明蕴涵式;熟练掌握推理理论。

[教学重点与难点] 命题公式的等价式和蕴含式,推理理论。

[      ] 以课堂讲授为主,课堂讨论和课下自学为辅。

[      ]

第一节 命题及表示法

一、命题的概念        

二、原子命题与复合命题

三、命题的表示法

四、命题常量与命题变元

第二节 联结词

一、五种联结词

二、命题符号化

第三节 命题公式与翻译

一、合式公式

二、命题的翻译举例

第四节 真值表与等价公式

    一、真值表

    二、等价公式及其证明

第五节 重言式与蕴含式

一、重言式的定义和性质

    二、蕴含式的定义和性质

三、等价式和蕴含式之间的关系

第六节 其他联结词

一、新联结词的真值表定义

 二、各联接词的性质

三、最小联结词组的概念及验证

第七节 对偶与范式

一、对偶式的概念、关系及性质

    二、合取(析取)范式的定义及求法

三、主合取(析取)范式的定义及求法

第八节 推理理论

一、真值表法

二、直接证法:P规则,T规则

三、间接证法:附加前提法,CP规则

 

第二章:谓词逻辑                           建议学时:8

[教学目的与要求] 熟练掌握有关谓词的概念;熟练量词的用法,会将自然语言表示为谓词公式;熟练运用谓词演算的等价式与蕴含式;会求谓词公式的前束范式;熟练掌握谓词演算的推理理论。

[教学重点与难点] 谓词公式的等价式和蕴含式,谓词演算的推理理论等。

[      ] 以课堂讲授为主,课堂讨论和课下自学为辅。

[      ]

第一节 谓词的概念与表示

一、谓词的概念和表示

二、谓词填式

第二节 命题函数与量词

一、命题函数的定义

二、全称量词和存在量词

第三节 谓词公式与翻译

一、谓词演算的合式公式的定义

二、谓词公式的翻译

第四节 变元的约束

一、变元及作用域

二、变元名称的更改

第五节 谓词演算的等价式与蕴含式

一、量词与否定联结词的关系

二、作用域的扩张与收缩所导致的等价式与蕴含式

三、多个量词的使用次序

第六节 前束范式

一、前束范式的定义

二、谓词公式化为前束范式、前束合取(析取)范式

第七节 谓词演算的推理理论

一、谓词演算的量词消去规则

二、谓词演算的量词产生规则

 

第三章:集合与关系                         建议学时:16

[教学目的与要求] 熟练掌握集合的交、并、补、差、复合、逆、闭包运算的定义性质及其关系;熟练掌握自反关系、对称关系、传递关系、反自反关系、反对称关系的定义及性质;熟练掌握等价关系、相容关系及序关系的性质。

[教学重点与难点] 关系五种性质的判断和证明;偏序关系的定义和判断等。

[      ] 以课堂讲授为主,课堂讨论和课下自学为辅。

[      ]

第一节  集合的概念和表示法

一、集合的定义、表示

二、子集、子集的包含、相互包含刻画相等

三、空集、全集、幂集

第二节  集合的运算

一、集合的并、交、差、补、对称差运算的定义及性质

二、证明集合相等的四种方法

第四节  序偶与笛卡尔积

一、序偶的定义

二、笛卡尔积的定义和性质

第五节  关系及其表示

一、关系的定义

二、关系的3种常用表示方法

第六节  关系的性质

一、自反关系、对称关系、传递关系、反自反关系以及反对称关系的概念

二、自反关系、对称关系、传递关系、反自反关系以及反对称关系的性质

三、自反关系、对称关系、传递关系、反自反关系以及反对称关系的关系图和关系矩阵

第七节  复合关系与逆关系

一、关系的复合运算与逆运算的定义

二、通过序偶运算与矩阵运算求复合关系和逆关系

三、复合运算与逆运算以及其它运算之间的关系

第八节 关系的闭包运算

一、三种闭包的定义和性质

二、三种闭包的序偶求法和关系矩阵求法

三、三种闭包之间的关系

第九节 集合的划分与覆盖

一、集合的覆盖和划分的定义

二、交叉划分

三、划分的加细

第十节 等价关系与等价类

一、等价关系的定义及验证

二、等价类的几个性质

三、集合上等价关系与集合的划分的相互唯一确定

第十一节 相容关系

一、相容关系的定义

二、相容类和最大相容类

三、集合的覆盖与相容关系的相互确定

第十二节 序关系

一、偏序关系的定义

二、偏序关系的Hasse图表示

三、偏序集中的最大()元、极大()元,上()界、上()确界

四、全序集、良序集的定义与关系

 

第四章:函数                               建议学时:8

[教学目的与要求] 熟练掌握函数逆函数和复合函数的概念及性质;掌握基数的概念,可数集与不可数集的有关性质;掌握基数的比较。

[教学重点与难点] 等势关系,集合的基数等。

[      ] 以课堂讲授为主,课堂讨论和课下自学为辅。

[      ]

第一节 函数的概念

一、从二元关系的观点理解函数的概念

二、几种特殊的函数

第二节 逆函数与复合函数

一、逆函数的概念及性质

二、复合函数的概念及性质

第四节 基数的概念

一、自然数集合的定义

二、两集合等势的概念

三、集合的基数的概念

第五节 可数集与不可数集

一、可数集与不可数集的概念

二、可数集与不可数集的性质

第六节 基数的比较

一、基数大小的定义

二、zermelo定理构造入射比较两集合基数的方法

三、连续统假设

 

第五章:代数结构                            建议学时:12

[教学目的与要求] 理解代数结构的一般意义;熟练掌握半群、群、环和域的有关概念与性质;熟练掌握同态与同构意义与性质。

[教学重点与难点] 子群的判定,同态同构的定义和性质等。

[      ] 以课堂讲授为主,课堂讨论和课下自学为辅。

[      ]

第一节 代数结构的引入

一、集合上的运算的概念

二、代数系统的概念

第二节 运算及性质

一、二元运算的几种特殊性质

二、代数系统的几种特殊的元素

第三节 半群

一、半群和子半群的概念

二、有限半群的性质

三、独异点的概念

第四节 群与子群

一、群与子群的概念

二、群的性质

三、群与子群的判定

第五节 阿贝尔群与循环群

一、阿贝尔群的概念与性质

二、循环群的概念与性质

第七节 陪集与拉格朗日定理

一、陪集的概念

二、拉格朗日定理

第八节 同态与同构

一、同态的概念和性质

二、同态与同构的判断

三、同态与同余关系的对应

第九节 环与域

一、环的概念与性质

二、几类特殊的环(含幺环、整环、域)及其性质

三、环上的同态与同余,及其相互关系

 

第六章:格与布尔代数                         建议学时:8

[教学目的与要求] 熟练掌握格的概念与性质;掌握分配格、有补格、布尔代数的概念与性质;了解布尔表达式的有关性质及运算。

[教学重点与难点] 格的两种观点(偏序集观点和代数观点),有限布尔代数结构定理等。

[      ] 以课堂讲授为主,课堂讨论和课下自学为辅。

[      ]

第一节 格的概念

一、从偏序集与代数学两个角度理解格的概念

二、格的性质

三、格同态的性质

第二节 分配格

一、分配格的概念与性质

二、模格的概念与性质

第三节 有补格

一、有界格的有关概念与性质

二、有补格的有关概念与性质

第四节 布尔代数

一、布尔代数的定义和性质

二、原子的一系列性质

三、stone表示定理

第五节 布尔表达式

一、布尔表达式的有关概念

二、布尔函数的有关概念

三、布尔代数上,函数、布尔函数、析()取范式之间的表达关系

 

第七章:图论                                 建议学时:16

[教学目的与要求] 掌握有关图及路与回路的基本概念,以及图的矩阵表示;熟练掌握欧拉图与汉密尔顿图的性质及判断方法;了解平面图的性质,了解对偶图与着色问题;熟练掌握树、生成树以及根树的概念、性质及应用。

[教学重点与难点]  图的矩阵表示,欧拉图与汉密尔顿图的判定,树的几种定价定义等。

[      ] 以课堂讲授为主,课堂讨论和课下自学为辅。

[      ]

第一节 图的基本概念

一、图的基本概念和基本性质

二、多重图、简单图、完全图、补图

三、图的同构

第二节 路与回路

一、路的相关概念

二、无向图的连通性

三、点割集、边割集的概念及其性质

四、单侧连通、强连通以及弱连通

五、强分图、单侧分图、弱分图的概念

第三节 图的矩阵表示

一、图中邻接矩阵、可达矩阵、完全关联矩阵的定义

二、利用邻接矩阵、可达矩阵、完全关联矩阵考察图的性质

第四节 欧拉图与汉密尔顿图

一、欧拉图的定义及判定

二、汉密尔顿图的定义及判定

第五节 平面图

一、平面图的有关概念

二、平面图的三个性质

第六节 对偶图与着色

一、对偶图的概念和性质

二、图的着色问题

三、韦尔奇×鲍威尔图着色法

第七节 树与生成树

一、树的概念及性质

二、生成树的有关概念

三、最小生成树的定义及求法

第八节 根树及其应用

一、根树的相关概念

二、m叉树的有关概念和性质

三、最优树的概念及求法

四、前缀码与二叉树的关系

 

 

撰稿人:王洪凯    审核人:靳绍礼 

 

 
» 上一篇:《高等代数2》教学大纲
» 下一篇:《算法与程序设计》教学大纲
check_website_is_ok,made by zheng_guang_yu,Do not delete
 
Copyright 济南大学数学科学学院. All rights reserved.
地址:济南市市中区南辛庄西路336号济南大学西校区第七教学楼   邮编:250022   电话(传真):0531-82767313