Fondamenti di Informatica, 13 Dicembre 2013 A.A. 2012/13

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) Che cosa e', a cosa serve la Logica di Hoare? Che forma hanno in giudizi della Logica di Hoare?
    (b) Qual e' la definizione di giudizio valido nella Logica di Hoare? Il seguente giudizio e' valido? Dimostrare informalmente perche'.

    {Pari(X2)} begin X2 := succ(X2); X1:=0 end { ¬ Pari(X2)}


    (c) Quella seguente e' la regola di inferenza della Logica di Hoare per le istruzioni condizionali: 
    {A ∧ E} I1 {B}    {A ∧ ¬E} I2 {B}
----------------------------------
{A} if E then I1  else I2 {B}
    Dimostrare la correttezza di tale regola.
    Esercizio 2
    (a) Che cosa si intende per "modello computazionale"? Elencarne alcuni, descrivendoli a grandi linee.
    (b) Definire formalmente ed in dettaglio il modello computazionale delle URM.
    (c) Scrivere un programma URM che, partendo con il valore x nel primo registro (R1) e con il valore 0 in tutti gli altri registri, termini lasciando 1 in R1 se x e' dispari e 0 se e' pari. (ricordiamo che Z(n) e' l'istruzione di reset, S(n) quella di incremento, T(m,n) quella di assegnamento e J(m,n,q) quella di salto condizionato).
    Commentare il codice. Codice non commentato non verra' valutato.
    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".