SILLABO

• Elementi di teoria della calcolabilita’: numerabilita’, modelli di calcolo e tesi di Church, macchina di Turing, calcolo non deterministico. Macchine a contatori.
• Funzioni e linguaggi calcolabili e non calcolabili, insiemi ricorsivi e ricorsivamente enumerabili. Linguaggi e problemi, accettabilita’ e decidibilita’ di linguaggi.
• Tecniche di diagonalizzazione, riduzioni, linguaggio universale, Teorema di Rice.
• Elementi di Teoria della complessita’: misure statiche e dinamiche, classi di complessita’ spaziali e temporali, le classi di problemi P ed NP. La congettura P=NP? NP-completezza.
• Riduzioni polinomiali. Teoremi riguardanti la NP-completezza. Enunciato del teorema di Cook. CSAT, 3SAT e altri problemi NP-completi.
• Classe PS e NPS, Teorema di Savitch. Cenni di aritmetica modulare e crittografia.