A.A.  2004-2005


 

FONDAMENTI DELL'INFORMATICA I

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. 

    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