离散数学基础

关注 (205) 学过 (14)

离散数学基础中文授课

暂无评价 (评价人数不足)

  • 知识量:--
  • 授课水平:--
  • 实用性:--
  • 课程设计:--

难度:困难

开始时间:2016-03-07

持续时间:15.0周/每周2.0-2.0小时

去上课

离散数学研究离散量的结构及相互关系,在符号处理的通用层面上讨论满足构造性思维的通用结构,其研究对象是符号化、结构化与可构造的数学对象,相应采用符号化、结构化与可构造的思维方法,是计算机专业的核心课程。
离散数学是计算机专业的核心基础课程。计算机只能处理离散结构的数据,连续的、复杂的应用结构只能通过适当的离散化,分解抽象出离散的计算模型,才能由计算机进行处理。离散数学是计算机科学技术与工程的理论基础,而且随着计算机科学技术的发展不断形成新的应用体系。学生通过离散数学的学习,能够在数学推理、组合分析、离散结构构造、算法设计以及应用与建模等方面形成基本的离散思维方法,提高抽象思维和逻辑推理能力。离散数学也是后续专业课程(数据结构、编译系统、操作系统、数据库原理、人工智能、计算机网络等)的数学基础。离散数学的应用体系十分广泛,例如数字逻辑理论、逻辑电路设计、程序正确性证明、信息编码理论以及大量的图的实际应用模型。
离散数学课程的主要内容包括:数理逻辑、集合与关系代数、图论以及代数结构等。通过本课程的学习,学生应该熟练掌握有关集合、关系、图、树等离散结构的基本知识,掌握有关逻辑和证明的基本技巧和方法,理解并能初步运用离散结构进行问题建模和求解。



证书要求
证书规则将在开课前发布。



预备知识



授课大纲
第1周 命题逻辑的基本概念
数理逻辑的发展:逻辑、经典逻辑与非经典逻辑,公理系统
命题及其符号化
命题合式公式及其真值
命题等值公式与联结词的完备集


第2周 命题逻辑的等值演算和自然推理
命题公式的范式
命题推理基本定律
举例及应用


第3周 一阶逻辑的基本概念
个体、谓词与量词
谓词公式及其解释
不可判定性


第4周 一阶逻辑的等值演算和自然推理
逻辑等值公式
前缀范式
推理基本定律
举例及应用


第5周 集合
集合与元素
集合的相等与蕴含
集合的基本运算
序偶与笛卡尔乘积


第6周 关系、序关系和函数
关系的概念与运算
关系的性质
序关系、格与布尔代数
函数


第7周 图的概念及表示
图的基本概念
Euler图与Hamilton图
图的矩阵表示
道路矩阵与Warshall算法


第8周 树的基本概念
树的概念与判定
连通图的关联矩阵及其秩。
连通图的生成树的数目


第9周 二元树
二元树
最优二元树
Huffman树与Huffman编码


第10周 最优路径问题
最短路径与Dijstra算法
最短树与Prim算法和Kruskal算法
关键路径问题


第11周 平面图
平面图
极大平面图及性质
图的可平面性及Kuratowski定理


第12周 图的染色
图的K-可着色
图的色数
图的色数多项式
图的独立集、支配集与覆盖


第13周 图的匹配
图的匹配理论
Hall婚姻定理
最大匹配的匈牙利算法


第14周 网络模型
运输网络
割切
最大流最小割定理
求最大流的Ford-Fulkerson算法



参考资料
1.Kenneth H. Rosen. Descrete Mathematics and its Applications (Seventh Edition, 影印版). 机械工业出版社,2012.
2.B. Kolman, R. C. Busby, S. C. Ross. Discrete Mathematical Structures (Fifth Edition). Prentice Hall. 罗平译,离散数学结构(第五版),高等教育出版社,2005
3.D. S. Malik, Discrete Mathematical Structures – Theory and Applications, 高等教育出版社, 2005.
4.耿素云、屈婉玲, 《离散数学》(修订版), 高等教育出版社, 2004.
5.左孝凌等,《离散数学》, 上海科技文献出版社, 2002.
6.李盘林等,《离散数学》, 高等教育出版社, 1999.


相关课程

京ICP证100430号    京网文[2015] 0609-239号    新出发京零字东150005号     京公网安备11010502007133号 ©2017果壳网

关于我们 新手指南