Obiettivi formativi
Fornire le nozioni fondamentali e gli strumenti formali per studiare problemi trattabili e non trattabili con il calcolatore.<br /><br />
Prerequisiti
Analisi matematica 1, Fondamenti di programmazione.<br />
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. <br /><br /><br />
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à''.<br />
U. Solitro. <em>Linguaggi Formali, Computabilità e Complessità: Esercizi risolti</em>, 2006.<br />
A. Pettorossi. <em>Automata Theory and Formal Languages</em>, Aracne Editrice, 2006. ISBN: 88-548-0889-X.<br />
A. Pettorossi. <em>Elements of Computability, Decidability, and Complexity</em>, Aracne Editrice, 2006. ISBN: 88-548-0682-X.