✍ Scribed by 王红梅
No coin nor oath required. For personal study only.
本书将经典问题和算法设计技术结合，以读者容易理解和接受的方式，系统介绍了算法设计技术，包括模拟法、递推法、蛮力法、分治法、减治法、贪心法、动态规划法、深度优先搜索、广度优先搜索、回溯法、A*算法、限界剪枝法、近似算法、概率算法和群智能算法；同时以通俗易懂的方式，系统介绍了算法分析技术，包括算法的时间复杂度分析、空间复杂度分析、算法、确定性算法、非确定性算法、P类问题、NP类问题和NP完全问题。所有问题都用伪代码给出了算法描述，并提供了C++语言程序源码，且在C++语言的典型编程环境下调试通过。 本书案例丰富，叙述清晰，深入浅出，结合应用，符合算法学习者的认知规律，可作为高等院校计算机专业本科和研究生学习算法类课程的教材，适合准备参加程序设计竞赛（NOIP或ACM）却无从下手的学生，也特别适合算法爱好者学习参考。
封面
书名
版权
前言
目录
第一篇 基础知识
第1章 算法设计基础
1.1什么是算法
1.1.1算法的定义
1.1.2算法的描述方法
1.1.3算法在问题求解中的地位
1.2什么是好算法
1.2.1如何评价算法
1.2.2效率——算法的核心和灵魂
1.3为什么要学习和研究算法
1.3.1算法研究是推动计算机技术发展的关键
1.3.2算法训练能够提高计算思维能力
1.3.3程序员必须要学习算法吗
1.4如何设计算法
1.4.1基本的数据结构
1.4.2重要的问题类型
1.4.3算法设计的一般过程
1.5拓展与演练
1.5.1算法研究与图灵奖
1.5.2代码优化技巧
实验1最大公约数
习题1
第2章 算法分析基础
2.1算法的时间复杂度分析
2.1.1输入规模与基本语句
2.1.2算法的渐近分析
2.1.3最好、最坏和平均情况
2.1.4非递归算法的时间复杂度分析
2.1.5递归算法的时间复杂度分析
2.2算法的空间复杂度分析
2.3算法的实验分析
2.4拓展与演练
2.4.1最优算法
2.4.2角谷猜想
实验2排序算法的实验比较
习题2
第二篇 基本的算法设计技术
第3章 模拟法
3.1概述
3.1.1模拟法的设计思想
3.1.2一个简单的例子：鸡兔同笼问题
3.2数学问题中的模拟法
3.2.1约瑟夫环问题
3.2.2埃拉托色尼筛法
3.3排序问题中的模拟法
3.3.1计数排序
3.3.2颜色排序
3.4拓展与演练
3.4.1装箱问题
3.4.2数字回转方阵
实验3埃氏筛法的优化
习题3
第4章 递推法
4.1概述
4.1.1递推法的设计思想
4.1.2一个简单的例子：猴子吃桃
4.2数学问题中的递推法
4.2.1 Fibonacci数列
4.2.2 Catalan数列
4.3组合问题中的递推法
4.3.1伯努利错装信封问题
4.3.2旋转的万花筒
4.4拓展与演练
4.4.1整数划分
4.4.2捕鱼知多少
实验4杨辉三角形
习题4
第5章 蛮力法
5.1概述
5.1.1蛮力法的设计思想
5.1.2一个简单的例子：百元买百鸡问题
5.2查找问题中的蛮力法
5.2.1顺序查找
5.2.2串匹配问题
5.3排序问题中的蛮力法
5.3.1选择排序
5.3.2起泡排序
5.4图问题中的蛮力法
5.4.1哈密顿回路问题
5.4.2 TSP问题
5.5几何问题中的蛮力法
5.5.1最近对问题
5.5.2凸包问题
5.6拓展与演练
5.6.1 KMP算法中next值的计算
5.6.2 0/1背包问题
实验5任务分配问题
习题5
第6章 分治法
6.1概述
6.1.1分治法的设计思想
6.1.2分治与递归
6.1.3一个简单的例子：汉诺塔问题
6.2排序问题中的分治法
6.2.1归并排序
6.2.2快速排序
6.3组合问题中的分治法
6.3.1最大子段和问题
6.3.2棋盘覆盖问题
6.4几何问题中的分治法
6.4.1最近对问题
6.4.2凸包问题
6.5拓展与演练
6.5.1扩展欧几里得算法
6.5.2中国剩余定理
实验6 Karatsuba乘法
习题6
第7章 减治法
7.1概述
7.1.1减治法的设计思想
7.1.2一个简单的例子：俄式乘法
7.2查找问题中的减治法
7.2.1折半查找
7.2.2选择问题
7.3排序问题中的减治法
7.3.1插入排序
7.3.2堆排序
7.4组合问题中的减治法
7.4.1淘汰赛冠军问题
7.4.2假币问题
7.5拓展与演练
7.5.1两个序列的中位数
7.5.2 topK问题
实验7假币问题的复杂版本
习题7
第8章 贪心法
8.1概述
8.1.1贪心法的设计思想
8.1.2一个简单的例子：付款问题
8.2图问题中的贪心法
8.2.1 TSP问题
8.2.2图着色问题
8.2.3最小生成树
8.3组合问题中的贪心法
8.3.1背包问题
8.3.2活动安排问题
8.3.3埃及分数
8.4拓展与演练
8.4.1贪心法的正确性证明
8.4.2田忌赛马
实验8合并字符串
习题8
第9章 动态规划法
9.1概述
9.1.1多阶段决策过程
9.1.2动态规划法的设计思想
9.1.3一个简单的例子：网格上的最短路径
9.2组合问题中的动态规划法
9.2.1最长公共子序列
9.2.2 0/1背包问题
9.3图问题中的动态规划法
9.3.1多段图的最短路径
9.3.2 TSP问题
9.4查找问题中的动态规划法
9.4.1近似串匹配
9.4.2最优二叉查找树
9.5拓展与演练
9.5.1最优性原理
9.5.2数塔问题
实验9最大子段和
习题9
第三篇 基于搜索的算法设计技术
第10章 深度优先搜索
10.1深度优先搜索概述
10.1.1深度优先搜索的设计思想
10.1.2山洞寻宝图
10.1.3城堡问题
10.2回溯法
10.2.1问题的解空间树
10.2.2回溯法的设计思想
10.2.3回溯法的时间性能
10.2.4素数环问题
10.2.5八皇后问题
10.2.6图着色问题
10.3拓展与演练
10.3.1批处理作业调度
10.3.2哈密顿回路
实验10 0/1背包问题
习题10
第11章 广度优先搜索
11.1广度优先搜索概述
11.1.1广度优先搜索的设计思想
11.1.2农夫抓牛
11.1.3骑士旅行
11.2 A算法
11.2.1 A算法的设计思想
11.2.2八数码问题
11.2.3多段图的最短路径问题
11.2.4任务分配问题
11.3限界剪枝法
11.3.1限界剪枝法的设计思想
11.3.2 0/1背包问题
11.3.3 TSP问题
11.3.4圆排列问题
11.4拓展与演练
11.4.1限界剪枝法的关键问题
11.4.2批处理作业调度问题
实验11电路布线问题
习题11
第四篇 NP问题的算法设计技术
第12章 问题的复杂性
12.1问题的复杂性分类
12.1.1什么是计算
12.1.2可计算问题与不可计算问题
12.1.3易解问题与难解问题
12.2 P类问题与NP类问题
12.2.1判定问题
12.2.2确定性算法与P类问题
12.2.3非确定性算法与NP类问题
12.3 NP完全问题
12.3.1问题变换
12.3.2 NP完全问题的定义
12.3.3基本的NP完全问题
12.4拓展与演练
12.4.1 k带图灵机
12.4.2 NP类问题的计算机处理
实验12 SAT问题
习题12
第13章 近似算法
13.1概述
13.1.1近似算法的设计思想
13.1.2一个简单的例子：求π的近似值
13.2图问题中的近似算法
13.2.1顶点覆盖问题
13.2.2 TSP问题
13.3组合问题中的近似算法
13.3.1装箱问题
13.3.2多机调度问题
13.4拓展与演练
13.4.1带权顶点覆盖问题
13.4.2子集和问题
实验13 TSP问题的近似算法
习题13
第14章 概率算法
14.1概述
14.1.1概率算法的设计思想
14.1.2随机数生成器
14.2舍伍德型概率算法
14.2.1舍伍德型概率算法的设计思想
14.2.2快速排序
14.2.3二叉查找树
14.3拉斯维加斯型概率算法
14.3.1拉斯维加斯型概率算法的设计思想
14.3.2八皇后问题
14.3.3整数因子划分问题
14.4蒙特卡罗型概率算法
14.4.1蒙特卡罗型概率算法的设计思想
14.4.2主元素问题
14.4.3素数测试
14.5拓展与演练
14.5.1随机数与随机数生成器
14.5.2蒙特卡罗型算法计算定积分
实验14随机数生成器
习题14
第15章 群智能算法
15.1遗传算法
15.1.1遗传算法的基本思想
15.1.2遗传算法的关键问题
15.1.3应用举例
15.2蚁群算法
15.2.1蚁群算法的基本原理
15.2.2蚁群算法的参数设定
15.2.3应用举例
15.3粒子群算法
15.3.1粒子群算法的基本思想
15.3.2粒子群算法的参数分析
15.3.3应用举例
实验15函数的最大值
习题15
名词索引
参考文献
封底
📜 SIMILAR VOLUMES
《算法设计与分析》系统地介绍了算法设计与分析的概念和方法，共4篇内容。第1篇介绍算法设计与分析的基本概念，结合穷举法、排序问题及其他一些算法，对算法的时间复杂性的概念及复杂性的分析方法作了较为详细的叙述；第2篇以算法设计技术为纲，从合并排序、堆排序、离散集合的union和find操作开始，进而介绍递归技术、分治法、贪婪法、动态规划、回溯法、分支与限界法和随机算法等算法设计技术及其复杂性分析；第3篇介绍计算机应用领域里的一些算法，如图和网络流，以及计算几何中的一些问题；第4篇介绍算法设计与分析中的一些理论问题，如NP完全问题、计算复杂性问题、下界理论问题，最后介绍近似算法及其性能分析。 《算法
本书是作者在多年从事算法设计与分析课程教学和研究的基础上编写而成，系统地介绍了算法设计与分析的理论、方法和技术。内容围绕两条主线来组织。一条主线是介绍典范性的算法问题，如排序、选择、图遍历等。 另一条主线是介绍典范性的算法设计分析策略，如分治、贪心、动态规划等算法设计策略和对手分析、平摊分析等算法分析策略。本书中两条主线交替进行，每条主线又各自分为基本和进阶两部分。 已附上书签
<p>本书为计算机类专业核心课程“算法设计与分析”教材. 全书以算法设计技术和分析方法为主线来组织各知识单元. 主要内容包括基础知识、分治策略、动态规划、贪心法、回溯与分支限界、线性规划、网络流算法、算法分析与问题的计算复杂度、NP完全性、近似算法、随机算法、处理难解问题的策略等. 力求突出对问题本身的分析和求解方法的阐述，从问题建模、算法设计与分析、改进措施等方面给出适当的建议，同时也简要介绍了计算复杂性理论的核心内容和处理难解问题的一些新技术.</p>
为了适应培养我国２１世纪计算机各类人才的需要，结合我国高等学校教育工作的现状，立足培养学生能跟上国际计算机科学技术的发展水平，更新教学内容和教学方法，提高教学质量，本书以算法设计策略为知识单元，系统地介绍计算机算法的设计方法与分析技巧，以期为计算机科学与技术学科的学生提供广泛而坚实的计算机算法基础知识。另有配套的《算法设计与分析（第4版）习题解答》，对本书的全部习题做了详尽的解答。 本书内容丰富，观点新颖，理论联系实际。不仅可用作高等学校计算机专业本科生和研究生学习计算机算法设计的教材，而且也适合广大工程技术人员和自学读者学习参考。