Corso di laurea magistrale Interateneo in Fisica dei sistemi complessi

Calcolabilità
o Macchine di Turing
o Funzioni calcolabili secondo Turing
o Insiemi ricorsivi e ricorsivamente enumerabili
o Tesi di Church
o Diagonalizzazione
o Indecidibilità
Complessità
o Misure di complessità, ordini di grandezza, modelli e rappresentazione di
problemi,
o Teorema di accelerazione lineare
o Esistenza di problemi di complessità arbitraria, linguaggio “arbitrariamente facile”
o Teorema della gerarchia (e funzioni time-constructible)
o Macchine di Turing non deterministiche e modello Guess&Verify
o Le classi P ed NP, problemi in NP, riduzioni polinomiali, problemi NP-completi,
SAT e il teorema di Cook
o Complessità in termini di spazio, relazioni tra complessità in termini di spazio e
tempo, e spazio non deterministico e tempo; teorema di Savitch
o Spazio sublineare. Minimo limite in termini di spazio per cui una macchina di
Turing ha potenza computazionale superiore ad un automa a stati finiti.
o Esistenza di linguaggi non riconoscibili in tempo poliniomiale
o Un problema PSPACE-completo e un problema non in PSPACE
Laboratorio
E' prevista attività in laboratorio come parte integrante del corso. In laboratorio gli
studenti sono invitati ad implementare macchine di Turing, utilizzando un simulatore
che viene messo a disposizione, e programmi in un linguaggio ad alto livello a scelta.
Lo scopo è approfondire la comprensione dei modelli studiati e delle simulazioni con
cui sono realizzate quasi tutte le dimostrazioni dei teoremi presentati.