Obiettivi formativi
Il corso fornisce gli strumenti formali e le nozioni fondamentali per studiare problemi trattabili e non mediante calcolatore. Viene presentata la teoria degli automi e dei linguaggi formali, teoria a fondamento della descrizione e dell'implementazione dei linguaggi di programmazione. Vengono poi illustrati i concetti e la natura dei problemi che ammettono soluzione effettiva, ovvero dei problemi risolvibili mediante calcolatore.
Prerequisiti
Fondamenti di programmazione. Analisi matematica. Algebra e geometria.
Contenuti dell'insegnamento
Fondamenti matematici dell'informatica:
* Cenni introduttivi sul concetto di algoritmo, sulla rappresentazione dell'informazione, e sull'architettura del calcolatore.
* Linguaggi formali.
* Espressioni regolari.
* Automi a stati finiti.
* Grammatiche generative.
* Linguaggi liberi dal contesto.
* Macchine di Turing.
* Funzioni calcolabili e non.
* Calcolabilità e linguaggi di programmazione.
* Cenni su insiemi ricorsivi e ricorsivamente enumerabili.
Programma esteso
- - -
Bibliografia
Testo di riferimento per il corso:
A. Dovier, R. Giacobazzi. Fondamenti dell'Informatica Bollati-Boringhieri, 2020.
Altri testi utili:
I. Mastroeni. Eserciziario per il corso ``Fondamenti dell'Informatica: Linguaggi Formali e Calcolabilità''.
U. Solitro. Linguaggi Formali, Computabilità e Complessità: Esercizi risolti, 2006.
Metodi didattici
Lezioni e esercitazioni.
Modalità verifica apprendimento
L'esame consiste in una prova scritta e un eventuale colloquio orale.
La prova scritta consiste in esercizi e domande aperte sul programma del
corso; il colloquio orale comprende ulteriori domande sul programma del corso. Il colloquio orale, quando
previsto, deve essere sostenuto nello stesso appello della prova scritta.
Agli studenti con voto compreso tra 18 e 26 nella prova scritta verrà
proposta la verbalizzazione (senza colloquio orale); al colloquio orale si
accede in caso di prova scritta con voto maggiore di 26 oppure compreso
tra 16 e 17.
Altre informazioni
- - -
