作者：吴及,陈健生,白铂编著
页数：346
出版社：清华大学出版社
出版日期：2017
ISBN：9787302468813
电子书格式：pdf/epub/txt
内容简介
为了解决膨胀的知识量与有限的学制之间的矛盾，提高教学效率和质量，培养拔尖型创新人才，清华大学电子工程系进行了全面的教学改革。在梳理出电子信息科学与技术知识构架的基础上，构建起了全新的课程体系。本书是清华大学电子工程系核心课系列教材之一，由清华大学副校长王希勤教授作序推荐。随着大数据和数据科学的兴起和发展，如何看待、处理和利用数据，已经成为理论和应用价值巨大的科学领域。本书从数据与算法的相互作用出发，涵盖数据结构、数学模型、数值分析和算法设计思想等相互关联的重要内容，有利于从整体上学习和把握这个学科的基础知识，培养基础能力。书中，问题和算法两个视角构成了纵横交织的网络，帮助读者更清楚地看到数据和算法的相互关系，更透彻地理解数值和非数值问题的差异和共性，帮助读者更全面地提升利用计算机作为工具解决实际问题的能力。
作者简介
作者简介：吴及，清华大学电子工程系副系主任，长聘副教授，博士生导师。1996年和2001年在清华大学电子工程系获得学士和工学博士学位。2013—2015年在美国佐治亚理工学院担任访问学者。主要从事数据与算法方面的教学工作，以及人工智能和大数据领域的研究工作。2006起担任清华-讯飞语音技术联合实验室主任。目前是中国语音产业联盟技术工作组组长。先后获得2011年度国家科技进步二等奖和2014年度北京市科学技术奖一等奖。已在国内外刊物和学术会议上发表论文一百余篇，现在为IEEE高级会员。
陈健生，博士，出生于安徽省芜湖市，毕业于清华大学计算机科学与技术系（学士、硕士）和香港中文大学计算机科学与工程系（博士）。目前在清华大学电子工程系任副教授，博士生导师。教学方面，担任电子系本科生核心课“数据与算法”及限选课“视听信息系统导论”的主讲教师；曾获清华大学第六届青年教师教学大赛理工科一等奖。主要研究领域为计算机视觉与机器学习。在国际期刊及会议上发表有多篇论文，曾获2013年度北京市科学技术奖一等奖。
白铂，男，1982年生于陕西西安，2004年毕业于西安电子科技大学，获学士学位，陕西省优秀毕业生。2010毕业于清华大学，获博士学位，电子系学术新秀。2010—2012年在香港科技大学做博士后研究。随后，进入清华大学电子系任讲师，硕士生导师。曾获2016年清华大学青年教师教学基本功大赛一等奖（理工组）。2017年加入华为技术有限公司2012实验室，任未来网络理论实验室高级研究员。研究方向包括无线协作资源分配、Cloud/Fog-无线计算网络、网络信息论、网络大数据分析等。发表学术论文近80篇，其中SCI检索论文近30篇，曾获IEEE ICC 2016最佳论文奖。
本书特色
本书从数据与算法的相互关系入手，内容涵盖了传统的数据结构和数值分析，并增加了数学模型和算法设计思想的介绍。
全书分四部分，最部分，介绍数据、数学模型和算法的基本概念，是全书的基础；数据结构部分从数学模型和问题的角度介绍线性结构、树结构、图结构，以及查找和排序这两种最常见的非数值问题；数值分析部分从问题的角度介绍误差分析、实数的表示和运算、一元非线性方程、线性方程组、拟合与插值、最化问题；第四部分，从算法设计思想的角度介绍蛮力法、分治法、贪心法、动态规划、搜索算法和最算法，以及求解具体问题时的应用实例。
目录
目录
第 1章数据、数学模型和算法 …………………………………………………………………….. 1
1.1数据时代 ……………………………………………………………………………………… 1
1.1.1什么是数据 …………………………………………………………………………. 1
1.1.2大数据时代 …………………………………………………………………………. 2
1.1.3数据的重要性 ………………………………………………………………………. 4
1.2数据的表示 …………………………………………………………………………………… 5
1.2.1二元关系及其性质 ………………………………………………………………… 5
1.2.2数据的逻辑结构 …………………………………………………………………… 9
1.2.3数据的存储结构 …………………………………………………………………..12
1.2.4抽象数据类型 ………………………………………………………………………12
1.3数学模型 ……………………………………………………………………………………..13
1.3.1什么是数学模型 …………………………………………………………………..13
1.3.2数学模型的种类 …………………………………………………………………..14
1.3.3数学模型与计算机 ………………………………………………………………..15
1.3.4数据结构 ……………………………………………………………………………16
1.4算法及复杂度分析 ………………………………………………………………………….16
1.4.1什么是算法 …………………………………………………………………………16
1.4.2问题与解 ……………………………………………………………………………17
1.4.3算法的分析与评价 ………………………………………………………………..18
1.5本章小结 ……………………………………………………………………………………..22
第 2章线性结构………………………………………………………………………………………24
2.1线性表 ………………………………………………………………………………………..24
2.1.1线性表的概念及其抽象数据类型 ………………………………………………24
2.1.2线性表的顺序存储——顺序表 …………………………………………………27
2.1.3线性表的链式存储——链表 …………………………………………………….30
2.1.4线性表小结 …………………………………………………………………………35
2.2栈 ………………………………………………………………………………………………35
2.2.1栈的概念与实现 …………………………………………………………………..35
2.2.2栈的应用 ……………………………………………………………………………38
2.2.3递归 ………………………………………………………………………………….41
2.3队列 ……………………………………………………………………………………………48
2.3.1队列的概念与实现 ………………………………………………………………..48
2.3.2优先级队列 …………………………………………………………………………51
2.4字符串 ………………………………………………………………………………………..55
2.4.1字符串的概念和 ADT …………………………………………………………….55
2.4.2字符串的存储表示 ………………………………………………………………..56
2.4.3字符串的模式匹配和简单匹配算法 ……………………………………………57
2.4.4 KMP算法 ………………………………………………………………………….58
2.5本章小结 ……………………………………………………………………………………..61
第 3章树与二叉树 …………………………………………………………………………………..62
3.1树的基本概念 ……………………………………………………………………………….62
3.1.1普遍存在的树结构 ………………………………………………………………..62
3.1.2树的定义和性质 …………………………………………………………………..65
3.2二叉树 ………………………………………………………………………………………..67
3.2.1二叉树的定义和性质 ……………………………………………………………..68
3.2.2二叉树的表示和实现 ……………………………………………………………..70
3.2.3二叉树的遍历 ………………………………………………………………………76
3.2.4二叉树运算 …………………………………………………………………………81
3.2.5二叉树的建立 ………………………………………………………………………83
3.3二叉树的应用 ……………………………………………………………………………….84
3.3.1表达式求值 …………………………………………………………………………84
3.3.2二叉搜索树 …………………………………………………………………………85
3.3.3 Hu.man树与编码 ………………………………………………………………..89
3.3.4堆 …………………………………………………………………………………….95
3.4并查集 ……………………………………………………………………………………… 102
3.5本章小结 …………………………………………………………………………………… 103
第 4章图…………………………………………………………………………………………….. 105
4.1图的基本概念 …………………………………………………………………………….. 105
4.1.1图的定义和概念 ………………………………………………………………… 105
4.1.2图的抽象数据类型 ……………………………………………………………… 110
4.1.3欧拉路径 …………………………………………………………………………. 110
4.2图的存储结构 …………………………………………………………………………….. 112
4.2.1图的邻接矩阵表示 ……………………………………………………………… 112
4.2.2图的邻接表表示 ………………………………………………………………… 115
4.2.3图的其他表示方法 ……………………………………………………………… 119
4.3图的遍历 …………………………………………………………………………………… 122
4.3.1图的深度优先遍历 ……………………………………………………………… 123
目录 IX 4.3.2图的广度优先遍历 ……………………………………………………………… 124
4.3.3图遍历的应用 ……………………………………………………………………. 125
4.3.4图的连通性 ………………………………………………………………………. 128
4.4有向图与有向无环图 ……………………………………………………………………. 129
4.4.1有向图的连通性和传递闭包 ………………………………………………….. 129
4.4.2有向无环图和拓扑排序 ……………………………………………………….. 132
4.4.3关键路径 …………………………………………………………………………. 135
4.5最小生成树 ………………………………………………………………………………… 137
4.5.1图的生成树与最小生成树 …………………………………………………….. 137
4.5.2普里姆 (Prim)算法 ……………………………………………………………. 139
4.5.3克鲁斯卡尔 (Kruskal)算法 …………………………………………………… 142
4.6最短路径问题 …………………………………………………………………………….. 144
4.6.1单源最短路径 ……………………………………………………………………. 145
4.6.2全源最短路径 ……………………………………………………………………. 147
4.7最大流 ……………………………………………………………………………………… 149
4.7.1网络流的基本概念 ……………………………………………………………… 150
4.7.2 Ford-Fulkerson方法 …………………………………………………………… 151
4.8匹配 …………………………………………………………………………………………. 154
4.8.1二分图和匹配的基本概念 …………………………………………………….. 154
4.8.2匈牙利算法 ………………………………………………………………………. 155
4.8.3最大匹配与最大流 ……………………………………………………………… 157
4.9本章小结 …………………………………………………………………………………… 157
第 5章查找和排序 ………………………………………………………………………………… 159
5.1线性查找表 ………………………………………………………………………………… 159
5.1.1顺序查找 …………………………………………………………………………. 160
5.1.2折半查找 …………………………………………………………………………. 161
5.1.3斐波那契查找 ……………………………………………………………………. 162
5.1.4线性查找表的性能比较 ……………………………………………………….. 163
5.2静态索引结构 …………………………………………………………………………….. 164
5.2.1索引查找 …………………………………………………………………………. 164
5.2.2索引存储方式 ……………………………………………………………………. 164
5.2.3索引文件结构 ……………………………………………………………………. 167
5.3二叉搜索树查找性能 ……………………………………………………………………. 169
5.4散列方法 …………………………………………………………………………………… 172
5.4.1散列技术的基本思想 …………………………………………………………… 172
5.4.2散列函数 …………………………………………………………………………. 173
5.4.3冲突处理 …………………………………………………………………………. 175
5.4.4散列的删除 ………………………………………………………………………. 178
5.4.5散列的性能 ………………………………………………………………………. 178
5.5排序的概念及算法性能分析 …………………………………………………………… 179
5.6基本排序方法 …………………………………………………………………………….. 180
5.6.1冒泡排序 …………………………………………………………………………. 181
5.6.2插入排序 …………………………………………………………………………. 182
5.6.3直接选择排序 ……………………………………………………………………. 187
5.6.4基本排序方法的比较 …………………………………………………………… 188
5.7快速排序 …………………………………………………………………………………… 189
5.7.1快速排序的过程 ………………………………………………………………… 189
5.7.2快速排序的性能分析 …………………………………………………………… 191
5.8归并排序 …………………………………………………………………………………… 192
5.8.1二路归并 …………………………………………………………………………. 192
5.8.2自底向上的归并排序 …………………………………………………………… 192
5.8.3自顶向下的归并排序 …………………………………………………………… 194
5.9堆和堆排序 ………………………………………………………………………………… 195
5.9.1堆排序的思想 ……………………………………………………………………. 195
5.9.2堆排序的实现 ……………………………………………………………………. 197
5.10内排序方法分析 ………………………………………………………………………… 198
5.10.1排序方法的下界 ……………………………………………………………… 198
5.10.2内排序方法的比较 …………………………………………………………… 199
5.11本章小结 …………………………………………………………………………………. 200
第 6章数值计算问题 ……………………………………………………………………………… 202
6.1引言 …………………………………………………………………………………………. 202
6.2近似与误差 ………………………………………………………………………………… 204
6.2.1误差的定义 ………………………………………………………………………. 204
6.2.2误差的分类 ………………………………………………………………………. 209
6.2.3条件数与敏感性 ………………………………………………………………… 212
6.3实数的表示与运算 ……………………………………………………………………….. 214
6.3.1浮点数系统 ………………………………………………………………………. 214
6.3.2浮点运算 …………………………………………………………………………. 217
6.4一元方程求解 …………………………………………………………………………….. 219
6.4.1一元方程 …………………………………………………………………………. 219
6.4.2二分法 …………………………………………………………………………….. 220
6.4.3不动点法 …………………………………………………………………………. 222
6.4.4牛顿法 …………………………………………………………………………….. 225
6.4.5迭代误差分析 ……………………………………………………………………. 229
6.5线性方程组求解 ………………………………………………………………………….. 232
6.5.1线性方程组 ………………………………………………………………………. 232
目录 XI 6.5.2向量与矩阵范数 ………………………………………………………………… 234
6.5.3线性方程组敏感性 ……………………………………………………………… 239
6.5.4线性方程组直接解法 …………………………………………………………… 242
6.5.5线性方程组迭代解法 …………………………………………………………… 252
6.6拟合与插值 ………………………………………………………………………………… 256
6.6.1线性最小二乘 ……………………………………………………………………. 256
6.6.2多项式插值 ………………………………………………………………………. 264
6.7本章小结 …………………………………………………………………………………… 267
第 7章最优化初步 ………………………………………………………………………………… 268
7.1优化问题及其性质 ……………………………………………………………………….. 268
7.2无约束优化问题 ………………………………………………………………………….. 271
7.2.1优化条件 …………………………………………………………………………. 271
7.2.2一维优化 …………………………………………………………………………. 272
7.2.3多维优化 …………………………………………………………………………. 275
7.3约束优化问题 …………………………………………………………………………….. 279
7.3.1优化条件 …………………………………………………………………………. 279
7.3.2序列二次规划法 ………………………………………………………………… 282
7.3.3障碍法 …………………………………………………………………………….. 284
7.4凸优化 ……………………………………………………………………………………… 286
7.4.1凸集合 …………………………………………………………………………….. 286
7.4.2凸函数 …………………………………………………………………………….. 289
7.4.3凸优化问题 ………………………………………………………………………. 292
7.5组合优化的数值求解 ……………………………………………………………………. 294
7.5.1组合优化问题 ……………………………………………………………………. 294
7.5.2线性规划初步 ……………………………………………………………………. 296
7.5.3顶点覆盖的线性规划求解 …………………………………………………….. 297
7.6本章小结 …………………………………………………………………………………… 298
第 8章随机算法……………………………………………………………………………………. 299
8.1随机性与随机数 ………………………………………………………………………….. 299
8.2舍伍德与拉斯维加斯算法 ………………………………………………………………. 301
8.3蒙特卡洛算法 …………………………………………………………………………….. 304
8.4模拟退火与遗传算法 ……………………………………………………………………. 307
8.5本章小结 …………………………………………………………………………………… 310
第 9章算法设计思想 ……………………………………………………………………………… 311
9.1蛮力法 ……………………………………………………………………………………… 311
9.2分治法 ……………………………………………………………………………………… 313
9.2.1分治法的运行时间 ……………………………………………………………… 314
9.2.2分治法应用举例 ………………………………………………………………… 316
9.2.3减治法 …………………………………………………………………………….. 319
9.2.4变治法 …………………………………………………………………………….. 321
9.3贪心法 ……………………………………………………………………………………… 323
9.4动态规划 …………………………………………………………………………………… 326
9.4.1动态规划的基本原理 …………………………………………………………… 326
9.4.2算法设计举例 ……………………………………………………………………. 328
9.5搜索算法：回溯法与分支定界法 ……………………………………………………… 334
9.5.1组合优化问题的解空间 ……………………………………………………….. 334
9.5.2回溯法 …………………………………………………………………………….. 338
9.5.3分支定界法 ………………………………………………………………………. 342
第 1章数据、数学模型和算法 …………………………………………………………………….. 1
1.1数据时代 ……………………………………………………………………………………… 1
1.1.1什么是数据 …………………………………………………………………………. 1
1.1.2大数据时代 …………………………………………………………………………. 2
1.1.3数据的重要性 ………………………………………………………………………. 4
1.2数据的表示 …………………………………………………………………………………… 5
1.2.1二元关系及其性质 ………………………………………………………………… 5
1.2.2数据的逻辑结构 …………………………………………………………………… 9
1.2.3数据的存储结构 …………………………………………………………………..12
1.2.4抽象数据类型 ………………………………………………………………………12
1.3数学模型 ……………………………………………………………………………………..13
1.3.1什么是数学模型 …………………………………………………………………..13
1.3.2数学模型的种类 …………………………………………………………………..14
1.3.3数学模型与计算机 ………………………………………………………………..15
1.3.4数据结构 ……………………………………………………………………………16
1.4算法及复杂度分析 ………………………………………………………………………….16
1.4.1什么是算法 …………………………………………………………………………16
1.4.2问题与解 ……………………………………………………………………………17
1.4.3算法的分析与评价 ………………………………………………………………..18
1.5本章小结 ……………………………………………………………………………………..22
第 2章线性结构………………………………………………………………………………………24
2.1线性表 ………………………………………………………………………………………..24
2.1.1线性表的概念及其抽象数据类型 ………………………………………………24
2.1.2线性表的顺序存储——顺序表 …………………………………………………27
2.1.3线性表的链式存储——链表 …………………………………………………….30
2.1.4线性表小结 …………………………………………………………………………35
2.2栈 ………………………………………………………………………………………………35
2.2.1栈的概念与实现 …………………………………………………………………..35
2.2.2栈的应用 ……………………………………………………………………………38
2.2.3递归 ………………………………………………………………………………….41
2.3队列 ……………………………………………………………………………………………48
2.3.1队列的概念与实现 ………………………………………………………………..48
2.3.2优先级队列 …………………………………………………………………………51
2.4字符串 ………………………………………………………………………………………..55
2.4.1字符串的概念和 ADT …………………………………………………………….55
2.4.2字符串的存储表示 ………………………………………………………………..56
2.4.3字符串的模式匹配和简单匹配算法 ……………………………………………57
2.4.4 KMP算法 ………………………………………………………………………….58
2.5本章小结 ……………………………………………………………………………………..61
第 3章树与二叉树 …………………………………………………………………………………..62
3.1树的基本概念 ……………………………………………………………………………….62
3.1.1普遍存在的树结构 ………………………………………………………………..62
3.1.2树的定义和性质 …………………………………………………………………..65
3.2二叉树 ………………………………………………………………………………………..67
3.2.1二叉树的定义和性质 ……………………………………………………………..68
3.2.2二叉树的表示和实现 ……………………………………………………………..70
3.2.3二叉树的遍历 ………………………………………………………………………76
3.2.4二叉树运算 …………………………………………………………………………81
3.2.5二叉树的建立 ………………………………………………………………………83
3.3二叉树的应用 ……………………………………………………………………………….84
3.3.1表达式求值 …………………………………………………………………………84
3.3.2二叉搜索树 …………………………………………………………………………85
3.3.3 Hu.man树与编码 ………………………………………………………………..89
3.3.4堆 …………………………………………………………………………………….95
3.4并查集 ……………………………………………………………………………………… 102
3.5本章小结 …………………………………………………………………………………… 103
第 4章图…………………………………………………………………………………………….. 105
4.1图的基本概念 …………………………………………………………………………….. 105
4.1.1图的定义和概念 ………………………………………………………………… 105
4.1.2图的抽象数据类型 ……………………………………………………………… 110
4.1.3欧拉路径 …………………………………………………………………………. 110
4.2图的存储结构 …………………………………………………………………………….. 112
4.2.1图的邻接矩阵表示 ……………………………………………………………… 112
4.2.2图的邻接表表示 ………………………………………………………………… 115
4.2.3图的其他表示方法 ……………………………………………………………… 119
4.3图的遍历 …………………………………………………………………………………… 122
4.3.1图的深度优先遍历 ……………………………………………………………… 123
目录 IX 4.3.2图的广度优先遍历 ……………………………………………………………… 124
4.3.3图遍历的应用 ……………………………………………………………………. 125
4.3.4图的连通性 ………………………………………………………………………. 128
4.4有向图与有向无环图 ……………………………………………………………………. 129
4.4.1有向图的连通性和传递闭包 ………………………………………………….. 129
4.4.2有向无环图和拓扑排序 ……………………………………………………….. 132
4.4.3关键路径 …………………………………………………………………………. 135
4.5最小生成树 ………………………………………………………………………………… 137
4.5.1图的生成树与最小生成树 …………………………………………………….. 137
4.5.2普里姆 (Prim)算法 ……………………………………………………………. 139
4.5.3克鲁斯卡尔 (Kruskal)算法 …………………………………………………… 142
4.6最短路径问题 …………………………………………………………………………….. 144
4.6.1单源最短路径 ……………………………………………………………………. 145
4.6.2全源最短路径 ……………………………………………………………………. 147
4.7最大流 ……………………………………………………………………………………… 149
4.7.1网络流的基本概念 ……………………………………………………………… 150
4.7.2 Ford-Fulkerson方法 …………………………………………………………… 151
4.8匹配 …………………………………………………………………………………………. 154
4.8.1二分图和匹配的基本概念 …………………………………………………….. 154
4.8.2匈牙利算法 ………………………………………………………………………. 155
4.8.3最大匹配与最大流 ……………………………………………………………… 157
4.9本章小结 …………………………………………………………………………………… 157
第 5章查找和排序 ………………………………………………………………………………… 159
5.1线性查找表 ………………………………………………………………………………… 159
5.1.1顺序查找 …………………………………………………………………………. 160
5.1.2折半查找 …………………………………………………………………………. 161
5.1.3斐波那契查找 ……………………………………………………………………. 162
5.1.4线性查找表的性能比较 ……………………………………………………….. 163
5.2静态索引结构 …………………………………………………………………………….. 164
5.2.1索引查找 …………………………………………………………………………. 164
5.2.2索引存储方式 ……………………………………………………………………. 164
5.2.3索引文件结构 ……………………………………………………………………. 167
5.3二叉搜索树查找性能 ……………………………………………………………………. 169
5.4散列方法 …………………………………………………………………………………… 172
5.4.1散列技术的基本思想 …………………………………………………………… 172
5.4.2散列函数 …………………………………………………………………………. 173
5.4.3冲突处理 …………………………………………………………………………. 175
5.4.4散列的删除 ………………………………………………………………………. 178
5.4.5散列的性能 ………………………………………………………………………. 178
5.5排序的概念及算法性能分析 …………………………………………………………… 179
5.6基本排序方法 …………………………………………………………………………….. 180
5.6.1冒泡排序 …………………………………………………………………………. 181
5.6.2插入排序 …………………………………………………………………………. 182
5.6.3直接选择排序 ……………………………………………………………………. 187
5.6.4基本排序方法的比较 …………………………………………………………… 188
5.7快速排序 …………………………………………………………………………………… 189
5.7.1快速排序的过程 ………………………………………………………………… 189
5.7.2快速排序的性能分析 …………………………………………………………… 191
5.8归并排序 …………………………………………………………………………………… 192
5.8.1二路归并 …………………………………………………………………………. 192
5.8.2自底向上的归并排序 …………………………………………………………… 192
5.8.3自顶向下的归并排序 …………………………………………………………… 194
5.9堆和堆排序 ………………………………………………………………………………… 195
5.9.1堆排序的思想 ……………………………………………………………………. 195
5.9.2堆排序的实现 ……………………………………………………………………. 197
5.10内排序方法分析 ………………………………………………………………………… 198
5.10.1排序方法的下界 ……………………………………………………………… 198
5.10.2内排序方法的比较 …………………………………………………………… 199
5.11本章小结 …………………………………………………………………………………. 200
第 6章数值计算问题 ……………………………………………………………………………… 202
6.1引言 …………………………………………………………………………………………. 202
6.2近似与误差 ………………………………………………………………………………… 204
6.2.1误差的定义 ………………………………………………………………………. 204
6.2.2误差的分类 ………………………………………………………………………. 209
6.2.3条件数与敏感性 ………………………………………………………………… 212
6.3实数的表示与运算 ……………………………………………………………………….. 214
6.3.1浮点数系统 ………………………………………………………………………. 214
6.3.2浮点运算 …………………………………………………………………………. 217
6.4一元方程求解 …………………………………………………………………………….. 219
6.4.1一元方程 …………………………………………………………………………. 219
6.4.2二分法 …………………………………………………………………………….. 220
6.4.3不动点法 …………………………………………………………………………. 222
6.4.4牛顿法 …………………………………………………………………………….. 225
6.4.5迭代误差分析 ……………………………………………………………………. 229
6.5线性方程组求解 ………………………………………………………………………….. 232
6.5.1线性方程组 ………………………………………………………………………. 232
目录 XI 6.5.2向量与矩阵范数 ………………………………………………………………… 234
6.5.3线性方程组敏感性 ……………………………………………………………… 239
6.5.4线性方程组直接解法 …………………………………………………………… 242
6.5.5线性方程组迭代解法 …………………………………………………………… 252
6.6拟合与插值 ………………………………………………………………………………… 256
6.6.1线性最小二乘 ……………………………………………………………………. 256
6.6.2多项式插值 ………………………………………………………………………. 264
6.7本章小结 …………………………………………………………………………………… 267
第 7章最优化初步 ………………………………………………………………………………… 268
7.1优化问题及其性质 ……………………………………………………………………….. 268
7.2无约束优化问题 ………………………………………………………………………….. 271
7.2.1优化条件 …………………………………………………………………………. 271
7.2.2一维优化 …………………………………………………………………………. 272
7.2.3多维优化 …………………………………………………………………………. 275
7.3约束优化问题 …………………………………………………………………………….. 279
7.3.1优化条件 …………………………………………………………………………. 279
7.3.2序列二次规划法 ………………………………………………………………… 282
7.3.3障碍法 …………………………………………………………………………….. 284
7.4凸优化 ……………………………………………………………………………………… 286
7.4.1凸集合 …………………………………………………………………………….. 286
7.4.2凸函数 …………………………………………………………………………….. 289
7.4.3凸优化问题 ………………………………………………………………………. 292
7.5组合优化的数值求解 ……………………………………………………………………. 294
7.5.1组合优化问题 ……………………………………………………………………. 294
7.5.2线性规划初步 ……………………………………………………………………. 296
7.5.3顶点覆盖的线性规划求解 …………………………………………………….. 297
7.6本章小结 …………………………………………………………………………………… 298
第 8章随机算法……………………………………………………………………………………. 299
8.1随机性与随机数 ………………………………………………………………………….. 299
8.2舍伍德与拉斯维加斯算法 ………………………………………………………………. 301
8.3蒙特卡洛算法 …………………………………………………………………………….. 304
8.4模拟退火与遗传算法 ……………………………………………………………………. 307
8.5本章小结 …………………………………………………………………………………… 310
第 9章算法设计思想 ……………………………………………………………………………… 311
9.1蛮力法 ……………………………………………………………………………………… 311
9.2分治法 ……………………………………………………………………………………… 313
9.2.1分治法的运行时间 ……………………………………………………………… 314
9.2.2分治法应用举例 ………………………………………………………………… 316
9.2.3减治法 …………………………………………………………………………….. 319
9.2.4变治法 …………………………………………………………………………….. 321
9.3贪心法 ……………………………………………………………………………………… 323
9.4动态规划 …………………………………………………………………………………… 326
9.4.1动态规划的基本原理 …………………………………………………………… 326
9.4.2算法设计举例 ……………………………………………………………………. 328
9.5搜索算法：回溯法与分支定界法 ……………………………………………………… 334
9.5.1组合优化问题的解空间 ……………………………………………………….. 334
9.5.2回溯法 …………………………………………………………………………….. 338
9.5.3分支定界法 ………………………………………………………………………. 342
