Complementi di algoritmi e strutture dati

A.A. 2018/2019
Insegnamento per
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.

Struttura insegnamento e programma

Linea Milano
Edizione attiva
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
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
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.

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