Search for contacts, projects,
courses and publications

Fondamenti Teorici dell’Informatica

People

Pozzi L.

Course director

Stojceski F.

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.