Algoritmi E Strutture Dati 2 2016/2017

1. Progettare algoritmi efficienti. Riepilogo delle tecniche più efficaci per progettare algoritmi efficienti: Greedy, Divide et Impera, Programmazione dinamica, Riduzioni. 2. Problemi computazionalmente difficili. La teoria dell'NP-completezza da un punto di vista algoritmico. Affrontare i problemi computazionalmente difficili: ricerca esaustiva, algoritmi approssimanti, euristiche. I problemi computazionalmente difficili come risorsa: il protocollo RSA e i fondamenti della crittografia a chiave pubblica. La matematica dietro le scene: Teoria dei numeri. 3. Algoritmi probabilistici. Il ruolo della "randomness" negli algoritmi: (1) progettare algoritmi più semplici; (2) progettare algoritmi più efficienti; (3) rompere la simmetria. Le tecniche per analizzare gli algoritmi probabilistici. Alcune semplici idee algoritmiche che hanno avuto un impatto significativo: i motori di ricerca e il problema del "ranking". La matematica dietro le scene: Algebra lineare e catene di Markov. Cenni ad algoritmi on-line e algoritmi che "imparano".