Fondamenti di Informatica, 21 Giugno 2013
Non e' ammesso l'uso di alcun testo, appunti,
calcolatrici, telefonini o smartphone. Le risposte vanno scritte nel foglio di bella copia. Si
raccomanda la massima SINTETICITA'. L'eccessiva verbosita' verra'
considerata negativamente.
Occorre essersi prenotati sul portale
studenti del nostro
ateneo. Se cio' non e' stato fatto, comunicatelo immediatamente
al docente o all'assistente in aula ed indicarlo chiaramente sull'elaborato che si consegna.
I risultati
verranno indicati nella pagina web del corso.
Date ed orari degli orali, sul Forum.
Esercizio 1
(a)
Descrivere il modello computazionale del λ-calcolo.
(b)
Inserire le parentesi ed i lambda lasciati impliciti nel seguente termine.
Rinominare inoltre le variabili legate in modo che non ci siano due variabili legate
con lo stesso nome:
(λxxxx.x(xx)x)xxx
(c)
Enunciare il Teorema di Church-Rosser e dimostrare la proprieta' di unicita' della
forma normale.
Dimostrare inoltre la consistenza del λ-calcolo.
Esercizio 2
(a)
Fornire la definizione di Macchina Astratta.
(b)
Descrivere le possibili realizzazioni di macchine astratte. Descrivere inoltre il concetto di struttura
a livelli dei sistemi di calcolo e discutere dei vantaggi della struttura a livelli.
Esercizio 3
(a)
Si forniscano le definizioni di Induzione, Induzione Completa ed Induzione Ben Fondata.
Si accenni poi alla corrispondenza tra Induzione e Ricorsione.
(b) Descrivere un efficiente algoritmo di conversione da base 2 a base 8 e
giustificarne formalmente la correttezza.