Unit COMPUTATIONAL MODELS AND ADVANCED ALGORITHMS
- Course
- Computer engineering and robotics
- Study-unit Code
- A002335
- Curriculum
- Data science
- Teacher
- Walter Didimo
- Teachers
-
- Walter Didimo
- Fabrizio Montecchiani (Codocenza)
- Hours
- 60 ore - Walter Didimo
- 12 ore (Codocenza) - Fabrizio Montecchiani
- CFU
- 9
- Course Regulation
- Coorte 2022
- Offered
- 2022/23
- Learning activities
- Caratterizzante
- Area
- Ingegneria informatica
- Academic discipline
- ING-INF/05
- Type of study-unit
- Obbligatorio (Required)
- Type of learning activities
- Attività formativa monodisciplinare
- Language of instruction
- Italian
- Contents
- Formal languages and grammars. Computational models. Complexity theory. Algorithmic techniques for NP-hard problems. Fundamentals of parameterized complexity. Applications.
- Reference texts
- Books: Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, "Linguaggi, Modelli, Complessità", Ed. Franco Angeli.
Slides: prepared by the teacher.
Further reading:
Rodney G. Downey, Michael R. Fellows: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer 2013, ISBN 978-1-4471-5558-4, pp. I-SSS, 3-707 - Educational objectives
- The aim of the course is to provide basic theoretical notions on formal languages and grammars, on their associated computational models, on the complexity analysis of algorithms and problems, and on the design of advanced algorithms for NP-hard problems, included basics on parametrized algorithms.
In particular, at the end of the course the student should have:
(a) knowledge of the basic theoretical concepts on programming languages and related formalisms for their description.
(b) knowledge of the different computational models to recognize the different types of formal languages.
(c) comprehension of the limits of current computational models and of the expressiveness of the related algorithmic techniques.
(d) ability of classifying theoretical and practical problems based on the difficulty to solve them algorithmically.
(e) ability of designing heuristics or exact algorithms to solve problems that are computationally hard. - Prerequisites
- [Knowledge and skills in logic and math]. Students should have good logic-math skills, which are usually acquired in the mathematics and geometry courses. Notions of discrete math might also facilitate the comprehension of some topics. The most common proof techniques in mathematics should be well understood, with particular emphasis on the proof techniques by induction and by contradiction.
[Knowledge and skills in computer science]. Students should have basic knowledge on algorithm design and analysis. They should also know the principle of common software programming paradigms, such as the imperative and the object-oriented ones, with special attention to Java, learned in the fundamental programming module. - Teaching methods
- The course is structured into two main parts:
(i) The first part, which covers about 85% of the total course, consists of lessons in the classroom. In each lesson the teacher devotes half of the time to illustrate new theoretical concepts, by projecting pre-defined slides. The remaining time of the lesson is devoted to making exercises on the explained theoretical notions, with the aim of facilitating and consolidating the student comprehension and of increasing his/her ability to use the new knowledge to solve theoretical and practical problems.
(ii) In the second part, which covers about 15% of the total course, the teacher illustrates some applications of the concepts studied in the first part. Most of these lessons are held in the software engineering laboratory, as they often involve the design and implementation of algorithms, under the supervision of the teacher. - Other information
- Learning verification modality
- [Aims of the assessment.] The assessment methods of this course aim to estimate the theoretical knowledge of the student and his/her ability to apply this knowledge to solve both theoretical and practical problems. The different types of tests are described hereunder. For each of them, details about its duration, structure, score, and specific aims are reported:
(i) Written test with theoretical and practical exercises
Duration: 120 minutes
Structure: theoretical and/or practical exercises
Score: 30/30 (all exercises have the same maximum score).
Aims: Assess the knowledge of the different theoretical notions provided by the course and the ability of applying these notions to solve problems concerned with formal languages, computational model design, analysis of algorithm, problem complexity, and design of advanced algorithms.
(ii) The correction of the written test is presented to the student during a brief interview; the student can comment and discuss the result with the teacher during this interview. - Extended program
- [Part I - Languages and grammars]. Alphabets and languages. Regular expressions. Chomsky's Grammars.
[Parte II - Computational models]. Regular languages: deterministic and non-deterministic finite state automata, properties of regular languages (pumping lemma, closure properties, decidable properties), Myhill-Nerode theorem. Context-free languages: deterministic and non-deterministic push-data automata, properties of context-free languages (pumping lemma, closure properties, decidable properties), ambiguous grammars and languages. Deterministic, non-deterministic, and multi tape Turing Machines. Composition of Turing Machines. The universal Turing Machine. Undecidable problems: the halting problem. Random Access Machines (RAM) with logarithmic and with uniform cost. Correlation between RAM and Turing Machines.
[Part III - Complexity theory]. Classes of problems. Time and space classes of problems. Main complexity classes. Karp-reducibility. NP-hard and NP-complete problems. Examples of NP-hardness proofs: CIRCUIT-SAT, SAT, 3CNF-SAT, CLIQUE, VERTEX-COVER.
[Part IV - Algorithmic techniques for NP-hard problems]. Further NP-Hard and NP-complete problems (geometric TSP, integer Knapsack). Heuristic algorithms. Approximation algorithms. Backtracking algorithms for searching problem. Branch and bound algorithms for optimization problems. Parameterized complexity, structural parameters, dynamic programming techniques, kernelization, W-hierarchy.
[Part V - Applications]. Use of regular expressions for text pattern definition: the POSIX notation. State finite automata for searching keywords in a textual document: implementation of a program that simulates non-deterministic finite state automata. Applications of context-free grammars: notes on parser architecture and types; tools for the automatic generation of a parser: using YAAC to automatically generate a parser starting from a formal grammar.