本地导入书籍的 AI 翻译功能
仅支持付费会员使用
仅支持付费会员使用
微信扫码开通付费会员
一键翻译全文
一键翻译全文
微信读书书城算法设计与分析基础(第3版) 10.1 单纯形法
查看
全部搜索结果
算法设计与分析基础(第3版)
Anany Levitin
- 版权信息
- 版权申明
- 内容简介
- 作者简介
- 译者简介
- 译者序
- 前言
- 算法设计技术的新分类法
- 设计技术作为问题求解的一般性策略
- 如何使用本书
- 第3版的变化
- 先修课程
- 课程进度安排
- 致谢
- 第1章 绪论
- 1.1 什么是算法
- 习题1.1
- 1.2 算法问题求解基础
- 1.2.1 理解问题
- 1.2.2 了解计算设备的性能
- 1.2.3 在精确解法和近似解法之间做出选择
- 1.2.4 算法的设计技术
- 1.2.5 确定适当的数据结构
- 1.2.6 算法的描述
- 1.2.7 算法的正确性证明
- 1.2.8 算法的分析
- 1.2.9 为算法写代码
- 习题1.2
- 1.3 重要的问题类型
- 1.3.1 排序
- 1.3.2 查找
- 1.3.3 字符串处理
- 1.3.4 图问题
- 1.3.5 组合问题
- 1.3.6 几何问题
- 1.3.7 数值问题
- 习题1.3
- 1.4 基本数据结构
- 1.4.1 线性数据结构
- 1.4.2 图
- 1.4.3 树
- 1.4.4 集合与字典
- 习题1.4
- 小结
- 第2章 算法效率分析基础
- 2.1 分析框架
- 2.1.1 输入规模的度量
- 2.1.2 运行时间的度量单位
- 2.1.3 增长次数
- 2.1.4 算法的最优、最差和平均效率
- 2.1.5 分析框架概要
- 习题2.1
- 2.2 渐近符号和基本效率类型
- 2.2.1 非正式的介绍
- 2.2.2 符号O
- 2.2.3 符号Ω
- 2.2.4 符号Θ
- 2.2.5 渐近符号的有用特性
- 2.2.6 利用极限比较增长次数
- 2.2.7 基本的效率类型
- 习题2.2
- 2.3 非递归算法的数学分析
- 习题2.3
- 2.4 递归算法的数学分析
- 习题2.4
- 2.5 例题：计算第n个斐波那契数
- 习题2.5
- 2.6 算法的经验分析
- 习题2.6
- 2.7 算法可视法
- 小结
- 第3章 蛮力法
- 3.1 选择排序和冒泡排序
- 3.1.1 选择排序
- 3.1.2 冒泡排序
- 习题3.1
- 3.2 顺序查找和蛮力字符串匹配
- 3.2.1 顺序查找
- 3.2.2 蛮力字符串匹配
- 习题3.2
- 3.3 最近对和凸包问题的蛮力算法
- 3.3.1 最近对问题
- 3.3.2 凸包问题
- 习题3.3
- 3.4 穷举查找
- 3.4.1 旅行商问题
- 3.4.2 背包问题
- 3.4.3 分配问题
- 习题3.4
- 3.5 深度优先查找和广度优先查找
- 3.5.1 深度优先查找
- 3.5.2 广度优先查找
- 习题3.5
- 小结
- 第4章 减治法
- 4.1 插入排序
- 习题4.1
- 4.2 拓扑排序
- 习题4.2
- 4.3 生成组合对象的算法
- 4.3.1 生成排列
- 4.3.2 生成子集
- 习题4.3
- 4.4 减常因子算法
- 4.4.1 折半查找
- 4.4.2 假币问题
- 4.4.3 俄式乘法
- 4.4.4 约瑟夫斯问题
- 习题4.4
- 4.5 减可变规模算法
- 4.5.1 计算中值和选择问题
- 4.5.2 插值查找
- 4.5.3 二叉查找树的查找和插入
- 4.5.4 拈游戏
- 习题4.5
- 小结
- 第5章 分治法
- 5.1 合并排序
- 习题5.1
- 5.2 快速排序
- 习题5.2
- 5.3 二叉树遍历及其相关特性
- 习题5.3
- 5.4 大整数乘法和Strassen矩阵乘法
- 5.4.1 大整数乘法
- 5.4.2 Strassen矩阵乘法
- 习题5.4
- 5.5 用分治法解最近对问题和凸包问题
- 5.5.1 最近对问题
- 5.5.2 凸包问题
- 习题5.5
- 小结
- 第6章 变治法
- 6.1 预排序
- 习题6.1
- 6.2 高斯消去法
- 6.2.1 LU分解
- 6.2.2 计算矩阵的逆
- 6.2.3 计算矩阵的行列式
- 习题6.2
- 6.3 平衡查找树
- 6.3.1 AVL树
- 6.3.2 2-3树
- 习题6.3
- 6.4 堆和堆排序
- 6.4.1 堆的概念
- 6.4.2 堆排序
- 习题6.4
- 6.5 霍纳法则和二进制幂
- 6.5.1 霍纳法则
- 6.5.2 二进制幂
- 习题6.5
- 6.6 问题化简
- 6.6.1 求最小公倍数
- 6.6.2 计算图中的路径数量
- 6.6.3 优化问题的化简
- 6.6.4 线性规划
- 6.6.5 简化为图问题
- 习题6.6
- 小结
- 第7章 时空权衡
- 7.1 计数排序
- 习题7.1
- 7.2 字符串匹配中的输入增强技术
- 7.2.1 Horspool算法
- 7.2.2 Boyer-Moore算法
- 习题7.2
- 7.3 散列法
- 7.3.1 开散列（分离链）
- 7.3.2 闭散列（开式寻址）
- 习题7.3
- 7.4 B树
- 习题7.4
- 小结
- 第8章 动态规划
- 8.1 三个基本例子
- 习题8.1
- 8.2 背包问题和记忆功能
- 8.2.1 背包问题
- 8.2.2 记忆化
- 习题8.2
- 8.3 最优二叉查找树
- 习题8.3
- 8.4 Warshall算法和Floyd算法
- 8.4.1 Warshall算法
- 8.4.2 计算完全最短路径的Floyd算法
- 习题8.4
- 小结
- 第9章 贪婪技术
- 9.1 Prim算法
- 习题9.1
- 9.2 Kruskal算法
- 不相交子集和并查算法
- 习题9.2
- 9.3 Dijkstra算法
- 习题9.3
- 9.4 哈夫曼树及编码
- 习题9.4
- 小结
- 第10章 迭代改进
- 10.1 单纯形法
- 10.1.1 线性规划的几何解释
- 10.1.2 单纯形法概述
- 10.1.3 单纯形法其他要点
- 习题10.1
- 10.2 最大流量问题
- 习题10.2
- 10.3 二分图的最大匹配
- 习题10.3
- 10.4 稳定婚姻问题
- 习题10.4
- 小结
- 第11章 算法能力的极限
- 11.1 如何求下界
- 11.1.1 平凡下界
- 11.1.2 信息论下界
- 11.1.3 敌手下界
- 11.1.4 问题化简
- 习题11.1
- 11.2 决策树
- 11.2.1 排序的决策树
- 11.2.2 查找有序数组的决策树
- 习题11.2
- 11.3 P、NP和NP完全问题
- 11.3.1 P和NP问题
- 11.3.2 NP完全问题
- 习题11.3
- 11.4 数值算法的挑战
- 习题11.4
- 小结
- 第12章 超越算法能力的极限
- 12.1 回溯法
- 12.1.1 n皇后问题
- 12.1.2 哈密顿回路问题
- 12.1.3 子集和问题
- 12.1.4 一般性说明
- 习题12.1
- 12.2 分支界限法
- 12.2.1 分配问题
- 12.2.2 背包问题
- 12.2.3 旅行商问题
- 习题12.2
- 12.3 NP困难问题的近似算法
- 12.3.1 旅行商问题的近似算法
- 12.3.2 背包问题的近似算法
- 习题12.3
- 12.4 解非线性方程的算法
- 12.4.1 平分法
- 12.4.2 试位法
- 12.4.3 牛顿法
- 习题12.4
- 小结
- 跋
- 附录A 算法分析的实用公式
- A.1 对数的性质
- A.2 组合学
- A.3 重要的求和公式
- A.4 求和乘法法则
- A.5 用定积分对求和进行近似计算
- A.6 向下取整和向上取整公式
- A.7 其他
- 附录B 递推关系简明指南
- B.1 序列和递推关系
- B.2 递推关系的求解方法
- B.3 算法分析中的常见递推类型
- 习题提示
- 第1章
- 习题1.1
- 习题1.2
- 习题1.3
- 习题1.4
- 第2章
- 习题2.1
- 习题2.2
- 习题2.3
- 习题2.4
- 习题2.5
- 习题2.6
- 第3章
- 习题3.1
- 习题3.2
- 习题3.3
- 习题3.4
- 习题3.5
- 第4章
- 习题4.1
- 习题4.2
- 习题4.3
- 习题4.4
- 习题4.5
- 第5章
- 习题5.1
- 习题5.2
- 习题5.3
- 习题5.4
- 习题5.5
- 第6章
- 习题6.1
- 习题6.2
- 习题6.3
- 习题6.4
- 习题6.5
- 习题6.6
- 第7章
- 习题7.1
- 习题7.2
- 习题7.3
- 习题7.4
- 第8章
- 习题8.1
- 习题8.2
- 习题8.3
- 习题8.4
- 第9章
- 习题9.1
- 习题9.2
- 习题9.3
- 习题9.4
- 第10章
- 习题10.1
- 习题10.2
- 习题10.3
- 习题10.4
- 第11章
- 习题11.1
- 习题11.2
- 习题11.3
- 习题11.4
- 第12章
- 习题12.1
- 习题12.2
- 习题12.3
- 习题12.4
- 参考文献
暂无笔记