Università degli
Studi dell'Aquila
Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica
Via Vetoio,
Località Coppito,
Programma
del Corso TFA
Didattica e Fondamenti
degli Algoritmi e della Calcolabilità
A.A. 2014/15 Prof. Guido Proietti
La dicotomia tra Informatica e Computer Science. Algoritmi e
Problemi. Introduzione alla teoria della calcolabilità. Problemi indecidibili:
il problema dell’arresto.
31 Marzo 2015 (3 ore):
Altri problemi indecidibili: le equazioni diofantee. Modelli di
calcolo: macchina di Turing e RAM. La notazione
asintotica “big O”. Classi di complessità computazionale dei problemi: la
classe P.
1 Aprile 2015 (3 ore):
La classe EXPTIME. Il problema della SODDISFACIBILITÀ. La classe
NP. I problemi NP-completi. La congettura P¹NP.
8 Aprile 2015 (3 ore):
Risolvere efficientemente un problema numerico in P: il calcolo
dell’n-esimo numero della sequenza di Fibonacci. Algoritmi elementari.
14 Aprile 2015 (3 ore):
Algoritmo ricorsivo per il calcolo dell’n-esimo numero della
sequenza di Fibonacci. Risolvere efficientemente un problema su sequenze in P:
l’ordinamento di n numeri. Selection Sort.
15 Aprile 2015 (3 ore):
Risolvere efficientemente un problema su sequenze in P:
l’ordinamento di n numeri. Insertion Sort. La notazione asintotica “big Omega”. Upper e lower bound
di un problema computazionale.
21 Aprile 2015 (3 ore):
Risolvere in modo ottimo il problema dell’ordinamento di n numeri.
Lower bound del problema dell’ordinamento. Un
algoritmo ottimo: il Merge Sort
22 Aprile 2015 (3 ore):
Risolvere (efficientemente) un problema non in P: Algoritmi di
approssimazione. Il problema dei cammini minimi su grafi: algoritmo di Floyd e Warshall. Algoritmo di 2-approssimazione per il Travelling Salesman Problem
metrico.