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, 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.
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: 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.
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.Type of evaluation
The exam consists of a written test of 3-4 hours. For students' convenience it is split into two parts. Evaluation in itinere: alternatively to the examination one can make use of the evaluation in itinere (intermediate tests). The ongoing evaluation is not mutually exclusive with respect to the traditional one, however, the student who presents himself for examination in a regular exam session implicitly refuses the vote of the evaluation in itinere. The result of the ongoing evaluation, if accepted by the student, will be recorded only in the first exam session. 4/5 intermediate tests are foreseen in all, distributed in the first semester. The program of each test includes the entire program from the first day of the lessons until the lesson immediately preceding the test. The final grade will be obtained by averaging the marks of the individual tests after having discarded the lowest grade (or not considering a test to which the student was absent). teacher profile teaching materials
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.
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 LM-32 PATRIGNANI MAURIZIO
Programme
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.
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.Type of evaluation
The exam consists of a written test of 3-4 hours. For students' convenience it is split into two parts. Evaluation in itinere: alternatively to the examination one can make use of the evaluation in itinere (intermediate tests). The ongoing evaluation is not mutually exclusive with respect to the traditional one, however, the student who presents himself for examination in a regular exam session implicitly refuses the vote of the evaluation in itinere. The result of the ongoing evaluation, if accepted by the student, will be recorded only in the first exam session. 4/5 intermediate tests are foreseen in all, distributed in the first semester. The program of each test includes the entire program from the first day of the lessons until the lesson immediately preceding the test. The final grade will be obtained by averaging the marks of the individual tests after having discarded the lowest grade (or not considering a test to which the student was absent). teacher profile teaching materials
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.
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 LM-32 PATRIGNANI MAURIZIO
Programme
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.
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.Type of evaluation
The exam consists of a written test of 3-4 hours. For students' convenience it is split into two parts. Evaluation in itinere: alternatively to the examination one can make use of the evaluation in itinere (intermediate tests). The ongoing evaluation is not mutually exclusive with respect to the traditional one, however, the student who presents himself for examination in a regular exam session implicitly refuses the vote of the evaluation in itinere. The result of the ongoing evaluation, if accepted by the student, will be recorded only in the first exam session. 4/5 intermediate tests are foreseen in all, distributed in the first semester. The program of each test includes the entire program from the first day of the lessons until the lesson immediately preceding the test. The final grade will be obtained by averaging the marks of the individual tests after having discarded the lowest grade (or not considering a test to which the student was absent). teacher profile teaching materials
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.
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 LM-32 PATRIGNANI MAURIZIO
Programme
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.
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.Type of evaluation
The exam consists of a written test of 3-4 hours. For students' convenience it is split into two parts. Evaluation in itinere: alternatively to the examination one can make use of the evaluation in itinere (intermediate tests). The ongoing evaluation is not mutually exclusive with respect to the traditional one, however, the student who presents himself for examination in a regular exam session implicitly refuses the vote of the evaluation in itinere. The result of the ongoing evaluation, if accepted by the student, will be recorded only in the first exam session. 4/5 intermediate tests are foreseen in all, distributed in the first semester. The program of each test includes the entire program from the first day of the lessons until the lesson immediately preceding the test. The final grade will be obtained by averaging the marks of the individual tests after having discarded the lowest grade (or not considering a test to which the student was absent).