Studiare
In questa sezione è possibile reperire le informazioni riguardanti l'organizzazione pratica del corso, lo svolgimento delle attività didattiche, le opportunità formative e i contatti utili durante tutto il percorso di studi, fino al conseguimento del titolo finale.
Piano Didattico
Queste informazioni sono destinate esclusivamente agli studenti e alle studentesse già iscritti a questo corso.Se sei un nuovo studente interessato all'immatricolazione, trovi le informazioni sul percorso di studi alla pagina del corso:
Laurea magistrale in Ingegneria e scienze informatiche - Immatricolazione dal 2025/2026Il piano didattico è l'elenco degli insegnamenti e delle altre attività formative che devono essere sostenute nel corso della propria carriera universitaria.
Selezionare il piano didattico in base all'anno accademico di iscrizione.
1° Anno
Insegnamenti | Crediti | TAF | SSD |
---|
2° Anno Attivato nell'A.A. 2013/2014
Insegnamenti | Crediti | TAF | SSD |
---|
Insegnamenti | Crediti | TAF | SSD |
---|
Insegnamenti | Crediti | TAF | SSD |
---|
Insegnamenti | Crediti | TAF | SSD |
---|
Tre insegnamenti a scelta tra i seguenti
Legenda | Tipo Attività Formativa (TAF)
TAF (Tipologia Attività Formativa) Tutti gli insegnamenti e le attività sono classificate in diversi tipi di attività formativa, indicati da una lettera.
Algoritmi - ALGORITMI (2012/2013)
Codice insegnamento
4S02709
Docente
Crediti
6
Lingua di erogazione
Italiano
Settore Scientifico Disciplinare (SSD)
ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
Periodo
II semestre dal 4 mar 2013 al 14 giu 2013.
Obiettivi formativi
Familiarizzare coi le principali tecniche e metodologie di analisi dei problemi per lo sviluppo di algoritmi efficienti
(ricorsione/induzione, programmazione dinamica).
Presentazione dei principali approcci per la gestione di problemi di ottimizzazione combinatorica NP-difficili (algoritmi approssimati, algoritmi ad enumerazione implicita e branch & bounds, fixed parameter tractability).
Prerequisiti Consigliati per Seguire con Profitto il Corso
------------------------
Per partecipare al corso in modo produttivo, lo studente e' importante si sia gia' posto questioni di efficienza relative a problemi affrontati o programmi scritti in un vissuto precedente, e sentirsi motivato al progetto di soluzioni efficienti.
PROGRAMMAZIONE: c/c++ e' il linguaggio di riferimento.
ALGORITMI: Lo studente dovrebbe avere ben chiari i seguenti concetti:
1. problemi e formulazioni, codifiche e istanze
2. tempo di calcolo e uso di memoria come funzione della lunghezza della codifica dell'istanza, analisi caso peggiore/caso medio/amortizzata, crescita e notazione asintotica
3. Structure dati base quali liste, stack, code, alberi, heap.
4. Ordinamento
5. Grafi: rappresentazione ed i seguenti algoritmi fondamentali
5.1 visite di grafi: BFS, DFS.
5.2 Componenti connesse e ordinamento topologico.
5.3 Alberi minimi di copertura. Algoritmi di Kruskal e di Prim.
5.4 Single-source shortest path: algoritmi di Dijkstra e di Bellman-Ford.
5.5 All-pairs shortest path: algoritmi di Floyd-Warshall e di Johnson.
5.6 Massimo flusso: algoritmo di Ford-Fulkerson.
Programma
Richiamo dei principali concetti inerenti ai problemi computazionali: descrizione, istanze, codifica, modelli precisi e modelli approssimati. Problemi computazioni di ottimizzazione. Esempi di problemi computazionali.
Richiamo dei principali concetti inerenti agli algoritmi: risorse computazionali, codifica dell'input, dimensione dell'input, definizione di tempo computazionale. Analisi caso peggiore e caso medio. Tempo di calcolo e ordini di grandezza: possibili insidie.
Tempi di calcolo e miglioramenti hardware: relazioni principali. Algoritmi efficienti e problemi trattabili.
Ricorsione ed induzione
-----------------------
esempi dell'approccio induttivo nella soluzione di problemi.
Paradigma divide et impera
--------------------------
Richiamo struttura ed analisi complessità. Esempi di applicazione: ordinamento,
prodotto tra due numeri, Prodotto fra due matrici.
Paradigma programmazione dinamica
---------------------------------
Una tecnica da principio controintuitiva ma che puo' essere fatta propria ed e' importante per efficacia e pervasivita'.
La vedremo dapprima come un'ulteriore dialetto della ricorsione
piu' qualche trucco (memoization) e cercheremo poi di concepire
direttamente soluzioni di programmazione dinamica.
Vedremo la programmazione dinamica in svariati contesti
e su strutture che le sono particolarmente congegnali
per inquadrarne svariati aspetti limite.
Paradigma greedy
----------------
Alcuni esempi.
Tecnica branch & bound
----------------------
Approccio ricorsivo ed enumerazione implicita.
Partizionamento in sottoproblemi e branching.
Lower bounds ed upper bounds.
Algoritmi di approssimazione
----------------------------
Algorimo r-approssimante. Problema r-approssimabile.
Studio dell'approssimabilità del problema Min Vertex Cover:
algoritmo greedy e 2-approssimazioni.
Approssimazioni per il Set Cover e varianti.
Christofides per il TSP metrico.
Un FPTAS per lo zaino.
Autore | Titolo | Casa editrice | Anno | ISBN | Note |
---|---|---|---|---|---|
T. Cormen, C. Leiserson, R. Rivest | Introduction to algorithms (Edizione 1) | MIT Press | 1990 | 0262031418 | |
T. Cormen, C. Leiserson, R. Rivest, C. Stein | Introduzione agli Algoritmi e Strutture Dati (Edizione 2) | McGraw-Hill | 2005 | 88-386-6251-7 |
Modalità d'esame
Parte dell'esame complessivo del corso qualifying in Algoritmi e Complessità (altro modulo: Complessità).
La prova di Algoritmi dura 5 ore e si svolge in aula computer:
Si richiede di progettare e codificare in c o c++ degli algoritmi
efficaci per 3 problemi assegnati.