This course provides an introduction to the theory of computation, including formal languages, grammars, automata theory, computability, and complexity. You will learn to reason formally about computation. The theory of computation examines the questions "What is a computer?" and "What can it do?".
• How to reason precisely about computation and prove mathematical theorems about its capabilities and limitations.
• Models of computation. Specifically, we will study finite automata, push-down automata and Turing machines.
• The intrinsic limits of computation. Computational problems that cannot be solved by any algorithm whatsoever (undecidability), and problems that are solvable but require inordinate computational resources (computational complexity).
• Formal language theory. The basics of grammars and parsing.
Also, you should demonstrate an understanding of and be able to apply mathematical and formal techniques for solving practical problems in computer science.
Textbook: Michael Sipser, Introduction to the Theory of Computation (Third Edition), Cengage Learning, 2013. (The 2nd edition can also be used)
Welcome to the course "Introduction to the Theory of Computation". I hope that you find it to be an interesting and enjoyable thing.
课程简介
Course Introduction
教学大纲
Teaching Syllabus
