Corso di Complessità Numerica

Corso di Laurea Specialistica in Ingegneria dell'Automazione
Corso di Laurea Specialistica in Ingegneria Informatica
Anno Accademico 2009/2010

Ultimo Aggiornamento 28/08/2013


Avvisi

A partire dal mese di Luglio 2012 l'esame consiste in una prova orale.
Gli studenti che devono sostenere l'esame possono concordare la data con il docente durante il ricevimento studenti.

A partire dal mese di Giugno 2011 l'esame può essere sostenuto solo da studenti iscritti all'ordinamento 509/99.

Organizzazione del Corso

Il Corso di Complessità Numerica ha il valore 3 crediti suddivisi secondo la seguente tipologia didattica:
3 crediti di lezioni teoriche (pari a 24 ore)

Finalità del Corso

Obiettivo del corso è quello di fornire agli studenti i concetti di base per la misura del costo computazionale degli algoritmi ed una valutazione circa l'efficienza di tali algoritmi e la complessità dei problemi. Il corso fornisce descrive inoltre la descrizione dei principali modelli di calcolo dell'Informatica Teorica.

Programma del Corso

Teoria della Calcolabilità. Introduzione storica al problema della calcolabilità. Problemi decidibili e non decidibili. Classificazione dei problemi: problemi di ricerca, di decisione e di enumerazione. Un esempio classico: il problema del commesso viaggiatore (TSP). Altri esempi di complessità di algoritmi: il calcolo del determinante di una matrice con la regola di Laplace e con il metodo di Gauss. Definzione di grafo ed esempi di algoritmi legati alla teoria dei grafi. Raggiungibilità dei grafi. L'idea intuitiva di algoritmo. Proprietà degli algoritmi deterministici. Modelli di calcolabilità. Le macchine di Turing. Configurazione delle macchine di Turing. Esempi di macchine di Turing. Costo computazionale in tempo e in spazio di una macchina di Turing. Le macchine di Turing multinastro. La tesi di Church. Macchine ad Accesso Casuale (RAM). Istruzioni base di una RAM. Esempi di RAM. Configurazione di una RAM. Costo computazionale di una RAM. Teoria della Complessità Computazionale. Il concetto di complessità dei problemi decidibili. Le risorse Tempo e Spazio. Classificazione degli algoritmi. Il criterio di efficienza polinomiale. Le classi di complessità. Definizione e proprietà principali di una classe di complessità. La classe P. LA classe EXP. Progresso tecnologico ed algoritmi esponenziali. Non determinismo e classe NP. Relazioni tra le classi P e NP. Problemi NP-hard.

Libro di testo:

A. Bernasconi, B. Codenotti, Introduzione alla complessità computazionale, Springer-Verlag 1998.
C.H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.

Materiale didattico

Dispense di Complessità Numerica (File in formato PDF):

Capitolo 1

Modalità dell'esame

L'esame consiste in una prova scritta ed in un colloquio orale.
È opportuno prenotarsi secondo una delle seguenti modalità:
Comunicando il proprio nome al docente al termine della lezione.
Mandando un e-mail al docente (politi@poliba.it) almeno tre-quattro giorni prima dell'esame scritto.

Tracce di esame

Tracce (File PDF)

Date degli appelli

Prossimo appello:

15 Settembre 2011 Aula C ore 8.30.