B024259 - THEORETICAL COMPUTER SCIENCE

Lectures will be in Italian, with most slides and reading material in English. The final exam may be done in English or Italian.

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:

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.

The objective of this course is to furnish the concepts and models of computation most important to the study of theoretical computer science:

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

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.

The course content consists entirely of lectures.

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.

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, Rice's Theoram 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.