|
Collegio Superiore dell'Università di Bologna, Anno accademico 2013-2014.
T5: Algoritmi, Complessità, Crittografia
Prima parte: Algoritmi e complessità (Simone Martini, 12 ore)
Ordinare: soluzioni naive e più sofisticate.
Modelli di costo degli algoritmi. Limiti inferiori di complessità ("Qual è il tempo più basso che devo impiegare per risolvere un certo problema?"). Limite inferiore per l'ordinamento. Algoritmi di ordinamento ottimali nel caso peggiore e nel caso medio.
Alcuni problemi su grafi: cammino minimo; flusso massimo; commesso viaggiatore.
Complessità astratta: riduzioni tra problemi e classi di complessità. Le classi PTIME e NPTIME. Problemi NP-completi.
Riconoscere un numero primo: soluzioni naive e più sofistificate. Algoritmo probabilistico.
Seconda parte: Crittografia (Ugo Dal Lago, 12 ore)
Crittografia classica: cifrari storici, crittanalisi, Principio di Kerkhoff.
Sicurezza perfetta: definire la sicurezza di un cifrario, il cifrario one-time-pad.
Teoremi limitativi: il Teorema di Shannon.
Pseudocasualità: algoritmi PPT, crittografia computationale, prove per riduzione, sicurezza computazionale contro
avversari passivi, generatori pseudocasuali, codifiche multiple e messaggi multipli, avversari attivi e funzioni
pseudocasuali.
Materiale didattico e trasparenze:
Esame:
Da definire
Prerequisiti:
Aritmetica elementare.
|