Athasit Surarerks

                        


2110 711 Theory of Computation
Course Syllabus


Credits
Department
Faculty
Semester
Year
Instructor(s)



Condition
Formation
Hours/Week
3(3-0-6)
Computer Engineering
Engineering
First
2003-4
Athasit Surarerks, Dr. en Inf.
Office 19-04, DSELab, tel:0 2218 6989, athasit@cp.eng.chula.ac.th
-


Master of Engineering / Master of Science / Ph.D.
3
Course Description          
Computable function; decidable predicates and solvable problems; computational complexity; NP-complete problems; automata theory; formal language; lambda calculus.
Evaluation


Mid-Term Examination
 50%
Final Examination
 50%

Week
 Topics
 		Volumn
1

2-3


4-6

Introduction to Language
Mathematical Induction
Turing Machine
Machine Enhancement
The Thesis of Church & Turing
Properties of the Enumeration
Universal Machines
Solvability and the Halting Problem
Reducibility and Unsolvability
Enumerable and Recursive Sets
 Preliminaries

Computability


Unsolvability
July
 Mid-Term Examination
 50 %
7-8




9-10


11-12

13-14
15
 Measures and Resource Bounds
Complexity classes
Reducibilities and Completeness
The Classes of P and NP
Intractable Problems
Languages & Grammars
Language Properties
The Chomsky Hierarchy
Numeric Computation
Mu-Recursive Functions
Lookahead in Context-Free Grammars
Special Problems
 Complexity




Languages


Decidability

Deterministic Parsing
September
 Final Examination
 50 %