Corso di Complessità Numerica
Corso di Laurea Specialistica in Ingegneria dell'Automazione
Corso di Laurea Specialistica in Ingegneria Informatica
Ultimo Aggiornamento 9/11/2006
Avvisi
L'appello del mese di Novembre 2006 è previsto il giorno:
23 novembre ore 14.30 Aula E (ING)
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.
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:
la soluzione di un sistema lineare con due diversi metodi.
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 di una macchina di Turing.
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 complementari. Un esempio: TSP Complementare. Le classi co-P e co-NP.
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.
È 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.
Utilizzando i fogli di prenotazione che si trovano al piano terra del
Dipartimento di Matematica dell'Università.
Tracce di esame
Tracce aggiornate a Settembre 2006 (File PDF)
Date degli appelli
7 Luglio 2006 ore 9.10 Aula 10 (ING.)
21 Luglio 2006 ore 9.10 Aula 10 (ING.)