Fondamenti di Informatica, 19 Giugno 2014

Non e' ammesso l'uso di alcun testo, appunti, calcolatrici o qualsivoglia app per 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, 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) Si consideri la seguente stringa di 8 bit:

10101010

ottenuta applicando una funzione di codifica ad un numero n.
Dire qual e' il valore di n (e, sinteticamente, come si e' ottenuto) quando la codifica e':

(i) codifica posizionale a lunghezza fissa (8) in base due a per numeri naturali
(ii) codifica posizionale a lunghezza fissa (6) in base due a per numeri naturali
(iii) codifica posizionale a lunghezza variabile in base due per numeri naturali
(iv) codifica posizionale a lunghezza fissa (8) in base tre per numeri naturali
(v) codifica posizionale a lunghezza fissa (8) in base uno per numeri naturali
(vi) codifica posizionale a lunghezza fissa (8) in base 2 in complemento a due per numeri interi
(vii) codifica posizionale a lunghezza variabile in base 2 in complemento a due per numeri interi

(b) Fornire brevemente la definizione di codice ad espansione con configurazione di espansione. Fornire un codice ad espansione con configurazione di espansione per l'insieme {pippo, pluto, paperino, paperoga, minni} utilizzando due formati: un bit e tre bit. Qual e' il vantaggio, in questo caso, rispetto ad un codice a formati multipli predefiniti?

(c) Presa la rappresentazione di un numero negativo utilizzando la codifica in complemento a due con n cifre, dimostrare che la rappresentazione dello stesso numero, ma con la codifica in complemento a due con n+m cifre, si ottiene aggiungendo m volte "1" alla sinistra.

Esercizio 2
(a) Sia {{},{s¹, p¹, a²}} una segnatura dove s e p sono simboli predicativi unari, mentre a un simbolo predicativo binario. Interpretando s(x) come "x e' uno studente", p(x) come "x e' un professore", a(x,y) come "x apprezza y" tradurre la seguente frase (scrivete cioe' la formula ben formata corrispondente, avendo a disposizione entrambi i quantificatori e tutti i connettivi logici):

Alcuni studenti apprezzano tutti i professori, altri no.

(b) Dimostrare che

(∀ x.∃ y. ¬ P(x,y)) → (∃ y. ¬ P(y,c))

dove c e' una costante, non e' derivabile nella logica del prim'ordine.
(c) Si consideri la logica dei predicati in deduzione naturale con uguaglianza.
Fornire una dimostrazione di

pippo=giuseppe |- ∀ x.(cugino(x,pippo) → cugino(x,giuseppe))

Ricordiamo che le due regole per l'uguaglianza in deduzione naturale che sono utili per la dimostrazione sono le seguenti:

-------
x = x

x₁ = y₁ ... x_n = y_n
-------------------------------------------------
A[x/z] → A[y/z]

Dove A e' un qualsiasi simbolo di predicato n-ario. Inoltre con la notazione x indichiamo una sequenza x₁....x_n di variabili.

Esercizio 3
Enunciare il Pumping Lemma e dimostrarlo. Descrivere brevemente un suo possibile utilizzo.