This is an old revision of the document!
Fondamenti di Informatica
News
- Martedì 6 Marzo si terrà la prima lezione del corso per l'anno accademico 2017/18
- Cari studenti, mi scuso ma la lezione di domani è cancellata confermo la lezione di mercoledì 21 Marzo.
Informazioni Generali
Docente:
Orario delle Lezioni:
- Martedì, 9 - 11
- Mercoledì, 9 - 11
Ricevimento studenti:
- Ampia disponibilità previo appuntamento
Obiettivi del Corso
- Comprendere le origini dell'informatica moderna e il concetto di calcolatore
- Conoscere, confrontare e saper usare i vari approcci alla computabilità
Contenuti del Corso
- 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.
Materiale
Slide del Corso (saranno pubblicate durante lo svolgimento delle lezioni)
- Introduzione al corso - pdf
- Introduzione alla teoria della computabilità - pdf
- Alfabeti, stringhe e linguaggi - class3_-_stringhelinguaggi.pdf
- Espressioni Regolari - pdf
- Grammatiche - pdf
- Esercizi con le Grammatiche - pdf
- ASFD e ASFND - pdf
- Problemi senza soluzioni pdf
- Funzioni Ricorsive - pdf
- Linguaggio WHILE: Sintassi e Semantica pdf
- Simulazione prova d’esame
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)
Esami
Le date di esame sono già disponibili al Seguente Link - https://didattica.unicam.it/Home.do
Regole di esame:
- Prova Scritta sugli argomenti del syllabus
- Domande a Risposta Aperta + Esercizi
- Durata: 2 h
Risultati Esame