Nome modulo

Docente:

• Barbara Re

Orario delle Lezioni:

• Martedì: 09:00 – 11:00
• Venerdì: 09:00 – 11:00

Ricevimento studenti:

• Ampia disponibilità previo appuntamento

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

Testi di Riferimento

• Libro di testo

Date Esami A.A. 2015/2016

• 1a sessione
• 2a sessione
• 3a sessione
• 4a sessione

Regole di esame:

Risultati Esame

• N/A