Informatica Teorica
(Metodi per il Trattamento dell'Informazione)
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
Bibliografia
Per entrambe le parti, sono previste dispense
reperibili al sito del corso.
Per approfondimenti, si segnalano i seguenti testi entrambi reperibili
alla biblioteca
del DSI.
Teoria della calcolabilità
di cui è disponibile (ma non nella nostra biblioteca)
la versione italiana:
Teoria della Complessità
