《离散数学》理论教学大纲

PAGE4《离散数学》理论教学大纲（DiscreteMathematics）课程代码：0610005总学时：64学时先修课程：《高等数学》、《线性代数》、《C语言程序设计》一、课程的性质、目的与任务离散数学是现代数学的一个重要分支，是计算机科学与技术专业的重要专业基础课程。它以研究离散量的结构和相互间的关系为主要目标。通过本课程的学习，使学生正确理解离散数学的概念、定理、公式的客观实际意义，掌握离散对象的基本研究方法，掌握离散数学理论、方法在计算机科学技术中的应用，培养学生利用离散数学思想分析问题与解决实际问题的能力。结合离散数学在计算机科学技术中的应用，介绍离散数学的基本知识，帮助学生了解数学中的抽象思维与计算机科学实践之间的内在联系，使学生熟练掌握离散数学的基本概念、结论、算法、推理与证明方法，培养学生的抽象思维、逻辑推理、符号演算和概括的能力，能够用离散数学中的数学方法解决本专业的实际问题。二、教学基本内容与基本要求1．基本内容本课程主要内容包括命题逻辑的基本概念、等值演算及推理理论，一阶谓词逻辑的基本概念、等值演算及推理理论；集合论、二元关系的运算及性质，函数的定义和性质，函数的复合与反函数；图的基本概念及性质，树的基本概念及性质，图的应用；代数系统的性质及运算，格的概念和性质，布尔代数、布尔函数的概念及性质等。2．基本要求本课程是计算机科学与技术专业的一门核心专业基础课，理论性较强、应用较广泛。通过学习，要求学生掌握离散数学的基本概念和基本原理，培养学生的抽象思维能力和逻辑推理能力，并为后继课程提供必要的理论和算法基础。三、教学内容及学时分配教学内容教学要求重点(☆)难点(Δ)学时安排备注第一部分数理逻辑1．命题与联结词2．命题公式及其赋值3．等值式4．析取范式与合取范式5．联结词完备集6．命题逻辑推理的形式结构7．自然推理系统PABAACBB☆☆☆☆ΔΔ22221128．一阶逻辑命题符号化9．一阶逻辑公式及其解释10．一阶逻辑等值式与置换规则11．一阶逻辑前束范式12．一阶逻辑推理理论ACBBB☆☆☆Δ21212第二部分集合论1．集合的基本概念及运算2．有穷集的计数、集合恒等式3．序偶与笛卡尔积4．二元关系及其表示5．关系的性质6．复合关系和逆关系7．关系的闭包8．等价关系与划分9.偏序关系10．函数的定义与性质11．复合函数和逆函数12．双射函数与集合的基数ABBAABBABABB☆☆☆☆ΔΔΔ221121221211第三部分图论1．图的基本概念2．通路、回路与图的连通性3．图的矩阵表示4．欧拉图5．哈密顿图6．树与生成树7．根树及其应用8．平面图及图的着色9.二部图的匹配AABBBBBCC☆☆☆☆Δ222112222第四部分代数结构1．二元运算及其性质2．代数系统3．半群与独异点4．群与子群5．群的同态与同构6.环与域7．格的定义与性质8．分配格、有补格9．布尔代数AAAABCCCC☆☆☆Δ211111111合计64（教学要求：A—熟练掌握；B—掌握；C—了解）四、建议实验项目及学时分配本课程无实验项目。五、教学方法与教学手段1．教学方法：以课堂讲授为主，含有习题课讲解。在重视课堂讲授的同时，注重培养学生的抽象思维以及实践、创新能力。在课堂教学中采用启发式、讨论式、参与式等教学方法，充分调动学生学习的积极性，提高教学质量，促进教学相长。2.教学手段：充分应用多媒体、CAI课件等现代化教学手段，提高课堂教学水平。采取讲练结合、理论联系实际等方式，提高课堂教学质量。六、建议教材与参考书目1．建议教材：《离散数学及其应用》，屈婉玲、耿素云、张立昂编，高等教育出版社，2011年5月。2．参考书目：①《离散数学与算法化思维》，程显毅、李医民编，清华大学出版社，2013年12月。②《计算机科学中的离散结构》，王元元编，机械工业出版社，2004年1月。③《离散数学结构》（第五版·翻译版），BernardKolman，RobertC.Busby，SharonCutlerRoss编，罗平翻译，高等教育出版社，2005年7月。④《离散数学及其在计算机科学中的应用》，徐洁磐编，人民邮电出版社，2005年4月七、大纲编写的依据与说明本课程教学大纲，是根据计算机科学与技术专业培养目标和基本要求，结合本课程的性质、教学的基本任务和基本要求