《算法概论》读书笔记
2022-03-22 14:04:02 0 举报AI智能生成
《算法概论》思维导图
作者其他创作
大纲/内容
0章 序言
0.1书籍和算法
印刷术
十进制
算法的词源
0.2从Fibonacci数列开始
兔子繁殖
编程计算
指数算法
多项式算法
0.3大0符号
算法的时空分析
增长速度对比：线性与多项式、指数、对数、阶乘等P8
1章 数字的算法
1.1基本算术
加法
乘法和除法
1.2模运算
模的加法和乘法
模的指数运算
Euclid的最大大公因数算法
Euclid算法的一种扩展
模的除法
1.3素性测试
费马小定理
素数的随机生成
Lagrange素数定理
1.4密码学
密钥机制：一次一密乱码本和AES
RSA
1.5通用散列表
散列表
散列函数族
2章 分治算法
2.1乘法
2.2递推式
2.3合并排序
2.4寻找中项
2.5矩阵乘法
2.6快速Fourier变换的细节
多项式的另一种表示法
计算步骤的分治实现
插值
快速Fourier变换的细节
确定性FTT算法
快速Fourier变换的内部机制
3章 图的分解
3.1为什么是图
图的表示
3.2无向图的深度优先搜索
迷宫搜索
深度优先搜索
无向图的连通性
前序和后序
3.3有向图的深度优先搜索
边的类型
有向无环图
3.4强连通部件
定义有向图的连通性
一个有效的算法
4章 图中的路径
4.1距离
4.2广度优先搜索（BFS）
正确性和效率
4.3边的长度
4.4Dijkstra算法
广度优先搜索的一个改进
另一种解释
运行时间
4.5优先队列的实现
数组
二分堆
d堆
4.6含有负边的图的最短路径
负边
负环
4.7有向无环图中的最短路径
5章 贪心算法
5.1最小生成树
一个贪心算法
分割性质
Kruskal算法
一种用于分离集的数据结构
Prim算法
5.2Huffman编码
5.3Horn公式
5.4集合覆盖
6章 动态规划
6.1 重新审视有向无环图的最短路径问题
6.2 最长递增子序列
6.3 编辑距离
一种动态规划解法
隐含的dag
6.4 背包问题
多副本的背包问题
单副本的背包问题
6.5 矩阵链式相乘
6.6 最短路径问题
最短可靠路劲
所有顶点间的最短路径
旅行商问题
6.7 树中的独立集
7章 线性规划与规约
7.1 线性规划简介
示例：利润最大化
示例：生产计划
示例：最优带宽分配
线性规划的变体
7.2 网络流
石油运输
最大流
对算法的深入观察
最优性的保证
最小分割最大流定理
算法的效率
7.3 二部图的匹配
7.4 对偶
7.5 零和博弈（游戏）
7.6 单纯形算法
n维空间中的顶点和邻居
算法
补遗
起始顶点
退化
无界性
单纯算法的运行时间
高斯消去法
单纯形法
7.7 后记：电路值
8章 NP-完全问题
搜索问题
可满足性问题
旅行商问题
Euler和Rudrata
分割与二等分
整数线性规划
3D匹配
独立集、顶点覆盖和团
最长路径问题
背包问题和子集合
NP-完全问题
困难的问题与容易的问题
P和NP
再论规约
因子分解
所有的规约
Rudrata（s,t）-路径->Rudurata环路
3SAT->独立集
SAT－＞３SAT
独立集－＞顶点覆盖
独立集－＞团问题
３SAT->3D问题
3D匹配->ZOE
ZOE->子集和
ZOE->ILP
ZOE->Rudrata环路
Rudrata环路->TSP
任意NP问题->SAT
9章 NP-完全问题的处理
9.1 智能穷举搜索
回溯
分支定界
9.2 近似算法
顶点覆盖
聚类
k-聚类（k-CLUSTERING）
TSP
背包问题
逼近的层次
9.3 局部搜索中的启发方法
重新审视旅行商问题
图划分
处理局部最优
随机化与重启
模拟退火
10章 量子算法
10.1 量子位元、叠加状态和度量
10.2 算法设计
10.3 量子傅里叶变换
10.4 周期性
10.5 量子电路
基本量子门
量子电路的两种基本类型
量子傅里叶变换电路
10.6 将因子分解问题转化为周期求解问题
10.7 因子分解的量子算法
自由主题
0 条评论
下一页
