Fondamenti dell'Informatica 1, SSISS, A.A. 2002/2003

Argomenti trattati a lezione

  1. 10 Gennaio 2003. Introduzione al corso. Diagonalizzazione. Il concetto di algoritmo.
  2. 17 Gennaio 2003. Formalismi per la descrizione di algoritmi/funzioni computabili. Macchina di Turing. Definizioni formali e visione modellistica. Funzioni Turing-calcolabili. Funzioni Primitive ricorsive.
  3. 27 Gennaio 2003. Enumerazione delle funzioni primitive ricorsive. Esistenza di funzioni totali e non primitive ricorsive (per diagonalizzazione). La funzione di Ackermann. Il μ-operatore e le funzioni ricorsive parziali.
  4. 31 Gennaio 2003. Teorema di equivalenza tra le funzioni ricorsive parziali e le funzioni Turing-calcolabili. Enumerazione di MdT.
  5. 7 Febbario 2003. (3ore) Il Teorema S-m-n. Indecidibilità del problema della terminazione. Altri formalismi: Descrizione di algoritmi con diagrammi di flusso e Teorema di Böhm-Jacopini.
  6. 14 Febbraio 2003. Il linguaggio While. Motivazioni, sintassi, semantica ed esempi.
  7. 21 Febbraio 2003 (3 ore). Funzioni While-calcolabili. Turing completezza del linguaggio While. Il linguaggio For. Equivalenza tra funzioni For-calcolabili e funzioni primitive ricorsive. Interpreti e Metainterpreti. Dimostrazione dell'indecidibilità dell'halting problem senza aritmetizzazione. Il teorema s-m-n per la While calcolabilità e gli Specializzatori.
  8. 28 Febbraio. Problemi e linguaggi. Problemi decisionali. Cenni sulle classi di Complessità in tempo deterministiche e non deterministiche. Esempi: Raggiungibilità, Circuito Hamiltoniano, Circuit Value, Circuit SAT e Ordinamento.
  9. 7 Marzo. Definizione precisa di P e NP con Macchine di Turing. Relazioni tra classi in tempo. Riduzioni tra problemi, completezza, Teoremi di Cook. NP completezza di CIRCUIT SAT, SAT, 3SAT, NAESAT, IS, CLIQUE, NODE COVER, TSP(k), k-COLORING.
Riferimenti bibliografici:
Home page