离散数学与算法化思维

拼音题名：li san shu xue yu suan fa hua si wei

其它题名

并列题名

ISBN：978-7-302-33530-6

责任者：程显毅，李医民编着

出版者：清华大学出版社

出版地：北京

出版时间：2013

中图分类号：O158

附注：21世纪高等学校规划教材 计算机科学与技术

《离散数学与算法化思维》本书共8章，包括集合论、数论、矩阵、关係、映射、函式、图论和数理逻辑。书中通过近40个算法实例，培养读者算法化思维的意识，且以节为单位布置习题。

本书共8章，包括集合论、数论、矩阵、关係、映射、函式、图论和数理逻辑。书中通过近40个算法实例，培养读者算法化思维的意识，且以节为单位布置习题。

第1章引论

1.1离散化

1.1.1为什幺要离散化

1.1.2计算机系统本质上是离散的

1.2离散数学与计算机的关係

1.2.1数学是计算机的基础

1.2.2计算机对数学的贡献

1.2.3离散数学的作用

1.2.4离散数学在计算机学科主干课程中的套用

1.3离散数学主题以及算法化思维

1.3.1离散数学主题

1.3.2算法化思维的重要性

1.4如何学习离散数学

1.4.1离散数学的特点

1.4.2学习离散数学要注意的问题

1.5本章小结

习题1

第2章基础知识

2.1集合论

2.1.1集合的基本概念

2.1.2集合论的思想渊源

2.1.3集合表示

2.1.4集合运算及相关算法

2.1.5集合证明技巧

习题2.1

2.2矩阵论

2.2.1矩阵的概念及其基本运算

2.2.2布尔矩阵及布尔积算法

习题2.2

2.3初等数论

2.3.1数的整除性

2.3.2同余

习题2.3

2.4本章小结

自测题2

第3章关係

3.1序偶和笛卡儿积

习题3.1

3.2关係及其表示

3.2.1关係的概念

3.2.2几种特殊的关係

3.2.3关係的表示

习题3.2

3.3关係的性质及其判定算法

3.3.1关係的性质

3.3.2关係性质判定算法

习题3.3

3.4複合关係

3.4.1複合关係的定义

3.4.2关係的複合运算的性质

3.4.3複合关係的矩阵表示及图形表示

3.4.4複合关係生成算法

习题3.4

3.5逆关係

3.5.1逆关係的概念及性质

3.5.2逆关係生成算法

习题3.5

3.6关係的闭包运算

3.6.1关係传递闭包

3.6.2关係传递闭包计算的warshall算法

习题3.6

3.7等价关係

3.7.1集合的划分和覆盖

3.7.2等价关係与等价类

3.7.3等价关係相关算法

习题3.7

3.8相容关係

习题3.8

3.9偏序关係

3.9.1偏序关係的定义

3.9.2哈斯图及其构造算法

3.9.3偏序集中特殊位置的元素

3.9.4拓扑排序算法

3.9.5良序

习题3.9

3.10格

习题3.10

3.11关係在计算机科学中的套用

3.11.1关係在关係资料库中的套用

3.11.2关係传递闭包在语法分析中的套用

3.12本章小结

自测题3

第4章映射

4.1映射的基本概念

4.1.1映射的概念

4.1.2映射的分类

习题4.1

4.2複合映射和逆映射

4.2.1複合映射

4.2.2逆映射

习题4.2

4.3置换函式

习题4.3

4.4计算机科学中常用的函式

4.4.1特徵函式

4.4.2取整函式

4.4.3布尔函式

4.4.4哈希函式

4.4.5算法複杂性分析的数学基础

习题4.4

4.5本章小结

自测题4

第5章组合分析

5.1计数

5.1.1基本计数关係式

5.1.2相容排斥原理

5.1.3加法法则和乘法法则

习题5.1

5.2排列

5.2.1无重複排列

5.2.2有重複的排列

5.2.3排列生成算法

习题5.2

5.3组合

5.3.1无重複的组合

5.3.2有重複的组合

5.3.3组合生成算法

习题5.3

5.4生成函式

习题5.4

5.5鸽巢原理

5.5.1一般的鸽巢原理

5.5.2推广的鸽巢原理

习题5.5

5.6组合分析在计算机中的套用

5.7本章小结

自测题5

第6章代数系统

6.1代数系统发展史

6.2运算与代数系统

6.2.1运算的概念

6.2.2代数系统的概念

6.2.3运算的性质及性质判定算法

6.2.4单位元、零元和逆元

习题6.2

6.3半群

6.3.1半群及其性质

6.3.2单位半群

习题6.3

6.4群

6.4.1群的基本概念

6.4.2群的性质

6.4.3子群

习题6.4

6.5特殊的群

6.5.1交换群

6.5.2循环群

6.5.3置换群

习题6.5

6.6代数系统的同态与同构

习题6.6

6.7代数系统在计算机中的套用

6.7.1布尔代数及其在电路设计中的套用

6.7.2群论在计算机编码纠错中的套用

6.7.3半群与文法及形式语言

习题6.7

6.8本章小结

自测题6

第7章图论

7.1图的基本概念

7.1.1图的定义与分类

7.1.2补图与生成子图

7.1.3握手定理

7.1.4同构图

习题7.1

7.2图的连通性

7.2.1基本路与基本迴路

7.2.2图的连通性

习题7.2

7.3图的矩阵表示

7.3.1邻接矩阵

7.3.2可达性矩阵

7.3.3完全关联矩阵

7.3.4与图有关的算法

习题7.3

7.4欧拉图与汉密尔顿图

7.4.1欧拉图

7.4.2汉密尔顿图

习题7.4

7.5二部图及匹配

7.5.1二部图

7.5.2匹配及最大匹配算法

习题7.5

7.6平面图

7.6.1平面图的定义

7.6.2欧拉公式

习题7.6

7.7最短路dijkstra算法

7.7.1问题的提出

7.7.2dijkstra算法

习题7.7

7.8树

7.8.1树的基本概念

7.8.2最小生成树kruskal算法

7.8.3二叉树

7.8.4最优二叉树哈夫曼算法

习题7.8

7.9图论在计算机中的套用

7.9.1二叉树的遍历算法及表达式表示

7.9.2前缀码的设计

7.9.3有限状态机的图表示

7.10本章小结

自测题7

第8章数理逻辑

8.1命题演算

8.1.1命题与命题联结词

8.1.2命题公式

8.1.3真值表及其真值计算算法

8.1.4命题等值式

8.1.5重言式、矛盾式和可满足式

8.1.6蕴涵式

习题8.1

8.2範式

8.2.1对偶原理

8.2.2範式转换算法

8.2.3主範式形成算法

习题8.2

8.3命题推理

8.3.1直接推理法

8.3.2间接推理法

习题8.3

8.4谓词演算

8.4.1个体、谓词和量词

8.4.2谓词公式和辖域

8.4.3谓词公式的解释及逻辑有效式

习题8.4

8.5谓词等值式和置换规则

习题8.5

8.6谓词推理

8.6.1逻辑有效蕴涵式

8.6.2推理定律

8.6.3推理实例

习题8.6

8.7数理逻辑在计算机中的套用

8.7.1逻辑推理在人工智慧中的套用

8.7.2人工智慧语言prolog简介

习题8.7

8.8本章小结

自测题8

后记