Fondamenti di Informatica, 20 Giugno 2012

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)
    Descrivere l'isomorfismo di Cantor tra N ed NxN.
    (b)
    Si consideri l'alfabeto A={a,c}. Associamo inoltre ad 'a' il numero 0 ed a 'c' il numero 2.
    Dire quindi (descrivendo il procedimento seguito) qual e' la codifica della stringa "acc" utilizzando l'isomorfismo di Cantor come descritto nel testo del corso.
    Si determini, inoltre, se possibile, la stringa codificata dal numero 18.
    (c)
    Si consideri la seguente definizione della funzione parziale ricorsiva f: 
     f(0,x) = P11(x)
 f(y+1,x) = h(y,f(y,x))
    dove h e' definita da 
     h(y,x) = S(P22(y,x))
    Dire, giustificando la risposta, cosa calcola f.
    Dire inoltre qual e' il valore di g(0), dove g e' definita da 
     g(x) = μ{y|f(y,x)=0}
    Ricordiamo che la funzione di base Pkj e' definita da Pkj(n1,..,nk) = nj.
    Esercizio 2
    (a)
    Cosa si intende per "modello computazionale"? Definire il modello computazionale delle URM.
    (b)
    Scrivere un programma URM che calcoli (n div 2), dove n e' l'input e div e' la divisione intera.
    (c)
    Sia A la seguente precondizione: ∃k.X2=k*2 e sia B la seguente postcondizione: ∃k.X2=k*2 ∧ X2≥X1.
    Fornire una istruzione WHILE E do I tale che il seguente giudizio della logica di Hoare sia valido: {A} WHILE E do I {B}.
    Esercizio 3 Cosa significa, nel calcolo proposizionale (logica proposizionale), che una formula A e' conseguenza tautologica di un insieme di formule Γ ( Γ |= A) ?
    E' vera la seguente affermazione? Giustificare la risposta.
    p → (p → q) |= p → q
    dove p e q sono variabili proposizionali.