ATTENZIONE Il seguente programma descrive i contenuti del corso
solo a grandi linee. Si consiglia di consultare
il diario delle lezioni
per avere una precisa indicazione degli argomenti trattati
NP-Completezza. Tecniche di riduzione. Classi di complessità
Algoritmi e schemi di approssimazione per problemi intrattabili.
Algoritmi di teoria dei numeri e applicazioni crittografiche
dell'intrattabilità: massimo comun divisore, aritmetica modulare,
test di primalità di Miller-Rabin e criptosistema RSA.
Introduzione agli algoritmi randomizzati: tecniche principali e applicazioni
