算法设计与分析 第2版
内容简介
[
《算法设计与分析（第2版）》为计算机类专业核心课程“算法设计与分析”教材。全书以算法设计技术和分析方法为主线来组织各知识单元。主要内容包括基础知识、分治策略、动态规划、贪心法、回溯与分支限界、线性规划、网络流算法、算法分析与问题的计算复杂度、NP完全性、近似算法、随机算法、处理难解问题的策略等。力求突出对问题本身的分析和求解方法的阐述，从问题建模、算法设计与分析、改进措施等方面给出适当的建议，同时也简要介绍了计算复杂性理论的核心内容和处理难解问题的一些新技术。 与《算法设计与分析（第2版）》配套有学习指导与习题解析用书、PPT电子教案，MOOC视频教学资源也将近期完成。 《算法设计与分析（第2版）》适合作为大学计算机科学与技术、软件工程、信息安全、信息与计算科学等专业本科生和研究生的教学用书，也可以作为从事实际问题求解的算法设计与分析工作的科技人员的参考书。
]
目录
第1章 基础知识1．1 有关算法的基本概念1．2 算法的伪码描述1．3 算法的数学基础1．3．1 函数的渐近的界1．3．2 求和的方法1．3．3 递推方程求解方法习题1第2章 分治策略2．1 分治策略的基本思想2．1．1 两个熟悉的例子2．1．2 分治算法的一般性描述2．2 分治算法的分析技术2．3 改进分治算法的途径2．3．1 通过代数变换减少子问题个数2．3．2 利用预处理减少递归内部的计算量2．4 典型实例2．4．1 快速排序算法2．4．2 选择问题2．4．3 n-1次多项式在全体2n次方根上的求值习题2第3章 动态规划3．1 动态规划的设计思想3．1．1 多起点、多终点的*短路径问题3．1．2 使用动态规划技术的必要条件3．2 动态规划算法的设计要素3．2．1 子问题的划分和递推方程3．2．2 动态规划算法的递归实现3．2．3 动态规划算法的迭代实现3．2．4 一个简单实例的计算过程3．3 动态规划算法的典型应用3．3．1 投资问题3．3．2 背包问题3．3．3 *长公共子序列3．3．4 图像压缩3．3．5 *大子段和3．3．6 *优二分检索树3．3．7 生物信息学中的动态规划算法习题3第4章 贪心法4．1 贪心法的设计思想4．2 关于贪心法的正确性证明4．3 对贪心法得不到*优解情况的处理4．4 贪心法的典型应用4．4．1 *优前缀码4．4．2 *小生成树4．4．3 单源*短路径习题4第5章 回溯与分支限界5．1 回溯算法的基本思想和适用条件5．1．1 几个典型的例子5．1．2 回溯算法的适用条件5．2 回溯算法的设计步骤5．2．1 回溯算法的递归实现和迭代实现5．2．2 几个典型的例子5．3 回溯算法的效率估计和改进途径5．4 分支限界5．4．1 背包问题5．4．2 *大团问题5．4．3 货郎问题5．4．4 圆排列问题5．4．5 连续邮资问题习题5第6章 线性规划6．1 线性规划模型6．1．1 模型6．1．2 二维线性规划的图解法6．2 标准形6．2．1 标准形基本概念6．2．2 标准形的可行解的性质6．3 单纯形法6．3．1 确定初始基本可行解6．3．2 *优性检验6．3．3 基变换6．3．4 单纯形表6．3．5 人工变量和两阶段法6．3．6 单纯形法的有限终止6．4 对偶性6．4．1 对偶线性规划6．4．2 对偶单纯形法6．5 整数线性规划的分支限界算法习题6第7章 网络流算法7．1 *大流问题7．1．1 网络流及其性质7．1．2 Ford-Fulkerson算法7．1．3 Dinic有效算法7．2 *小费用流7．2．1 Floyd算法7．2．2 *小费用流的负回路算法7．2．3 *小费用流的*短路径算法7．3 运输问题7．3．1 确定初始调运方案7．3．2 改进调运方案7．3．3 表上作业法7．4 二部图匹配7．4．1 二部图的*大匹配7．4．2 赋权二部图的匹配习题7第8章 算法分析与问题的计算复杂度8．1 平凡下界8．2 直接计数求解该问题所需要的*少运算8．3 决策树8．4 检索算法的时间复杂度分析8．5 排序算法的时间复杂度分析8．5．1 冒泡排序算法8．5．2 堆排序算法8．5．3 排序算法的决策树与算法类时间复杂度的下界8．6 选择算法的时间复杂度分析8．6．1 找*大和*小问题8．6．2 找第二大问题8．6．3 找中位数的问题8．7 通过归约确认问题计算复杂度的下界习题8第9章 NP完全性9．1 P类与NP类9．1．1 易解的问题与难解的问题9．1．2 判定问题9．1．3 NP类9．2 多项式时间变换与NP完全性9．2．1 多项式时间变换9．2．2 NP完全性及其性质9．2．3 Cook-Levin定理——**个NP完全问题9．3 几个NP完全问题9．3．1 *大可满足性与三元可满足性9．3．2 顶点覆盖、团与独立集9．3．3 哈密顿回路与货郎问题9．3．4 恰好覆盖9．3．5 子集和、背包、装箱与双机调度9．3．6 整数线性规划习题9第10章 近似算法10．1 近似算法及其近似比10．2 多机调度问题10．2．1 贪心的近似算法10．2．2 改进的贪心近似算法10．3 货郎问题10．3．1 *邻近法10．3．2 *小生成树法10．3．3 *小权匹配法10．4 背包问题10．4．1 一个简单的贪心算法10．4．2 多项式时间近似方案10．4．3 伪多项式时间算法与完全多项式时间近似方案习题10第11章 随机算法11．1 概率论预备知识11．2 对随机快速排序算法的分析11．3 随机算法的分类及其局限性11．3．1 拉斯维加斯型随机算法11．3．2 蒙特卡洛型随机算法11．3．3 随机算法的局限性11．4 素数检验和多项式恒等检验11．4．1 素数检验11．4．2 多项式恒等检验11．5 随机游动算法11．5．1 有限马氏链及其表示11．5．2 求解二元布尔可满足性问题的随机游动算法习题11第12章 处理难解问题的策略12．1 对问题施加限制12．1．1 二元可满足性问题12．1．2 霍恩公式可满足性问题12．2 固定参数算法12．3 改进指数时间算法12．4 启发式方法12．5 平均情形的复杂性12．6 难解算例生成12．6．1 相变现象与难解性12．6．2 隐藏解的难解算例12．7 基于统计物理的消息传递算法12．7．1 消息传递算法与回溯法、局部搜索算法的比较12．7．2 用消息传递算法求解3SAT问题12．8 量子算法简介12．8．1 量子比特12．8．2 正交测量12．8．3 量子门12．8．4 一个量子算法习题12参考文献
封面
书名:算法设计与分析 第2版
作者:刘田等
页数:297
定价:¥49.0
出版社:清华大学出版社
出版日期:2019-03-01
ISBN:9787302424505
PDF电子书大小:35MB 高清扫描完整版