Informatica teorica

A.A. 2015/2016
Insegnamento per
6
Crediti massimi
48
Ore totali
Lingua
Italiano
Obiettivi formativi
L'insegnamento introduce le nozioni fondamentali della teoria della calcolabilità e della complessità. Viene affrontato il concetto di problema risolvibile per via algoritmica e di problema che non ammette algoritmi di risoluzione. Vengono poi presentate la classificazione e la suddivisione dei problemi in classi di complessità, definite in termini di limiti alla quantità di risorse a disposizione.

Struttura insegnamento e programma

Edizione attiva
Responsabile
Lezioni: 48 ore
Programma
Teoria della calcolabilità
· Prerequisiti matematici
· Funzione coppia
· Linguaggi di programmazione RAM e while
· Sintassi e semantica operazionale
· Compilatori
· Aritmetizzazione di programmi
· Interprete e funzione universale
· Eliminazione del "goto"
· Funzioni ricorsive parziali
· Tesi di Church
· Esistenza di problemi non decidibili
· Passaggio automatico di parametri
· Sistemi di programmazione accettabili
· Teorema di ricorsione
· Insiemi ricorsivi e ricorsivamente numerabili
· Proprietà di chiusura
· Teorema di Rice
Teoria della complessità
· Introduzione alla complessità sequenziale
· Prerequisiti matematici: la notazione "O grande"
· Macchine di Turing deterministiche
· Risorse computazionali: tempo e spazio
· Classi di complessità in tempo e spazio
· Le classi L, P, PSPACE
· Tesi di Church ristretta
· Macchine di Turing nondeterministiche: tempo e spazio
· Le classi NL, NP, NPSPACE
· Teorema di Savitch
· Riduzioni tra problemi e completezza
· Problemi NP-completi, P-completi, PSPACE-completi
· Teorema di Cook ed esempi di riduzione
Informazioni sul programma
Il corso si compone di lezioni frontali in cui vengono presentati i principi della teoria della calcolabilità e della complessità computazionale
Propedeuticità
Nessuna
Prerequisiti e modalità di esame
L'esame consiste in una discussione orale obbligatoria che copre il più completamente
possibile tutti gli argomenti trattati al corso di Informatica Teorica. Verranno proposte
domande su entrambe le parti che caratterizzano il corso: teoria della calcolabilità e
teoria della complessità. Le domande saranno volte ad accertare la padronanza, da
parte dello studente, sia dei concetti base sia della capacità di formalizzare gli stessi
nella maniera più precisa possibile. Verranno anche proposte domande in cui si chiederà
un contributo "originale" da parte dello studente, al fine di cogliere una certa maturità
scientifica. Durata della prova: 40 minuti circa.
Metodi didattici
Modalità di erogazione: Lezioni frontali, in aggiunta videolezioni registrate.
Modalità di frequenza: Fortemente consigliata.
Materiale didattico e bibliografia
· Dispense reperibili al sito del corso (vedi sotto)
· Teoria della calcolabilità: A.J. Kfoury, R.N. Mall, M.A. Arbib. Programmazione e computabilità. Etas libri, 1986
· Teoria della Complessità :M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, 1979
Periodo
Secondo semestre
Periodo
Secondo semestre
Modalità di valutazione
Esame
Giudizio di valutazione
voto verbalizzato in trentesimi
Docente/i
Ricevimento:
su appuntamento via mail
Sala Dottorato, V piano (edificio Lita), Dip. Fisica, via Celoria 16