Calolabilia' e Complessita'

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:
red bullet Lunedi' ore 14:00 - 16:00. Aula E3
red bullet 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:

red bullet Prima Lezione: Breve introduzione al corso
red bullet Seconda Lezione: Automi e PDA (versione aggiornata al 26/10)
red bullet Terza Lezione: Introduzione alle Macchine di Turing (versione aggiornata al 26/10)
red bullet Quarta Lezione: Macchine di Turing multinastro (lezione parziale)
             green bullet link esterno
red bullet Quinta Lezione: Macchine di Turing nondeterministiche
red bullet Sesta Lezione: Macchine di Turing Universali
red bullet Settima Lezione: Problemi decidibili e indecidibili
red bullet Ottava Lezione: Riducibilita' e problemi indecidibili.
red bullet Nona Lezione: Linear Bounded Automata e Post Correspondence Problem.
red bullet Decima Lezione: Mapping Reducibility.
red bullet Undicesima Lezione: Decidibilita' delle teorie logiche (richiede approfondimenti).
red bullet Dodicesima Lezione: Misurazione della Complessita' e introduzione alla classe P (incompleta).
red bullet Tredicesima Lezione: La classe dei problemi NP (nuova versione 23/11).
red bullet Quattordicesima Lezione: Problemi NP-completi 1.
red bullet Quindicesima Lezione: Problemi NP-completi 2.
red bullet Sedicesima Lezione: Problemi NP-completi 3.
red bullet Diciassettesima lezione : Esercitazione su Problemi NP-completi.
red bullet Diciottesima lezione: Space Complexity e Savitch's Theorem.
red bullet Diciannovesima lezione: PSPACE-Complete.
red bullet Ventesima lezione: La classe NL.
red bullet Ventunesima lezione: La classe APTIME e APSPACE.
red bullet Ventiduesima lezione: Teoria dei Giochi (link esterno).
red bullet Ventitreesima lezione: Esercitazione.

Comunicazioni:

Prossime prove d'esame 2014: 31 gennaio, 17 febbraio (da confermare) e 7 marzo. E' necessario prenotarsi entro 5 giorni dalla data d'esame, anche tramite mail al docente.

Tesine per l'anno accademico 2013/14.
Di seguito vengono riportati alcuni articoli su giochi di parita'. In base alle difficoltà, alcuni articoli possono essere utilizzati in gruppi di piu' studenti come indicato.
E' possibile discutere le tesine secondo il seguente calendario:

  • Infinite games on finitely coloured graphs with applications to automata on infinite trees (tre studenti).
  • A Deterministic Subexponential Algorithm for Solving Parity Games (singolo studente)
  • Small Progress Measures for Solving Parity Games (singolo studente)
  • The PGSolver Collection of Parity Game Solvers (due studenti)
  • On Promptness in Parity Games (singolo studente + due per eventuale implementazione in PGSolver)
  • Energy parity games (singolo studente)
  • Solving Parity Games in Big Steps (singolo studente)
  • Solving Parity Games on the GPU (singolo studente). materiale aggiuntivo
  • On the Power of Imperfect Information (singolo studente)
  • Solving Parity Games by a Reduction to SAT (singolo studente)
  • Mean-Payoff Parity Games (singolo studente)
  • Alternating Tree Automata and Parity Games (singolo studente)
  • The Complexity of Partial-Observation Parity Games (singolo studente)
  • Articolo aggiuntivo per tesine: Playing Games with Algorithms.