算法设计与分析王晓东

书名：算法设计与分析 作者：王晓东 图书目录 第1章 算法引论 1.1 算法与程序 1.2 表达算法的抽象机制 1.3 描述算法 1.4 算法复杂性分析 小结 习题 第2章 递归与分治策略 2.1 速归的概念 2.2 分治法的基本思想 2.3 二分搜索技术 2.4 大整数的乘法 2.5 Strassen矩阵乘法 2.6 棋盘覆盖 2.7 合并排序 2.8 快速排序 2.9 线性时间选择 2.10 最接近点对问题 2.11 循环赛日程表 小结 习题 第3章 动态规划 3.1 矩阵连乘问题 3.2 动态规划算法的基本要素 3.3 最长公共子序列 3.4 凸多边形最优三角剖分 3.5 多边形游戏 3.6 图像压缩 3.7 电路布线 3.8 流水作业调度 3.9 0-1背包问题 3.10 最优二叉搜索树 小结 习题 第4章 贪心算法 4.1 活动安排问题 4.2 贪心算法的基本要素 4.2.1 贪心选择性质 4.2.2 最优子结构性质 4.2.3 贪心算法与动态规划算法的差异 4.3 最优装载 4.4 哈夫曼编码 4.4.1 前缀码 4.4.2 构造哈夫曼编码 4.4.3 哈夫曼算法的正确性 4.5 单源最短路径 4.5.1 算法基本思想 4.5.2 算法的正确性和计算复杂性 4.6 最小生成树 4.6.1 最小生成树性质 4 6.2 Prim算法 4.6.3 Kruskal算法 4.7 多机调度问题 4.8 贪心算法的理论基础 4.8.1 拟阵 4.8.2 带权拟阵的贪心算法 4.8.3 任务时间表问题 小结 习题 第5章 回溯法 5.1 回溯法的算法框架 5.1.1 问题的解空间 5.1.2 回溯法的基本思想 5.1.3 递归回溯 5.1.4 迭代回溯 5.1.5 子集树与排列树 5.2 装载问题 5.3 批处理作业调度 5.4 符号三角形问题 5.5 n后问题 5.6 0-1背包问题 5.7 最大团问题 5.8 图的m着色问题 5.9 旅行售货员问题 5.10 圆排列问题 5.11 电路板排列问题 5.12 连续邮资问题 5.13 回溯法的效率分析 小结 习题 第6章 分支限界法 6.1 分支限界法的基本思想 6.2 单源最短路径问题 6.3 装载问题 6.4 布线问题 6.5 0-1背包问题 6.6 最大团问题 6.7 旅行售货员问题 6.8 电路板排列问题 6.9 批处理作业调度 小结 习题 第7章 概率算法 7.1 随机数 .2 数值概率算法 7.2.1 用随机投点法计算л值 7.2.2 计算定积分 7.2.3 解非线性方程组 7.3 舍伍德算法 7.3.1 线性时间选择算法 7.3.2 跳跃表 7.4 拉斯维加斯算法 7.4.1 n后问题 7.4.2 整数因子分解 7.5 蒙特卡罗算法 7.5.1 蒙特卡罗算法的基本思想 7.5.2 主元素问题 7.5.3 素数测试 小结 习题 第8章 NP完全性理论 8.1 计算模型 8.1.1 随机存取机RAM 8.1.2 随机存取存储程序机RASP 8.1.3 RAM模型的变形与简化 8.1.4 图灵机 8.1.5 图灵机模型与RAM模型的关系 8.1.6 问题变换与计算复杂性归约 8.2 P类与NP类问题 8.2.1 非确定性图灵机 8.2.2 P类与NP类语言 8.2.3 多项式时间验证 8.3 NP完全问题 8.3.1 多项式时间变换 8.3.2 Cook定理 8.4 一些典型的NP完全问题 8.4.1 合取范式的可满足性问题 8.4.2 3元合取范式的可满足性问题 8.4.3 团问题 8.4.4 顶点覆盖问题 8.4.5 子集和问题 8.4.6 哈密顿回路问题 《算法设计与分析》是由王晓东编著的一部计算机科学领域的教材，全面系统地介绍了算法设计与分析的核心知识，包括各种算法的策略、方法和技巧，并针对不同问题类型提供了相应的算法解决方案。 在第1章算法引论中，介绍了算法与程序的关系，阐述了表达算法的抽象机制，并讨论了如何描述算法以及算法复杂性分析的基本概念和方法。这一章为读者提供了一个算法分析的基础框架，帮助理解后续章节中复杂的算法设计方法。 第2章深入探讨了递归与分治策略。本章阐述了递归的概念和分治法的基本思想，详细介绍了包括二分搜索技术、大整数乘法、Strassen矩阵乘法、棋盘覆盖、合并排序、快速排序、线性时间选择和最接近点对问题等在内的多种应用实例。通过这些实例，读者能够掌握分治法解决问题的思想和技巧。 第3章介绍了动态规划算法，这是一种解决复杂问题时常用的方法。本章涵盖了矩阵连乘问题、动态规划算法的基本要素、最长公共子序列、凸多边形最优三角剖分、多边形游戏、图像压缩、电路布线、流水作业调度和0-1背包问题等。通过学习这一章，读者能够了解动态规划在优化问题中的应用。 第4章关注贪心算法，这是一种在每一步选择中都采取当前状态下最优的选择，以此希望导致全局最优解的算法设计技术。本章详细分析了贪心算法的基本要素，包括贪心选择性质和最优子结构性质，并通过活动安排问题、最优装载、哈夫曼编码、单源最短路径、最小生成树、多机调度问题等实例，深入讲解了贪心算法的应用。 第5章和第6章分别介绍了回溯法和分支限界法。回溯法是一种通过试错来寻找问题解的方法，通常用于解决约束满足问题。分支限界法则是一种用于解决优化问题的方法，通过减少搜索空间来更高效地找到最优解。这两章通过一系列问题实例，如装载问题、批处理作业调度、n后问题、旅行售货员问题等，讲解了这两种算法的设计与分析。 第7章讲述了概率算法，包括随机数生成、数值概率算法以及基于概率的几种特定算法：舍伍德算法、拉斯维加斯算法和蒙特卡罗算法。这部分内容让读者理解如何利用概率和随机性来设计高效算法。 第8章讲述了NP完全性理论，这是计算机科学中一个核心概念，涉及计算复杂性理论。本章首先介绍了计算模型，包括RAM和图灵机模型，随后讨论了P类与NP类问题，以及多项式时间变换和Cook定理。在理解了这些基础理论之后，本章进一步探讨了一些典型的NP完全问题，如合取范式的可满足性问题、团问题和哈密顿回路问题等。 《算法设计与分析》是一本专业性强的教材，既适合大学本科生和研究生学习使用，也适合计算机科学与技术领域的工程技术人员参考。教材内容深入浅出，注重实例分析，强调算法设计的实际应用，通过丰富的习题和教学资料，帮助读者深入理解和掌握各种算法设计与分析技巧。