北京大学：《离散数学》离散数学之二《代数结构与组合数学》引言（主讲：屈婉玲）

代数结构与组合数学 离散数学之二 Algebraic Structure and Combinatorial mathematics 北京大学信息学院屈婉玲

1 代数结构与组合数学 离散数学之二 Algebraic Structure and Combinatorial Mathematics 北京大学信息学院 屈婉玲

引言 ■课程简介 数学发展的三个阶段 现代数学的特点 离散数学与计算机科学 ■学习安排 教学要求 教学安排 教材与参考书

2 引 言 „ 课程简介 „ 数学发展的三个阶段 „ 现代数学的特点 „ 离散数学与计算机科学 „ 学习安排 „ 教学要求 „ 教学安排 „ 教材与参考书

数学发展的三个阶段 发展阶段标志 数、形研究内容 初等数学 常量 常量的代数运算一—初等代数 几何图形图形间的关系一初等几何 高等数学起点:解析几何变量 函数和变换、数形紧密结合 标志:微积分曲线、曲面高等代数、几何、分析 现代数学起点:集合论集合 数、形难以区分 标志:公理化空间、流形集合和映射 结构观点

3 数学发展的三个阶段 发展阶段 标志 数、形 研究内容 初等数学 常量 几何图形 常量的代数运算----初等代数 图形间的关系----初等几何 高等数学 起点：解析几何 标志：微积分 变量 曲线、曲面 函数和变换、数形紧密结合 高等代数、几何、分析 现代数学 起点：集合论 标志：公理化 结构观点 集合 空间、流形 数、形难以区分 集合和映射

现代数学的特点 高度抽象和统 学科 内容 时间 算数 算术运算 几千年 小代数次方程、二次方程 1千年 大代数高次方程、线性方程组 16-19世纪 高等代数矩阵、置换群、数域等具体代数结构1920世纪 抽象代数代数系统、公理+结构 20世纪20年代 泛代数范畴 近几十年

4 现代数学的特点 高度抽象和统一 学科 内容 时间 算数 算术运算 几千年 小代数 一次方程、二次方程 1 千年 大代数 高次方程、线性方程组 16-19 世纪 高等代数 矩阵、置换群、数域等具体代数结构 19-20 世纪 抽象代数 代数系统、公理 +结构 20 世纪 20 年代 泛代数 范畴 近几十年

现代数学的特点(续) 注重公理化体系的建立和结构分析 ■公理化体系 欧几里德的平面几何公理、集合论的公理化体系 结构分析 集合、对应规则+公理构成结构 例如:序结构(偏序集) 代数结构(群、环、域、格、线性空间) 拓扑结构(距离空间、拓扑空间) 测度结构 上述结构的复合结构(有序距离线性空间)等

5 现代数学的特点（续） 注重公理化体系的建立和结构分析 „ 公理化体系 欧几里德的平面几何公理、集合论的公理化体系 „ 结构分析 集合、对应规则 +公理构成结构 例如：序结构（偏序集） 代数结构（群、环、域、格、线性空间） 拓扑结构（距离空间、拓扑空间） 测度结构 上述结构的复合结构（有序距离线性空间）等

现代数学的特点(续) 学科交叉、领域交叉 数学研究领域交叉 泛函分析、解析数论 代数拓扑、代数图论 确定性与非确定性交叉 随机微分方程 ■与其它应用学科交叉 模糊数学 运筹学

6 现代数学的特点（续） 学科交叉、领域交叉 „ 数学研究领域交叉 „ 泛函分析、解析数论 „ 代数拓扑、代数图论 „ 确定性与非确定性交叉 „ 随机微分方程 „ 与其它应用学科交叉 „ 模糊数学 „ 运筹学

离散数学与计算机科学 ■离散数学简介 离散数学与计算机科学的关系 ■学习离散数学的目的

7 离散数学与计算机科学 „ 离散数学简介 „ 离散数学与计算机科学的关系 „ 学习离散数学的目的

离散数学简介 研究对象——离散个体及其结构 研究思想一以集合和映射为工具、体现公理化和结构的思想 研究内容—包含不同的数学分支,模块化结构 数理逻辑:推理、形式化方法 集合论:离散结构的表示、描述工具 代数结构:离散结构的代数模型 图论:离散结构的关系模型 组合数学:离散结构的存在性、计数、枚举、优化、设计 离散概率(概率统计课程)

8 离散数学简介 研究对象----离散个体及其结构 研究思想----以集合和映射为工具、体现公理化和结构的思想 研究内容----包含不同的数学分支，模块化结构 数理逻辑：推理、形式化方法 集合论：离散结构的表示、描述工具 代数结构：离散结构的代数模型 图论：离散结构的关系模型 组合数学：离散结构的存在性、计数、枚举、优化、设计 离散概率（概率统计课程）

离散数学主要内容的知识结构 代数结构 组合数学 数理逻辑集合论→图论

9 离散数学主要内容的知识结构 集合论 图论 组合数学 数理逻辑 代数结构

离散数学与计算机科学的关系 数理逻辑人工智能、程序正确性证明及验证 集合论关系数据库模型 图论数据结构、数据库模型、网络模型等 代数结构 软件规范、形式语义、编译系统 编码理论、密码学、数据仓库 ■组合数学算法设计与分析、编码理论、容错

10 离散数学与计算机科学的关系 „ 数理逻辑 人工智能、程序正确性证明及验证 „ 集合论 关系数据库模型 „ 图论 数据结构、数据库模型、网络模型等 „ 代数结构 软件规范、形式语义、编译系统 编码理论、密码学、数据仓库 „ 组合数学 算法设计与分析、编码理论、容错