详情

About the Course:

This course explores computational complexity, from search algorithms and solution landscapes to reductions and universality. We explore problems ranging from easy (polynomial time) to hard (NP-complete) to impossible (undecidable). These ideas form one of the most beautiful fields of modern mathematics, and they are increasingly relevant to sciences ranging from physics to biology. The aim of this course is to help participants gain an understanding of the deep ideas of theoretical computer science in a clear and enjoyable fashion, making those ideas accessible both to non-computer scientists and to computer scientists who want to revisit these ideas in a broader and deeper way.

Units include:

1.Easy and Hard
2.Algorithms and Landscapes
3.P versus NP
4.Worst-case, Natural, and Random
5.Computation Everywhere
Units will be released approximately one per week, with a unit exam at the end of each and due by the end of the subsequent week (eg. unit 1 released at start of week 1; unit 1 exam due at the end of week 2). Each unit will require an average of about 5 hours to complete (including all content and assessments). All coursework is conducted in English.

The course consists of lectures, interactive exercises, quizzes for self-assessment, and unit exams. The interactive exercises allow participants to see various problems from the lectures in practice and to see the effects of various perturbations. The quizzes are intended to help participants assess their understanding of the material and to prepare for the unit exams. Only the unit exam scores count toward completion of the course, which requires that a participant achieve ≥ 60% score on all unit exams. The unit exams consist of quiz questions and are peer-graded according to a grading rubric provided by the instructor. Completion of grading assignments is also required to recieve a certificate of completion for the course.


讲师介绍

Cristopher Moore

Cris Moore is resident faculty at the Santa Fe Institute. He received his B.A. in Physics, Mathematics, and Integrated Science from Northwestern University, and his Ph.D. in Physics from Cornell. From 2000 to 2012 he was a professor at the University of New Mexico, with joint appointments in Computer Science and Physics. He has also held visiting positions at École Normale Superieure, École Polytechnique, Université Paris 7, École Normale Superieure de Lyon, the University of Michigan, and Northeastern University. He has written 150 papers at the boundary between physics and computer science, ranging from quantum computing, to phase transitions in NP-complete problems, to the theory of social networks and efficient algorithms for analyzing their structure. He is an elected Fellow of the American Physical Society, the American Mathematical Society, and the American Association for the Advancement of Science. With Stephan Mertens, he is the author of The Nature of Computation from Oxford University Press.


 课程学习




学习地址:

https://campus.swarma.org/course/2666






集智学园公众号:swarmAI
集智学园QQ群:426390994
集智学园官网:campus.swarma.org
商务合作&投稿转载|swarma@swarma.org