Università degli Studi dell'Aquila
Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica
Via Vetoio, Località Coppito, 67010 L'AQUILA


Programma del Corso TFA

Didattica dei Fondamenti dell’Informatica II
A.A. 2012/13 Prof. Guido Proietti

 


12 Aprile 2013 (4 ore):

Teoria della calcolabilità e principali classi di complessità computazionale dei problemi

     Problemi indecidibili

     Notazione asintotica

     Le classi P, NP, ExpTime

Slides: Lezione 1.

 

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

Slides: Lezione 2.

 

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

Slides: Lezione 3.

Pdf: Protocollo random