【文件属性】：
文件名称：算法概论.pdf
文件大小：54.45MB
文件格式：PDF
更新时间：2019-09-17 16:24:31
算法
序言
Preface
方框目录
0Prologue（序论）
0．1Booksandalgorithms（书和算法）
0．2EnterFibonacci（斐波那契数列）
0．3Big-Onotation（大O记号）
Exercises（习题）
1Algorithmswithnumbers（数的算法）
1．1Basicarithmetic（基本算术）
1．2Modulararithmetic（模运算）
1．3Primalitytesting（素性测试）
1．4Cryptography（密码学）
1．5Universalhashing（全域散列）
Exercises（习题）
Randomizedalgorithms：avirtualchapter（虚拟章：随机化算法）
2Divide-and-conqueralgorithms（分而治之算法）
2．1Multiplication（乘法）
2．2Recurrencerelations（递归关系）
2．3Mergesort（合并排序）
2．4Medians（中位数）
2．5Matrixmultiplication（矩阵乘法）
2．6ThefastFouriertransform（快速傅里叶变换）
Exercises（习题）
3Decompositionsofgraphs（图的分解）
3．1Whygraphs？（图论）
3．2Depth-firstsearchinundirectedgraphs（无向图中的深度优先搜索）
3．3Depth-firstsearchindirectedgraphs（有向图中的深度优先搜索）
3．4Stronglyconnectedcomponents（强连通分量）
Exercises（习题）——
4Pathsingraphs（图的路径）
4．1Distances（距离）
4．2Breadth-firstsearch（广度优先搜索）
4．3Lengthsonedges（边的长度）
4．4Dijkstra’salgorithm（Dijkstra算法）
4．5Priorityqueueimplementations（实现优先队列）
4．6Shortestpathsinthepresenceofnegativeedges（带负权的边的图中的最短路径）
4．7Shortestpathsindags（有向无环图中的最短路径）
Exercises（习题）
5Greedyalgorithms（贪婪算法）
5．1Minimumspanningtrees（最小生成树）
5．2Huffmanencoding（赫夫曼编码）
5．3Hornformulas（Horn公式）
5．4Setcover（集合覆盖）
Exercises（习题）
6Dynamicprogramming（动态规划）
6．1Shortestpathsindags，revisited（回顾：有向无环图中的最短路径）
6．2Longestincreasingsubsequences（最长
递增子序列）
6．3Editdistance（编辑距离）
6．4Knapsack（背包问题）
6．5Chainmatrixmultiplication（链式矩阵乘法）
6．6Shortestpaths（最短路径）
6．7Independentsetsintrees（树中的独立集）
Exercises（习题）
7Linearprogrammingandreductions（线性规划与归约）
7．1Anintroductiontolinearprogramming（线性规划入门）
7．2Flowsinnetworks（网络流）
7．3Bipartitematching（二部图匹配）
7．4Duality（对偶性）
7．5Zero-sumgames（零和游戏）
7．6Thesimplexalgorithm（单纯形算法）
7．7Postscript：circuitevaluation（附录：电路求值）
Exercises（习题）
8NP-completeproblems（NP完全问题）
8．1Searchproblems（搜索问题）
8．2NP-completeproblems（NP完全问题）
8．3Thereductions（归约）
Exercises（习题）
9CopingwithNP-completeness（处理NP完全问题）
9．1Intelligentexhaustivesearch（智能穷举搜索）
9．2Approximationalgorithms（近似算法）
9．3Localsearchheuristics（局部启发式搜索）
Exercises（习题）
10Quantumalgorithms（量子算法）
10．1Qubits，superposition，andmeasurement（量子比特、叠加态与测量）
10．2Theplan（下文纵览）3
10．3ThequantumFouriertransform（量子傅里叶变换）
10．4Periodicity（周期性）3
10．5Quantumcircuits（量子电路）3
10．6Factoringasperiodicity（因子分解：利用周期性）
10．7Thequantumalgorithmforfactoring（因子分解的量子算法）
Exercises（习题）
Historicalnotesandfurtherreading
（历史注记与扩展阅读）
索引
注释