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. 2016/2017
Insegnamenti | Crediti | TAF | SSD |
---|
Insegnamenti | Crediti | TAF | SSD |
---|
Insegnamenti | Crediti | TAF | SSD |
---|
Insegnamenti | Crediti | TAF | SSD |
---|
Due insegnamenti a scelta
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 (2015/2016)
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 1 mar 2016 al 10 giu 2016.
Sede
VERONA
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).
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.
Modalità d'esame
Il voto finale per Algoritmi e Complessita' e la media arrotondata per eccesso del voto di Algoritmi e di quello di Complessita', dove un 30+lode viene conteggiato come un 33.
Non serve dare i due esami entro una stessa sessione: entrambi i voti mantengono validita' sul corso dell'anno e, per Algoritmi, si tiene il massimo dei voti conseguiti.
La prova di Algoritmi dura 5 ore e si svolge in aula computer:
lo studente progetta e codifica (in c o c++) degli algoritmi
il piu' posibile efficaci per 3 problemi assegnati.
Trovate i testi degli scritti precedenti e relative correzioni alla pagina del corso:
http://profs.sci.univr.it/~rrizzi/classes/Algoritmi/index.html
A seconda dell'edizione del corso e dell'accordo con gli studenti e' anche possibile raccogliere dei punti aggiuntivi da sommarsi al voto dell'esame. Questi possono essere ottenuti con partecipazione attiva e attivita' di servizio al corso o attraverso dei progetti inseriti nel corso.
Rimandiamo alla pagina del corso per informazioni aggiornate in merito ai progetti:
http://profs.sci.univr.it/~rrizzi/classes/Algoritmi/index.html