|
Teacher
|
PATRIGNANI MAURIZIO
(syllabus)
Elementary properties of languages: operations on languages, Kleene operator, regular expressions, cardinality of languages.
Formal grammars: Chomsky grammars, productions, recognition of languages.
Regular languages: finite state automata, relationships between automata and regular languages, pumping lemma, closure properties of regular languages, regular expressions and regular languages, Myhill-Nerode theorem.
Context-free languages.
Cardinality of infinite sets.
Turing Machines (TM) and computability: operation of TM, multi-tape TM, non deterministic TM, linear description of a TM, universal TM, halting problem, Turing computability, Rice theorem, Type 0 languages and TMs.
Random Access Machines (RAM): cost models for RAMs, uniform cost model, logarithmic cost model, RAM and TM.
Complexity theory: type of problems, decision problems, complexity and decision problems involving languages, complexity classes, elementary relationships between complexity classes, reductions, completeness, the class NP, NP-completeness, examples of NP-complete problems.
(reference books)
Slides provided by the professor.
Books (useful but non mandatory):
G. Ausiello, F. d'Amore, G. Gambosi, Linguaggi Modelli Complessità, Franco Angeli (i primi dieci capitoli sono distribuiti dagli autori gratuitamente)
M. Sipser, Introduction to the Theory of Computation, Thompson
|
Università Roma Tre