新書推薦：
《
格林童话：1812/1815初版合集（权威全译本）
》
售價：HK$
117.6
《
思想会·军力：现代战争的胜败解释
》
售價：HK$
117.6
《
边界之外：海外社会研究（第一辑）
》
售價：HK$
82.8
《
好销售，不违心：在你的舒适区内拿订单
》
售價：HK$
70.8
《
阿富汗史：骑驰在风暴中的国度
》
售價：HK$
117.6
《
背影2
》
售價：HK$
82.8
《
她的罪名
》
售價：HK$
59.8
《
巨变与突围：碰撞中的清帝国：1644—1840
》
售價：HK$
93.6
|
| 編輯推薦： |
本书由北京大学优秀教学团队编写，凝聚了教学团队多年教学经验和科研成果。
计算机科学技术发展迅猛，各种新的技术和算法层出不穷。然而万变不离其宗，各种新的算法依然是建立在各种经典算法技术的基础上，最新的算法技术往往是对各种已有算法技术的组合和改进。在掌握了本书所介绍的各种经典算法技术之后，再学习理解新的算法技术时，或者再学习掌握各领域内的专门算法时，往往可以事半功倍。
本书以算法设计技术为主线组织素材，以伪码描述算法，深入分析了各种设计技术的使用范围、设计步骤、算法正确性证明与时间复杂度估计方法，以及改进算法的途径、局限性等，为实际问题的建模与算法设计在理论上提供清晰的思路。从对具体算法的设计与分析，自然过渡到对问题难度的分析和界定，系统地介绍了一些关于问题复杂度的分析方法。力求用清晰易懂的语言介绍NP完全性理论的核心内容和难解问题的处理策略，希望为求解实际中的复杂问题提供帮助。除了传统的算法外，本书还介绍了随机算法、模拟退火算法、基于统计物理的消息传递算法、量子算法等，给有兴趣的读者提供进一步学习和研究的入门知识。本书的主要素材来自多年的教学积淀，也有一些研究的心得。既注意理论上
|
| 內容簡介： |
|
本书为高等学校计算机类专业核心课程“算法设计与分析”教材. 全书以算法设计技术和分析方法为主线来组织各知识单元. 主要内容包括基础知识、分治策略、动态规划、贪心法、回溯与分支限界、线性规划、网络流算法、算法分析与问题的计算复杂度、NP完全性、近似算法、随机算法、处理难解问题的策略等. 力求突出对问题本身的分析和求解方法的阐述，从问题建模、算法设计与分析、改进措施等方面给出适当的建议，同时也简要介绍了计算复杂性理论的核心内容和处理难解问题的一些新技术. 与本书配套的有习题解答与学习指导用书、PPT电子教案以及MOOC视频教学资源等. 本书适合作为高等学校计算机科学与技术、软件工程、信息安全、信息与计算科学等专业本科生和研究生的教学用书，也可以作为从事实际问题求解的算法设计与分析工作的科技人员的参考书.
|
| 目錄：
|
第1章基础知识1
1.1有关算法的基本概念1
1.2算法的伪码描述5
1.3算法的数学基础6
1.3.1函数的渐近的界6
1.3.2求和的方法10
1.3.3递推方程求解方法12
习题121
第2章分治策略26
2.1分治策略的基本思想26
2.1.1两个熟悉的例子26
2.1.2分治算法的一般性描述27
2.2分治算法的分析技术27
2.3改进分治算法的途径31
2.3.1通过代数变换减少子问题个数31
2.3.2利用预处理减少递归内部的计算量34
2.4典型实例37
2.4.1快速排序算法37
2.4.2选择问题40
2.4.3n-1次多项式在全体2n次方根上的求值44
习题247
第3章动态规划52
3.1动态规划的设计思想52
3.1.1多起点、多终点的最短路径问题53
3.1.2使用动态规划技术的必要条件54
3.2动态规划算法的设计要素55目录算法设计与分析（第3版）3.2.1子问题的划分和递推方程56
3.2.2动态规划算法的递归实现57
3.2.3动态规划算法的迭代实现58
3.2.4一个简单实例的计算过程59
3.3动态规划算法的典型应用60
3.3.1投资问题60
3.3.2背包问题63
3.3.3最长公共子序列LCS65
3.3.4图像压缩68
3.3.5最大子段和72
3.3.6最优二分检索树76
3.3.7生物信息学中的动态规划算法80
习题383
第4章贪心法87
4.1贪心法的设计思想87
4.2关于贪心法的正确性证明90
4.3对贪心法得不到最优解情况的处理94
4.4贪心法的典型应用98
4.4.1最优前缀码98
4.4.2最小生成树103
4.4.3单源最短路径108
习题4110
第5章回溯与分支限界114
5.1回溯算法的基本思想和适用条件114
5.1.1几个典型的例子114
5.1.2回溯算法的适用条件118
5.2回溯算法的设计步骤119
5.2.1回溯算法的递归实现和迭代实现119
5.2.2几个典型的例子120
5.3回溯算法的效率估计和改进途径122
5.4分支限界124
5.4.1背包问题125
5.4.2最大团问题127
5.4.3货郎问题128
5.4.4圆排列问题129
5.4.5连续邮资问题131
习题5132
第6章线性规划134
6.1线性规划模型134
6.1.1模型134
6.1.2二维线性规划的图解法137
6.2标准形139
6.2.1标准形的基本概念139
6.2.2标准形的可行解的性质140
6.3单纯形法143
6.3.1确定初始基本可行解143
6.3.2最优性检验143
6.3.3基变换144
6.3.4单纯形表146
6.3.5人工变量和两阶段法148
6.3.6单纯形法的有限终止154
6.4对偶性155
6.4.1对偶线性规划155
6.4.2对偶单纯形法159
6.5整数线性规划的分支限界算法160
习题6165
第7章网络流算法171
7.1最大流问题171
7.1.1网络流及其性质171
7.1.2FordFulkerson算法173
7.1.3Dinic有效算法176
7.2最小费用流184
7.2.1Floyd算法184
7.2.2最小费用流的负回路算法186
7.2.3最小费用流的最短路径算法188
7.3运输问题189
7.3.1确定初始调运方案191
7.3.2改进调运方案191
7.3.3表上作业法193
7.4二部图匹配194
7.4.1二部图的最大匹配194
7.4.2赋权二部图的匹配197
习题7203
第8章算法分析与问题的计算复杂度208
8.1平凡下界209
8.2直接计数求解该问题所需要的最少运算210
8.3决策树211
8.4检索算法的时间复杂度分析212
8.5排序算法的时间复杂度分析214
8.5.1冒泡排序算法214
8.5.2堆排序算法215
8.5.3排序算法的决策树与算法类时间复杂度的下界220
8.6选择算法的时间复杂度分析222
8.6.1找最大和最小问题223
8.6.2找第二大问题224
8.6.3找中位数的问题226
8.7通过归约确认问题计算复杂度的下界228
习题8229
第9章NP完全性231
9.1P类与NP类231
9.1.1易解的问题与难解的问题231
9.1.2判定问题233
9.1.3NP类235
9.2多项式时间变换与NP完全性236
9.2.1多项式时间变换236
9.2.2NP完全性及其性质238
9.2.3CookLevin定理——第一个NP完全问题239
9.3几个NP完全问题239
9.3.1最大可满足性与三元可满足性239
9.3.2顶点覆盖、团与独立集241
9.3.3哈密顿回路与货郎问题243
9.3.4恰好覆盖245
9.3.5子集和、背包、装箱与双机调度247
9.3.6整数线性规划249
习题9252
第10章近似算法255
10.1近似算法及其近似比255
10.2多机调度问题256
10.2.1贪心的近似算法256
10.2.2改进的贪心近似算法257
10.3货郎问题258
10.3.1最邻近法258
10.3.2最小生成树法259
10.3.3最小权匹配法259
10.4背包问题261
10.4.1一个简单的贪心算法261
10.4.2多项式时间近似方案261
10.4.3伪多项式时间算法与完全多项式时间近似方案262
习题10264
第11章随机算法266
11.1概率论预备知识266
11.2对随机快速排序算法的分析268
11.3随机算法的分类及其局限性270
11.3.1拉斯维加斯型随机算法270
11.3.2蒙特卡洛型随机算法270
11.3.3随机算法的局限性271
11.4素数检验和多项式恒等检验271
11.4.1素数检验272
11.4.2多项式恒等检验273
11.5随机游动算法274
11.5.1有限马尔可夫链及其表示274
11.5.2求解二元布尔可满足性问题的随机游动算法275
11.6姚的极小极大原理276
习题11278
第12章处理难解问题的策略279
12.1对问题施加限制279
12.1.1二元可满足性问题280
12.1.2霍恩公式可满足性问题280
12.2固定参数算法282
12.3改进指数时间算法284
12.4启发式方法286
12.5平均情形的复杂性287
12.6难解算例生成289
12.6.1相变现象与难解性289
12.6.2隐藏解的难解算例291
12.7基于统计物理的消息传递算法292
12.7.1消息传递算法与回溯法、局部搜索算法的比较292
12.7.2用消息传递算法求解3SAT问题293
12.8量子算法简介294
12.8.1量子比特294
12.8.2正交测量295
12.8.3量子门296
12.8.4一个量子算法297
习题12299
参考文献300
|
| 內容試閱：
|
普通高等教育“十一五”国家级规划教材《算法设计与分析（第2版）》已经出版6年了. 在这6年里，计算机科学技术又有了新的发展，各种新的技术和算法层出不穷. 然而万变不离其宗，各种新的算法依然是建立在各种经典算法技术的基础上，最新的算法技术往往是对各种已有算法技术的组合和改进. 掌握了本书所介绍的各种经典算法技术之后，在学习理解新的算法技术时，或者在学习掌握各领域内的专门算法时，可以事半功倍.
本次修订对第2版的内容未作大的改动，除了订正一些错误，以及对文字做了进一步的精细加工外，主要在第11章中新增最后一节，介绍了姚的极小极大原理，并补充了相应的习题. 姚的极小极大原理是证明随机算法复杂度下界的主要工具，在各种随机算法模型下都有着广泛应用.
本次修订主要由刘田完成. 对广大读者提出的宝贵建议和意见，以及清华大学出版社的大力支持，我们一如既往地表示衷心的感谢！
作者2022年6月于北京大学第2版前言FOREWORD作为普通高等教育“十一五”国家级规划教材，《算法设计与分析》出版已经近5年了. 在这5年的时间里，大数据、云计算、“互联网 ”等新领域、新问题、新应用层出不穷，许多问题求解都离不开问题的建模和算法的设计与分析.
这次修订保持了第1版原书的基本结构、主要内容与写作特色，仍旧以算法设计技术为主线来组织素材. 考虑到线性规划与网络流问题在实践中的广泛应用，本书增加了两章(第6、7章)内容，并在第9章中增添了整数线性规划的NP完全性证明. 此外，补充了部分习题，并对原书的某些疏漏之处进行了更新.
与本书同步更新的还有教学辅导用书《算法设计与分析习题解答与学习指导（第2版）》、PPT电子课件，本书MOOC视频教学资源也将于近期完成.
本书第1章至第4章由屈婉玲完成，第5章和第8章由王捍贫完成，第6章、第7章、第9章和第10章由张立昂完成，第11章和第12章由刘田完成. 对广大读者所提出的建议和意见，我们表示衷心的感谢！
作者2015年11月于北京大学第1版前言FOREWORD作为问题求解和程序设计的重要基础，“算法设计与分析”在高等学校计算机科学与技术专业的课程体系中是一门重要的必修课. 通过该课程的学习，不但为学习其他专业课程奠定了扎实的基础，也对培养学生的逻辑思维和创造性有着不可替代的作用. ACM IEEE Computing Curricula 2004与我国教育高等学校计算机科学与技术专业教学指导委员会提出的《计算机科学与技术专业规范》都把该课程列入相关专业的核心课程之一. 纵观计算机学科数十年发展的历史，算法与计算复杂性理论一直是计算机科学研究的热点和活跃领域，也是获得图灵奖最多的研究领域之一. 面对计算机应用领域的大量问题，最重要的是根据问题的性质选择正确的求解思路，即找到一个好的算法. 特别在复杂的、海量信息的处理中，一个好的算法往往起着决定性的作用.
目前已经出版了许多算法教材，各有特色. 作为普通高等教育“十一五”国家级规划教材，我们在多年从事算法设计分析及计算复杂性理论的教学和研究的基础上，精心选材，完成了本书的写作. 本书的主要特点是：
(1) 以算法设计技术为主线来组织素材，深入分析各种设计技术的适用范围、设计步骤、算法的正确性证明与复杂度的分析方法、算法改进的途径、局限性等. 与通常的算法与数据结构教材有所不同，本书不过多地关注实现细节，算法描述采用伪码，力求突出对问题本身的分析和求解方法的阐述，从问题建模、算法设计与分析、改进措施等方面给出适当的建议，为从事实际问题的算法设计与分析工作在理论上提供清晰的、整体的思路和方法.
(2) 从对具体算法的设计技术与分析方法，自然过渡到对问题难度的分析和界定. 这里处理的不是一个具体的算法，而是对求解该问题的一大类算法的评价和分析，是对问题本身计算复杂度的估计. 基于这种分析，就能回答“求解该问题的最好算法是什么”和“它能好到什么程度”等问题，从而为选择最好的算法给出依据. 一般的算法教材涉及这方面的知识比较少，本书比较系统地介绍了一些关于问题复杂度的分析方法.
(3) NP完全理论是计算复杂性理论的核心内容，其中“P≠NP”问题是21世纪最重要的数学难题之一. 计算复杂性理论关注的不仅仅是某个具体问题，而是希望了解每一个问题在计算难度的层次结构中到底处于什么位置，不同问题的难度之间有什么关系. 本书力求用清晰易懂的语言，对计算复杂性理论的核心内容和针对难解问题的处理策略加以简单的介绍，希望为从事复杂问题求解的读者提供一点帮助.
(4) 本书的素材来自多年的教学积淀，选材适当，组织合理，首先引入基本概念和数学基础知识，然后进入算法设计与分析的核心内容. 在叙述中不但注意理论的严谨，也精选了大量生动有趣的例子. 每章都配有难度适当的练习，适合教学使用.
全书共10章，第1章是基础知识，介绍和算法设计与分析有关的基本概念、符号和数学知识；第2章至第5章分别阐述分治策略、动态规划、贪心法、回溯与分支限界等算法设计技术；第6章介绍算法分析与问题的计算复杂度；第7章是NP完全性理论；第8章是近似算法；第9章是随机算法；第10章介绍处理难解问题的策略.
本书既可以作为本科生教材，也可以作为研究生教材. 对于本科生教学，建议讲授第1章至第6章的全部内容，第7章至第10章可根据情况选择部分内容做一些概括性的介绍. 研究生教学可以选择第1章至第9章的全部内容，第10章可根据情况选讲. 此外，对于从事实际问题求解的研究工作者，本书也可以作为一本算法设计与分析的入门参考书.
为了更好地为使用本教材的读者服务，作者正在撰写和开发与本教材配套的教学辅导书和PPT电子教案.
本书的第1章至第4章由屈婉玲完成，第5章和第6章由王捍贫完成，第7章和第8章由张立昂完成，第9章和第10章由刘田完成.
在编写过程中，作者参考了国内外多种版本的算法设计与分析以及计算复杂性方面的教材、论文和专著，从中吸取了一些好的思路和素材，在此一并向有关作者致谢. 特别感谢李晓明教授审阅了初稿并提出了宝贵意见，感谢清华大学出版社对本书出版的大力支持. 我们期待着广大读者，特别是使用本书的教师和学生对本书的批评、指正和建议.
作者2010年11月于北京大学
|
|
購物車/收銀台(
0
) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
