Fondamenti Teorici dell’Informatica
People
Course director
Assistant
Description
OBIETTIVI
I fondamenti teorici dell'informatica spiegano al contempo la potenza ma anche le limitazioni alla base della computazione. Imparerai i modelli formali di computazione, per poi comprendere i concetti di complessità e di computabilità.
CONTENUTO
Il corso descriverà inizialmente i Linguaggi Regolari e i Linguaggi Context Free, insieme ai modelli di computazione che li descrivono: Automi Finiti, Automi Non Deterministici, Espressioni Regolari; Grammatiche Context-Free e Automi a Pila. Studieremo la teoria che supporta questi modelli, e svolgeremo inoltre numerosi esercizi pratici per fissare le nozioni acquisite. Vedremo poi la Macchina di Turing, e tratteremo i concetti di complessità e di computabilità.
IMPOSTAZIONE PEDAGOTICO-DIDATTICA
Lezioni ed esercizi in classe, Compiti a casa.
RIFERIMENTI BIBLIOGRAFICI
Introduction to the Theory of Computation, Michael Sipser.