算法设计与分析

书籍目录

第一部分 基础知识第1章 算法设计基础3  1.1 算法的基本概念3  1.1.1 算法及其重要特性3  1.1.2 算法的描述方法5  1.1.3 算法设计的一般过程6  1.2 为什么要学习和研究算法7  1.2.1 算法在问题求解中的地位8  1.2.2 算法训练能够提高计算思维能力10  1.2.3 算法研究是推动计算机技术发展的关键11  1.3 重要的问题类型12  1.3.1 查找问题12  1.3.2 排序问题12  1.3.3 图问题13  1.3.4 组合问题13  1.3.5 几何问题13  阅读材料--算法研究与图灵奖14  习题1第2章 算法分析基础17  2.1 算法的时间复杂性分析17  2.1.1 输入规模与基本语句18  2.1.2 算法的渐进分析19  2.1.3 最好、最坏和平均情况20  2.1.4 非递归算法的时间复杂性分析20  2.1.5 递归算法的时间复杂性分析22  2.2 算法的空间复杂性分析23  2.3 最优算法23  2.3.1 问题的计算复杂性下界24  2.3.2 平凡下界25  2.3.3 判定树模型25  阅读材料--算法的实验分析26  习题2第二部分 基本的算法设计技术第3章 蛮力法33  3.1 概述33  3.1.1 蛮力法的设计思想33  3.1.2 一个简单的例子--百元买百鸡问题34  3.2 查找问题中的蛮力法36  3.2.1 顺序查找36  3.2.2 串匹配问题37  3.3 排序问题中的蛮力法42  3.3.1 选择排序42  3.3.2 起泡排序43  3.4 组合问题中的蛮力法44  3.4.1 0/1背包问题44  3.4.2 任务分配问题45  3.5 图问题中的蛮力法46  3.5.1 哈密顿回路问题46  3.5.2 TSP问题47  3.6 几何问题中的蛮力法48  3.6.1 最近对问题48  3.6.2 凸包问题49  阅读材料--KMP算法中next值的计算51  习题3第4章 分治法55  4.1 概述55  4.1.1 分治法的设计思想55  4.1.2 一个简单的例子--数字旋转方阵57  4.2 排序问题中的分治法59  4.2.1 归并排序59  4.2.2 快速排序61  4.3 组合问题中的分治法64  4.3.1 最大子段和问题64  4.3.2 棋盘覆盖问题65  4.4 几何问题中的分治法67  4.4.1 最近对问题68  4.4.2 凸包问题71  阅读材料--递归函数的执行过程72  习题4第5章 减治法77  5.1 概述77  5.1.1 减治法的设计思想77  5.1.2 一个简单的例子--两个序列的中位数78  5.2 查找问题中的减治法80  5.2.1 折半查找80  5.2.2 二叉查找树82  5.2.3 选择问题84  5.3 排序问题中的减治法86  5.3.1 插入排序86  5.3.2 堆排序88  5.4 组合问题中的减治法90  5.4.1 淘汰赛冠军问题90  5.4.2 假币问题91  阅读材料--假币问题的复杂版本93  习题5第6章 动态规划法97  6.1 概述97  6.1.1 多阶段决策过程98  6.1.2 动态规划法的设计思想99  6.1.3 一个简单的例子--数塔问题100  6.2 图问题中的动态规划法102  6.2.1 多段图的最短路径问题102  6.2.2 多源点最短路径问题106  6.2.3 TSP问题107  6.3 组合问题中的动态规划法109  6.3.1 最长递增子序列问题109  6.3.2 最长公共子序列问题111  6.3.3 0/1背包问题114  6.4 查找问题中的动态规划法116  6.4.1 最优二叉查找树116  6.4.2 近似串匹配问题119  阅读材料--人工神经网络121  习题6第7章 贪心法127  7.1 概述127  7.1.1 贪心法的设计思想127  7.1.2 一个简单的例子--埃及分数128  7.2 图问题中的贪心法129  7.2.1 TSP问题129  7.2.2 图着色问题132  7.2.3 最小生成树问题134  7.3 组合问题中的贪心法138  7.3.1 背包问题138  7.3.2 活动安排问题140  7.3.3 多机调度问题142  阅读材料--贪心法的正确性证明144  习题7第三部分 基于搜索的算法设计技术第8章 回溯法151  8.1 概述151  8.1.1 问题的解空间树151  8.1.2 回溯法的设计思想152  8.1.3 回溯法的时间性能153  8.1.4 一个简单的例子--素数环问题154  8.2 图问题中的回溯法155  8.2.1 图着色问题155  8.2.2 哈密顿回路问题158  8.3 组合问题中的回溯法160  8.3.1 八皇后问题160  8.3.2 批处理作业调度问题163  阅读材料--遗传算法166  习题8第9章 分支限界法171  9.1 概述171  9.1.1 分支限界法的设计思想171  9.1.2 分支限界法的时间性能172  9.1.3 一个简单的例子--圆排列问题173  9.2 图问题中的分支限界法175  9.2.1 TSP问题175  9.2.2 多段图的最短路径问题178  9.3 组合问题中的分支限界法180  9.3.1 0/1背包问题180  9.3.2 任务分配问题182  9.3.3 批处理作业调度问题184  阅读材料--蚁群算法187  习题9第四部分 计算的限制第10章 问题的复杂性193  10.1 问题的复杂性分类193  10.1.1 什么是计算194  10.1.2 可计算问题与不可计算问题195  10.1.3 易解问题与难解问题197  10.2 P类问题和NP类问题199  10.2.1 判定问题199  10.2.2 确定性算法与P类问题199  10.2.3 非确定性算法与NP类问题200  10.3 NP完全问题201  10.3.1 问题变换201  10.3.2 NP完全问题的定义202  10.3.3 基本的NP完全问题202  10.3.4 NP完全问题的计算机处理203  阅读材料--Cook定理204  习题10第11章 近似算法209  11.1 概述209  11.1.1 近似算法的设计思想209  11.1.2 一个简单的例子--求π的近似值210    11.2 图问题中的近似算法211  11.2.1 顶点覆盖问题211  11.2.2 TSP问题212  11.3 组合问题中的近似算法214  11.3.1 装箱问题214  11.3.2 子集和问题216  阅读材料--粒子群算法219  习题11第12章 概率算法223  12.1 概述223  12.1.1 概率算法的设计思想224  12.1.2 随机数发生器224  12.2 舍伍德型概率算法225  12.2.1 舍伍德型概率算法的设计思想225  12.2.2 快速排序226  12.2.3 二叉查找树227  12.3 拉斯维加斯型概率算法228  12.3.1 拉斯维加斯型概率算法的设计思想228  12.3.2 八皇后问题229  12.3.2 整数因子划分问题230  12.4 蒙特卡罗型概率算法231  12.4.1 蒙特卡罗型概率算法的设计思想231  12.4.2 主元素问题232  12.4.3 素数测试问题233  阅读材料--模拟淬火算法234  习题12附录A 名词索引237参考文献243

编辑推荐

王红梅、胡明编著的《算法设计与分析》共12章，第1章介绍了算法的基本概念和算法分析方法，第2章从算法的观点非形式化地介绍了NP完全理论，第3章-第11章分别介绍了蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等算法设计技术，第12章基于图灵机计算模型介绍了计算复杂性理论。书中所有问题均给出了若干应用实例，每章还设有一个实验项目，通过设计提高学生创造性思维的培养。每章均附有一篇阅读材料，以通俗易懂的笔触介绍了算法领域的一些最新研究成果，保证知识的先进性。书中所有算法均给出了伪代码，大部分算法还给出了C++描述。在算法介绍上，注重对问题求解过程的理解，注重算法设计思路和分析过程的讲解，体现了“授之以渔”的教学理念。

作者简介

王红梅、胡明编著的《算法设计与分析》将经典问题和算法设计技术很好地结合起来，系统地介绍了算法设计技术及其在经典问题中的应用。全书共分四部分：第一部分是基础知识，包括算法设计基础和算法分析基础；第二部分是基本的算法设计技术，包括蛮力法、分治法、减治法、动态规划法和贪心法；第三部分是基于搜索的算法设计技术，包括回溯法和分支限界法；第四部分是计算的限制，介绍了问题的复杂性、近似算法和概率算法。所有问题都用伪代码给出了算法描述，大多数问题都给出了C++语言的算法实现，并且所有程序均在VC++6.0环境下调试通过。每章均附有一篇阅读材料，以通俗易懂的方式介绍了算法领域的一些最新研究成果。

    《算法设计与分析》内容丰富，深入浅出，结合应用，图例丰富，可作为高等院校计算机专业本科和研究生学习算法设计与分析的教材，也可供工程技术人员和自学者学习参考。

 算法设计与分析下载