### Introduction to Theory of Computation

Course Code: B62005Y

Course Name: Introduction to Theory of Computation

Credits: 3.0

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