Lectures will be in Italian, with most slides and reading material in English. The final exam may be done in English or Italian.
Contenuto del corso
The course is organized around a number of technical and theoretical topics related to the Theory of Computation. Please see the Course Program for more details.
The course notes are designed to be complete and self-contained. However, most material was drawn from following books:
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.
Obiettivi Formativi
In this course we will develop theories of computation from the ground up. We will begin by examing the class of regular languages and three different models for them: regular expressions, deterministic finite automata, and nondeterministic finite automata. Then we will establish the precise limitations of this basic model, and begin extending it to the context-free languages, and finally the languages accepted by Turing Machine. Emphasis will be on formalizing our intuition about computation into a rigorous Theory of Computation that can be used to precisely bound capability models and complexity of problems. The course concludes with a rigorous treatment of complexity theory and the P=NP conjecture.
Prerequisiti
Past familiarity with formal methods of proof, especially techniques based on mathematical induction, will be extremely useful but not essential. The course will begin with a basic, high-entropy introduction to these technique.
Metodi Didattici
The course content consists entirely of lectures.
Modalità di verifica apprendimento
There is a single oral final exam. This exam will consist of two components:
- a twenty-minute presentation of a topic selected by the student; and
- a selection of questions drawn from all course lectures.
Programma del corso
The course is organized around the following topics:
- Regular Languages: regular expressions, deterministic finite automata, nondeterministic finite automata, the limitations of regular languages, the Myhill-Nerode Theorem and the Pumping Lemma.
- Context-free Languages: context-free grammars, pushdown automata, parsing, limitations of context-free languages, and the Pumping Lemma for context-free languages
- Turing Machines: the Turing Machine model of computation, equivalence of multi- and single-tape machines, unrestricted grammars.
- Computability Theory: the limitations of the Turing Machine, the Halting Problem, and other undecidable problems.
- Complexity Theory: asymptotic complexity, the complexity of a Turing Machine, the classes P and NP, the P=NP conjecture, and Cook's Theorem.