Fondamenti di Informatica


  • La lezione di domani 13 marzo è cancellata confermo la lezione di mercoledì 14 Marzo.

Docente:

Orario delle Lezioni:

  • Lunedì, 9 - 11
  • Martedì, 9 - 11

Ricevimento studenti:

  • Ampia disponibilità previo appuntamento

  • Comprendere le origini dell'informatica moderna e il concetto di calcolatore
  • Conoscere, confrontare e saper usare i vari approcci alla computabilità

  • La computabilità da Leibniz ai giorni nostri. Il concetto di Algoritmo.
  • Alfabeti, stringhe e linguaggi. Il ruolo che stringhe e linguaggi hanno per rappresentare l’informazione.
  • Linguaggi. Strumenti per definire un linguaggio. Espressioni Regolari, Approccio Generativo, Approccio Riconoscitivo.
  • Calcolabilità e Grammatiche. Grammatiche e automi. La gerarchia di Chomsky. Linguaggi regolari, liberi da contesto, dipendenti dal contesto.
  • Automi di riconoscimento. Deterministici e Non Deterministici. Trasformazioni.
  • Macchine di Turing. 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 Linguaggi di Programmazione. Il linguaggio WHILE: sintassi e semantica.

Slide del Corso (saranno pubblicate durante lo svolgimento delle lezioni)

Slide anno accademico precedente [zip file].

Testi di Riferimento

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

2017_-_3._compito_settembre_risultati_.pdf

Date Esami A.A. 2015/2016 (Maggiori Dettagli al Seguente Link - https://didattica.unicam.it/Home.do)

  • 22/06/2017 17:00
  • 06/07/2017 09:00
  • 20/07/2017 09:00
  • 08/09/2017 11:30
  • 28/09/2017 11:30
  • 30/01/2018 11:30
  • 13/02/2018 11:30

Regole di esame:

  • Prova Scritta sugli argomenti del syllabus
  • Domande a Risposta Aperta + Esercizi
  • Durata: 2 h

Risultati Esame