PPT《*》

* */74 课程基本信息 课程编号:

21190120 上课时间、地点:2011年 秋学期周二(

9、10)曹光彪 西104 、周四(7~8)曹光彪 西104上机:周四(

9、10)软件学院机房考试时间:?考试形式:?学时/学分:4-2/周 学时/ 2-1 学分 * */74 Office &

Homepage Office:工商楼 215My Homepage:http://www.

cs.zju.edu.cn/people/yedeshi/Course Home: * */74 Examination Grading Polices:Class attendance 10%Homework (or quiz): 25% Programming Project: 20%Final Exam: 45% 课堂讨论或随堂测验、报告20%作业 25%大程 15%期末考试 40% New Grading Polices * */74 What is the position of algorithms in CS 1. Linguists: what shall we talk to the machines?2. Algorithms: what is a good method for solving a problem fast on my computer3. Architects: Can I build a better computer?4. Sculptors of Machine Intelligence: Can I write a computer program that can find its own solution. * */74 * */74 Algorithms in Computer Science Algorithms Hardware Compilers, Programming languages Machine learning, Statistics, Information retrieval, AI Networking, Distributed systems, Fault tolerance, Security Bioinformatics ....... * */74 MIT Undergraduate Programs * */74 What is algorithm? (Oxford Dict.)Algorithm: A set of rules that must be followed when solving a particular problem.From Math world A specific set of instructions for carrying out a procedure or solving a problem, usually with the requirement that the procedure terminate at some point. An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. * */74 * */74 What will CS be? Computer Science:Past, Present, and Future Ed Lazowska (Washington)Computer Science is the new Math Christos H. Papadimitriou (Berkeley) * */74 Algorithm Problem definition 问题Objective 目标 (very important)Evaluation 算法评价 Methods 方法 * */74 Algorithm evaluation Quality: how far away from the optimal solution ?Cost: Running time Space neededOur goal is to design algorithm with high quality, but in low cost * */74 Reasonable times Poly(|I|), Time polynomial in |I|, where |I| is the size of the problem instanceInput size: size(x) of an instance x with rational data is the total number of bits needed for the binary prepresentation. Time complexity logarithmic time if T(n) = O(log n).sub-linear time if T(n) = o(n)linear time, or O(n) timelinearithmic function: T(n) = O(n log n), quasilinear time if T(n) = O(n logk n)polynomial time: T(n) = O(nk) for some constant kstrongly polynomial time: the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance;

andthe space used by the algorithm is bounded by a polynomial in the size of the input.weakly polynomial time: P but not strongly P * */74 Time complexity Quasi-polynomial time:for some fixed c. Sub-exponential time if T(n) = 2o(n)Exponential time, if T(n) is upper bounded by 2poly(n) * */74 * */74 Hardness of problems Polynomial (e.g. n2, n log n, n3, n1000).Quasi-polynomial(e.g.:n log n, n log2n, c log7n).Sub-exponential (e.g.: 2√n, 5(n0.98)).Exponential (e.g.: 2n, 8n, n!, nn). Easy Hard * */74 Running time Computer A is

100 times faster than computer BSort n numbersComputer A requires instructionsComputer B requires 50nlgn instructionsn = 1,000, 000Computer A: 2(10^6)^2/10^9 =

2000 secondsComputer B: 50*10^6 lg 10^6/10^7 ~

100 seconds * */74 Running time

10 <

1 s <

1s <

1 s <

1 s <

1 s