导图社区 算法概论
此思维导图为算法概论。包括完全问题的处理、数字的算法、分治算法、图的分解等内容,十分详细,希望给大家带来帮助!
编辑于2022-04-18 14:22:18《算法概论》
1. 0章 序言
1.1. 0.1书籍和算法
1.1.1. 印刷术
1.1.2. 十进制
1.1.3. 算法的词源
1.2. 0.2从Fibonacci数列开始
1.2.1. 兔子繁殖
1.2.2. 编程计算
1.2.3. 指数算法
1.2.4. 多项式算法
1.3. 0.3大0符号
1.3.1. 算法的时空分析
1.3.2. 增长速度对比:线性与多项式、指数、对数、阶乘等P8
2. 1章 数字的算法
2.1. 1.1基本算术
2.1.1. 加法
2.1.2. 乘法和除法
2.2. 1.2模运算
2.2.1. 模的加法和乘法
2.2.2. 模的指数运算
2.2.3. Euclid的最大大公因数算法
2.2.4. Euclid算法的一种扩展
2.2.5. 模的除法
2.3. 1.3素性测试
2.3.1. 费马小定理
2.3.2. 素数的随机生成
2.3.2.1. Lagrange素数定理
2.4. 1.4密码学
2.4.1. 密钥机制:一次一密乱码本和AES
2.4.2. RSA
2.5. 1.5通用散列表
2.5.1. 散列表
2.5.2. 散列函数族
3. 2章 分治算法
3.1. 2.1乘法
3.2. 2.2递推式
3.3. 2.3合并排序
3.4. 2.4寻找中项
3.5. 2.5矩阵乘法
3.6. 2.6快速Fourier变换的细节
3.6.1. 多项式的另一种表示法
3.6.2. 计算步骤的分治实现
3.6.3. 插值
3.6.4. 快速Fourier变换的细节
3.6.4.1. 确定性FTT算法
3.6.4.2. 快速Fourier变换的内部机制
4. 3章 图的分解
4.1. 3.1为什么是图
4.1.1. 图的表示
4.2. 3.2无向图的深度优先搜索
4.2.1. 迷宫搜索
4.2.2. 深度优先搜索
4.2.3. 无向图的连通性
4.2.4. 前序和后序
4.3. 3.3有向图的深度优先搜索
4.3.1. 边的类型
4.3.2. 有向无环图
4.4. 3.4强连通部件
4.4.1. 定义有向图的连通性
4.4.2. 一个有效的算法
5. 4章 图中的路径
5.1. 4.1距离
5.2. 4.2广度优先搜索(BFS)
5.2.1. 正确性和效率
5.3. 4.3边的长度
5.4. 4.4Dijkstra算法
5.4.1. 广度优先搜索的一个改进
5.4.2. 另一种解释
5.4.3. 运行时间
5.5. 4.5优先队列的实现
5.5.1. 数组
5.5.2. 二分堆
5.5.3. d堆
5.6. 4.6含有负边的图的最短路径
5.6.1. 负边
5.6.2. 负环
5.7. 4.7有向无环图中的最短路径
6. 5章 贪心算法
6.1. 5.1最小生成树
6.1.1. 一个贪心算法
6.1.2. 分割性质
6.1.3. Kruskal算法
6.1.4. 一种用于分离集的数据结构
6.1.5. Prim算法
6.2. 5.2Huffman编码
6.3. 5.3Horn公式
6.4. 5.4集合覆盖
7. 6章 动态规划
7.1. 6.1 重新审视有向无环图的最短路径问题
7.2. 6.2 最长递增子序列
7.3. 6.3 编辑距离
7.3.1. 一种动态规划解法
7.3.2. 隐含的dag
7.4. 6.4 背包问题
7.4.1. 多副本的背包问题
7.4.2. 单副本的背包问题
7.5. 6.5 矩阵链式相乘
7.6. 6.6 最短路径问题
7.6.1. 最短可靠路劲
7.6.2. 所有顶点间的最短路径
7.6.3. 旅行商问题
7.7. 6.7 树中的独立集
8. 7章 线性规划与规约
8.1. 7.1 线性规划简介
8.1.1. 示例:利润最大化
8.1.2. 示例:生产计划
8.1.3. 示例:最优带宽分配
8.1.4. 线性规划的变体
8.2. 7.2 网络流
8.2.1. 石油运输
8.2.2. 最大流
8.2.3. 对算法的深入观察
8.2.4. 最优性的保证
8.2.4.1. 最小分割最大流定理
8.2.5. 算法的效率
8.3. 7.3 二部图的匹配
8.4. 7.4 对偶
8.5. 7.5 零和博弈(游戏)
8.6. 7.6 单纯形算法
8.6.1. n维空间中的顶点和邻居
8.6.2. 算法
8.6.3. 补遗
8.6.3.1. 起始顶点
8.6.3.2. 退化
8.6.3.3. 无界性
8.6.4. 单纯算法的运行时间
8.6.4.1. 高斯消去法
8.6.4.2. 单纯形法
8.7. 7.7 后记:电路值
9. 8章 NP-完全问题
9.1. 搜索问题
9.1.1. 可满足性问题
9.1.2. 旅行商问题
9.1.3. Euler和Rudrata
9.1.4. 分割与二等分
9.1.5. 整数线性规划
9.1.6. 3D匹配
9.1.7. 独立集、顶点覆盖和团
9.1.8. 最长路径问题
9.1.9. 背包问题和子集合
9.2. NP-完全问题
9.2.1. 困难的问题与容易的问题
9.2.2. P和NP
9.2.3. 再论规约
9.2.4. 因子分解
9.3. 所有的规约
9.3.1. Rudrata(s,t)-路径->Rudurata环路
9.3.2. 3SAT->独立集
9.3.3. SAT->3SAT
9.3.4. 独立集->顶点覆盖
9.3.5. 独立集->团问题
9.3.6. 3SAT->3D问题
9.3.7. 3D匹配->ZOE
9.3.8. ZOE->子集和
9.3.9. ZOE->ILP
9.3.10. ZOE->Rudrata环路
9.3.11. Rudrata环路->TSP
9.3.12. 任意NP问题->SAT
10. 9章 NP-完全问题的处理
10.1. 9.1 智能穷举搜索
10.1.1. 回溯
10.1.2. 分支定界
10.2. 9.2 近似算法
10.2.1. 顶点覆盖
10.2.2. 聚类
10.2.2.1. k-聚类(k-CLUSTERING)
10.2.3. TSP
10.2.4. 背包问题
10.2.5. 逼近的层次
10.3. 9.3 局部搜索中的启发方法
10.3.1. 重新审视旅行商问题
10.3.2. 图划分
10.3.3. 处理局部最优
10.3.3.1. 随机化与重启
10.3.3.2. 模拟退火
11. 10章 量子算法
11.1. 10.1 量子位元、叠加状态和度量
11.2. 10.2 算法设计
11.3. 10.3 量子傅里叶变换
11.4. 10.4 周期性
11.5. 10.5 量子电路
11.5.1. 基本量子门
11.5.2. 量子电路的两种基本类型
11.5.3. 量子傅里叶变换电路
11.6. 10.6 将因子分解问题转化为周期求解问题
11.7. 10.7 因子分解的量子算法