Università degli
Studi dell'Aquila
Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica
Via Vetoio,
Località Coppito,
Programma
del Corso PAS
Teoria degli Algoritmi e
della Computabilità
A.A. 2013/14 Prof. Guido Proietti
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().
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
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)
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).