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).

Evaluation:

• Exercises: 60 points.
• 2 exams, of 20 points each.

Answers to exercises:

• Ex 1 , Ex 2 , Ex 3 , Ex 4 , Ex 6

Answers to exams: First exam 

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)
  • Automata ExA1 , ExA2 , ExA3 , ExA4 , ExA5 , ExA6
  • Context-free languages ExCFL1 , ExCFL2 , ExCFL3 , ExCFL4