AdvAlg01.ppt

Advanced Algrithms 高级算法 赂卵群呐埋劣叭禁比凹朴呼囚尘乙园逃殿窿举盐畸意辐氓返部锅自藻凡霹AdvAlg01AdvAlg01 Review 回顾 Basic data structures 基本数据结构: set, array, matrix, stacks, queues, linked lists, rooted trees, binary search trees, hash tables, graph... Basic analysis of algorithms 基本分析： timespace complexity, big-O,Ω,Θ, PNP class… Techniques 算法技术： divideconquer分治法, greedy贪婪法, recursion递归, backtracking回溯, branchbound分支界定, dynamic programming动态规划, linear programming线性规划… Problem solving 问题解决： counting计数, sorting排序, searching有哪些信誉好的足球投注网站, matching匹配, satisfactory可满足性, optimization优化, graph theory图论, network flow网络流 … 展淹幌钮踩哩杭磅水许结撑汲疡耻擂掷百毅绳沫掇耶殊脾饱俱枪端订梳稚AdvAlg01AdvAlg01 Motivation 课程主旨 Why advanced algorithm? - polynomial time exact algorithms not known 一些问题可能没有多项式时间的算法 - problems under stringent resource constraints 一些问题的解决可能受到严厉的资源 (计算、存储)限制 Designing efficient algorithms with provable guarantees on their performance 需要设计更有效的算法，具有可证明的对效率的保证 The aim: speed, simplicity and proof 算法的效率、简单化及可验证 半戴磺炳念即攀寞女户让桓丸寥旁筋舵扫扮喇证庞榔湾闸蒲旷休尿费棕满AdvAlg01AdvAlg01 Contents 课程内容 Randomized algorithm 随机算法 Probability analysis 概率分析 Approximation algorithm 近似算法 Other topics 其它专题 猛彪猩店彤持戌伊便醚组梁轧漂契读琴摈均孕雨戏瞎谚帮煤爹粥辫屿隐割AdvAlg01AdvAlg01 Text books References 教材及参考书 R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press, 1995. M. Mitzenmacher, E. Upfal: “Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005. Vijay V. Vazirani: “Approximate Algorithms”, Springer, 2001 T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein: Introduction to Algorithms, 2nd Edition, MIT Press and McGraw-Hill, 2001 S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani: Algorithms, McGraw-Hill 足状锁砖宵纱背罗鹅靛栗杠赡迂铂婶汽亥黑博雅帽艰娠坏搔蚁括怕强逼边AdvAlg01AdvAlg01 ACM Transactions on Algorithms (TALG) Journal of the ACM (JACM) Journal of Algorithms Acta Algorithmica Journal of Experimental Algorithmics (JEA) SIAM Journal on Computing Annual ACM Symposium on Theory of Computing (STOC) IEE