|
| 編輯推薦： |
《算法设计与分析（第3版）》是“十二五”普通高等教育本科规划教材；由具有25年算法与数据结构教学经验，同时具有指导ACM竞赛经验的省级教学名师王红梅老师编著。100多所高校、近10万学子先后使用，是算法设计与分析课程的经典教材。
将算法设计技术划分为基本的算法设计技术、基于搜索的算法设计技术、NP问题的算法设计技术三个模块，内容相互独立，拓扑结构合理。
系统而全面地介绍了算法设计技术，包括模拟法、递推法、蛮力法、分治法、减治法、贪心法、动态规划法、深度优先搜索、广度优先搜索、回溯法、A*算法、限界剪枝法、近似算法、概率算法和群智能算法。
将经典问题和算法设计技术很好地结合起来，读者可以体会同一算法设计技术在不同问题中的应用，以及相同问题的不同解决方法。
兼顾技术层和实现层，注重算法设计过程，按照“问题->想法->算法->程序”的模式，所有问题都用伪代码给出了算法描述，所有程序均在C 典型编程环境下调试通过。
附配实验项目、教学课件、程序源码等数字化教学资源。
|
| 內容簡介： |
|
本书将经典问题和算法设计技术结合，以读者容易理解和接受的方式，系统介绍了算法设计技术，包括模拟法、递推法、蛮力法、分治法、减治法、贪心法、动态规划法、深度优先搜索、广度优先搜索、回溯法、A*算法、限界剪枝法、近似算法、概率算法和群智能算法；同时以通俗易懂的方式，系统介绍了算法分析技术，包括算法的时间复杂度分析、空间复杂度分析、**算法、确定性算法、非确定性算法、P类问题、NP类问题和NP完全问题。所有问题都用伪代码给出了算法描述，并提供了C 语言程序源码，且在C 语言的典型编程环境下调试通过。 本书案例丰富，叙述清晰，深入浅出，结合应用，符合算法学习者的认知规律，可作为高等院校计算机专业本科和研究生学习算法类课程的教材，适合准备参加程序设计竞赛（NOIP或ACM）却无从下手的学生，也特别适合算法爱好者学习参考。
|
| 關於作者： |
|
王红梅，女，53岁，三级教授，硕士生导师，省级教学名师，省级教学团队“算法与程序设计”带头人，从事计算机专业教学工作24年，精品课“计算机学科概论”、一流课程“数据结构”负责人，出版了《数据结构（C 版）》、《计算机学科概论》、《程序设计基础》、《算法设计与分析》等教材，均被评为“十二五”规划教材，《数据结构（C 版）》参评首批优秀教材，获省级教学成果奖一等奖1项、二等奖2项、三等奖2项，发表学术论文20余篇。
|
| 目錄：
|
篇基 础 知 识
第1章算法设计基础3
1.1什么是算法3
1.1.1算法的定义3
1.1.2算法的描述方法4
1.1.3算法在问题求解中的地位6
1.2什么是好算法6
1.2.1如何评价算法6
1.2.2效率——算法的核心和灵魂7
1.3为什么要学习和研究算法8
1.3.1算法研究是推动计算机技术发展的关键8
1.3.2算法训练能够提高计算思维能力8
1.3.3程序员必须要学习算法吗9
1.4如何设计算法9
1.4.1基本的数据结构9
1.4.2重要的问题类型11
1.4.3算法设计的一般过程13
1.5拓展与演练14
1.5.1算法研究与图灵奖14
1.5.2代码优化技巧15
实验1公约数17
习题118第2章算法分析基础19
2.1算法的时间复杂度分析19
2.1.1输入规模与基本语句192.1.2算法的渐近分析21
2.1.3好、坏和平均情况22
2.1.4非递归算法的时间复杂度分析22
2.1.5递归算法的时间复杂度分析23
2.2算法的空间复杂度分析24
2.3算法的实验分析25
2.4拓展与演练26
2.4.1算法26
2.4.2角谷猜想27
实验2排序算法的实验比较28
习题229
算法设计与分析（第3版）目录第二篇基本的算法设计技术
第3章模拟法33
3.1概述33
3.1.1模拟法的设计思想33
3.1.2一个简单的例子: 鸡兔同笼问题33
3.2数学问题中的模拟法34
3.2.1约瑟夫环问题34
3.2.2埃拉托色尼筛法35
3.3排序问题中的模拟法37
3.3.1计数排序37
3.3.2颜色排序38
3.4拓展与演练39
3.4.1装箱问题39
3.4.2数字回转方阵41
实验3埃氏筛法的优化42
习题342第4章递推法45
4.1概述45
4.1.1递推法的设计思想45
4.1.2一个简单的例子: 猴子吃桃45
4.2数学问题中的递推法46
4.2.1Fibonacci数列46
4.2.2Catalan数列46
4.3组合问题中的递推法48
4.3.1伯努利错装信封问题48
4.3.2旋转的万花筒49
4.4拓展与演练49
4.4.1整数划分49
4.4.2捕鱼知多少50
实验4杨辉三角形51
习题451第5章蛮力法53
5.1概述53
5.1.1蛮力法的设计思想53
5.1.2一个简单的例子: 百元买百鸡问题54
5.2查找问题中的蛮力法54
5.2.1顺序查找54
5.2.2串匹配问题56
5.3排序问题中的蛮力法61
5.3.1选择排序61
5.3.2起泡排序62
5.4图问题中的蛮力法63
5.4.1哈密顿回路问题63
5.4.2TSP问题64
5.5几何问题中的蛮力法65
5.5.1近对问题65
5.5.2凸包问题66
5.6拓展与演练68
5.6.1KMP算法中next值的计算68
5.6.20/1背包问题69
实验5任务分配问题70
习题571第6章分治法73
6.1概述73
6.1.1分治法的设计思想73
6.1.2分治与递归74
6.1.3一个简单的例子: 汉诺塔问题74
6.2排序问题中的分治法75
6.2.1归并排序75
6.2.2快速排序77
6.3组合问题中的分治法80
6.3.1子段和问题80
6.3.2棋盘覆盖问题82
6.4几何问题中的分治法84
6.4.1近对问题84
6.4.2凸包问题86
6.5拓展与演练88
6.5.1扩展欧几里得算法88
6.5.2中国剩余定理89
实验6Karatsuba乘法90
习题691第7章减治法93
7.1概述93
7.1.1减治法的设计思想93
7.1.2一个简单的例子: 俄式乘法94
7.2查找问题中的减治法94
7.2.1折半查找94
7.2.2选择问题96
7.3排序问题中的减治法98
7.3.1插入排序98
7.3.2堆排序99
7.4组合问题中的减治法101
7.4.1淘汰赛冠军问题101
7.4.2问题102
7.5拓展与演练104
7.5.1两个序列的中位数104
7.5.2topK问题106
实验7问题的复杂版本107
习题7109第8章贪心法111
8.1概述111
8.1.1贪心法的设计思想111
8.1.2一个简单的例子: 付款问题111
8.2图问题中的贪心法112
8.2.1TSP问题112
8.2.2图着色问题114
8.2.3小生成树116
8.3组合问题中的贪心法119
8.3.1背包问题119
8.3.2活动安排问题121
8.3.3埃及分数123
8.4拓展与演练124
8.4.1贪心法的正确性证明124
8.4.2田忌赛马126
实验8合并字符串127
习题8127第9章动态规划法129
9.1概述129
9.1.1多阶段决策过程129
9.1.2动态规划法的设计思想130
9.1.3一个简单的例子: 网格上的短路径131
9.2组合问题中的动态规划法133
9.2.1长公共子序列133
9.2.20/1背包问题135
9.3图问题中的动态规划法137
9.3.1多段图的短路径137
9.3.2TSP问题140
9.4查找问题中的动态规划法141
9.4.1近似串匹配141
9.4.2二叉查找树144
9.5拓展与演练146
9.5.1性原理146
9.5.2数塔问题147
实验9子段和150
习题9150
第三篇基于搜索的算法设计技术
第10章深度优先搜索155
10.1深度优先搜索概述155
10.1.1深度优先搜索的设计思想155
10.1.2山洞寻宝图156
10.1.3城堡问题157
10.2回溯法158
10.2.1问题的解空间树158
10.2.2回溯法的设计思想159
10.2.3回溯法的时间性能160
10.2.4素数环问题160
10.2.5八皇后问题162
10.2.6图着色问题164
10.3拓展与演练167
10.3.1批处理作业调度167
10.3.2哈密顿回路170
实验100/1背包问题172
习题10173第11章广度优先搜索175
11.1广度优先搜索概述175
11.1.1广度优先搜索的设计思想175
11.1.2农夫抓牛176
11.1.3骑士旅行177
11.2A算法179
11.2.1A算法的设计思想179
11.2.2八数码问题180
11.2.3多段图的短路径问题181
11.2.4任务分配问题183
11.3限界剪枝法184
11.3.1限界剪枝法的设计思想184
11.3.20/1背包问题185
11.3.3TSP问题187
11.3.4圆排列问题189
11.4拓展与演练191
11.4.1限界剪枝法的关键问题191
11.4.2批处理作业调度问题192
实验11电路布线问题194
习题11195
第四篇NP问题的算法设计技术
第12章问题的复杂性199
12.1问题的复杂性分类199
12.1.1什么是计算199
12.1.2可计算问题与不可计算问题201
12.1.3易解问题与难解问题202
12.2P类问题与NP类问题204
12.2.1判定问题204
12.2.2确定性算法与P类问题205
12.2.3非确定性算法与NP类问题205
12.3NP完全问题206
12.3.1问题变换206
12.3.2NP完全问题的定义207
12.3.3基本的NP完全问题207
12.4拓展与演练208
12.4.1k带图灵机208
12.4.2NP类问题的计算机处理209
实验12SAT问题210
习题12210第13章近似算法213
13.1概述213
13.1.1近似算法的设计思想213
13.1.2一个简单的例子: 求π的近似值214
13.2图问题中的近似算法215
13.2.1顶点覆盖问题215
13.2.2TSP问题216
13.3组合问题中的近似算法217
13.3.1装箱问题217
13.3.2多机调度问题219
13.4拓展与演练222
13.4.1带权顶点覆盖问题222
13.4.2子集和问题223
实验13TSP问题的近似算法226
习题13227第14章概率算法229
14.1概述229
14.1.1概率算法的设计思想229
14.1.2随机数生成器230
14.2舍伍德型概率算法231
14.2.1舍伍德型概率算法的设计思想231
14.2.2快速排序231
14.2.3二叉查找树232
14.3拉斯维加斯型概率算法234
14.3.1拉斯维加斯型概率算法的设计思想234
14.3.2八皇后问题234
14.3.3整数因子划分问题235
14.4蒙特卡罗型概率算法236
14.4.1蒙特卡罗型概率算法的设计思想236
14.4.2主元素问题237
14.4.3素数测试238
14.5拓展与演练239
14.5.1随机数与随机数生成器239
14.5.2蒙特卡罗型算法计算定积分240
实验14随机数生成器241
习题14241第15章群智能算法243
15.1遗传算法243
15.1.1遗传算法的基本思想243
15.1.2遗传算法的关键问题244
15.1.3应用举例245
15.2蚁群算法246
15.2.1蚁群算法的基本原理246
15.2.2蚁群算法的参数设定247
15.2.3应用举例248
15.3粒子群算法249
15.3.1粒子群算法的基本思想249
15.3.2粒子群算法的参数分析250
15.3.3应用举例250
实验15函数的值251
习题15251名词索引253参考文献257
|
| 內容試閱：
|
第3版前言计算机已经成为当今社会的普通工具，这个世界越来越被算法所驱动。“算法基础”“程序设计实践”“算法设计与分析”等算法类课程不仅能够培养学生的算法设计与分析能力，以进一步增强程序设计与实现能力，而且能够引导学生的思维过程，培养计算思维能力。用计算机求解问题的重要环节就是将人的想法抽象为算法，在描述问题和求解问题的过程中，主要采用抽象思维和逻辑思维。因此，算法训练就像一种思维体操，能够锻炼思维，使思维变得更清晰、更有逻辑。
好的算法整洁、漂亮，像艺术品，像诗歌。研究算法很有乐趣，而且研究算法之后会发现自己的思维能力提高了很多，那种成就感非常棒！本书的很多经典问题即便已经有人发布过算法和程序代码，作者仍希望本书呈现的是优雅的算法，是漂亮的代码，同时又是完全不一样的算法设计过程，阅读本书的一个个算法就像完成了一个个思维体操动作。因此，本次修订中作者把很多算法重新写了一遍，更注重算法设计技术的运用，使读者更容易理解和上手，从而能够运用算法设计技术解决实际问题。需要强调的是，对算法设计技术的顿悟是通过不断地阅读算法并加以实践来实现的，本书假定读者已经掌握基本的程序设计知识，能够读懂并上机调试本书提供的程序源码。
本书包括四个独立的部分: 篇是基础知识，第二篇是基本的算法设计技术，第三篇是基于搜索的算法设计技术，第四篇是NP问题的算法设计技术。如图1所示，学习了基础知识，完全可以独立学习其余各篇的算法设计技术，当然也可以按照本书的章节顺序依次学习。这些算法设计技术既相互独立，在设计思想上又有一定的互通关系，无论采用哪种学习方式，都希望读者能够在学习中加以思考，逐渐地将这些算法设计技术在脑海中连成一个知识网，进而融会贯通、灵活运用。
图1知识单元的拓扑结构
一般来讲，在计算机类专业培养计划中，算法类课程有两种开设方式: ①在“程序设计语言”课程之后开设“算法基础”或“程序设计实践”等课程，然后再开设“数据结构”或“算法与数据结构”课程； ②在“数据结构”课程之后开设“算法设计与分析”课程。本书适合作为“算法基础”“程序设计实践”“算法设计与分析”等课程的主讲教材，建议的教学安排请参见表1。算法设计与分析（第3版）第3版前言续表表1不同算法类课程的建议教学安排教学内容（章、节）教学方案及进度未学习“数据结构”课程已学习“数据结构”课程方案A
（40学时）方案B
（48学时）方案C
（40学时）方案D
（48学时）第1章
算法设计基础1.1～1.2111.30.50.50.50.51.4.1111.4.2～1.4.30.50.50.50.51.51第2章
算法分析基础2.1～2.2222.3～2.4111第3章
模拟法3.10.50.50.50.53.2～3.32.52.53.410.50.5第4章
递推法4.10.50.50.50.54.2.1，4.3114.2.2，4.41.51.51.51.5第5章
蛮力法5.10.50.50.50.55.2～5.322第5章
蛮力法5.4～5.51.51.5115.60.50.5第6章
分治法6.111116.21.51.56.31.51.51.51.56.4～6.5222第7章
减治法7.10.50.50.50.57.2～7.43.53.57.5111第8章
贪心法8.10.50.50.50.58.22228.3，8.4.22.52.52.52.58.4.11第9章
动态规划法9.1～9.2，9.5.244449.3～9.4，9.5.133第10章
深度优先搜索10.12.52.510.22.52.52.52.510.31.51.5第11章
广度优先搜索11.12.52.511.22.52.52.52.511.3～11.42.52.5第12章
问题的复杂性12.1～12.33312.41第13章
近似算法13.1～13.32213.41第14章
概率算法14.1～14.21114.3～14.52第15章
群智能算法15.1～15.33为方便读者学习，本书配备了教学课件、程序源码、实验项目、课后习题等数字教学资源，扫描相应位置的二维码即可获得。本书的适用读者是:
作为“程序设计基础”的后续课程，初步掌握程序设计语言后，希望提高程序设计能力的学生，为学习“数据结构”课程奠定坚实的基础，请参考表1安排学习进度。
作为“数据结构”的后续课程，掌握数据结构及基本操作后，希望提高算法设计能力的学生，请参考表1安排学习进度。
准备参加程序设计竞赛（NOIP或ACM），尚未入门又无从下手的学生，系统学习了本书的算法设计技术，就可以去学习《算法导论》或其他竞赛类算法的书了。
对算法领域感兴趣的任何人，跟随本书完成大量的算法训练后，你会发现自己的思维变得更清晰、更有逻辑性。
参加本书编写的还有王涛、王贵参、刘冰、张丽杰、党源源、肖巍等。由于作者的知识和写作水平有限，书稿虽再三斟酌几经修改，仍难免有不足之处，欢迎专家和读者批评指正。
作者2021年6月
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
