Theory of Computation

This is the course page for the Theory of Computation course in the Laurea in Ingegneria Informatica at the University of Florence. The course is offered for 6 CFU (ECTS).

This page collects public-facing information about the course and it’s content. If you are a registered student at the University of Florence, please see the Course Moodle for this academic year for detailed and up-to-date information about the course.

Overview

The objective of this course is to furnish the concepts and models of computation most important to the study of theoretical computer science. The course is organized around the following learning objectives:

  • Knowledge and understanding of proof techniques use in theoretical computer science: constructive proofs, proof by contradiction, proof by induction (mathematical, complete, and structural).
  • Knowledge and understanding of the most important computational models: deterministic and nondeterministic finite automata, regular languages, context-free languages, pushdown automata, and Turing Machines.
  • Knowledge and understanding of computability theory: recursive and recursively enumerable languages, undecidable problems, the Halting Problem and its undecidability.
  • Knowledge and understanding of computational complexity theory: asymptotic complexity, polynomial reduction, the classes P, NP, NP-hard, NP-complete, NP-completeness di SAT, and the implications of the P=NP Conjecture.

At the end of the course, students will be able to apply this knowledge and understanding to problems of computation, computability, and computational complexity theory.

The course notes are designed to be complete and self-contained. However, most material was drawn from following books:

Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning.

Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2013). Introduction to Automata Theory, Languages, and Computation (3rd ed). Pearson.

Martin, John (2002). Introduction to Languages and the Theory of Computation (3rd ed). McGraw-Hill.

Final Examination

The final grade for the course is based on a written and oral exam consisting of questions and exercises verifying the student’s ability to:

  • Construct simple automata/grammars that accept/generate a specific language.- Apply formal mathematical proof techniques to prove properties of languages and automata.
  • Recognize ambiguous grammars and disambiguate them.
  • Prove that a language is not regular or not context-free.
  • Prove that specific problems are undecidable.
  • Distinguish the principal classes of computational complexity.

About halfway through the course there will be a written midterm exam. If the grade on this midterm is sufficient (>= 18), it is possible to take the final written exam on only the remaining part of the course program.