Complementi di algoritmi e strutture dati

A.A. 2016/2017
Insegnamento per
6
Crediti massimi
48
Ore totali
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.

Struttura insegnamento e programma

Linea Milano
Edizione attiva
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 e modalità di esame
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 didattico e bibliografia
J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005.

Dispense fornite dal Docente
Periodo
Secondo semestre
Periodo
Secondo semestre
Modalità di valutazione
Esame
Giudizio di valutazione
voto verbalizzato in trentesimi
Docente/i
Ricevimento:
Mercoledì 9:30-12:30
via Celoria 18, stanza 7007