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.
Curriculum
teacher profile teaching materials
Formal grammars: Chomsky grammars, productions, language recognition.
Regular languages: finite state automata, relationships between automata and regular languages, pumping lemma, closure of regular languages, regular expressions and regular languages, decidability and regular languages, Myhill-Nerode theorem.
Context-free languages.
Cardinality of infinite sets.
Turing machines (TMs) and Turing computability: how TMs work, multitape TMs, nondeterministic TMs, linearized description of TMs, universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages and TMs.
Register machines (RAMs): RAM cost models, uniform cost model, logarithmic cost model, RAM and TMs.
Complexity theory: types of problems, decision problems, complexity and language decision problems, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the NP class, NP-completeness, examples of NP-complete problems. The PSPACE class. The relationship between complexity and elementary machine learning problems.
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
Programme
Elementary properties of languages: language operations, the Kleene operator, regular expressions, language cardinality.Formal grammars: Chomsky grammars, productions, language recognition.
Regular languages: finite state automata, relationships between automata and regular languages, pumping lemma, closure of regular languages, regular expressions and regular languages, decidability and regular languages, Myhill-Nerode theorem.
Context-free languages.
Cardinality of infinite sets.
Turing machines (TMs) and Turing computability: how TMs work, multitape TMs, nondeterministic TMs, linearized description of TMs, universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages and TMs.
Register machines (RAMs): RAM cost models, uniform cost model, logarithmic cost model, RAM and TMs.
Complexity theory: types of problems, decision problems, complexity and language decision problems, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the NP class, NP-completeness, examples of NP-complete problems. The PSPACE class. The relationship between complexity and elementary machine learning problems.
Core Documentation
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
Type of delivery of the course
Traditional lectures and exercises.Attendance
Lecture in class.Type of evaluation
The exam consists of a written test with 8 questions and lasting approximately two hours. Students who wish to can use the following additional evaluation mechanism. During the lessons, exercises will be proposed to be done on moodle (questions in progress) in real time. This can happen during all lessons. The evaluation of the questions will be yes/no. Those who have passed at least eighty percent of the questions in progress will be able to do, only at the first call, a task of 6 questions, with three quarters of the time and obtaining the maximum score (7.5/30) on the two questions not to be asked. Those who have passed at least forty percent of the questions in progress will be able to do, only at the first call, a task of 7 questions, with seven eighths of the time and obtaining the maximum score (3.75/30) on the question not to be asked. Only those who are present in class will be able to do the questions in progress. To record those present, in each lesson there will be a list in which each person can indicate their presence. The list of those present will not be used in any other way. To answer questions in progress, it will be necessary to bring at least one smartphone or a laptop or a tablet to class. teacher profile teaching materials
Formal grammars: Chomsky grammars, productions, language recognition.
Regular languages: finite state automata, relationships between automata and regular languages, pumping lemma, closure of regular languages, regular expressions and regular languages, decidability and regular languages, Myhill-Nerode theorem.
Context-free languages.
Cardinality of infinite sets.
Turing machines (TMs) and Turing computability: how TMs work, multitape TMs, nondeterministic TMs, linearized description of TMs, universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages and TMs.
Register machines (RAMs): RAM cost models, uniform cost model, logarithmic cost model, RAM and TMs.
Complexity theory: types of problems, decision problems, complexity and language decision problems, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the NP class, NP-completeness, examples of NP-complete problems. The PSPACE class. The relationship between complexity and elementary machine learning problems.
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
Mutuazione: 20810256 Automata, Languages and Computing in Ingegneria informatica e dell'intelligenza artificiale LM-32 DI BATTISTA GIUSEPPE
Programme
Elementary properties of languages: language operations, the Kleene operator, regular expressions, language cardinality.Formal grammars: Chomsky grammars, productions, language recognition.
Regular languages: finite state automata, relationships between automata and regular languages, pumping lemma, closure of regular languages, regular expressions and regular languages, decidability and regular languages, Myhill-Nerode theorem.
Context-free languages.
Cardinality of infinite sets.
Turing machines (TMs) and Turing computability: how TMs work, multitape TMs, nondeterministic TMs, linearized description of TMs, universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages and TMs.
Register machines (RAMs): RAM cost models, uniform cost model, logarithmic cost model, RAM and TMs.
Complexity theory: types of problems, decision problems, complexity and language decision problems, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the NP class, NP-completeness, examples of NP-complete problems. The PSPACE class. The relationship between complexity and elementary machine learning problems.
Core Documentation
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
Type of delivery of the course
Traditional lectures and exercises.Attendance
Lecture in class.Type of evaluation
The exam consists of a written test with 8 questions and lasting approximately two hours. Students who wish to can use the following additional evaluation mechanism. During the lessons, exercises will be proposed to be done on moodle (questions in progress) in real time. This can happen during all lessons. The evaluation of the questions will be yes/no. Those who have passed at least eighty percent of the questions in progress will be able to do, only at the first call, a task of 6 questions, with three quarters of the time and obtaining the maximum score (7.5/30) on the two questions not to be asked. Those who have passed at least forty percent of the questions in progress will be able to do, only at the first call, a task of 7 questions, with seven eighths of the time and obtaining the maximum score (3.75/30) on the question not to be asked. Only those who are present in class will be able to do the questions in progress. To record those present, in each lesson there will be a list in which each person can indicate their presence. The list of those present will not be used in any other way. To answer questions in progress, it will be necessary to bring at least one smartphone or a laptop or a tablet to class. teacher profile teaching materials
Formal grammars: Chomsky grammars, productions, language recognition.
Regular languages: finite state automata, relationships between automata and regular languages, pumping lemma, closure of regular languages, regular expressions and regular languages, decidability and regular languages, Myhill-Nerode theorem.
Context-free languages.
Cardinality of infinite sets.
Turing machines (TMs) and Turing computability: how TMs work, multitape TMs, nondeterministic TMs, linearized description of TMs, universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages and TMs.
Register machines (RAMs): RAM cost models, uniform cost model, logarithmic cost model, RAM and TMs.
Complexity theory: types of problems, decision problems, complexity and language decision problems, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the NP class, NP-completeness, examples of NP-complete problems. The PSPACE class. The relationship between complexity and elementary machine learning problems.
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
Mutuazione: 20810256 Automata, Languages and Computing in Ingegneria informatica e dell'intelligenza artificiale LM-32 DI BATTISTA GIUSEPPE
Programme
Elementary properties of languages: language operations, the Kleene operator, regular expressions, language cardinality.Formal grammars: Chomsky grammars, productions, language recognition.
Regular languages: finite state automata, relationships between automata and regular languages, pumping lemma, closure of regular languages, regular expressions and regular languages, decidability and regular languages, Myhill-Nerode theorem.
Context-free languages.
Cardinality of infinite sets.
Turing machines (TMs) and Turing computability: how TMs work, multitape TMs, nondeterministic TMs, linearized description of TMs, universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages and TMs.
Register machines (RAMs): RAM cost models, uniform cost model, logarithmic cost model, RAM and TMs.
Complexity theory: types of problems, decision problems, complexity and language decision problems, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the NP class, NP-completeness, examples of NP-complete problems. The PSPACE class. The relationship between complexity and elementary machine learning problems.
Core Documentation
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
Type of delivery of the course
Traditional lectures and exercises.Attendance
Lecture in class.Type of evaluation
The exam consists of a written test with 8 questions and lasting approximately two hours. Students who wish to can use the following additional evaluation mechanism. During the lessons, exercises will be proposed to be done on moodle (questions in progress) in real time. This can happen during all lessons. The evaluation of the questions will be yes/no. Those who have passed at least eighty percent of the questions in progress will be able to do, only at the first call, a task of 6 questions, with three quarters of the time and obtaining the maximum score (7.5/30) on the two questions not to be asked. Those who have passed at least forty percent of the questions in progress will be able to do, only at the first call, a task of 7 questions, with seven eighths of the time and obtaining the maximum score (3.75/30) on the question not to be asked. Only those who are present in class will be able to do the questions in progress. To record those present, in each lesson there will be a list in which each person can indicate their presence. The list of those present will not be used in any other way. To answer questions in progress, it will be necessary to bring at least one smartphone or a laptop or a tablet to class. teacher profile teaching materials
Formal grammars: Chomsky grammars, productions, language recognition.
Regular languages: finite state automata, relationships between automata and regular languages, pumping lemma, closure of regular languages, regular expressions and regular languages, decidability and regular languages, Myhill-Nerode theorem.
Context-free languages.
Cardinality of infinite sets.
Turing machines (TMs) and Turing computability: how TMs work, multitape TMs, nondeterministic TMs, linearized description of TMs, universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages and TMs.
Register machines (RAMs): RAM cost models, uniform cost model, logarithmic cost model, RAM and TMs.
Complexity theory: types of problems, decision problems, complexity and language decision problems, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the NP class, NP-completeness, examples of NP-complete problems. The PSPACE class. The relationship between complexity and elementary machine learning problems.
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
Mutuazione: 20810256 Automata, Languages and Computing in Ingegneria informatica e dell'intelligenza artificiale LM-32 DI BATTISTA GIUSEPPE
Programme
Elementary properties of languages: language operations, the Kleene operator, regular expressions, language cardinality.Formal grammars: Chomsky grammars, productions, language recognition.
Regular languages: finite state automata, relationships between automata and regular languages, pumping lemma, closure of regular languages, regular expressions and regular languages, decidability and regular languages, Myhill-Nerode theorem.
Context-free languages.
Cardinality of infinite sets.
Turing machines (TMs) and Turing computability: how TMs work, multitape TMs, nondeterministic TMs, linearized description of TMs, universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages and TMs.
Register machines (RAMs): RAM cost models, uniform cost model, logarithmic cost model, RAM and TMs.
Complexity theory: types of problems, decision problems, complexity and language decision problems, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the NP class, NP-completeness, examples of NP-complete problems. The PSPACE class. The relationship between complexity and elementary machine learning problems.
Core Documentation
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
Type of delivery of the course
Traditional lectures and exercises.Attendance
Lecture in class.Type of evaluation
The exam consists of a written test with 8 questions and lasting approximately two hours. Students who wish to can use the following additional evaluation mechanism. During the lessons, exercises will be proposed to be done on moodle (questions in progress) in real time. This can happen during all lessons. The evaluation of the questions will be yes/no. Those who have passed at least eighty percent of the questions in progress will be able to do, only at the first call, a task of 6 questions, with three quarters of the time and obtaining the maximum score (7.5/30) on the two questions not to be asked. Those who have passed at least forty percent of the questions in progress will be able to do, only at the first call, a task of 7 questions, with seven eighths of the time and obtaining the maximum score (3.75/30) on the question not to be asked. Only those who are present in class will be able to do the questions in progress. To record those present, in each lesson there will be a list in which each person can indicate their presence. The list of those present will not be used in any other way. To answer questions in progress, it will be necessary to bring at least one smartphone or a laptop or a tablet to class. teacher profile teaching materials
Formal grammars: Chomsky grammars, productions, language recognition.
Regular languages: finite state automata, relationships between automata and regular languages, pumping lemma, closure of regular languages, regular expressions and regular languages, decidability and regular languages, Myhill-Nerode theorem.
Context-free languages.
Cardinality of infinite sets.
Turing machines (TMs) and Turing computability: how TMs work, multitape TMs, nondeterministic TMs, linearized description of TMs, universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages and TMs.
Register machines (RAMs): RAM cost models, uniform cost model, logarithmic cost model, RAM and TMs.
Complexity theory: types of problems, decision problems, complexity and language decision problems, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the NP class, NP-completeness, examples of NP-complete problems. The PSPACE class. The relationship between complexity and elementary machine learning problems.
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
Mutuazione: 20810256 Automata, Languages and Computing in Ingegneria informatica e dell'intelligenza artificiale LM-32 DI BATTISTA GIUSEPPE
Programme
Elementary properties of languages: language operations, the Kleene operator, regular expressions, language cardinality.Formal grammars: Chomsky grammars, productions, language recognition.
Regular languages: finite state automata, relationships between automata and regular languages, pumping lemma, closure of regular languages, regular expressions and regular languages, decidability and regular languages, Myhill-Nerode theorem.
Context-free languages.
Cardinality of infinite sets.
Turing machines (TMs) and Turing computability: how TMs work, multitape TMs, nondeterministic TMs, linearized description of TMs, universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages and TMs.
Register machines (RAMs): RAM cost models, uniform cost model, logarithmic cost model, RAM and TMs.
Complexity theory: types of problems, decision problems, complexity and language decision problems, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the NP class, NP-completeness, examples of NP-complete problems. The PSPACE class. The relationship between complexity and elementary machine learning problems.
Core Documentation
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
Type of delivery of the course
Traditional lectures and exercises.Attendance
Lecture in class.Type of evaluation
The exam consists of a written test with 8 questions and lasting approximately two hours. Students who wish to can use the following additional evaluation mechanism. During the lessons, exercises will be proposed to be done on moodle (questions in progress) in real time. This can happen during all lessons. The evaluation of the questions will be yes/no. Those who have passed at least eighty percent of the questions in progress will be able to do, only at the first call, a task of 6 questions, with three quarters of the time and obtaining the maximum score (7.5/30) on the two questions not to be asked. Those who have passed at least forty percent of the questions in progress will be able to do, only at the first call, a task of 7 questions, with seven eighths of the time and obtaining the maximum score (3.75/30) on the question not to be asked. Only those who are present in class will be able to do the questions in progress. To record those present, in each lesson there will be a list in which each person can indicate their presence. The list of those present will not be used in any other way. To answer questions in progress, it will be necessary to bring at least one smartphone or a laptop or a tablet to class.