THEORY OF COMPUTATION
Graduate level course at UFMG
Prof: Carlos
Camarão de Figueiredo
Course Program:
- Background: Mathematical Preliminaries
- Introduction to set theory
- Recursive definitions and mathematical induction
- Graphs
- Languages and Machines
- Strings and Languages
- Regular sets and regular expressions
- Context-free languages and grammars
- Parsing
- Finite-state automata, Push-down automata and Turing Machines
- Computability
- Church-Turing Thesis
- Decidability, halting problem
- Reducibility
- Recursion Theorem
- Complexity
- Big-O and small-o
- Classes P and NP
- NP-completeness
You will like this course because:
- The course material intends
to make the subjects fun and enjoyable
- The topics are of utmost importance for distinguished students
- The course will give you valuable information if you are
interested in doing a thesis involving some topics
related to one of the areas mentioned above
- Evaluation will not give priority to exams but to
exercises by the students
- Students will have class time available for doing the exercises
and discussing them with me
- The teacher is confused ;-)
Bibliography:
- Languages and Machines,
Thomas Sudkamp, Addison-Wesley, 1997. (Chapters 1-4)
- Introduction to the Theory of Computation,
Michael Sipser, PWS Publishing Company, 1997 (Chapters 3-9).
These books are available in the department library.
Evaluation:
- Exercises: 60 points.
- 2 exams, of 20 points each.
Answers to exercises:
Transparencies:
- Mathematical Preliminaries
- Introduction
- Automata
A1 ,
A2 ,
A3 ,
A4 ,
A5 ,
A6
- Context-free languages
CFL1
CFL2 ,
CFL3 ,
CFL4
- Computability, Decidability and Turing Machines
TM1 ,
TM2 ,
TM3 ,
TM4 ,
TM5 ,
TM6 ,
TM7
- Examples of exercises (for studying)