Fondamenti di Informatica, 9 Novembre 2011

Non e' ammesso l'uso di alcun testo, appunti o calcolatrici. 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.
  • I risultati verranno indicati nella pagina web del corso. Date ed orari degli orali, sul Forum.


    • Esercizio 1
    (a)
    Fornire la definizione di lambda-termine e definire formalmente la nozione di alfa-conversione.

    (b)
    Dato il seguente termine, cerchiare le sue variabili libere e collegare, utilizzando delle frecce, le sue variabili legate con i lambda relativi.

    λz.( ((λx.λx.yx)x)(vλz.λw.v) )

    (c)
    Qual e' la forma normale, se esiste, del seguente lambda-termine? Mostrare l'intera sequenza di beta-riduzioni che portano eventualmente a tale forma normale.

    (λx.xxy)(λxy.xyy)

    Esercizio 2
    (a)
    Fornire la definizione di codice. Definire i codici ad espansione.

    (b)
    Sia data la seguente stringa di 12 cifre binarie: 
    101101110000
    Trovare il valore (giustificando la risposta) della stringa interpretata come: Convertire in base 8 i valori assoluti dei numeri ricavati, e sommarli

    (c)
    Descrivere l'algoritmo che, dato un numero naturale n, fornisca la sua rappresentazione posizionale in base B. Dimostrarne la correttezza.
    Esercizio 3
    Cos'e' un sistema formale? Cos'e' un sistema formale alla Hilbert per la logica? Cos'e' un sistema formale di deduzione naturale per la logica?