Fondamenti di Informatica, 6 Marzo 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, indicatelo chiaramente nello scritto o comunicatelo al docente o all'assistente in aula in caso di ritiro.
  • I risultati verranno indicati nella pagina web del corso. Date ed orari degli orali, sul Forum.


    • Esercizio 1
    (a)
    Fornire la definizione di Codice. Cos'e' un codice ad espansione? Descrivere brevemente uno dei possibili codici ad espansione.
    (b)
    Si consideri il numero naturale la cui rappresentazione posizionale in base 8 e' 274.
    Lo si rappresenti in base 7
    Lo si rappresenti poi in base 2 nel modo piu' veloce possibile.
    Giustificare la risposte.
    (c)
    Un semplice algoritmo per passare dalla notazione posizionale binaria a quella esadecimale e' il seguente: Dividiamo la stringa della rappresentazione binaria in blocchi da 4 bit (partendo da destra) e per ogni blocco consideriamo la cifra esadecimale corrispondente al numero rappresentato dai vari blocchi.
    Dimostrare la correttezza di tale algoritmo.


    Esercizio 2
    (a)
    Cosa e' una Segnatura Σ per la logica dei predicati del prim'ordine (calcolo dei predicati)? Fornire la definizione di struttura AΣ per una segnatura Σ.
    (b)
    Dimostrare in deduzione naturale che ¬ A → ¬B |- B → A e che ¬(A → B) |- ¬ B
    Dimostrare una delle due cose utilizzando il teorema di correttezza e completezza.
    (c)
    Cosa si intende con numero di Goedel di una formula di PA?
    Enunciare alcuni risultati limitativi della logica.


    Esercizio 3
    Sia add il lambda termine λnmfx.nf(mfx) che rappresenta la somma nel lambda calcolo. Utilizzare tale termine per calcolare 1+1, mostrando i vari passaggi nel calcolo.