算法设计与分析

本书以算法设计与分析的理论、方法和技术为主线，系统地介绍分治算法、动态规划算法、贪心算法、最小值最大值方法、搜索策略、随机算法、近似算法和在线算法等算法设计技术，以及循环不变量方法、反例方法、平摊分析方法、概率分析方法、近似度分析方法和竞争度分析方法等算法分析技术。在介绍这些理论、方法和技术的同时，还介绍计算几何、图论、元素选取、最大流、顶点覆盖和匹配等领域的一些基本算法。全书强调问题特征分析、基本算法和算法设计技术的有机结合构成典型的算法设计过程。书中配置了大量习题，以期读者能够在实践过程中加深对算法设计与分析方法的理解并提高算法设计与分析的速度。

目录 前言 教学建议 第1章绪论 11算法在计算机科学体系中的地位 111计算机理论模型和计算问题的分类 112利用计算机求解问题 113计算机科学的知识体系 114算法是计算机科学的重要主题 115算法设计与分析的意义 12算法的概念 13算法分析 131算法正确性分析 132算法复杂度分析 14算法设计方法 习题 第2章数学基础 21复杂度函数的阶 211函数阶的定义 212函数阶的性质 22标准符号和通用函数 221flour函数和ceiling函数 222求和 23递归方程 231常系数线性递归方程 232非常系数线性递归方程 233生成函数 234分治算法递归方程 习题 第3章分治算法 31分治算法原理 32大整数乘法 33Strassen矩阵乘法 34快速傅里叶变换 35最邻近点问题 36平面点集的凸包 361求解凸包问题的蛮力算法 362GrahamScan算法 363凸包问题的分治算法 37基于剪枝搜索方法的分治算法 371剪枝搜索方法 372线性时间选择算法 373二元线性规划的线性时间算法 3741圆心问题的线性时间算法 习题 第4章动态规划算法 41动态规划原理 42最长公共子序列 43矩阵链乘法 4401背包问题 45最优二叉搜索树 46评注 习题 第5章贪心算法 51贪心算法的基本原理 52活动选择问题 53哈夫曼编码问题 54最小生成树问题 541Kruskal算法 542Prim算法 55贪心算法的理论基础 551拟阵 552加权拟阵上的贪心算法 56单位时间任务调度问题 习题 第6章平摊分析 61平摊分析方法 611聚集方法 612会计方法 613势能方法 62动态表性能的平摊分析 621动态表及其操作 622动态表的扩张 623动态表扩张和收缩 63斐波那契堆及其操作代价的平摊分析 631斐波那契堆 632斐波那契堆操作算法及其平摊代价 633斐波那契堆最大度的上界 64并查集及其操作代价的平摊分析 641并査集及其基本性质 642阿克曼函数及其逆函数 643并查集上操作序列代价的平摊分析 习题 第7章最大值最小值方法 71网络流 711最大流问题和最小割问题 712FordFulkerson算法 713EdmondsKarp算法 714推送复标算法 715复标前置算法 72匹配算法 721匹配与覆盖 722最大二分匹配 723一般图上的最大匹配 724最大权值二分匹配 725稳定二分匹配 习题 第8章树的搜索策略 81问题解空间的树表示 82典型搜索策略 821广度优先搜索 822深度优先搜索 823爬山法 824最佳优先搜索 825分支限界法 83分支限界法的应用 831用分支限界法求解人员分配问题 832用分支限界法求解旅行商问题 833用分支限界法求解01背包问题 84A*算法及其应用 85博弈树和αβ剪枝 851博弈树及其评估 852αβ剪枝 习题 第9章随机算法 91随机算法概述 92数值随机算法 921随机投点法 922平均值方法 93随机选择和拉斯维加斯算法 931随机选择算法 932拉斯维加斯算法 94快速排序和舍伍德算法 941快速排序算法描述 942快速排序算法的性能分析 943随机快速排序算法 944舍伍德算法 95素数测试和蒙特卡罗算法 951素数测试随机算法 952蒙特卡罗算法 96最小割随机算法 习题 第10章近似算法 101近似算法的性能分析 102基于组合优化的近似算法 1021顶点覆盖问题的近似算法 1022装箱问题的近似算法 1023最短并行调度问题的近似算法 1024旅行商问题的近似算法 1025子集和问题的完全多项式近似模式 103基于贪心思想的近似算法 1031集合覆盖问题的近似算法 1032不相交路径问题的近似算法 104基于局部搜索的近似算法 1041最大割问题的近似算法 1042设施定位问题的近似算法 105基于动态规划的近似算法 105101背包问题的完全多项式近似模式 1052装箱问题的多项式近似模式 106基于线性规划的近似算法 1061线性规划及对偶定理 1062加权集合覆盖问题的线性规划表示 1063舍入法及随机舍入法 1064对偶拟合方法 1065原偶模式 107不可近似性 1071鸿沟归约与不可近似性 1072PCP定理 1073MAX3SAT问题的不可近似性 1074α,β鸿沟归约与不可近似性 习题 第11章在线算法 111在线算法与竞争度分析 112欧几里得最小生成树问题的在线算法 1121在线贪心算法 1122在线随机算法 113凸包在线算法 114线性链表在线更新算法 115最短并行调度在线算法 习题 参考文献