算法设计与分析

前言教学建议第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最短并行调度在线算法习题参考文献