Sillabo dell'insegnamento

• A - Fondamenti
V - Varie
Mathematical background (sets, relations, functions, cardinalities, graphs)
* CAL - Calcolabilità
Computability and decidability (Church-Turing thesis, linearized description of TM; universal TM)
* CAL - Calcolabilità
Computability and decidability: the halting problem, undecidable languages, enumeration of recursive properties, properties of enumerations of recursive functions, uncomputable functions, Kleene and Rice theorems, decidable and semidecidable sets)
* CAL - Calcolabilità
Undecidability and incompleteness in First-order logic (elements of propositional logic, elements of First-order logic, Gödel's theorems, axioms for number theory, undecidability and incompleteness)
COM - Complessità
Deterministic complexity classes (P, P-complete problems)
* CAL - Calcolabilità
Turing machines (single-tape TM, deterministic TM, Turing computability, multi-tape TM)
COM - Complessità
Non-deterministic Turing machines. The class NP. Polynomial time verification.
COM - Complessità
NP-completeness. Cook-Levin theorem.
COM - Complessità
Space complexity
COM - Complessità
Hierarchy theorems
• B - Algoritmi
* A - Algoritmi fondamentali
Introduction (problems and algorithms: Reachability, MST, TSP)
• D - Linguaggi
* LF - Linguaggi Formali
Formal languages (alphabets, languages, finite representations of languages, finite automata and regular languages)