Fondamenti d’Informatica

Questo corso è parte della laurea in Informatica all’Università degli Studi di Camerino (a.a. 2014/15).

Contenuti del corso

  • La computabilità da Leibniz ai giorni nostri. Il concetto di Algoritmo.
  • Macchine di Turing. Alfabeti, stringhe e linguaggi. Funzioni calcolabili e linguaggi decidibili secondo Turing. La tesi di Church. Macchine di Turing non deterministiche.
  • Problemi senza soluzione. La macchina Universale. Il problema dell’arresto. Il decimo problema di Hilbert. I teoremi di Rice e di Kleene.
  • Funzioni Ricorsive. Calcolabilità secondo Church. Funzioni parziali ricorsive.
  • Calcolabilità e Grammatiche. Grammatiche e automi. La gerarchia di Chomsky. Linguaggi regolari, liberi da contesto, dipendenti dal contesto. Automi di riconoscimento.
  • Calcolabilità e Linguaggi di Programmazione. Il linguaggio WILE: sintassi e semantica.

Testo di Riferimento

F. Corradini, S. Leonesi, S. Mancini, C. Toffalori: Teoria della computabilità e della complessità. McGraw-Hill Italia, 2005. (Capitolo 1 – 6)

Esiti Prove d’Esame

  • 03/02/2015 – esito
  • 23/02/2015 – esito
  • NEW!!! – 31/03/2015 – esito

Materiale

Le dispense in formato PowerPoint sono disponibili su richiesta. Se interessati, si prega di inviare una e-mail a barbara.re [at] unicam.it