Complementi di algoritmi e strutture dati

A.A. 2016/2017
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Italiano
Obiettivi formativi
L'analisi degli algoritmi è una parte importante dell'informatica. Questo corso introduce gli studenti alle tecniche avanzate per il progetto e l'analisi di algoritmi, esplorando una varietà di applicazioni. In particolare, ci focalizzeremo su quattro temi fondamentali: complessità computazionale, algoritmi su stringhe, programmazione lineare, algoritmi probabilistici.
Risultati apprendimento attesi
Non definiti
Programma e organizzazione didattica

Linea Milano

Periodo
Secondo semestre
Programma
Algoritmi su stringhe
Algoritmo di Knuth-Morris-Pratt
I suffix tree

Cenni alla complessità computazionale
Le classi P e NP
Riducibilità polinomiale tra problemi di decisione
I problemi NP-completi
Le classi di complessità probabilistiche

Programmazione lineare
Forma standard
Dualità
Il metodo dell'ellissoide
MaxFlow e MinCut
Il teorema Minimax di von Neumann

Algoritmi probabilistici
Il problema del coupon collector
L'algoritmo di Karger per MinCut
L'algoritmo di Goemans e Williamson per MaxCut
Hashing e conteggio approssimato
Locality Sensitive Hashing
Propedeuticità
Algoritmi e Strutture Dati, Statistica e Analisi dei Dati
Prerequisiti
Sono prerequisiti consigliati: Matematica del continuo, matematica del discreto, Statistica e analisi dei dati, algoritmi e strutture dati.
L'esame consiste in una discussione orale esclusivamente sugli argomenti trattati nel corso.
Metodi didattici
Modalità di esame: Orale; Modalità di frequenza: Fortemente consigliata; Modalità di erogazione: Tradizionale.
Materiale di riferimento
J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005.

Dispense fornite dal Docente
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente/i
Ricevimento:
Mercoledì 9:30-12:30
via Celoria 18, stanza 7007