Programma Preliminare
Fondamenti dell'Informatica (Corso C) a.a.2002/2003
Docente: Covino Emanuele

Obiettivi
Comprendere quali sono i problemi risolvibili meccanicamente, in assenza e 
in presenza di vincoli sulle risorse di calcolo.

Descrizione
Il corso introduce le nozioni fondamentali della teoria della 
calcolabilitą e della complessitą. La prima parte delinea i concetti e la 
natura dei problemi che hanno soluzione effettiva. La seconda parte 
caratterizza i problemi che sono risolvibili con risorse di calcolo 
limitate.

Programma
1. Concetti matematici di base (4 h)
Insiemi, relazioni, funzioni. Cardinalitą e numerabilitą degli insiemi. 
Strutture algebriche di base. Linguaggi ed operazioni su linguaggi. 
Espressioni regolari

2. Macchine di Turing e calcolabilitą secondo Turino (8 h)
Macchine di Turing ed equivalenza fra i modelli modificati. Macchine di 
Turing non deterministiche. Linguaggi decidibili e semidecidibili. 
Calcolabilitą secondo Turing. Macchina di Turing universale. Il
problema della terminazione.

3. Modelli di calcolo per linguaggi imperativi e funzionali (8 h)
La macchina a registri. Equivalenza tra macchine di Turing e macchine a 
registri. Macchine a registri e linguaggi imperativi. Funzioni ricorsive, 
totalitą e diagonalizzazione. Rapporto fra funzioni ricorsive e linguaggi 
imperativi e funzionali.

4. Teoria generale della calcolabilitą (8 h)
Enumerazione delle funzioni calcolabili. Funzioni non calcolabili e 
problemi indecidibili. Proprietą degli insiemi semidecidibili. 

5. Complessitą di algoritmi sequenziali (8 h) 
Un modello basato su linguaggio ad alto livello. Modelli di costo. 
Funzioni di complessitą. Ordini di complessitą. Relazioni di ricorrenza. 
Classi di complessitą. Tesi della computazione sequenziale. Analisi di 
algoritmi di ordinamento e di ricerca su vettori. Analisi di algoritmi di 
ricerca su grafi. Analisi di algoritmi algebrici. 

6 Complessitą di problemi (8 h)
Complessitą di problemi. Funzioni di misura di tempo e spazio 
(accelerazione lineare, riduzione del numero dei nastri, relazioni fra le 
misure di complessitą). Modelli di calcolo nondeterministici. 
Classificazione di problemi in base alla complessitą. Classi 
(tempo/spazio) deterministiche e non: P, NP, PSPACE, LOGSPACE. NP-
completezza. I problemi SAT e QBF. Il problema P=NP per macchine di Turing 
con oracoli.

Riferimenti:
Ausiello, D’Amore & Gambosi. Linguaggi, modelli, complessitą
Bovet & Crescenzi. Teoria della complessitą computazionale.
Cormen, Leseirson & Rivest. Introduzione agli algoritmi.
Cutland. Computability: an introduction to recursive function theory.
Hopcroft & Ullman. Introduction to automata theory, languages, and 
computation.