算法基础及应用 / 高等学校计算机专业系列教材
定价：￥79.00
作者： 吕云翔，张师毓等
出版社：机械工业出版社
- 机械工业出版社
- 9787111812166
- 1-1
- 449
内容简介
本书系统地介绍了算法的基础理论、设计方法及其应用，旨在为读者提供全面而深入的算法知识体系。全书共分为11章，内容涵盖算法的基本概念、特性及评价方式；详细阐述了数据结构的基础知识，包括线性表、栈、队列、树、图等，并介绍了容器的使用；深入讲解了多种基础算法，如穷举法、递归、分治法、回溯法、分支界限法、动态规划、贪心算法等，每种算法都配有详细的模型设计和丰富的应用实例；最后，通过图算法、背包问题、旅行商问题、几何问题、数论应用、NP问题、概率算法、近似算法等综合应用，展示了算法在不同领域的实际应用。此外，本书还附有如何使用大语言模型学习算法的指导，以及相关参考文献，为读者提供了进一步学习和研究的资源。
目录
前言
第1章 算法概述1
1.1 算法的概念1
1.2 算法的特点1
1.3 算法的描述方式2
1.4 算法设计过程4
1.5 算法的评价方式4
1.5.1 时间复杂度5
1.5.2 空间复杂度5
1.5.3 算法的其他评价方式5
习题6
第2章 数据结构7
2.1 数据结构概述7
2.2 线性表7
2.2.1 顺序表(数组)7
2.2.2 链表9
2.2.3 串11
2.3 栈13
2.3.1 简单栈13
2.3.2 双向栈14
2.4 队列16
2.4.1 简单队列16
2.4.2 双端队列17
2.4.3 循环队列18
2.5 树19
2.5.1 树的概念19
2.5.2 树的存储20
2.5.3 二叉树20
2.5.4 二叉树的存储21
2.6 图22
2.6.1 图的概念22
2.6.2 图的存储22
2.7 集合容器24
2.7.1 List25
2.7.2 Set26
2.7.3 Queue27
2.8 映射容器28
习题29
第3章 穷举法31
3.1 穷举法概述31
3.1.1 什么是穷举法31
3.1.2 穷举法的设计理念31
3.1.3 穷举法的算法评价32
3.2 穷举法模型设计32
3.2.1 算法模型32
3.2.2 穷举中的循环遍历33
3.3 穷举算法应用33
3.3.1 回文串个数34
3.3.2 最大连续子序列39
3.3.3 求全排列41
3.3.4 求幂集42
3.3.5 n皇后问题45
3.3.6 任务分配问题49
习题52
第4章 递归法54
4.1 递归法概述54
4.1.1 什么是递归法54
4.1.2 递归法的设计理念55
4.1.3 递归法的算法评价55
4.2 递归法模型设计56
4.3 递归算法应用57
4.3.1 简单排序57
4.3.2 表达式的值60
4.3.3 汉诺塔63
4.3.4 斐波那契数列65
4.3.5 线性规划67
习题70
第5章 分治法72
5.1 分治法概述72
5.1.1 什么是分治法72
5.1.2 分治法的设计理念73
5.1.3 分治法的算法评价73
5.2 分治法模型设计73
5.3 分治算法应用74
5.3.1 快速排序74
5.3.2 二路归并排序77
5.3.3 希尔排序80
5.3.4 堆排序83
5.3.5 二分查找86
5.3.6 散列问题88
5.3.7 最大连续子序列和93
5.3.8 棋盘覆盖问题96
5.3.9 循环日程安排问题99
5.3.10 快速傅里叶变换102
习题105
第6章 回溯法107
6.1 回溯法概述107
6.1.1 什么是回溯法107
6.1.2 回溯法的设计理念108
6.1.3 回溯法的算法评价108
6.2 回溯法模型设计108
6.3 回溯算法应用109
6.3.1 树的遍历109
6.3.2 求幂集/子集/子集和112
6.3.3 图的遍历116
6.3.4 构造表达式119
6.3.5 着色问题122
6.3.6 n皇后问题125
6.3.7 任务分配问题127
6.3.8 哈密顿环问题129
习题132
第7章 分支界限法134
7.1 分支界限法概述134
7.1.1 什么是分支界限法134
7.1.2 分支界限法的设计理念135
7.1.3 分支界限法的算法评价135
7.2 分支界限法模型设计136
7.3 分支界限算法应用137
7.3.1 图的遍历与最短路径137
7.3.2 任务分配问题140
7.3.3 作业调度问题145
7.3.4 A*算法150
7.3.5 博弈搜索算法154
习题157
第8章 动态规划159
8.1 动态规划概述159
8.1.1 什么是动态规划159
8.1.2 动态规划的设计理念160
8.1.3 动态规划的算法评价160
8.2 动态规划模型设计160
8.3 动态规划算法应用161
8.3.1 最大连续子序列和161
8.3.2 最长递增子序列162
8.3.3 最长公共子序列165
8.3.4 三角最小路径和168
8.3.5 资源分配问题170
8.3.6 旅行商问题173
8.3.7 最少士兵数目问题176
8.3.8 矩阵连乘问题177
习题180
第9章 贪心算法182
9.1 贪心算法概述182
9.1.1 什么是贪心算法182
9.1.2 贪心算法的设计理念183
9.1.3 贪心算法的算法评价183
9.2 贪心算法模型设计183
9.3 贪心算法应用184
9.3.1 区间调度问题184
9.3.2 田忌赛马186
9.3.3 零钱兑换189
9.3.4 哈夫曼编码192
9.3.5 多机调度196
9.3.6 拟阵198
习题203
第10章 算法综合应用205
10.1 图算法205
10.1.1 最小生成树205
10.1.2 最短路径208
10.1.3 网络流(最大流、最小割、
匹配算法)212
10.2 背包问题217
10.2.1 0/1背包问题217
10.2.2 完全背包问题219
10.2.3 多重背包问题219
10.3 回顾旅行商问题220
10.4 几何问题223
10.4.1 向量运算223
10.4.2 凸包问题224
10.4.3 最远点对229
10.5 数论应用231
10.5.1 欧几里得算法232
10.5.2 同余定理234
10.5.3 素性检验算法236
10.6 NP问题238
10.6.1 P以及NP239
10.6.2 多项式时间归约239
10.6.3 NP完全问题239
10.6.4 NP困难问题239
10.7 概率算法240
10.7.1 数值概率算法240
10.7.2 蒙特卡洛算法242
10.7.3 拉斯维加斯算法243
10.7.4 舍伍德算法246
10.8 近似算法247
第11章 使用大语言模型学习
算法249
11.1 什么是大语言模型249
11.2 大语言模型能帮我们做些
什么250
11.3 尝试使用大语言模型进行
算法学习250
参考文献257
第1章 算法概述1
1.1 算法的概念1
1.2 算法的特点1
1.3 算法的描述方式2
1.4 算法设计过程4
1.5 算法的评价方式4
1.5.1 时间复杂度5
1.5.2 空间复杂度5
1.5.3 算法的其他评价方式5
习题6
第2章 数据结构7
2.1 数据结构概述7
2.2 线性表7
2.2.1 顺序表(数组)7
2.2.2 链表9
2.2.3 串11
2.3 栈13
2.3.1 简单栈13
2.3.2 双向栈14
2.4 队列16
2.4.1 简单队列16
2.4.2 双端队列17
2.4.3 循环队列18
2.5 树19
2.5.1 树的概念19
2.5.2 树的存储20
2.5.3 二叉树20
2.5.4 二叉树的存储21
2.6 图22
2.6.1 图的概念22
2.6.2 图的存储22
2.7 集合容器24
2.7.1 List25
2.7.2 Set26
2.7.3 Queue27
2.8 映射容器28
习题29
第3章 穷举法31
3.1 穷举法概述31
3.1.1 什么是穷举法31
3.1.2 穷举法的设计理念31
3.1.3 穷举法的算法评价32
3.2 穷举法模型设计32
3.2.1 算法模型32
3.2.2 穷举中的循环遍历33
3.3 穷举算法应用33
3.3.1 回文串个数34
3.3.2 最大连续子序列39
3.3.3 求全排列41
3.3.4 求幂集42
3.3.5 n皇后问题45
3.3.6 任务分配问题49
习题52
第4章 递归法54
4.1 递归法概述54
4.1.1 什么是递归法54
4.1.2 递归法的设计理念55
4.1.3 递归法的算法评价55
4.2 递归法模型设计56
4.3 递归算法应用57
4.3.1 简单排序57
4.3.2 表达式的值60
4.3.3 汉诺塔63
4.3.4 斐波那契数列65
4.3.5 线性规划67
习题70
第5章 分治法72
5.1 分治法概述72
5.1.1 什么是分治法72
5.1.2 分治法的设计理念73
5.1.3 分治法的算法评价73
5.2 分治法模型设计73
5.3 分治算法应用74
5.3.1 快速排序74
5.3.2 二路归并排序77
5.3.3 希尔排序80
5.3.4 堆排序83
5.3.5 二分查找86
5.3.6 散列问题88
5.3.7 最大连续子序列和93
5.3.8 棋盘覆盖问题96
5.3.9 循环日程安排问题99
5.3.10 快速傅里叶变换102
习题105
第6章 回溯法107
6.1 回溯法概述107
6.1.1 什么是回溯法107
6.1.2 回溯法的设计理念108
6.1.3 回溯法的算法评价108
6.2 回溯法模型设计108
6.3 回溯算法应用109
6.3.1 树的遍历109
6.3.2 求幂集/子集/子集和112
6.3.3 图的遍历116
6.3.4 构造表达式119
6.3.5 着色问题122
6.3.6 n皇后问题125
6.3.7 任务分配问题127
6.3.8 哈密顿环问题129
习题132
第7章 分支界限法134
7.1 分支界限法概述134
7.1.1 什么是分支界限法134
7.1.2 分支界限法的设计理念135
7.1.3 分支界限法的算法评价135
7.2 分支界限法模型设计136
7.3 分支界限算法应用137
7.3.1 图的遍历与最短路径137
7.3.2 任务分配问题140
7.3.3 作业调度问题145
7.3.4 A*算法150
7.3.5 博弈搜索算法154
习题157
第8章 动态规划159
8.1 动态规划概述159
8.1.1 什么是动态规划159
8.1.2 动态规划的设计理念160
8.1.3 动态规划的算法评价160
8.2 动态规划模型设计160
8.3 动态规划算法应用161
8.3.1 最大连续子序列和161
8.3.2 最长递增子序列162
8.3.3 最长公共子序列165
8.3.4 三角最小路径和168
8.3.5 资源分配问题170
8.3.6 旅行商问题173
8.3.7 最少士兵数目问题176
8.3.8 矩阵连乘问题177
习题180
第9章 贪心算法182
9.1 贪心算法概述182
9.1.1 什么是贪心算法182
9.1.2 贪心算法的设计理念183
9.1.3 贪心算法的算法评价183
9.2 贪心算法模型设计183
9.3 贪心算法应用184
9.3.1 区间调度问题184
9.3.2 田忌赛马186
9.3.3 零钱兑换189
9.3.4 哈夫曼编码192
9.3.5 多机调度196
9.3.6 拟阵198
习题203
第10章 算法综合应用205
10.1 图算法205
10.1.1 最小生成树205
10.1.2 最短路径208
10.1.3 网络流(最大流、最小割、
匹配算法)212
10.2 背包问题217
10.2.1 0/1背包问题217
10.2.2 完全背包问题219
10.2.3 多重背包问题219
10.3 回顾旅行商问题220
10.4 几何问题223
10.4.1 向量运算223
10.4.2 凸包问题224
10.4.3 最远点对229
10.5 数论应用231
10.5.1 欧几里得算法232
10.5.2 同余定理234
10.5.3 素性检验算法236
10.6 NP问题238
10.6.1 P以及NP239
10.6.2 多项式时间归约239
10.6.3 NP完全问题239
10.6.4 NP困难问题239
10.7 概率算法240
10.7.1 数值概率算法240
10.7.2 蒙特卡洛算法242
10.7.3 拉斯维加斯算法243
10.7.4 舍伍德算法246
10.8 近似算法247
第11章 使用大语言模型学习
算法249
11.1 什么是大语言模型249
11.2 大语言模型能帮我们做些
什么250
11.3 尝试使用大语言模型进行
算法学习250
参考文献257
