Corso di

INFORMATICA TEORICA

Prof. G. Ausiello

 

Prerequisiti

Il corso prevede che lo studente abbia una conoscenza completa dei contenuti dei corsi di Fondamenti di Informatica I e Fondamenti di Informatica II. Inoltre è opportuna la conoscenza di concetti di algebra, e matematica discreta che possono essere acquisiti nei corsi di Geometria e Algebra e di Ricerca operativa

Obiettivi

Il corso intende dare una trattazione complessiva dei metodi formali utilizzati in informatica per studiare le principali proprietà di linguaggi e modelli di calcolo, di algoritmi e programmi nonche’ dei problemi che si devono affrontare e risolvere con l'elaboratore.

Programma

1. Concetti matematici di base

Insiemi, relazioni, funzioni. Cardinalita’e numerabilita’ degli insiemi. Strutture algebriche di base. Linguaggi ed operazioni su linguaggi. Espressioni regolari

2. Linguaggi formali e automi

Grammatiche di Chomsky. Linguaggi di tipo 0, 1, 2, 3. Linguaggi regolari e automi a stati finiti. Proprieta' dei linguaggi regolari. Linguaggi noncontestuali e automi a pila. Proprieta' dei linguaggi noncontestuali.

3. Macchine di Turing e calcolabilità secondo Turing

Macchine di Turing. Macchine di Turing a piu’ nastri. Macchine di Turing non deterministiche. Linguaggi decidibili e semidecidibili. Linguaggi di tipo 0 e macchine di Turing. Calcolabilità secondo Turing. Macchina di Turing universale. Il problema della terminazione

4. Modelli di calcolo per linguaggi imperativi e funzionali

La macchina RAM. Equivalenza tra macchine di Turing e RAM. Funzioni ricorsive. Il formalismo di Mc Carthy. Il LISP

 

5. Teoria generale della calcolabilita’

Enumerazione delle funzioni calcolabili. Funzioni non calcolabili e problemi indecidibili. Proprieta’ degli insiemi semidecidibili.

6. Complessità di algoritmi e problemi

Complessità di algoritmi. Complessità di problemi. Modelli di calcolo nondeterministici. Classificazione di problemi in base alla complessità. Problemi NP-completi. Accenno alla gerarchia polinomiale

7. Proprietà semantiche dei programmi

Vari approcci alla semantica. Semantica operazionale (call by name e call by value). Semantica denotazionale. Teoria del punto fisso negli ordini parziali completi. Semantica denotazionale di un semplice linguaggio funzionale

 

Le esercitaziuoni hanno per oggetto:

- Esercizi relativi ai temi trattati nelle lezioni

- Programmazione nel linguaggio LISP

 

Testi adottati

Dispense a cura di G. Ausiello, F. d’Amore, G. Gambosi relative alle parti 1 - 6

R. De Nicola, A. Piperno, Semantica operazionale e denotazionale, UTET

Altri testi consigliati

H. R. Lewis, Ch. Papadimitriou, Elements of the theory of computation, Freeman