A.A.  2004-2005


 

FONDAMENTI DELL'INFORMATICA II

Prof. Stefano Kasangian



 

Programma


 La macchina di Turing
  • Descrizione modellistica e matematica della MDT. Macchine di Turing non deterministiche.
  • Funzioni parziali computabili. 
  • Introduzione alla teoria della ricorsività . La nozione di calcolabilità: le funzioni intuitivamente calcolabili. Caratterizzazione delle funzioni calcolabili. Funzioni ricorsive parziali. Tesi di Church. Enumerazione effettiva.. Sistema di programmazione accettabile. Il teorema di ricorsione e il teorma di isomorfismo. 
  • La problematica della decidibilità. 
  Insiemi ricorsivi 
  • Insiemi ricorsivamente numerabili. Problemi non decidibili 
  • Il problema dell'arresto. Riducibilità tra insiemi e insiemi completi. Il teorema di Rice.
  Generalità sui  linguaggi formali.
  • Macchine di Turing come sistema di programmazione accettabile e come riconoscitori. 
  • Linguaggi e sistemi di riscrittura. 
  • Grammatiche formali. Gerarchia di Chomsky. Grammatiche di tipo 0, context sensitive e context  free, regolari e le rispettive classi di linguaggi. 
  • Alberi di derivazione nelle gramatiche context free. Emptiness problem. Lemma di iterazione per i linguaggi context free. 
 Elementi di architettura dei calcolatori.
  • Definizione di "performance". Definizione di "costo". 
  • La struttura gerarchica dei calcolatori. Livelli e relazione tra essi. 
  • Architetture e linguaggi. 
  • Compilazione ed interpretazione. 
  • Il modello di Von Neumann
  • Il problema dell'affidabilità. 
  • Codici binari. Strutture fisiche dell'informazione.  Il livello di linguaggio di macchina.
  • ll formato di istruzione e i metodi di indirizzamento : indirizzamento mediante "modo e registro". 
  • La concorrenza e le architetture parallele (cenni)
Teoria degli automi
  • Automi a stati finiti,  deterministici e non deterministici. 
  • Grammatiche regolari. 
  • Subset construction. 
  • Composizione in serie e parallelo di automi. 
  • Automi ridotti per osservabilità e raggiungibilità. 
  • Automi minimi. 
  • Espressioni regolari. 
  • Teorema di caratterizazione di Kleene. 
  • Macchine sequenziali generalizzate, "pumping lemmas". 
  • Automi a push down, grammatiche libere dal contesto, automi ad albero.


Teoria delle categorie.

  • Nozione di categoria. 
  • Monomorfismi, oggetti iniziali, prodotti, limiti, pullback e loro duali. 
  • Completezza. 
  • Funtori e trasformazioni naturali. 
  • Categorie distributive 
Tipi di dati e categorie distributive
  • Programmi imperativi. 
  • Stacks e Arrays. 
  • Alberi binari. 
  • Code. 
  • Puntatori.

Testi consigliati: 

 A. Bertoni, Metodi per il trattamento dell'informazione, Clued,1985
 M.Davis, Computability and Unsolvability, Dover.
 R.Goldblatt, Topoi, North Holland.
 J.Hennessy, D.Patterson, Computer architecture: a quantitative approach, Morgan&Kauffmann.
 L.Kronsjo, Complessità computazionale degli algoritmi sequenziali e paralleli, Tecniche Nuove. 
 A. J. Kfoury, R N. Moll, M. A. Arbib, An Introduction to formal language theory, Springer. 
 A. J. Kfoury, R N. Moll, M. A. Arbib, A programming approach to computability, Springer.
 F.W. Lawvere, Conceptual Mathematics, traduzione italiana presso Muzzio.
 H.Lewis, C. Papadimitriou, Elements of the Theory of Computation, Prentice Hall.
 S.Maclane, Le Categorie Nella Pratica Matematica, Boringhieri.
 R.F.C.Walters, Categories and Computer Science, Cambridge University Press.
 Dispense, esercizi, download