离散数学及其应用

图书标准信息

• 作者 栾尚敏 著
• 出版社 清华大学出版社
• 出版时间 2021-11
• 版次 1
• ISBN 9787512145726
• 定价 45.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 232页
• 字数 371千字

【内容简介】

离散数学在信息技术领域有着广泛的应用，是计算机类相关专业必备的基础知识，也是计算机类及其他信息类相关专业的一门重要基础课程。离散数学研究的对象是离散数量关系和离散结构的数学模型，包含集合理论、数理逻辑、图论、代数系统和计算理论。这些概念、理论以及方法广泛地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络、密码学等专业课程中。该课程所提供的训练有助于提高学生概括抽象能力、逻辑思维能力、归纳构造能力，有益于学生严谨、完整、规范的科学态度的培养，实践环节的内容对提高学生的编程技能也有很大帮助。

 

本书可作为信息技术领域相关专业本科生“离散数学”及相关课程的教材，也可作为想了解离散数学及其应用人员的参考书。

 

【作者简介】

栾尚敏，男，1968年出生，教授，博士毕业于北京航空航天大学，博士后出站于中国科学院软件研究所，曾经在山东大学、北京理工大学、中国科学院软件研究所工作，目前就职于华北科技学院。主要从事计算机软件与理论、人工智能的研究工作，发表论文50余篇，这些论文发表在《Logic Journal of IGPL》《Science in China:Series F》《Journal of Computer Science and Technology》《中国科学：信息科学》《中国科学：技术科学》《计算机学报》《软件学报》《计算机研究与发展》等刊物，SCI收入12篇，EI收入9篇。

【目录】

目录

 

第1章绪论

 

1.1离散数学的研究对象

 

1.2连续量的数字化

 

1.2.1图像的数字化

 

1.2.2语音的数字化

 

1.3离散数学在信息技术中的应用

 

1.3.1离散数学与关系数据库

 

1.3.2形式语言与编译系统

 

1.3.3数理逻辑与程序设计语言

 

1.3.4代数系统与密码学

 

1.3.5代数系统与程序语义

 

1.3.6印刷电路板布线问题

 

1.4本课程的特点和学习方法

 

1.5本章小结

 

1.6习题

 

第2章集合理论

 

2.1集合理论的发展历史

 

2.2集合的定义和运算

 

2.2.1集合的基本概念

 

2.2.2集合上的基本运算

 

2.3关系及其性质

 

2.3.1序对和笛卡儿积

 

2.3.2二元关系

 

2.3.3关系的运算

 

2.3.4关系的性质

 

2.3.5关系的闭包运算

 

2.4等价关系与集合的划分

 

2.4.1等价关系与等价类

 

2.4.2集合的划分

 

2.5序关系

 

2.5.1偏序关系的定义

 

2.5.2偏序集的哈斯图

 

2.6函数

 

2.6.1函数的定义

 

2.6.2逆函数与复合函数

 

2.7集合理论在计算机科学中的应用

 

2.7.1集合理论在关系数据库理论中的应用：关系代数

 

2.7.2集合理论在机器学习中的应用：粗糙集理论

 

2.8实践内容：集合上的运算

 

2.8.1编程实现集合的交、并和差运算

 

2.8.2二元关系性质的验证

 

2.9本章小结

 

2.10习题

 

第3章数理逻辑

 

3.1数理逻辑的发展历史

 

3.2命题逻辑

 

3.2.1命题演算的基本概念

 

3.2.2命题逻辑的合式公式及范式

 

3.2.3命题逻辑的推理理论

 

3.3谓词逻辑

 

3.3.1谓词逻辑的基本概念

 

3.3.2谓词逻辑的合式公式

 

3.3.3谓词形式系统的语义

 

3.3.4谓词演算的等值式

 

3.3.5前束范式

 

3.4数理逻辑在人工智能中的应用

 

3.4.1定理自动证明

 

3.4.2逻辑式程序设计语言Prolog运行机理

 

3.5实践内容：命题公式可满足性验证

 

3.5.1SAT基础知识

 

3.5.2SAT的求解算法

 

3.5.3变量和子句的存储方法

 

3.6本章小结

 

3.7习题

 

第4章图论及其应用

 

4.1图论的发展历史

 

4.2图的基本概念

 

4.2.1无向图及有向图

 

4.2.2相邻和度

 

4.2.3子图

 

4.2.4通路与连通性

 

4.3图的矩阵表示

 

4.3.1关联矩阵

 

4.3.2邻接矩阵

 

4.3.3可达矩阵

 

4.4欧拉图与哈密顿图

 

4.4.1欧拉图

 

4.4.2哈密顿图

 

4.5平面图与平面化算法

 

4.5.1平面图

 

4.5.2平面化算法

 

4.6带权图与生成树

 

4.6.1带权图

 

4.6.2树与生成树

 

4.7根树及最优二叉树

 

4.7.1根树

 

4.7.2最优二叉树

 

4.7.3最优前缀编码

 

4.8实践内容：用最优前缀编码压缩文件

 

4.9本章小结

 

4.10习题

 

第5章代数系统

 

5.1代数学的发展历史

 

5.2代数系统的基本概念、运算与性质

 

5.2.1二元运算

 

5.2.2代数系统的基本概念及性质

 

5.3半群、群与子群

 

5.3.1半群与含幺半群

 

5.3.2群与子群

 

5.3.3阿贝尔群

 

5.3.4循环群

 

5.3.5置换群

 

5.4同态、同构

 

5.4.1同态与同构的概念及性质

 

5.4.2同余

 

5.5环、域、格和布尔代数

 

5.5.1环

 

5.5.2域

 

5.5.3格

 

5.5.4布尔代数

 

5.5.5一元多项式环

 

5.6数据类型的代数规格说明

 

5.6.1代数系统的规格说明

 

5.6.2数据类型的代数规格说明

 

5.6.3SPEC-代数

 

5.7代数系统与密码学

 

5.7.1AES方法的总体结构

 

5.7.2数学基础

 

5.7.3AES的基本变换

 

5.7.4圈密钥生成

 

5.7.5AES的加密算法

 

5.7.6AES的基本逆变换

 

5.8实践内容：代数系统的实现

 

5.8.1面向对象的程序设计与代数系统

 

5.8.2代数系统的面向对象实现

 

5.9本章小结

 

5.10习题

 

第6章形式语言与自动机理论

 

6.1形式语言发展的历史

 

6.2形式语言理论

 

6.2.1语言的表示

 

6.2.2文法：语言的有限描述

 

6.2.3文法的乔姆斯基体系

 

6.2.4正规表达式

 

6.3自动机理论

 

6.3.1有限自动机

 

6.3.2下推自动机

 

6.3.3图灵机

 

6.3.4通用图灵机

 

6.4实践内容：词法分析器的设计

 

6.4.1目标语言的定义

 

6.4.2程序实现

 

6.5本章小结

 

6.6习题

 

第7章递归理论及其应用

 

7.1递归与计算

 

7.1.1递归、归纳和迭代

 

7.1.2可计算的含义

 

7.1.3递归理论的发展历史

 

7.2递归函数理论

 

7.2.1构造函数的方法

 

7.2.2递归函数

 

7.3递归与程序设计

 

7.4递归式求解

 

7.4.1递归关系的建立

 

7.4.2常系数齐次线性递归方程

 

7.4.3常系数非齐次线性递归方程

 

7.4.4迭代法

 

7.4.5归纳法

 

7.4.6母函数法

 

7.5实践内容：用堆栈模拟递归

 

7.5.1斐波那契数列问题的递归和迭代的比较

 

7.5.2用堆栈模拟递归

 

7.6本章小结

 

7.7习题

 

第8章组合理论初步

 

8.1组合理论简介

 

8.2排列、组合与二项式定理

 

8.2.1基本计数原理

 

8.2.2排列与组合

 

8.2.3多重集的排列组合

 

8.2.4二项式定理

 

8.3排列组合生成算法

 

8.3.1生成排列

 

8.3.2生成组合

 

8.4鸽巢原理

 

8.4.1第一抽屉原理

 

8.4.2鸽巢原理的加强形式

 

8.4.3Ramsey数及其在信息技术中的应用

 

8.5组合设计

 

8.5.1区组设计

 

8.5.2拉丁方设计

 

8.6本章小结

 

8.7习题

 

参考文献