Fondamenti d’Informatica (a.a. 2015/16)

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

ESITI – Appello 28.10.2016 – pdf

ESITI – Appello 14.09.2016 – pdf

ESITI – Appello 27/07/2016 -pdf

ESITI – Appello 06/07/2016 – pdf

ESITI – Appello 22/06/2016 – pdf

ESITI – Appello 08/06/2016 – pdf

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)

Materiale

  • Introduzione al corso – slide
  • Introduzione alla teoria della computabilità – slide
  • Alfabeti, stringhe e linguaggi – slide
  • Espressioni Regolari – slide
  • Grammatiche – slide
  • Esercitazioni – slide
  • Automi slide1slide2
  • ASFD e ASFND – slide
  • Macchine di Turing – slide
  • Macchine di Turing (esercitazioni) – slide
  • Problemi senza soluzioni – slide
  • Funzioni Ricorsive – slide
  • Linguaggio WHILE: Sintassi e Semantica- slide
  • Simulazione prova d’esame – Traccia –  slide

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