IN2, I Semestre, Crediti 7.5 Università Roma Tre

IN2 Informatica Generale 2 A.A. 2008/2009

Prof. Marco Pedicini Modelli di Calcolo

1. Computabilità, complessità e rappresentabilità

- Introduzione ai problemi di decisione, procedure algoritmiche e non algoritmiche, computazioni deterministiche, procedure discrete, nozione di alfabeto, di parola. Decidibilità e semidecidibilità di un insieme. Computazioni deterministiche, finitarie e discrete. Algoritmi formali. Esempio di formalizzazione di un algoritmo. Decidibilità per automa finito. Computazioni deterministiche, finitarie e discrete. Algoritmi formali: definizione formale di algoritmo, configurazioni di input, di output, funzione di transizione. Esempio di formalizzazione di un algoritmo. Decidibilità per automa finito. Rappresentazione degli automi mediante matrici.

- Macchine RAM: definizione di base, istruzioni per programmi eseguibili da macchine RAM, semantica di un programma, codifica di un programma per RAM in un algoritmo formale, complessità uniforme di un programma per RAM.

- Macchine di Turing: definizione, decidibilità per macchina di Turing, tempo di arresto, spazio di arresto. Costo della computazione. Complessità: caso peggiore e caso medio. Indipendenza del tempo di decisione da un numero finito di configurazioni di input. Funzioni di complessità, classi di complessità DTIME e DSPACE (deterministic time e space). Inclusione DT IME(T (n)) ⊂ DSP ACE(T (n)) ⊂ DT IME(2^{cT (n)}). Pumping Lemma. Simulazione di algoritmi, simulazione della macchina di Turing a seminastro, simulazione di una macchina multinastro. Macchine di Turing speciali. Teorema di Speedup lineare per macchine di Turing con alfabeto esteso. Valutazione del coefficente di accelerazione in relazione agli alfabeti.

- Turing calcolabilità: definizione di funzione Turing calcolabile, funzioni caratteristiche di insiemi Turing decidibili, la classe delle funzioni Turing calcolabili è chiusa per composizione, coppia, ricorsione e minimizzazione. Esempi di funzioni Turing calcolabili. Funzioni Ricorsive: equivalenza tra Turing computabilità e funzioni ricorsive. ([1] capp. 1, 2, 3, 4, 5 e [4] cap. 1)

2. Lambda calcolo e programmazione funzionale

A.A. 2008/2009, I Semestre  IN2  Crediti 7.5

- Programmazione dichiarativa: cenni storici sul lambda calcolo, definizioni di base, i termini del lambda calcolo, la sostituzione semplice Relazioni sui lambda termini. Congruenze, passaggio al contesto Alpha equivalenza. L’alpha equivalenza passa al contesto. Chiusura transitiva di una relazione, proprietà di Church-Rosser. Quozientamento dei lambda-termini rispetto all’alpha equivalenza.

- Definizione di beta-redesso e di beta-riduzione. Teorema di Chuch-Rosser per la beta-riduzione. Forme normali per beta-riduzione. Strategie di beta-riduzione. Strategia normalizzante: riduzione di sinistra (left most- outer most). Riduzione di testa. Termini Risolubili. Forme Normali di Testa. Teorema di caratterizzazione della risolubilità.

- Rappresentazione delle funzioni ricorsive: teorema di lambda definibilità Esistenza del punto fisso per il lambda termini. Punto Fisso di Church ed punto fisso di Curry.

- Rappresentazione di altri tipi di dato nel lambda-calcolo: coppie, liste, alberi, soluzione di equazioni ricorsive su lambda-termini. ([2] capp. 1, 2, 5)

Testi consigliati

[1] Dehornoy, P., Complexité et Decidabilité. Springer-Verlag, (1993).

[2] Krivine, J.-L., Lambda Calculus: Types and Models. Masson,

[3] Aho, Hopcroft, Ullman, Design and Analysis of Computer Programming..

Bibliografia supplementare

[4] Ausiello, G., Gambosi, G., d’Amore F., Linguaggi, Modelli, Complessità. F. Angeli, (2003).

[5] Hermes, H., Enumerability, Decidability, Computability. Die Grundlehren der Mathematichen Wissenshaften in Einzeldarstellungen, n. 127, Springer-Verlag, (1965).

[6] Sethi, R., Programming Languages: concepts and constructs. Addison-Wesley (ed. italiana Zanichelli),

Modalità d’esame

- valutazione in itinere (“esoneri”)  SI  NO
- esame finale  scritto  SI  NO
orale  SI  NO
- altre prove di valutazione del profitto  SI  NO

(meglio descritte sotto)

L’esame consiste di due parti: un esame scritto e della discussione di una tesina. La prova orale é prevista per riparare le insufficenze lievi. L’argomento della tesina deve essere concordato con il docente e va presentata solo

dopo il superamento dell’esame scritto.

Le due prove di esonero unitamente alla soluzione dei tre fogli di esercizi, proposti durante il corso sostituiscono la prova scritta e la tesina.