Programma

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. The class PSPACE.

Testi Adottati

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

Modalità Erogazione

Traditional lectures and exercises.

Modalità Frequenza

Lecture in class.

Modalità Valutazione

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.

Programma

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. The class PSPACE.

Testi Adottati

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

Modalità Erogazione

Traditional lectures and exercises.

Modalità Frequenza

Lecture in class.

Modalità Valutazione

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.

Programma

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. The class PSPACE.

Testi Adottati

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

Modalità Erogazione

Traditional lectures and exercises.

Modalità Frequenza

Lecture in class.

Modalità Valutazione

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.

Programma

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. The class PSPACE.

Testi Adottati

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

Modalità Erogazione

Traditional lectures and exercises.

Modalità Frequenza

Lecture in class.

Modalità Valutazione

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.

Programma

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. The class PSPACE.

Testi Adottati

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

Modalità Erogazione

Traditional lectures and exercises.

Modalità Frequenza

Lecture in class.

Modalità Valutazione

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.