离散教学大纲

1、教学大纲一、课程信息开课单位信息科学与工程学院课程编号CS04001课程名称离散数学英文名称DiscreteMathematics课程性质理科B2组学分4总学时80先修课程高等数学，线性代数开课学期春季适应专业计科大类、软件、安全、信安、课程内容（一）课程教学目标离散数学是计算机科学与技术专业必修的一门专业基础课。它的任务是：使学生掌握高级科研人员或高级技术人员必须具备的离散数学基本理论和基本方法， 从事科研或工程技术工作以及进一步提高科学技术水平打下一定的基础； 的特点，培养学生辩证唯物主义观点和观察、分析、解决冋题的能力，的创新能力和实践能力。为学习后继专业课程、 同时，结合本课程 特别应

2、着力培养学生（二）教学内容第一部分命题逻辑命题、联结词、命题公式、等值式、析取范式与合取范式、推理理论、消解法第二部分谓词逻辑基本概念、谓词公式及其解释、合法的谓词公式、个体变元的身份、谓词公式的真值、谓词公式的类型、谓词公式等值演算、词公式的范式、谓词推理第三部分集合与关系基本概念、集合运算与性质、有穷集的计数、序偶、直积或笛卡尔积、关系、关系的复合、关系分类、关系的闭包、等价关系与集合的划分、偏序关系第四部分代数系统概念、运算的定义、运算的性质、代数系统、半群、群、子群、群的陪集分解、循环群、 置换群、环、域第五部分图论图的概念与描述、图的连通性、欧拉图、哈密尔顿图、平面图与四色猜想、树与

3、生成树、 最短路径、网络流图第六部分组合数学力卩法原则、乘法原则、允许重复的组合、不相邻的组合、街道方格问题、递 推关系、线性常系数齐次递推关系、线性常系数非齐次递推关系、整数拆分问题、 母函数、指数型母函数、广义二项式定理。三、课时分配课程内容讲课小班讨论上机周数备注命题逻辑9442+1谓词逻辑6222集合与关系9222+1代数系统9223图论7222.5组合数学8443.5合计48161616四、考核方式总评成绩=25%*期中考试+35%* （程序设计*40+小班讨论发言*20%+20%* 作业 +20%*课堂测试）+40%*期末考试。小班课实为习题讲解课。小班课上课前交作业，小班讨论由老

4、师抽查作业决定哪位同学 上来讲，在讲的过程中老师予以打分。程序设计在课后完成， 实验课期间，助教与任课老师验收程序，学生直接讲解程序如何设计及当面改动程序。五、答疑说明：答疑可通过 QQ群在线交流系统、邮件等方式答疑，每周二晚上7点院楼127六、授课手段课堂多媒体演示讲解；课堂讲解、样例训练，课程设计与课堂、QQ在线交流、邮件离线交流及教学辅助系统交流。周 次课堂讲授阅读内容作业考试（测验）实验小班讨论备注1第1讲命题与联结词习题一的讲解，合式公式检测的编 码1第2讲赋值，等值式前2节后的习题一全做2第3讲范式第一章习题二全做3第4讲命题逻辑的推理理论习题三全做逻辑推理习题讲解真值表生成的编3

5、第5讲消解法谓词逻辑的基本概念第一章习题四全做公式合法检测4第6讲谓词逻辑命题公式及其解释第二章的习题一全做第一章内容测验码5第7讲谓词逻辑等值式与等值演算谓词逻辑前束范式第二章习题二全做真值表生成与 等值演算谓词逻辑的习题讲解集合的基本运算代码5第8讲谓词逻辑的推理理论第二章习题6第9讲集合的基本概念与运算，容斥原理第三章习题7第10讲有序对,笛卡儿积与二兀关系集合的基本运算关系的例题关系的基本运算7第11讲二元关系的运算与性质，关系闭包第三章习题二：1-5第二章内容测验8第12讲等价关系与划分，偏序关系第三章习题二: 6-109第13讲二元运算及其性质关系的基本运算期中考试分小班考试9第1

6、4讲群的定义及性质10第15讲子群及其判定11第16讲群的陪集分解循环群，置换群第四章习题 全做第三章实验：见教材第十二节11第17讲图的基本概念，图的矩阵表示图的连通 性与Warshall算法欧拉图及其充要条 件第三章内容测验群的例题图的基本算法12第18讲欧拉图及其充要条件哈密尔顿图：充分 条件、必要条件，平面图：概念与性质13第19讲树与生成树 Kruskal算法，Prim算法最优二叉树与Huffman算法图论的基本算法图的例题图的稍复杂问题的编码13第20讲最短路算法，网络流图加法原则、乘法 原则、允许重复的组合、不相邻的组合第五章习题全做14第21讲街道方格问题、递推关系、线性常系数

7、 齐次递推关系经典例题的变化15第22讲线性常系数非齐次递推关系、整数拆分 问题第四章内容测验图论的稍复杂问题的编码组合数学习题讲 解与全书的复习15第23讲母函数、指数型母函数、广义二项式定理16第24讲总复习小班建议:内容：主讲相应章节的习题作业与相应的问题编码,操作步骤：1、小班课前收作业，按作业收到的先后次序+对错给分，随机抽取刚提交的作业，由学生上来讲解，老师点评。同时讲解相应问题的编码，或提供思路，或提供样例。2、学生讲解的同时，老师给予打分，学生回答问题也打分，没有讲解也没有回答问题 的，酌情给平均分。一学期下来确保每人讲到一次！实验课:1、实验课题内容已经在教学大纲给出参考建议。2、程序设计在课后完成，实验课期间，助教与任课老师验收程序，学生直接讲解程序 如何设计及当面改动程序。3、关于助教的使用：小班课还是老师讲，作