Nome modulo

Docente:

• Barbara Re

Orario delle Lezioni:

• Martedì: 15:00 – 17:00
• Giovedì: 15:00 – 17:00

Ricevimento studenti:

• Al termine delle lezioni o previo appuntamento via mail.

• 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à

• 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.

Slide del Corso

• Introduzione al corso
• Introduzione alla teoria della computabilità
• Alfabeti, stringhe e linguaggi
• Grammatiche
• Esercitazioni
• Automi1
• Automi2
• Esercitazioni
• Esercitazioni
• ASFD e ASFND
• Macchine di Turing
• Macchine di Turing (esercitazioni)
• Problemi senza soluzioni
• Funzioni Ricorsive
• Linguaggio WHILE: Sintassi e Semantica
• Simulazione prova d’esame
• Soluzioni Simulazione prova d’esame

Testi di Riferimento

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

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