SITE TITLE

LOGO DIETI

Elementi di informatica teorica

Titolo insegnamento in inglese: Introduction to Theoretical Computer Science

Lingua: italiano 

Insegnamento: Elementi di informatica teorica

Anno di corso: II

CFU: 6

SSD: INF/01

Ore di lezione: 48

Semestre: 1

Modulo: Nessuno

Codice: 04343

Obiettivi formativi:
Introdurre lo studente a nozioni e risultati teorici di base soggiacenti all’informatica. Lo studente potrà impadronirsi di concetti fondamentali dell'Informatica teorica e dei relativi modelli astratti di calcolo, apprezzandone l’utilità sia per un inquadramento generale del curriculum in Informatica sia per lo sviluppo delle sue capacità professionali.

Contenuti:
Automi finiti e macchine sequenziali. Automi non deterministici. Linguaggi regolari. Espressioni regolari. Pumping lemma per i linguaggi regolari. Grammatiche e linguaggi indipendenti dal contesto. Forme normali di Chomski. Automi a pilae non determinismo. Corrispondenza tra automi e grammatiche. Pumping lemma per i linguaggi indipendenti dal contesto. La gerarchia di Chomsky. I concetti di algoritmo, funzione calcolabile e parzialmente calcolabile. Funzioni primitive ricorsive. La minimalizzazione. Funzioni parziali ricorsive. Numerazioni di Goedel. Macchina universale. Tesi di Church - Turing. Problemi di decisione e di enumerazione. Indecidibilità. Insiemi ricorsivi e ricorsivamente numerabili. Macchina di Turing e indecidibilità, Complessità computazionale: nozioni di base.

Prerequisiti: Nessuno

Modalità didattiche:

Lezioni frontali ad argomento teorico ed esercitazioni per la soluzione di esercizi e problemi elementari di informatica teorica.

 

Materiale didattico:

Capitoli scelti dai seguenti libri di testo: 
1) M. Davis, R. Sigal, E. J. Weyuker: Computability, Complexity, and Languages (2nd ed.), Academic Press, San Diego and London. 
2) M. Sipser: Introduzione alla teoria della computazione, Apogeo, Milano.

Modalità di esame:

L'esame si articola in prova

Scritta e orale

 

 

 

 

     

 

 

 

 

 

 

 

 

 

 

In caso di prova scritta i quesiti sono

 

 

 

A risposta libera

 

 

Esercizi numerici

 

Altro

 

Docente: Tamburrini Guglielmo