1、精研课程* 2/74课程基本信息课程编号： 21190120 上课时间、地点： 2013年 夏学期周二 (12)曹光彪 西 101 、周四（ 12）曹光彪 西 101考试时间： 7月 3日 闭卷* 3/74Office & HomepageOffice：工商楼 215My Homepage：http:/ 4/74ExaminationGrading Polices：1) Homework: 10%2) Quiz: 15% (May 21)3) Presentation: 15%4) Programming Projects: 20% (2 programms)5) Final Exam: 40
2、% TA information史如意 : rolesGuide to group the studentsCollect the homework, program, and projectReview of homework, programsEmail: * 5/74* 6/74The core of TCSAlgorithms and complexity of computationComputational limits of proof methodsLogic and program verificationThe power of randomizationCryptogra
3、phyQuantum computationDistributed computation and communicationComputational learning theoryImportant themes in TCSEfficiency common measures: computation time, memory, parallelism, randomness,.Impossibility results intellectual ancestors: impossibility of perpetual motion, impossibility of trisecti
4、ng an angle, incompleteness theorem, undecidability, etc.Approximationapproximately optimal answers, algorithms that work “most of the time”,mathematical characterizations that are approximate (e.g., approximatemax-flow min-cut theorem)Central role of randomnessrandomized algorithms and protocols, p
5、robabilistic encryption,random graph models, probabilistic models of the WWW, etc. ReductionsNP-completeness and other intractability results (including complexity-based cryptography) What is the position of algorithms in CS1. Linguists: what shall we talk to the machines?2. Algorithms: what is a go
6、od 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. * 9/74* 10/74Algorithms in Computer ScienceAlgorithmsHardwareCompilers, Programming languagesMachine learning, Statistics, Information retrieval, AINetworking, Distributed systems, Fault tolerance, SecurityBioinformatics .
