1
代数结构与组合数学
离散数学之二
Algebraic Structure and
Combinatorial Mathematics
北京大学信息学院屈婉玲
2
引言
?课程简介
?数学发展的三个阶段
?现代数学的特点
?离散数学与计算机科学
?学习安排
?教学要求
?教学安排
?教材与参考书
3
数学发展的三个阶段
发展阶段 标志 数、形 研究内容
初等数学 常量
几何图形
常量的代数运算----初等代数
图形间的关系----初等几何
高等数学 起点：解析几何
标志：微积分
变量
曲线、曲面
函数和变换、数形紧密结合
高等代数、几何、分析
现代数学 起点：集合论
标志：公理化
结构观点
集合
空间、流形
数、形难以区分
集合和映射
4
现代数学的特点
高度抽象和统一
学科 内容 时间
算数 算术运算 几千年
小代数 一次方程、二次方程 1千年
大代数 高次方程、线性方程组 16-19世纪
高等代数 矩阵、置换群、数域等具体代数结构19-20世纪
抽象代数 代数系统、公理+结构 20世纪20年代
泛代数 范畴 近几十年
5
现代数学的特点（续）
注重公理化体系的建立和结构分析
?公理化体系
欧几里德的平面几何公理、集合论的公理化体系
?结构分析
集合、对应规则+公理构成结构
例如：序结构（偏序集）
代数结构（群、环、域、格、线性空间）
拓扑结构（距离空间、拓扑空间）
测度结构
上述结构的复合结构（有序距离线性空间）等
6
现代数学的特点（续）
学科交叉、领域交叉
?数学研究领域交叉
?泛函分析、解析数论
?代数拓扑、代数图论
?确定性与非确定性交叉
?随机微分方程
?与其它应用学科交叉
?模糊数学
?运筹学
7
离散数学与计算机科学
?离散数学简介
?离散数学与计算机科学的关系
?学习离散数学的目的
8
离散数学简介
研究对象----离散个体及其结构
研究思想----以集合和映射为工具、体现公理化和结构的思想
研究内容----包含不同的数学分支，模块化结构
数理逻辑：推理、形式化方法
集合论：离散结构的表示、描述工具
代数结构：离散结构的代数模型
图论：离散结构的关系模型
组合数学：离散结构的存在性、计数、枚举、优化、设计
离散概率（概率统计课程）
9
离散数学主要内容的知识结构
图论集合论
组合数学
数理逻辑
代数结构
10
离散数学与计算机科学的关系
?数理逻辑人工智能、程序正确性证明及验证
?集合论关系数据库模型
?图论数据结构、数据库模型、网络模型等
?代数结构
软件规范、形式语义、编译系统
编码理论、密码学、数据仓库
?组合数学算法设计与分析、编码理论、容错
11
学习离散数学的目的
?掌握离散结构的描述语言和分析工具
为其它专业课程的学习打基础
为掌握软硬件模型的建模与分析方法准备必要
的数学工具
?学习现代数学的思想方法
?培养分析问题解决问题的能力
12
离散数学的学习安排
学习要求
知识体系：基本概念、基本计算、基本证明方法
注意能力的培养：
获取知识的能力----读书
分析问题解决问题的能力----解题
理论联系实际的能力----联系其它课程或研究课题
学习安排
平时成绩：40%
作业、小测验
期末笔试：60%
13
教材：
离散数学教程---耿素云、屈婉玲、王捍贫，北大出版社
参考书：
[1] 离散数学，耿素云，屈婉玲，高教出版社，2002.
[2] Discrete Mathematics and Its Applications,
Kenneth H. Rosen, Mc Graw Hill Companies, 1998.
[3] 离散数学及其应用（译著），袁崇义，屈婉玲，王捍贫，
刘田，机械工业出版社，2002.
[4] 离散数学习题解----抽象代数分册，张立昂，
北京大学出版社，1990
教材与参考书
