中南大学算法设计郑谨..ppt

* Central South University * Example: Fibonacci Number 问题：一年以后，一共有多少对兔子？ 1. In the beginning: (1 pair) 2. End of month 1: (1 pair) Rabbits are ready to mate. 3. End of month 2: (2 pairs) A new pair of rabbits are born. 4. End of month 3: (3 pairs) A new pair and two old pairs. 5. End of month 4: (5 pairs) ... 6. End of month 5: (8 pairs) ... …….. 7.After 12 months, there will be 233 pairs rabbits! * Central South University * Recurrence Relation of Fibonacci Number fib(n) (递推关系） {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …} Tips:自然界中的Fibonacci Number 现象：海浪，钟声，...癌细胞? * Central South University * Algorithm: Fibonacci Problem: What is fib(200)? What about fib(n), where n is any positive integer? Algorithm1 fib (n) if n = 0 thenreturn 0 if n = 1thenreturn 1 return (fib(n?1) + fib(n?2)) Questions that we should ask ourselves: 1. What is the running time of the algorithm? 2. Can we do better? * Central South University * Answer of Questions How fast is the algorithm? If we let the run time of fib(n) be T(n), then we can formulate T(n) = T(n?1) + T(n?2) + 3 ? 1.6n T(200) ? 2139 Tips: 用世界是最快的计算机BlueGene/L: 每秒能运行248 条指令, 需运算 291 秒,(291 seconds = 7.85 × 1019 years ) * Central South University * Improvement Can we do better? Yes, because many computations in the previous algorithm are repeated. Algorithm 2: fib(n) // Initially we create an array A[0: n]A[0] ← 0, A[1] ← 1 For i = 2 to n do A[i] = A[i ? 1] + A[i ? 2] return (A[n]) * Central South University * Part2: Algorithm Design Techniques/Strategies Brute force Divide and conquer Decrease and conquer Greedy approach Dynamic programming Backtracking Branch and bound * * * * * ？？=编程 这门课十分有趣，同时也比较难，大家必须努力学习才能学好它！ * * * * Gcd(70, 25) = gcd(25, 20) = gcd(20, 5) = gcd (5, 0) = 5 Gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12 * * prime factors:素因数 * Pseudo-code （伪代码），类高级语言，由于其非常简练，便于表达算法的思想， indentation(缩进） * * 性能是1，其它的都是后面的0 * The first part of this course is focused on analysis, the second part of t