Obiettivi formativi
Fornire le nozioni fondamentali e gli strumenti formali per studiare problemi trattabili e non trattabili con il calcolatore.
Prerequisiti
Funzioni di una variabile A, Programmazione 1.
Contenuti dell'insegnamento
<br /> Cenni introduttivi sul concetto di algoritmo, sulla rappresentazione<br />dell'informazione, e sull'architettura del calcolatore.<br />Linguaggi formali.<br />Espressioni regolari.<br />Automi a stati finiti.<br />Grammatiche generative.<br />Linguaggi liberi dal contesto.<br />Macchine di Turing.<br />Funzioni calcolabili e non.
Programma esteso
- - -
Bibliografia
A. Dovier, R. Giacobazzi. Fondamenti dell'Informatica: Linguaggi Formali e Calcolabilità.<br />A. M. Pitts. Regular Languages and Finite Automata.<br />I. Mastroeni. Eserciziario per il corso ``Fondamenti dell'Informatica: Linguaggi Formali e Calcolabilità''.
Metodi didattici
<br />
Modalità verifica apprendimento
- - -
Altre informazioni
- - -