Fondamenti di Informatica

Docente:

• Barbara Re

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)

• Introduzione al corso
• Introduzione alla teoria della computabilità
• Alfabeti, stringhe e linguaggi
• Espressioni Regolari
• Grammatiche
• Esercizi con le Grammatiche
• Automi parte1 parte II Esercizi
• ASFD e ASFND
• Macchine di Turing Esercizi
• Problemi senza soluzioni
• Funzioni Ricorsive
• Linguaggio WHILE: Sintassi e Semantica
• Simulazione prova d’esame SLIDE

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)

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

• 22/06/2017 - Esito
• 06/07/2017 - Esito
• 20/07/2017 - Esito
• 08/09/2017 - Esito
• 28/09/2017 - Esito