Fondamenti dell'Informatica I

A.A. 2003/04

Corsi di Laurea Base in Informatica e in Matematica

Docente: Luca Forlizzi, Ph.D.
Durata: Trimestrale (5 Aprile 2003 - 19 Giugno 2004)
Lezioni: Martedý 15.00-17.00, Mercoledý 17.00-19.00, Venerdý 09.30-11.30 in Aula Magna
Ricevimento: Martedý 17.00-19.00

Prerequisiti del corso

Obiettivi di apprendimento

Sillabo del corso

  1. Elementi di logica: calcolo delle proposizioni, calcolo dei predicati, sistemi formali.
  2. Elementi di teoria della calcolabilita': numerabilita', modelli di calcolo e tesi di Church, macchina di Turing e macchina a registri.
  3. Funzioni calcolabili e non calcolabili, problema della fermata, insiemi ricorsivi e ricorsivamente enumerabili
  4. Linguaggi e problemi, accettabilita' e decidibilita' di linguaggi, calcolo non deterministico.
  5. Elementi di Teoria della complessita': misure statiche e dinamiche, classi di complessita' spaziali e temporali, le classi di problemi P ed NP.
  6. La congettura P=NP? NP-completezza. Schema di dimostrazione di NP-completezza. Enunciato del teorema di Cook.

Testi di riferimento

Testi consigliati per approfondimenti