广西民族学院理学院2014-2015第一学期课程教学大纲之离.doc

离散数学 Discrete Mathmatics【课程编号】BZ25151【课程类别】必修课【学分数】4【适用专业】【学时数】72【编写日期】2010.4.16【适用专业】计算机科学与技术、软件工程、信息与计算科学、信息管理与信息系统【先修课程】线性代数【后续课程】数据结构、数据库应用技术、操作系统、编译原理、算法分析与设计等课程一、教学目的、任务 离散数学是基础核心课程。通过本课程的学习，使学生具有现代数学的观点和方法，并初步掌握处理离散结构所必须的描述工具和方法。同时，也要培养学生抽象思维和慎密概括的能力，使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力，为学生以后学习计算机基础理论与专业课程打下良好的基础。本课程是一门理论性较强的课程，要求在完成基础知识教学任务的同时，通过适当的实际应用的介绍，提高学生的实际应用能力的培养。二、课程教学的基本要求 本课程是基础核心课程，教学内容以基本概念、结论、算法、推理与证明方法，以及一般应用方法的介绍为主，课程内容突出简明扼要、体系结构清楚为原则。 本课程主要内容包括数理逻辑、集合论、组合数学与图论等四个方面的内容。具体要求为：1了解离散数学的主要组成部分，各个部分所涉及的基本内容，及其在计算机科学与技术领域中的应用；2理解离散数学的基本概念、结论、算法、应用方法及适用范围；3掌握离散数学的本推理与证明过程、基本算法及应用方法。三、教学内容和学时分配（一）绪论 2 学时（课堂讲授学时）主要内容： (1)离散数学在计算机科学与技术专业学习中的作用 (2)离散数学的发展现状 (3)学习本课程的目的与方法教学要求： 了解：离散数学课程的内容 理解：离散数学课程的在计算机专业学习中的重要性（二）第一部分 数理逻辑 28学时（课堂讲授学时+课程实验学时）主要内容： (1)第一章命题逻辑基本概念:命题与连接词,命题公式 (2)第二章命题逻辑等值演算:等值式， 析取范式与合取范式， 联结词的完备集 (3)第三章 命题逻辑的推理理论:推理的形式结构，自然推理系统 (4)第四章一阶逻辑基本概念: 一阶逻辑命题符号化，一阶逻辑公式及解释 (5)第五章一阶逻辑等值演算与推理:一阶逻辑等值与置换规则，前束范式，一阶逻辑的推理理论教学要求： 了解：命题逻辑的基本概念、基本理论与方法；谓词逻辑的基本概念、基本理论与方法。 理解：命题公式的概念，命题联结词的概念；范式的概念；命题逻辑的等值式与蕴涵式的概念；谓词公式的概念；谓词逻辑的等值式与蕴涵式的概念。 掌握：命题符号化、求命题公式的真值表；合取范式、析取范式、主合取范式及主析取范式的求解；等值式与蕴涵式的基本证明方法；命题逻辑的推理理论；谓词命题符号化；简单的谓词公式的解释。其它教学环节： 实验设计:通过求真值表判断公式的性质（三）第二部分 集合论 16学时（课堂讲授学时+课程实验学时）主要内容： (1)第六章集合代数:集合的基本概念、集合的运算、集合的恒等式2学时 (2)第七章二元关系:二元关系及表达式、关系的运算、关系的性质、关系的闭包运算、等价关系与划分8学时 (3)第八章函数:函数的基本概念、函数的性质、函数的复合运算、函数的逆运算 4学时教学要求： 了解：函数与关系的区别。理解：关系的概念，关系的性质；复合关系、逆关系及关系的闭包的概念；等价关系与等价类、序关系等的概念；函数的概念及其性质；逆函数与复合函数的概念。掌握：笛卡儿积，关系的表示；复合关系、逆关系及关系的闭包的运算；等价关系的判定，等价类的计算，序关系的判定与哈斯图等的计算；函数的判定，逆函数与复合函数的计算。其它教学环节： 实验设计:利用矩阵判断关系的对称性等 2 学时（四）第三部分 组合数学 14学时（课堂讲授学时+课程实验学时）主要内容： (1)第十二章基本的组合计数: 加法和乘法法则、排列与组合、二项式定理、多项式定理6学时 (2)第十三章递推方程与生成函数: 递推方程的定义及实例、递推方程的公式解法、递推方程的其他解法、生成函数及其应用、指数生成函数及其应用 6学时教学要求： 了解：排列组合, 递推方程的概念。理解：多重排列与组合的概念；二项式定理；递推方程的公式求法；生成函数与指数函数的定义。掌握：排列与组合的应用，二项式定理与多项式定理的应用；递推方程的计算，生成函数及其应用、指数生成函数及其应用。其它教学环节： 实验设计: 根据输入的整数，生成组合数和排列数 2 学时（四）第四部分 图论 14学时（课堂讲授学时+课程实验学时）主要内容： (1)第十四章图的基本概念:图的基本概念、通路与回路、无向图、连通性 6学时 (2)第十五章欧拉图与哈密尔顿图:欧拉图、哈密尔顿图 2学时 (3)第十六章树:无向树及其性质、生成树、根树及其应用 6学时教学要求： 了解：图论的基本内容及其在计算机领域中的应用；最短路的算法；树在计算机领域中的应用。理解：图的基本概念，子图、补图概念；路与回路、图的连通性与连通度等概念；欧拉回路与欧拉图、汉密尔顿回路与汉密尔顿图的概念及性质；树、生成树、有向树、根树、最优树的概念。掌握：图的表示方法；图的路、回路及连通性的判断；连通度的计算；对欧拉图、汉密尔顿图的判定方法；最小生成树的Kruskal算法，求最优树的Huffman算法，前缀码的求法。其它教学环节： 实验设计: 根据输入的整数对，输出一个图形的邻接矩阵。并求出各结点的出度和入度，判定一个以邻接矩阵表示的图是否是一棵树 2 学时四、教学重点、难点及教学方法 教学重点：命题公式演算，等价式与蕴含式，范式推理理论，谓词演算的等价与蕴含式，复合关系和逆运算，等价关系，序关系，组合计算，递推方程，树及其应用。 教学难点： 谓词演算的等价式与蕴含式，关系的闭包运算、递推方程、生成函数、哈密顿图。 建议：离散数学的内容是“离散化”的，各部分可相对独立，自成体系，但许多内容抽象难学，因此要在教学方法上下功夫，培养学生的学习兴趣。五、考核方式及成绩评定方式 闭卷考试;平时30-40%， 期末 60-70%六、教材及参考书目教材：离散数学， 屈婉玲、耿素云、张立昂，高等教育出版社参考书目： 1、Discrete Mathematics and Its Application(6Ed), K.H.Rosen,机械工业出版社 2、Dis