| 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
|
DI BATTISTA GIUSEPPE
(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
(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
|
|
Dates of beginning and end of teaching activities
|
From 01/10/2019 to 24/01/2020 |
|
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
|
DI BATTISTA GIUSEPPE
(syllabus)
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, the class Pspace, Pspace-completeness, Savitch theorem, the classes L and NL, NL-completeness.
(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
|
|
Dates of beginning and end of teaching activities
|
From 01/10/2019 to 24/01/2020 |
|
Delivery mode
|
Traditional
|
|
Attendance
|
not mandatory
|
|
Evaluation methods
|
Written test
|
|
|
|
Università Roma Tre