Descrizione del corso
Il corso si propone di fornire le conoscenze di base della teoria della calcolabilita' e della complessita'.
La teoria della calcolabilita' si preoccupa di stabilire quali problemi sono effettivamente risolvibili da un calcolatore.
La teoria della complessita' invece, ha lo scopo di studiare e classificare i problemi rispetto alle risorse (di tempo, di spazio, ecc.) necessari per poterli risolvere.
Il corso e' rivolto a studenti del corso di Laurea Magistrale in Informatica e pertanto e' richiesta una buona conoscenza da parte degli studenti di alcuni argomenti fondamentali trattati nella laurea triennale in Informatica tra cui gli algoritmi di ordinamento e quelli su grafi, le tecniche di analisi della complessita' degli algoritmi, le principali tecniche di progettazione di algoritmi e conoscenze di base sui principali modelli computazionali teorici.
Il corso e' composto da 4 parti principali. Le prime 3 parti sono di 6 CFU e rappresentano il programma per gli studenti del vecchio ordinamento. L'ultima parte e' di 3 CFU e unitamente alla prima parte rappresentano il programma completo degli studenti del nuovo ordinamento.
Nella prima parte, sara' presentata un richiamo ai modelli computazionali teorici fondamentali come automi, macchine pushdown, macchine di turing, ecc. Per le macchine di Turing saranno considerati vari modelli tra cui la versione a piu' nastri e quella nondeterministica.
Nella seconda parte si introdurranno i concetti fondamentali della teoria della calcolabilita' e sara' presentato formalmente il concetto di indecidibilita'. In questa parte si studiera' la tesi di Church-Turing e si procedera' anche a collocarla storicamente. Tutto questo servira' ad introdurre metodi formali per giustificare l'esistenza di problemi privi di soluzioni algoritmiche e dunque non risolvibili da un calcolatore.
Nella terza parte si introdurranno i concetti di base della teoria della complessita' e saranno presentate alcune classi di complessita' fondamentali come la classe polinomiale deterministica P, e quella nondeterministica NP, la classe di spazio polinomiale deterministica PSPACE e quella nondeterministica NPSPACE. Inoltre, sara' presentato il concetto di riduzione e quello di completezza. Il concetto di riduzione permettera' di stabilire tra l'altro che un problema non puo' essere piu' semplice di un altro, memtre quello di completezza permettera' di stabilire un concetto di appartenenza "forte" ad una certa classe. In questa parte del corso si dimostrera' formalmente l'appartenenza di alcuni problemi fondamentali alle classi studiate, come per esempio il teorema di Cook-Levin che mostra che il problema di stabilire se una formula booleana e' soddisfacibile o meno e' NP-completo. Si mostreranno anche alcuni risultati sull'equivalenza di alcune classi di complessita' come il teroma di Savitch che mostra che PSAPCE e' uguale a NPSPACE. Inotre, si mostreranno alcuni problemi aperti fondamentali dell'informatica come la questione P diverso da NP.
Nella quarta parte, infine, saranno investigati problemi specifici su logiche temporali e automi su oggetti infiniti. Laddove il problema sara' dimostrato essere decidibile, si mostreranno opportuni algoritmi e se ne discutera' la complessita'.

Calendario delle lezioni anno accademico 2010/2011
Primo semestre:
Lunedi' ore 14:00 - 16:00. Aula E3
Mercoledi' ore 11:00 - 13:00 (**NEW**). Aula E4
Secondo semestre: Due ore a settimana, per 12 settimane. Orario e giorno ancora da stabilire

Orario di Ricevimento:
Si ricevono gli studenti su appuntamento - studio 0f29.

Materiale didattico: