This is an old revision of the document!
Nome modulo
News
Informazioni Generali
Docente:
Orario delle Lezioni:
- Martedì: 15:00 – 17:00
- Giovedì: 15:00 – 17:00
Ricevimento studenti:
- Al termine delle lezioni o previo appuntamento via mail.
Obiettivi del Corso
- Conoscere le motivazioni della nascita dell'Informatica moderna e dell'idea astratta di calcolatore
- Osservare l'esistenza di problemi che non si possono risolvere, o che si possono risolvere solo a costi inaccessibili
- Confrontare i vari possibili approcci alla computabilità
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 WHILE: sintassi e semantica.
Materiale
Slide del Corso
Testi di Riferimento
- F. Corradini, S. Leonesi, S. Mancini, C. Toffalori: Teoria della computabilità e della complessità. McGraw-Hill Italia, 2005. (Capitolo 1 – 6)
Esami
Date Esami A.A. 2014/2015 (https://didattica.unicam.it/Home.do)
- 01/02/2016 11:30
- 01/10/2015 11:30
- 15/09/2015 11:30
- 01/07/2015 11:30
- 16/06/2015 11:30
- 31/03/2015 11:30
- 23/02/2015 11:30
- 03/02/2015 11:30
Regole di esame:
La prova consiste in uno scritto sugli argomenti del syllabus composto da domande a risposta aperta ed esercizi. La durata prevista è di 2 h.
Risultati Esame
- N/A
