| THEORETICAL INFORMATICS
(objectives)
Introduce the students to the theory of languages and, at the same time, to the theory of automata. introduce computability and complexity paradigms. At the end of the course students should know new formal methodologies, should be able to critically review, from the perspective of their expressive potential, already known methodologies and should be able to classify problems from the point of view of the resources required for their solution.
|
|
Code
|
20801728 |
|
Language
|
ITA |
|
Type of certificate
|
Profit certificate
|
| Module:
(objectives)
Introduce the students to the theory of languages and, at the same time, to the theory of automata. introduce computability and complexity paradigms. At the end of the course students should know new formal methodologies, should be able to critically review, from the perspective of their expressive potential, already known methodologies and should be able to classify problems from the point of view of the resources required for their solution.
|
|
Code
|
20801728-1 |
|
Language
|
ITA |
|
Type of certificate
|
Profit certificate
|
|
Credits
|
6
|
|
Scientific Disciplinary Sector Code
|
ING-INF/05
|
|
Contact Hours
|
54
|
|
Type of Activity
|
Core compulsory activities
|
|
Teacher
|
PATRIGNANI MAURIZIO
(syllabus)
Basic language properties: Operations with languages, Kleene's operator, regular expressions, languages and cardinalities
Grammars: Chomsky's grammars, productions, language generation and recognition.
Regular Languages: Finite State Automata, relationship between automata and regular languages, pumping lemma, closure of regular languages, regular expressions and regular languages, regular languages and decidable properties, Myhill-Nerode theorem.
(reference books)
G. Ausiello, F. d'Amore, G. Gambosi, "Linguaggi Modelli Complessità", FrancoAngeli
|
|
Dates of beginning and end of teaching activities
|
From 01/10/2016 to 20/12/2016 |
|
Delivery mode
|
Traditional
|
|
Attendance
|
not mandatory
|
|
Evaluation methods
|
Written test
|
|
|
| Module:
(objectives)
Introduce the students to the theory of languages and, at the same time, to the theory of automata. introduce computability and complexity paradigms. At the end of the course students should know new formal methodologies, should be able to critically review, from the perspective of their expressive potential, already known methodologies and should be able to classify problems from the point of view of the resources required for their solution.
|
|
Code
|
20801728-2 |
|
Language
|
ITA |
|
Type of certificate
|
Profit certificate
|
|
Credits
|
6
|
|
Scientific Disciplinary Sector Code
|
ING-INF/05
|
|
Contact Hours
|
54
|
|
Type of Activity
|
Core compulsory activities
|
|
Teacher
|
PATRIGNANI MAURIZIO
(syllabus)
Context-Free Languages.
Cardinalities for infinite sets.
Turing Machines (TM) and Turing computability: definition of TM, multi-tape TM, non deterministic TM, linearized description of TM, universal TM universale.
The Halting theorem, calcolability according to Turing, Rice theorem, TM and type 0 languages.
Random Access Machines (RAM): cost models for RAMs, uniform costs, logaritmic costs, relationship between RAM and TM.
Theory of complexity: kind of problems, decision problems, complexity and decision problems on languages, complexity classes, relationship among complexity classes, reductions, completeness, the NP class, NP-completeness, example of NP-complete problems, the P-space class, P-space completeness, Savitch theorem, the classes L and NL, NL-completeness.
(reference books)
Michael Sipser, "Introduction to the Theory of Computation", Second Edition, Thompson.
|
|
Dates of beginning and end of teaching activities
|
From 01/10/2016 to 20/12/2016 |
|
Delivery mode
|
Traditional
|
|
Attendance
|
not mandatory
|
|
Evaluation methods
|
Written test
|
|
|
|
Università Roma Tre