This course provides the basic foundational elements of computing, mostly focusing on the limitations of what is computable. By starting from the study of formal languages, Turing machines are introduced and a few undecidable problems are presented. Finally, for decidable problems, the most significant complexity classes are introduced. 

In more detail, the course is structured in 3 parts.

PART 1: FORMAL LANGUAGES. Finite state automata; non-determinism; regular expressions; regular grammars; Pumping Lemma for regular languages; context-free grammars; pushdown automata; Pumping Lemma for context-free languages; context-sensitive grammars and 0-type grammars; Chomsky hierarchy.

PART 2: COMPUTABILITY THEORY. Turing machines; equivalence with 0-type grammars; variants of Turing machines (multitape and non-deterministic); definition of algorithm; Church-Turing thesis; decidable problems; undecidability; Rice's theorem.

PART 3: COMPLEXITY THEORY. Measuring time complexity; classes P and NP; polynomial-time reductions; NP completeness and NPC problems; approximation algorithms; hints at other complexity classes (P-SPACE, L, NL).

[S] M. Sipser: Introduction to the Theory of Computation. III edition (2013)

[HU] J.E.Hopcroft, J.D.Ullman: Introduction to Automata theory, Languages and Computation (1979). Chapter 9 (Chomsky hierarchy)

[CLRS] Cormen, Leiserson, Rivest, Stern: Introduction to algorithms. III edition (2009): chapters 34 (NP-completeness) and 35 (Approximation Algorithms)

The exam will consist in a written classwork on the first part of the course (practical exercises on formal languages - to be precise, on the first two chapters of [S]) and, for those who pass this, an oral exam on all the three parts of the course (definitions, theorems, proofs, ...).

The detailed exam modalities can be found here .

In Sapienza's Moodle platform, you can find all the slides of the course and a forum for discussing the topics of the classes (where you can post exercises, ask for explanations, interact between you, and interact with me). I suggest you to register (with your studenti.uniroma1.it account) at https://elearning.uniroma1.it (look for «Foundations of Computer Science»). The pwd has been communicated in the first class of the course, or you can ask it to me by email. You're NOT authorized to distribute the material downloaded nor the credentials to access the site.