Complementi di algoritmi e strutture dati
A.A. 2018/2019
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
Periodo: Secondo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Linea Milano
Responsabile
Periodo
Secondo semestre
Programma
1. String matching
Algoritmo di Rabin-Karp
Algoritmi basati su automi
Algoritmo di Knuth-Morris-Pratt
Gli alberi di suffissi
2. Cenni alla complessità computazionale
Riducibilità polinomiale tra problemi di decisione
Le classi P e NP
I problemi NP-completi
3. Algoritmi probabilistici
Algoritmi Montecarlo e Las Vegas
L'algoritmo di Karger per MinCut
Le classi di complessità probabilistiche
L'estrattore di von Neumann
Il problema del coupon collector
Reservoir sampling
Hashing universale
Conteggio approssimato
Proiezioni casuali
4. Programmazione lineare
Forma standard
Dualità
Il metodo dell'ellissoide
MaxFlow e MinCut
Il teorema Minimax di von Neumann
Algoritmo di Rabin-Karp
Algoritmi basati su automi
Algoritmo di Knuth-Morris-Pratt
Gli alberi di suffissi
2. Cenni alla complessità computazionale
Riducibilità polinomiale tra problemi di decisione
Le classi P e NP
I problemi NP-completi
3. Algoritmi probabilistici
Algoritmi Montecarlo e Las Vegas
L'algoritmo di Karger per MinCut
Le classi di complessità probabilistiche
L'estrattore di von Neumann
Il problema del coupon collector
Reservoir sampling
Hashing universale
Conteggio approssimato
Proiezioni casuali
4. Programmazione lineare
Forma standard
Dualità
Il metodo dell'ellissoide
MaxFlow e MinCut
Il teorema Minimax di von Neumann
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.
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.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduzione agli algoritmi e strutture dati 3/ed. McGraw-Hill Education, 2010.
Dispense fornite dal Docente
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduzione agli algoritmi e strutture dati 3/ed. McGraw-Hill Education, 2010.
Dispense fornite dal Docente
Docente/i