Studying at the University of Verona

Here you can find information on the organisational aspects of the Programme, lecture timetables, learning activities and useful contact details for your time at the University, from enrolment to graduation.

This information is intended exclusively for students already enrolled in this course.
If you are a new student interested in enrolling, you can find information about the course of study on the course page:

Laurea magistrale in Ingegneria e scienze informatiche - Enrollment from 2025/2026

The Study Plan includes all modules, teaching and learning activities that each student will need to undertake during their time at the University.
Please select your Study Plan based on your enrollment year.

CURRICULUM TIPO:

1° Year 

ModulesCreditsTAFSSD
12
B
ING-INF/05
6
B
ING-INF/05
6
B
ING-INF/05
12
B
ING-INF/05
6
B
ING-INF/05

2° Year   activated in the A.Y. 2010/2011

ModulesCreditsTAFSSD
6
B
INF/01
Altre attivita' formative
4
F
-
ModulesCreditsTAFSSD
12
B
ING-INF/05
6
B
ING-INF/05
6
B
ING-INF/05
12
B
ING-INF/05
6
B
ING-INF/05
activated in the A.Y. 2010/2011
ModulesCreditsTAFSSD
6
B
INF/01
Altre attivita' formative
4
F
-
Modules Credits TAF SSD
Between the years: 1°- 2°

Legend | Type of training activity (TTA)

TAF (Type of Educational Activity) All courses and activities are classified into different types of educational activities, indicated by a letter.




S Placements in companies, public or private institutions and professional associations

Teaching code

4S02709

Credits

12

Coordinator

Roberto Posenato

Language

Italian

Also offered in courses:

The teaching is organized as follows:

ALGORITMI AVANZATI

Credits

4

Period

1st Semester

Academic staff

Roberto Posenato

COMPLESSITÀ

Credits

4

Period

1st Semester

Academic staff

Roberto Posenato

INTELLIGENZA ARTIFICIALE

Credits

4

Period

1st Semester

Learning outcomes

Module: ALGORITMI AVANZATI
-------
The goal of this course is to introduce some advanced paradigms for algorithms development and analysis in order to determine good approximate solutions for hard optimization problems.

Module: COMPLESSITÀ
-------
The goal of this module is to introduce students to computational complexity theory in general, to the NP-completeness theory in detail and to computational analysis of problems with respect to their approximability.

Module: INTELLIGENZA ARTIFICIALE
-------
The class presents the main techniques for problem solving, based on the central paradigm of symbolic representation. The objective is to provide the students with the ability to design, apply and evaluate algorithms for difficult problems, meaning that their mechanical solution captures aspects of artificial intelligence or computational rationality.

Program

Module: ALGORITMI AVANZATI
-------
Main concepts recall about computational problems: definition, instances, encoding, precise and approximate models. Optimization computational problem.
Main concepts recall about algorithms: computational resources, input encoding, input size/cost, computational time. Worst and average analysis. Computational time and growth order.
Computational time vs. hardware improvements: main relations. Efficient algorithms and tractable problems.

Divide et impera paradigm
Definition and application to some problems.

Greedy paradigm
Definition and application to some problems. Matroids and greedy algorithms.

Backtracking technique
Definition and application to some problems.

Branch & Bound technique
Definition and application to some problems.

Dynamic programming paradigm
Definition and application to some problems.
Memoization and Dynamic programming.

Local search technique
Definition and application to some problems.

Approximations algorithms
Definition and some application examples.
Simulated annealing.
Tabu search.

Probabilistic algorithms
Definition and few application examples.
Numerical probabilistic algorithms, Monte Carlo algorithms and Las Vegas algorithms. Examples: Buffon's needle, Pattern Matching and Universal hashing.


Module: COMPLESSITÀ
-------
Introduction.
Computational model concept, computational resource, efficient algorithm and tractable problem.

Computational models
Turing Machine (MdT). MdT extension: multi-tape MdT (k-MdT). MdT and languages: the difference between accepting and deciding a language.
Random Access Machine (RAM) computational model. Computation time considering uniform cost criterion or logarithmic cost one.

Time Complexity
Computational class TIME(). Theorem about polynomial relation between k-MdT computations and MdT ones (sketch of proof).
Theorem about simulation cost of a MdT by a RAM.
Theorem about simulation cost of a RAM program by a MdT.
Sequential Computation Thesis and its consequences.
Linear Speed-up Theorem and its consequences.
P Computational Class.
Problems in P: PATH, MAX FLOW, PERFECT MATCHING.
Extension of MdT: non-deterministic MdT (NMdT).
Time resource for k-NMdT. NTIME() computational class. Relation between NMdT and MdT.
NP Computational Class.
An alternative characterization of NP: polynomial verifiers.
EXP Computation Class.

Space Complexity.
Space complexity concept. MdT with I/O. Computational Classes: SPACE() and NSPACE().
Compression Theorem.
Computational Classes: L and NL.
Example of problems: PALINDROME ∈ L and PATH ∈ NL.
Theorems about relations between space and time for a MdT with I/O. Relations between complexity classes.
Proper function concept and example of proper functions.
Borodin Gap Theorem.
Reachability method.
Theorem about space-time classes: NTIME(f(n)) ⊆ SPACE(f(n)), NSPACE(f(n)) ⊆ TIME(k(log n+f(n))).
Universal MdT. The Hf set. Lemma 1 and 2 for time hierarchy theorem.
Time Hierarchy Theorem: strict and no-strict versions. P ⊂ EXP Corollary.
Space Hierarchy Theorem. L ⊂ PSPACE Corollary. Savitch Theorem. SPACE(f(n))=SPACE(f(n)^2) corollary. PSPACE=NPSPACE Corollary.

Reductions and completeness.
Reduction concept and logarithmic space reduction.
HAMILTON PATH ≤log SAT, PATH ≤log CIRCUIT VALUE, CIRCUIT SAT ≤log SAT.
Language completeness concept.
Closure concept with respect to reduction. Class reduction of L, NL, P, NP, PSPACE and EXP.
Computation Table concept.
Theorem about P-completeness of CIRCUIT VALUE problem.
Cook Theorem: an alternative proof.
Gadget concept and completeness proof of: INDEPENDENT SET, CLIQUE, VERTEX COVER and others.


Module: INTELLIGENZA ARTIFICIALE
-------
Problem solving as search in a state space; un-informed search procedures; informed search procedures and heuristic search. Constraint problem solving. Knowledge representation: use of propositional logic and first-order logic; normal forms; equality. Algorithms for satisfiability (SAT). Theorem proving: resolution and rewriting.

Bibliography

Reference texts
Author Title Publishing house Year ISBN Notes
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani Algorithms (Edizione 1) McGraw-Hill Higher Education 2007 978-0-07-352340-8 Testo secondario
Alan Bertossi Algoritmi e strutture dati (Edizione 1) UTET 2000 88-7750-611-3 Testo secondario
T. Cormen, C. Leiserson, R. Rivest, C. Stein Introduzione agli Algoritmi e Strutture Dati (Edizione 2) McGraw-Hill 2005 88-386-6251-7 Testo consigliato per la prima parte del corso
Steven S. Skiena The Algorithm Design Manual (Edizione 2) Springer 2008 9781848000698 Testo secondario per il corso ma ottimo come manuale di riferimento per un'ampia classe di problemi.
Christos H. Papadimitriou Computational complexity Addison Wesley 1994 0201530821 testo principale
Stuart Russell, Peter Norvig Artificial Intelligence: A Modern Approach (Edizione 2) Prentice Hall 2003 0137903952 Testo adottato
Judea Pearl Heuristics: Intelligent search strategies for computer problem solving (Edizione 1) Addison Wesley 1985 0-201-0559 Testo complementare
Stuart Russell, Peter Norvig Intelligenza artificiale: Un approccio moderno (Edizione 2) Pearson Education Italia 2005 88-7192-22 Traduzione italiana del testo adottato
Chin-Liang Chang, Richard Char-Tung Lee Symbolic Logic and Mechanical Theorem Proving (Edizione 1) Academic Press 1973 0121703509 Testo complementare

Examination Methods

Module: ALGORITMI AVANZATI
-------
The examination consists of a written test (at the same time as the other two module tests) that lasts 1 hour (all tests together last 3 hours). The grade in this module is worth 1/3 of the grade in the Algorithms examination.


Module: COMPLESSITÀ
-------
The examination consists of a written test (at the same time as the other two module tests) that lasts 1 hour (all tests together last 3 hours). The grade in this module is worth 1/3 of the grade in the Algorithms examination.


Module: INTELLIGENZA ARTIFICIALE
-------
The grade in Artificial Intelligence is worth 1/3 of the grade in the Algorithms exam, and it is determined by the grade in a written test.

Students with disabilities or specific learning disorders (SLD), who intend to request the adaptation of the exam, must follow the instructions given HERE