文件名称:
加州大学伯克利分校计算机系算法课程讲义
开发工具:
文件大小: 1mb
下载次数: 0
上传时间: 2012-12-10
详细说明： Contents Preface 9 0 Prologue 11 0.1 Booksandalgorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 0.2 EnterFibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 0.3 Big-Onotation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1 Algorithmswithnumbers 21 1.1 Basicarithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.2 Modulararithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.3 Primalitytesting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.4 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.5 Universalhashing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Randomizedalgorithms:avirtualchapter 39 2 Divide-and-conqueralgorithms 55 2.1 Multiplication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.2 Recurrencerelations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.3 Mergesort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.4 Medians. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 2.5 Matrixmultiplication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.6 Thefast Fouriertransform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3 Decompositionsofgraphs 91 3.1 Whygraphs? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 3.2 Depth-rstsearchinundirectedgraphs . . . . . . . . . . . . . . . . . . . . . . . . 93 3.3 Depth-rstsearchindirectedgraphs. . . . . . . . . . . . . . . . . . . . . . . . . . 98 3.4 Stronglyconnectedcomponents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 3 4 Algorithms 4 Pathsingraphs 115 4.1 Distances. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 4.2 Breadth-rstsearch. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 4.3 Lengthsonedges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 4.4 Dijkstra'salgorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 4.5 Priorityqueueimplementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 4.6 Shortestpathsinthepresenceofnegativeedges . . . . . . . . . . . . . . . . . . . 128 4.7 Shortestpathsindags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 5 Greedyalgorithms 139 5.1 Minimumspanningtrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 5.2 Huffmanencoding. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 5.3 Hornformulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 5.4 Setcover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 6 Dynamicprogramming 169 6.1 Shortestpathsindags, revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 6.2 Longestincreasingsubsequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 6.3 Editdistance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 6.4 Knapsack. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 6.5 Chainmatrixmultiplication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 6.6 Shortestpaths. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 6.7 Independentsetsintrees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 7 Linearprogrammingandreductions 201 7.1 Anintroductiontolinear programming . . . . . . . . . . . . . . . . . . . . . . . . 201 7.2 Flowsinnetworks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 7.3 Bipartitematching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 7.4 Duality. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 7.5 Zero-sumgames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 7.6 Thesimplexalgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 7.7 Postscript:circuitevaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 8 NP-completeproblems 247 8.1 Searchproblems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 8.2 NP-completeproblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 8.3 Thereductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 S. Dasgupta,C.H. Papadimitriou,andU.V. Vazirani 5 9 CopingwithNP-completeness 283 9.1 Intelligentexhaustivesearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 9.2 Approximationalgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 9.3 Localsearchheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 10Quantumalgorithms 311 10.1Qubits, superposition,andmeasurement . . . . . . . . . . . . . . . . . . . . . . . 311 10.2Theplan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 10.3ThequantumFouriertransform . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 10.4Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 10.5Quantumcircuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 10.6Factoringasperiodicity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 10.7Thequantumalgorithmfor factoring . . . . . . . . . . . . . . . . . . . . . . . . . . 326 Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 Historicalnotesandfurtherreading 331 Index ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
