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)

From this academic year, there are two exam modalities:

1. STANDARD MODALITY: 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 written part has no marks; it is made up by 3 simple exercises to be solved in 45 minutes and it is passed with 2 correct exercises. The real exam is the oral one, whose questions will be grouped according to their difficulty and, correspondingly, will grant you different ranges of mark; see here the detailed arguments of the exam, grouped according to the mark that you may obtain.

2. SIMPLIFIED MODALITY: If you aim at passing the exam with a low mark (at most 20), after the exercises mentioned above, you can do a second part of the written exam where, in 30 minutes, you will be asked two theoretical questions (one definition and one proof) from those of the range 18-24 listed in the document above. To pass the exam in this modality, you must correctly do at least one exercise and one theoretical question.

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.