Fondamenti di Informatica, 5 Ottobre 2017

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.
  • Per sostenere l'esame e' obbligatorio essersi prenotati sul portale studenti del nostro ateneo. Elaborati di studenti non prenotati NON verranno valutati.
  • I risultati verranno indicati nella pagina web del corso. Date ed orari degli orali, sul Forum.

    • Esercizio 1
    (a) Fornire le definizioni di codice, codice a lunghezza variabile e codice a lunghezza fissa. Cosa caratterizza i codici ad espansione tra quelli a lunghezza variabile?

    (b) Dimostrare che il seguente algoritmo, che prende in input un numero naturale, produce le cifre cp-1cp-2....c2c1c0 della sua codifica in notazione posizionale in base B. 
    input n

val := n
i:= 0

REPEAT
  quoz := val
  val := quoz div B
  ci := quoz mod B
  i := i+1
UNTIL (quoz < B)

    (c) Dimostrare che, per x e y numeri positivi,
    codZc2p(-x) (+) codZc2p(-y) = codZc2p(-x-y)
    Dove (+) rappresenta l'algoritmo di somma per i numeri naturali codificati in notazione posizionale.
    Esercizio 2
    (a) Sia α una formula ben formata della logica dei predicati del prim'ordine (calcolo dei predicati) rispetto una data segnatura Σ, e sia AΣ una struttura.
    Dare le definizioni di:
    (b) Fornire la definizione di regola derivabile in un sistema formale.
    Dimostrare che in deduzione naturale per la logica proposizionale la regola 
            ¬¬α
      -------
         α
    e' derivabile.
    Fare lo stesso per la regola 
            α
      -------
        ¬¬α
    (c) Dimostrare che , se x non appartiene alle variabili libere di B, allora
    ((∃x.A) → B) → ∀x.(A → B)
    e' un teorema della logica dei predicati del primo ordine.
    Esercizio 3
    Calcolare la forma normale (mostrando la computazione eseguita) del lambda-termine
    x(λ z.(zx)) [λt.(w(ty))/x]