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. 2016/2017

InsegnamentiCreditiTAFSSD
6
B
INF/01
Altre attivita' formative (taf f)
4
F
-
InsegnamentiCreditiTAFSSD
12
B
ING-INF/05
12
B
INF/01
12
B
ING-INF/05
Attivato nell'A.A. 2016/2017
InsegnamentiCreditiTAFSSD
6
B
INF/01
Altre attivita' formative (taf f)
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 1 mar 2016 al 10 giu 2016.

Sede

VERONA

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


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

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