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


Programma del Corso PAS

Teoria degli Algoritmi e della Computabilità
A.A. 2013/14 Prof. Guido Proietti

 


27 Maggio 2014 (4 ore):

La dicotomia tra Informatica e Computer Science. Algoritmi e Problemi.

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

     Problemi indecidibili: il problema dell’arresto.

     Notazione asintotica: O().

Slides: Lezione 1.

 

3 Giugno 2014 (5 ore):

Le classi P, NP, ExpTime

Risolvere efficientemente un problema in P: il problema dell’ordinamento

     Selection Sort, Insertion Sort

     Lower bound del problema dell’ordinamento

Slides: Lezione 2.

 

12 Giugno 2014 (5 ore):

Un algoritmo di ricerca ottimo su sequenze ordinate: la ricerca binaria

Un algoritmo di ordinamento ottimo: il Merge Sort

Risolvere (efficientemente) un problema non in P: Algoritmi di approssimazione e il potere della randomizzazione

     La congettura P≠NP

     Algoritmo di 2-approssimazione per Vertex Cover.

     Protocollo di comunicazione randomizzato per stabilire la consistenza di due database (cenni)

Slides: Lezione 3.

Pdf: Protocollo random

 

Materiale didattico di formazione a distanza:

 

        Un altro modo di definire la classe NP: il concetto di certificato. La classe dei problemi NP-completi ed esempi di riduzioni Slides

        Un modo divertente di parlare di complessità computazionale: puzzle, matematica e algoritmi ricorsivi Slides

 

Appelli di esame

1.      Appello di Lunedì 7 Luglio 2014, ore 14:30 aula A1.3 (Orale Giovedì 10 Luglio 2014, ore 10:30 Studio Prof. Proietti Edificio Alan Turing (ex Blocco Zero)): (clicca qui per scaricare la prova corretta, e clicca qui per verificare l’esito).