Course Syllabus
Obiettivi
Gli studenti acquisiranno la conoscenza delle principali tecniche di progetto e analisi degli algoritmi e la capacità di individuare le più idonee tecniche algoritmiche per la soluzione efficiente di specifici problemi computazionali.
Accenni ai problemi Np-Completi e complessità di approssimazione.
Contenuti sintetici
L'insegnamento intende introdurre le principali tecniche algoritmiche (programmazione dinamica, greedy), con particolare attenzione agli aspetti di efficienza degli algoritmi, con i relativi strumenti di analisi. Verranno illustrati i principali algoritmi per la ricerca su grafi, la ricerca di cammini minimi, la costruzione di alberi di copertura minimi.
Programma esteso
PARTE 1:
1. Strumenti matematici
Crescita delle funzioni, notazioni asintotiche
Calcolo del tempo di esecuzione per algoritmi iterativi
Richiami sulla ricorsione: calcolo del fattoriale
Ricorrenze e tempi di calcolo di algoritmi ricorsivi
Ricerca dicotomica, calcolo altezza di un albero binario
2. Tecniche algoritmiche: Programmazione Dinamica (DP)
Esempi introduttivi
Caratteristiche principali - Ricorsione
Implementazione con matrici
3. Tecniche algoritmiche: il metodo Greedy (goloso)
Esempi introduttivi
Matroidi
Teorema di Rado
PARTE 2:
4. Algoritmi su grafi
Rappresentazione dei grafi.
Visita in ampiezza dei grafi
Visita in profondità dei grafi
5. Alberi di copertura minimi
Algoritmo di Kruskal
Algoritmo di Prim
5. Problemi di cammino minimo
Algoritmo di Dijkstra
Algoritmo di Bellman-Ford
Algoritmo di Floyd-Warshall
6. Problemi di flusso massimo
Algoritmo di Ford-Fulkerson
7. NP completezza e riducibilità. Approssimazione.
Prerequisiti
Nozioni base di programmazione, algoritmi e strutture dati
Modalità didattica
Lezioni, esercitazioni e esercitazioni laboratoriali in aula. La lingua del corso è l'italiano.
Materiale didattico
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture dati, Ed. Mc. Graw Hill
Materiale integrativo (lucidi ed esercizi) disponibili sul sito e-learning.
Periodo di erogazione dell'insegnamento
Primo semestre
Modalità di verifica del profitto e valutazione
Prova scritta: la valutazione massima della prova scritta è 30/30. Tale prova consiste di due sezioni, una per ciascuna parte del corso e su argomenti ad essa relativi. Esse consistono di:
- esercizi relativi ai contenuti del corso
- domande aperte relative alle nozioni teoriche presentate a lezione
Possono essere assegnati fino a 2 punti aggiuntivi in caso di esercizi svolti particolarmente bene.
Prove parziali:
La prova scritta puo' essere sostituita da due prove parziali, che si tengono a meta' e fine corso.
Ogni prova parziale verte sugli argomenti trattati nella corrispondente parte del corso. Consiste di esercizi e domande aperte raltive alle nozioni teoriche presentate a lezione.
Ogni prova parziale ha valutazione massima 15/15: il voto finale si ottiene sommando i voti delle due prove parziali. Possono essere assegnati fino a 2 punti aggiuntivi (totali per le due prove) in caso di esercizi svolti particolarmente bene.
Orario di ricevimento
su appuntamento
Aims
Students will acquire knowledge of the main techniques for the design and analysis of algorithms and the ability to identify the most appropriate algorithmic techniques to efficiently solve specific computational problems.
We introduce the NP-complexity and approximation algorithms.
Contents
The course will introduce the main algorithmic techniques (dynamic programming, greedy), with particular attention to the efficiency of the algorithms, with the main analysis methods. The main algorithms for graph search, minimum spanning trees construction, Shortest path problems will be presented.
Detailed program
PART 1:
1. Mathematical tools
- Growth of functions, asymptotic notations
- Execution time of iterative algorithms
- Recurrence equations and Execution times of recursive algorithms
- Dichotomic Search, height of a binary tree
2. Algorithmic Techniques: Dynamic Programming (DP)
- Introductory examples
- Main features - Recursion
- Implementation with matrices
3. Algorithmic Techniques: Greedy method
- Introductory examples
- Matroids
- Rado Theorem
PART 2:
4. Graph Algorithms
- Representations of graphs.
- Breadth first visit of graphs
- Depth first visit of graphs
5. Minimum spanning trees
- Kruskal algorithm
- Prim algorithm
5. Shortest path problems
- Dijkstra Algorithm
- Bellman-Ford Algorithm
- Floyd-Warshall Algorithm
6. Maximum flow problems
- Ford-Fulkerson Algorithm
7. NP completeness and reducibility. Approximation.
Prerequisites
Basic notions of programming, algorithms and data structures
Teaching form
Lectures, practice exercises, and classroom laboratory exercises. The course is in Italian.
Textbook and teaching resource
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture dati, Ed. Mc. Graw Hill
Further slides and exercises are available through the e-learning website.
Semester
First semester
Assessment method
Written examination: the total score is 30/30. The exam consists of two sections, each of them regarding one of the two parts of the course. They consitst of
- exercises related to the main topics
- open questions on the theoretical aspects of the topics explained in the course
2 additional points may be assigned if the exercises are perfectly solved
Partial written examinations:
The written exam can be substituted by two partial written examinations in the middle and at the end of the course.
Each partial written examination is about the topics of the corresponding part of the course and it consists of exercises to the main topics and open questions on the related theoretical aspects.
Each partial written examination has a maximum score of 15/15: the final score of the exam is the sum of the two partial scores. 2 additional points may be assigned if the exercises are perfectly solved
Office hours
By appointment