Università degli
Studi dell'Aquila
Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica
Via Vetoio,
Località Coppito,
Programma
del Corso TFA
Didattica dei Fondamenti
dell’Informatica II
A.A. 2012/13 Prof. Guido Proietti
Teoria della calcolabilità e principali classi di complessità
computazionale dei problemi
–
Problemi indecidibili
–
Notazione asintotica
–
Le classi P, NP, ExpTime
19 Aprile 2013 (4 ore):
Risolvere efficientemente un problema in P: il problema
dell’ordinamento
–
Selection Sort, Insertion
Sort
–
Lower bound del problema
dell’ordinamento
–
Un algoritmo ottimo: il Merge Sort
26
Aprile 2013 (4 ore):
Risolvere (efficientemente) un problema non in P: Algoritmi di
approssimazione e il potere della randomizzazione
–
La congettura P≠NP
–
Algoritmi di 2-approssimazione per Vertex
Cover e Travelling Salesman Problem
–
Protocollo di comunicazione randomizzato per stabilire la
consistenza di due database