Algoritmi - ALGORITMI (2011/2012)

Codice insegnamento
4S02709
Docente
Romeo Rizzi
crediti
6
Settore disciplinare
ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
Lingua di erogazione
Italiano
Sede
VERONA
Periodo
II semestre dal 1-mar-2012 al 15-giu-2012.
Pagina Web
http://profs.sci.univr.it/~rrizzi/classes/Algoritmi/temi/

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

Orario lezioni

II semestre
Giorno Ora Tipo Luogo Note
lunedì 9.30 - 11.30 lezione Aula I dal 5-mar-2012  al 15-giu-2012
lunedì 14.30 - 15.30 lezione Aula I  
martedì 11.30 - 13.30 lezione Aula I  
giovedì 10.30 - 13.30 lezione Aula I dal 1-mar-2012  al 2-mar-2012

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

Programma

Cerchiamoo di seguire un approccio diretto, basato su problemi da risolvere assieme.
Volendo tracciare un percorso ne viene il seguente:

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.