Fondamenti di Informatica, 2 Ottobre 2015

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, comunicarlo 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) Fornire la definizione di sistema formale e fornire un esempio di sistema formale.
    (b) Nella deduzione naturale per la logica proposizionale, fornire la dimostrazione del seguente teorema 
    (A --> (B --> C)) --> ((A ∧ B) --> C))
    (c) Si consideri il seguente frammento di codice WHILE, dove a,b,c,s sono variabili: 
    s:=a;
c:=b;
while c≠0 do
    s:=s+1;
    c:=c-1
endw
    Si dimostri formalmente (saltando eventualmente qualche passaggio banale e regole di indebolimento o rafforzamento di condizioni), utilizzando la Logica di Hoare, che quando questo codice viene eseguito in uno stato in cui la variabile b contiene un numero non negativo, alla fine dell'esecuzione la variabile s contiene la somma di a e b.
    Esercizio 2
    (a) Cos'e' un modello computazionale? Si descriva il modello computazionale delle URM.
    (b) Dimostrare che la relazione binaria sui naturali "x e' il doppio di y" e' una relazione ricorsiva, fornendo la sua funzione caratteristica come URM. (Ricordiamo che una relazione binaria e' un insieme di coppie)
    Ricordiamo che le istruzioni delle URM sono Z(n), S(n), T(m,n) e J(m,n,q)
    (c) Enunciare il Problema della fermata e dimostrarne l'insolubilita'.
    Esercizio 3
    Dimostrare che nella codifica in complemento a due dei numeri interi la rappresentazione dei i numeri positivi ha "0" come cifra piu' a sinistra, mentre quella dei numeri negativi "1".