Fondamenti di Informatica, 4 Febbraio 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) Definire brevemente, ma formalmente , la nozione di passo di computazione nel contesto
    - degli automi a stati finiti
    - delle macchinedi Turing
    - del λ-calcolo
    - delle URM
    - del formalismo delle funzioni primitive ricorsive
    - della Logica di Hoare

    (b) Si consideri la Macchina di Turing definita da
    Γ = {a,b}
    Q = {q0,q1,q2,qF}
    F = {qF}
    stato iniziale = q0
    e dalla seguente tabella di transizione: 
         a         b       blank
----------------------------------
q0 | a,q2,D | b,q1,D |            |
   -------------------------------
q1 | a,q0,D | b,q2,D |            |
   -------------------------------
q2 | a,q1,D | b,q2,D | blank,qF,I |
----------------------------------
    E' possibile capire subito se questa macchina di turing riconosce un linguaggio regolare? Perche'?

    (c) Dimostrare che un linguaggio non-regolare ha un numero infinito di stringhe.
    Esercizio 2
    (a) Data una segnatura Σ per la logica dei predicati del primo ordine, definire l'insieme dei termini sulla segnatura Σ (TermΣ) e l'insieme delle formule ben formate (FbfΣ).
    Data inoltre una struttura AΣ ed una formula ben formata α in FbfΣ, si dica quando α e' soddisfacibile in AΣ, α e' vera in AΣ (valida in AΣ), α e' valida (o vera), α e' contradittoria.
    (b) Si prendano in considerazione le seguenti definizioni (testo Martini):
    A ∨ B = ((¬A) → B)
    A ∧ B = ¬(¬A ∨ ¬B)
    Dimostrare che, dato un assegnamento proposizionale,
    - la formula A ∧ B e' vera (il suo valore di verita' e' 1) se e solo se A e' vera e B e' vera
    - la formula A ∨ B e' falsa (il suo valore di verita' e' 0) se e solo se A e' falsa e B e' falsa

    (c) Si consideri la seguente formula della logica dei predicati del prim'ordine su una segnatura che contenga i simboli di predicato unari A e B:
    (∃x.A(x)→∃x.B(x)) →(∃x.A(x)∧B(x))
    Dimostrare che tale formula non e' valida.
    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".