Page begin -
Logo DISCO
|
Go to the Highly accessible area
|
Go to the Content page
|
Go to the End of content
|
Go to the Main menu
|
Go to the Navigation Bar (location)
|
Go to the Navigation menu (tree)
|
Go to the Commands list
|
Go to the Further readings
|
Go to the Bottom Menu
|
Logo Ateneo
   
Education
Informatica teorica (elementi)
 

 

Descrizione e Programma del corso

1. Elementi di computabilità

  • Macchine di Turing e funzioni parziali ricorsive
  • Tesi di Church
  • Insiemi ricorsivi e ricorsivamente enumerabili
  • Teorema di Rice e problemi irresolubili

2. Semantica formale dei linguaggi di programmazione

  • Semantica operazionale
  • Semantica denotazionale
  • Il teorema del punto fisso di Scott

3. Dimostrazione delle proprietà di un programma:

  • Semantica assiomatica
  • Prove di correttezza

4. Classi di complessità computazionale: P e NP

5. Riduzione tra problemi: problemi NP-completi

6. Algoritmi di Approssimazione

Libri di testo:

  • C. Toffalori, F. Corradini, S. Leonesi, S. Mancini, Teoria della computabilità e della complessità, Ed. McGraw-Hill.
  • Glynn Winskel, The formal semantics of programming languages, Ed. MIT Press.

Per ulteriori informazioni sul corso rivolgersi direttamente al docente.

Vai al sito WEB del corso

Further readings
(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - last update of this page 25/03/2011