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
Esame scritto.
Altre informazioni
- - -
