What's fun in EE Algorithm 1920 30 1. 3 2. 3. well defined executable 1. 2. (?) 10617 Email: dept@cc.ee.ntu.edu.tw http://www.ee.ntu.edu.tw/
Turing Machine [1] n n n findmin (a 1, a 2,, a n ) 1. result a 1 2. index 2 3. result min (result, aindex) 4. index index + 1 5. go to step 3 till (index > n) 6. return result pseudo-code n Θ(n) 5 1 Θ(.) Θ(n) Θ(n 0.5 ) Θ(log n) n 100 200 200 200 200 n [2] constant factor asymptotically optimal lower bound Θ(n) Θ(n) closed problem Θ(log n)
n n 1 reduction 1 n n 1 2 n 2 n 1 0 Θ(n 2 ) 3 a, b, c 3! = 6 a b a > b abc, acb, cab 3 6 2 [log 2 6] = 3 adversary argument 3 3 n n [log 2 (n!)] n! log Stirling [log 2 (n!)] = Θ(n log n)
Θ(n 2 ) merge sort divide-and-conquer Merge sort (merge) n n/2 n/4 1 merge sort Merge sort von Neumann 1945 [3] <a i ><b i > a 1, b 1 a 1 c 1 a 1 a 2 b 1 <ci> ) k k 2k-1 n T(n) T(n) = 2T(n/2) + cn c 1 T(2) = 1 n = 2 k T(n) = Θ(nlogn) merge sort open problems 3SUM n 3 0? C n 3 Θ(n 3 ) Θ(n 2 ) n Θ(nlogn) a + b + c = 0 c a + b = c Θ(n) 0 3SUM Θ(n 2 ) c Θ(n) 3SUM Θ(n 2 ) Turing machine Θ(n 2 ) 2008 Θ(n 2 ) Turing machine n polynomial time Θ(n c ) c RSA RSA RSA
C/C++ Windows7 Android Linux C/C++ Basic Java Java Java applet Java genetic algorithms Computer Science: An Overview by Brookshear, PEARSON 5 4 Darwin f x f (x) x f (x) x f (x)
open problems [1] Alan Turing Turing award 1936 Turing machine Church Church-Turing thesis Turing machine [2] adversary argument [3] von Neumann von Neumann