Programme

The syllabus for the course "Automata, Languages, and Computing" is as follows:
•    Elementary properties of languages: operations on languages, the Kleene operator, regular expressions, cardinality of languages.
•    Formal grammars: Chomsky grammars, productions, language recognition.
•    Regular languages: finite-state automata, relationships between automata and regular languages, the pumping lemma, closure properties of regular languages, regular expressions and regular languages, decidability and regular languages, the Myhill-Nerode theorem.
•    Context-free languages: non-deterministic pushdown automata, relationships between automata and context-free languages, the pumping lemma, closure and decidability properties, ambiguity.
•    Turing machines (TMs) and Turing computability: operation of TMs, multi-tape TMs, non-deterministic TMs, linearized descriptions of TMs, the universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages ​​and TMs.
•    Complexity theory: types of problems, decision problems, complexity and decision problems for languages, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the class NP, NP-completeness, examples of NP-complete problems. The class PSPACE. Complexity of problems in machine learning.

Prerequisiti

No special requirements.

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 examination consists of a written test containing 8 questions, with a duration of two hours. Students may choose to take advantage of the following additional assessment mechanism: - During lectures, exercises (in-class questions) will be presented via Moodle to be completed in real time. - This may occur during any lecture. - These questions will be graded on a yes/no basis. - Students who have successfully answered at least 80% of these in-class questions may—exclusively during the first exam session—complete a 6-question test. In this case, they will be allotted three-quarters of the standard time and will automatically receive full marks (7.5/30) for the two questions they are not required to answer. - Students who have successfully answered at least 40% of these in-class questions may—exclusively during the first exam session—complete a 7-question test. In this case, they will be allotted seven-eighths of the standard time and will automatically receive full marks (3.75/30) for the one question they are not required to answer. - Only students present in class are eligible to complete these in-class questions. - To track attendance, a digital register will be available during each lecture, where students can record their presence. - This attendance record will not be used for any other purpose. - To complete the in-class questions, students must bring a smartphone, laptop, or tablet to the lecture.

Programme

The syllabus for the course "Automata, Languages, and Computing" is as follows:
•    Elementary properties of languages: operations on languages, the Kleene operator, regular expressions, cardinality of languages.
•    Formal grammars: Chomsky grammars, productions, language recognition.
•    Regular languages: finite-state automata, relationships between automata and regular languages, the pumping lemma, closure properties of regular languages, regular expressions and regular languages, decidability and regular languages, the Myhill-Nerode theorem.
•    Context-free languages: non-deterministic pushdown automata, relationships between automata and context-free languages, the pumping lemma, closure and decidability properties, ambiguity.
•    Turing machines (TMs) and Turing computability: operation of TMs, multi-tape TMs, non-deterministic TMs, linearized descriptions of TMs, the universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages ​​and TMs.
•    Complexity theory: types of problems, decision problems, complexity and decision problems for languages, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the class NP, NP-completeness, examples of NP-complete problems. The class PSPACE. Complexity of problems in machine learning.

Prerequisiti

No special requirements.

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 examination consists of a written test containing 8 questions, with a duration of two hours. Students may choose to take advantage of the following additional assessment mechanism: - During lectures, exercises (in-class questions) will be presented via Moodle to be completed in real time. - This may occur during any lecture. - These questions will be graded on a yes/no basis. - Students who have successfully answered at least 80% of these in-class questions may—exclusively during the first exam session—complete a 6-question test. In this case, they will be allotted three-quarters of the standard time and will automatically receive full marks (7.5/30) for the two questions they are not required to answer. - Students who have successfully answered at least 40% of these in-class questions may—exclusively during the first exam session—complete a 7-question test. In this case, they will be allotted seven-eighths of the standard time and will automatically receive full marks (3.75/30) for the one question they are not required to answer. - Only students present in class are eligible to complete these in-class questions. - To track attendance, a digital register will be available during each lecture, where students can record their presence. - This attendance record will not be used for any other purpose. - To complete the in-class questions, students must bring a smartphone, laptop, or tablet to the lecture.

Programme

The syllabus for the course "Automata, Languages, and Computing" is as follows:
•    Elementary properties of languages: operations on languages, the Kleene operator, regular expressions, cardinality of languages.
•    Formal grammars: Chomsky grammars, productions, language recognition.
•    Regular languages: finite-state automata, relationships between automata and regular languages, the pumping lemma, closure properties of regular languages, regular expressions and regular languages, decidability and regular languages, the Myhill-Nerode theorem.
•    Context-free languages: non-deterministic pushdown automata, relationships between automata and context-free languages, the pumping lemma, closure and decidability properties, ambiguity.
•    Turing machines (TMs) and Turing computability: operation of TMs, multi-tape TMs, non-deterministic TMs, linearized descriptions of TMs, the universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages ​​and TMs.
•    Complexity theory: types of problems, decision problems, complexity and decision problems for languages, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the class NP, NP-completeness, examples of NP-complete problems. The class PSPACE. Complexity of problems in machine learning.

Prerequisiti

No special requirements.

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 examination consists of a written test containing 8 questions, with a duration of two hours. Students may choose to take advantage of the following additional assessment mechanism: - During lectures, exercises (in-class questions) will be presented via Moodle to be completed in real time. - This may occur during any lecture. - These questions will be graded on a yes/no basis. - Students who have successfully answered at least 80% of these in-class questions may—exclusively during the first exam session—complete a 6-question test. In this case, they will be allotted three-quarters of the standard time and will automatically receive full marks (7.5/30) for the two questions they are not required to answer. - Students who have successfully answered at least 40% of these in-class questions may—exclusively during the first exam session—complete a 7-question test. In this case, they will be allotted seven-eighths of the standard time and will automatically receive full marks (3.75/30) for the one question they are not required to answer. - Only students present in class are eligible to complete these in-class questions. - To track attendance, a digital register will be available during each lecture, where students can record their presence. - This attendance record will not be used for any other purpose. - To complete the in-class questions, students must bring a smartphone, laptop, or tablet to the lecture.

Programme

The syllabus for the course "Automata, Languages, and Computing" is as follows:
•    Elementary properties of languages: operations on languages, the Kleene operator, regular expressions, cardinality of languages.
•    Formal grammars: Chomsky grammars, productions, language recognition.
•    Regular languages: finite-state automata, relationships between automata and regular languages, the pumping lemma, closure properties of regular languages, regular expressions and regular languages, decidability and regular languages, the Myhill-Nerode theorem.
•    Context-free languages: non-deterministic pushdown automata, relationships between automata and context-free languages, the pumping lemma, closure and decidability properties, ambiguity.
•    Turing machines (TMs) and Turing computability: operation of TMs, multi-tape TMs, non-deterministic TMs, linearized descriptions of TMs, the universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages ​​and TMs.
•    Complexity theory: types of problems, decision problems, complexity and decision problems for languages, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the class NP, NP-completeness, examples of NP-complete problems. The class PSPACE. Complexity of problems in machine learning.

Prerequisiti

No special requirements.

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 examination consists of a written test containing 8 questions, with a duration of two hours. Students may choose to take advantage of the following additional assessment mechanism: - During lectures, exercises (in-class questions) will be presented via Moodle to be completed in real time. - This may occur during any lecture. - These questions will be graded on a yes/no basis. - Students who have successfully answered at least 80% of these in-class questions may—exclusively during the first exam session—complete a 6-question test. In this case, they will be allotted three-quarters of the standard time and will automatically receive full marks (7.5/30) for the two questions they are not required to answer. - Students who have successfully answered at least 40% of these in-class questions may—exclusively during the first exam session—complete a 7-question test. In this case, they will be allotted seven-eighths of the standard time and will automatically receive full marks (3.75/30) for the one question they are not required to answer. - Only students present in class are eligible to complete these in-class questions. - To track attendance, a digital register will be available during each lecture, where students can record their presence. - This attendance record will not be used for any other purpose. - To complete the in-class questions, students must bring a smartphone, laptop, or tablet to the lecture.

Programme

The syllabus for the course "Automata, Languages, and Computing" is as follows:
•    Elementary properties of languages: operations on languages, the Kleene operator, regular expressions, cardinality of languages.
•    Formal grammars: Chomsky grammars, productions, language recognition.
•    Regular languages: finite-state automata, relationships between automata and regular languages, the pumping lemma, closure properties of regular languages, regular expressions and regular languages, decidability and regular languages, the Myhill-Nerode theorem.
•    Context-free languages: non-deterministic pushdown automata, relationships between automata and context-free languages, the pumping lemma, closure and decidability properties, ambiguity.
•    Turing machines (TMs) and Turing computability: operation of TMs, multi-tape TMs, non-deterministic TMs, linearized descriptions of TMs, the universal TM, the halting problem, Turing computability, Rice's theorem, type-0 languages ​​and TMs.
•    Complexity theory: types of problems, decision problems, complexity and decision problems for languages, complexity classes, elementary relationships between complexity classes, reducibility, completeness, the class NP, NP-completeness, examples of NP-complete problems. The class PSPACE. Complexity of problems in machine learning.

Prerequisiti

No special requirements.

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 examination consists of a written test containing 8 questions, with a duration of two hours. Students may choose to take advantage of the following additional assessment mechanism: - During lectures, exercises (in-class questions) will be presented via Moodle to be completed in real time. - This may occur during any lecture. - These questions will be graded on a yes/no basis. - Students who have successfully answered at least 80% of these in-class questions may—exclusively during the first exam session—complete a 6-question test. In this case, they will be allotted three-quarters of the standard time and will automatically receive full marks (7.5/30) for the two questions they are not required to answer. - Students who have successfully answered at least 40% of these in-class questions may—exclusively during the first exam session—complete a 7-question test. In this case, they will be allotted seven-eighths of the standard time and will automatically receive full marks (3.75/30) for the one question they are not required to answer. - Only students present in class are eligible to complete these in-class questions. - To track attendance, a digital register will be available during each lecture, where students can record their presence. - This attendance record will not be used for any other purpose. - To complete the in-class questions, students must bring a smartphone, laptop, or tablet to the lecture.