Course Code: B62005Y
Course Name: Introduction to Theory of Computation
Credits: 3.0
Level: Undergraduate
Pre-requisite: Discrete mathematics, Probability Theory, Mathematical Statistics
Course Description:
This course consists of three parts: formal language and automata, computability, and computational complexity. In the first part, students will master the formal description method of computing devices, laying the foundation for the remaining course and future courses such as Compiler Theory. The second part, focused on the concept of algorithm, enables students to grasp the definition of computation and to distinguish the difference between computable and incomputable problems. In the third part, students will understand the definition of effectiveness and learn what kind of problems can be effectively computed.
Topics and Schedule:
No. Contents Hours Knowledge Remarks
1 Introduction 0.5 Course Introduction, Pre-knowledge Chapter 0
2 Finite automata 1.5 DFA, RL, Regular Operation, Closure Chapter 1, Section 1.1
3 Non-deterministic 2 NFA, Equivalence of DFA Chapter 1, Section 1.2
4 Regular expressions 1 RE, Equivalence of FA Chapter 1, Section1.3
5 Non-regular languages 1 Pumping lemma of RL Chapter 1, Section1.4
6 CFG 2 CFG, CFL, Ambiguity, Chomsky Paradigm Chapter 2, Section 2.1
7 Pushdown automaton 2 PDA, Equivalence of CFG Chapter 2, Section 2.2
8 Non-context-free languages 1 Pumping lemma of NFL Chapter 2, Section 2.3
9 Deterministic context-free languages 3 PDA, CFG, Closure, DCFG, Equivalence of DPDA, LR (k) grammar Chapter 2, Section2.4
10 Turing machine 2 TM, Turing recognizable, Turing decidable Chapter 3, Section 3.1
11 Turing machine deformation 2 Multitude TM, NDTM, Enumerators, Equivalence of other models Chapter 3, Section 3.2
12 Algorithm 2 Hilbert Problem, The Church-Turing thesis, Encoding, Versatility Chapter 3, Section 3.3
13 Decidable language 2 Decidability of RL, Decidability of CFL Chapter 4, Section 4.1
14 Undecidability 2 Diagonalization method, Undecidable languages, non-Turing-recognizable languages Chapter 4, Section 4.2
15 Reducibility 2 Halting Problem, Linear boundaries automaton, Reduction of the history of computing Chapter 5, Section 5.1
16 Post correspondence problem 2 Post correspondence problem Chapter 5, Section 5.2
17 Mapping reduction 1 Computable functions, Mapping reduction, Closure Chapter 5, Section 5.3
18 Advanced topics of computability theory 3 Recursion Theorem, Incompleteness theorem, Turing reduction, Descriptive Complexity Chapter 6
19 Time complexity 2 Metric Complexity, P class, NP class Chapter 7, Section 7.1-7.3
20 NP complete 2 Polynomial time reduction, NP completeness, Satisfiability Problem, Cook-Levin Theorem Chapter 7, Section 7.4
21 NP-complete problems 2 Vertex Cover Problem, the Hamiltonian path problem, Subset sum problem Chapter 7, Section 7.5
22 Spatial complexity 2 Savage theorems, PSPACE class, PSPACE complete, Full-band quantifier Boolean formula problem Chapter 8, Section 8.1-8.3
23 Logarithmic space 2 L class, NL class, NL complete, NL=coNL Chapter 8, Section 8.4-8.6
24 Hierarchy theorem 2 Space-constructible function, Space hierarchy theorem, Time constructor, Time hierarchy theorem Chapter 9, Section 9.1
25 Relativization 1 Relativization Chapter 9, Section 9.2
26 Circuit complexity 3 Circuit complexity Chapter 9, Section 9.3
27 Approximation algorithm 0.5 Approximation algorithm, Approximation ratio Chapter 10, Section10.1
28 Probabilistic algorithm 1.5 BPP class, Prime Test Chapter 10, Section10.2
29 Polynomial hierarchy 1 Interlace, PH class Chapter 10, Section10.3
30 Interactive proof system 1 IP classes, IP = PSPACE Chapter 10, Section10.4
31 Parallel computing 1 Consistency, NC class, P Complete Chapter 10, Section10.5
32 Cryptology 1 Public key cryptography system, One-way function, Trapdoor function Chapter 10, Section10.6
33 Student presentation 2
Textbook:
Michael Sipser, Introduction to the Theory of Computation, ISBN:. 9787111499718
