Algoritmi E Strutture Dati 2 2020/2021

Progettare algoritmi efficienti. Riepilogo delle tecniche più efficaci per progettare algoritmi efficienti: Greedy, Divide et Impera, Programmazione dinamica, Riduzioni.

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.

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: (1) i motori di ricerca e il problema del "ranking". La matematica dietro le scene: Algebra lineare e catene di Markov. (2) Cenni ad algoritmi on-line e algoritmi che "imparano". (3) "Cryptocurrencies": Le idee algoritmiche che hanno dato vita a Bitcoin e alla Blockchain. Gli ingredienti: reti Peer-to-Peer, funzioni hash crittografiche e firme digitali.