UniBo's logo
home
contact
teaching
publications
talks
Università di Bologna
Dipartimento di Informatica — Scienza e Ingegneria
 
Simone Martini
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.