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.

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/2026

Il 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.

CURRICULUM TIPO:

1° Anno 

InsegnamentiCreditiTAFSSD
12
B
ING-INF/05
12
B
INF/01
12
B
ING-INF/05

2° Anno   Attivato nell'A.A. 2013/2014

InsegnamentiCreditiTAFSSD
6
B
INF/01
Altre attivita' formative
4
F
-
InsegnamentiCreditiTAFSSD
12
B
ING-INF/05
12
B
INF/01
12
B
ING-INF/05
Attivato nell'A.A. 2013/2014
InsegnamentiCreditiTAFSSD
6
B
INF/01
Altre attivita' formative
4
F
-
Insegnamenti Crediti TAF SSD

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.




S Stage e tirocini presso imprese, enti pubblici o privati, ordini professionali

Codice insegnamento

4S02709

Docente

Romeo Rizzi

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.

Per visualizzare la struttura dell’insegnamento a cui questo modulo appartiene, consultare:  organizzazione dell'insegnamento

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.

Testi di riferimento
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.

Le/gli studentesse/studenti con disabilità o disturbi specifici di apprendimento (DSA), che intendano richiedere l'adattamento della prova d'esame, devono seguire le indicazioni riportate QUI