包邮算法设计与分析-(第2版)

第1章基础知识11.1有关算法的基本概念11.2算法的伪码描述51.3算法的数学基础61.3.1函数的渐近的界61.3.2求和的方法101.3.3递推方程求解方法12习题121第2章分治策略262.1分治策略的基本思想262.1.1两个熟悉的例子262.1.2分治算法的一般性描述272.2分治算法的分析技术272.3改进分治算法的途径312.3.1通过代数变换减少子问题个数312.3.2利用预处理减少递归内部的计算量342.4典型实例372.4.1快速排序算法372.4.2选择问题402.4.3n-1次多项式在全体2n次方根上的求值44习题247第3章动态规划523.1动态规划的设计思想523.1.1多起点、多终点的*短路径问题523.1.2使用动态规划技术的必要条件543.2动态规划算法的设计要素55目录算法设计与分析(第2版)3.2.1子问题的划分和递推方程563.2.2动态规划算法的递归实现573.2.3动态规划算法的迭代实现583.2.4一个简单实例的计算过程593.3动态规划算法的典型应用603.3.1投资问题603.3.2背包问题633.3.3*长公共子序列lcs653.3.4图像压缩683.3.5*大子段和723.3.6*优二分检索树753.3.7生物信息学中的动态规划算法79习题382第4章贪心法874.1贪心法的设计思想874.2关于贪心法的正确性证明904.3对贪心法得不到*优解情况的处理944.4贪心法的典型应用984.4.1*优前缀码984.4.2*小生成树1034.4.3单源*短路径108习题4110第5章回溯与分支限界1145.1回溯算法的基本思想和适用条件1145.1.1几个典型的例子1145.1.2回溯算法的适用条件1185.2回溯算法的设计步骤1195.2.1回溯算法的递归实现和迭代实现1195.2.2几个典型的例子1205.3回溯算法的效率估计和改进途径1225.4分支限界1245.4.1背包问题1255.4.2*大团问题1275.4.3货郎问题1275.4.4圆排列问题1295.4.5连续邮资问题131习题5132第6章线性规划1346.1线性规划模型1346.1.1模型1346.1.2二维线性规划的图解法1376.2标准形1386.2.1标准形基本概念1386.2.2标准形的可行解的性质1406.3单纯形法1426.3.1确定初始基本可行解1436.3.2*优性检验1436.3.3基变换1446.3.4单纯形表1466.3.5人工变量和两阶段法1486.3.6单纯形法的有限终止1546.4对偶性1556.4.1对偶线性规划1556.4.2对偶单纯形法1596.5整数线性规划的分支限界算法160习题6165第7章网络流算法1717.1*大流问题1717.1.1网络流及其性质1717.1.2fordfulkerson算法1737.1.3dinic有效算法1767.2*小费用流1847.2.1floyd算法1847.2.2*小费用流的负回路算法1867.2.3*小费用流的*短路径算法1887.3运输问题1897.3.1确定初始调运方案1917.3.2改进调运方案1917.3.3表上作业法1937.4二部图匹配1947.4.1二部图的*大匹配1947.4.2赋权二部图的匹配197习题7203第8章算法分析与问题的计算复杂度2088.1平凡下界2098.2直接计数求解该问题所需要的*少运算2108.3决策树2118.4检索算法的时间复杂度分析2128.5排序算法的时间复杂度分析2148.5.1冒泡排序算法2148.5.2堆排序算法2158.5.3排序算法的决策树与算法类时间复杂度的下界2208.6选择算法的时间复杂度分析2228.6.1找*大和*小问题2238.6.2找第二大问题2248.6.3找中位数的问题2268.7通过归约确认问题计算复杂度的下界228习题8229第9章np完全性2319.1p类与np类2319.1.1易解的问题与难解的问题2319.1.2判定问题2339.1.3np类2359.2多项式时间变换与np完全性2369.2.1多项式时间变换2369.2.2np完全性及其性质2389.2.3cooklevin定理——**个np完全问题2399.3几个np完全问题2399.3.1*大可满足性与三元可满足性2409.3.2顶点覆盖、团与独立集2419.3.3哈密顿回路与货郎问题2439.3.4恰好覆盖2459.3.5子集和、背包、装箱与双机调度2479.3.6整数线性规划249习题9252第10章近似算法25510.1近似算法及其近似比25510.2多机调度问题25610.2.1贪心的近似算法25610.2.2改进的贪心近似算法25710.3货郎问题25810.3.1*邻近法25810.3.2*小生成树法25910.3.3*小权匹配法26010.4背包问题26110.4.1一个简单的贪心算法26110.4.2多项式时间近似方案26110.4.3伪多项式时间算法与完全多项式时间近似方案262习题10264第11章随机算法26611.1概率论预备知识26611.2对随机快速排序算法的分析26811.3随机算法的分类及其局限性27011.3.1拉斯维加斯型随机算法27011.3.2蒙特卡洛型随机算法27011.3.3随机算法的局限性27111.4素数检验和多项式恒等检验27111.4.1素数检验27111.4.2多项式恒等检验27211.5随机游动算法27411.5.1有限马氏链及其表示27411.5.2求解二元布尔可满足性问题的随机游动算法275习题11276第12章处理难解问题的策略27712.1对问题施加限制27712.1.1二元可满足性问题27812.1.2霍恩公式可满足性问题27912.2固定参数算法28012.3改进指数时间算法28212.4启发式方法28412.5平均情形的复杂性28512.6难解算例生成28712.6.1相变现象与难解性28712.6.2隐藏解的难解算例28912.7基于统计物理的消息传递算法29012.7.1消息传递算法与回溯法、局部搜索算法的比较29012.7.2用消息传递算法求解3sat问题29112.8量子算法简介29212.8.1量子比特29212.8.2正交测量29312.8.3量子门29412.8.4一个量子算法295习题12297参考文献298