Fondamenti di Informatica, 3 Ottobre 2018

Non e' ammesso l'uso di alcun testo, appunti, calcolatrici, telefonini o smartphone (questi ultimi vanno riposti lontano dalla propria persona). Le risposte vanno scritte nel foglio di bella copia. Si raccomanda la massima SINTETICITA'. L'eccessiva verbosita' verra' considerata negativamente.
  • Per sostenere l'esame e' obbligatorio essersi prenotati sul portale studenti del nostro ateneo. Elaborati di studenti non prenotati NON verranno valutati.
  • I risultati verranno indicati nella pagina web del corso. Date ed orari degli orali, sul Forum.


    • Esercizio 1
    (a) Fornire le definizioni formali di automa a stati finiti deterministico e non deterministico.

    (b) Si fornisca una macchina di Turing che, preso un numero intero n rappresentato in complemento a due, restituisca la rappresentazione in complemento a due del numero -n-1.
    Giustificare il procedimento utilizzato.

    (c) Fornire le definizioni di linguaggio decidibile e di linguaggio semidecidibile. Fornire informalmente un algoritmo di semidecisione per linguaggi di tipo 1 (contestuali).
    Esercizio 2
    (a) Nel contesto della Logica Proposizionale (Calcolo Proposizionale), fornire le definizioni di (b) Sia {{}, {ssa1, epa1, s2} } una segnatura senza simboli di funzione, dove 'ssa' ed 'epa' sono simboli di relazione unari, e 's' e' un simbolo di relazione binario. Supponendo di avere come dominio (supporto della struttura) l'insieme degli studenti e degli esami, ed interpretando ssa(x) come "x e' uno studente del secondo anno", epa(x) come "x e' un esame del primo anno" ed s(x,y) come "lo studente x ha superato l'esame y", si fornisca la formula ben formata il cui significato, nell'interpretazione fornita, corrisponda alla seguente frase in italiano:
    Non tutti gli studenti del secondo anno hanno superato tutti gli esami del primo,
    ma tutti ne hanno superato almeno uno

    (c) Dimostrare il seguente teorema della logica proposizionale:
    Se Γ∪{α} e' contraddittorio, allora Γ |- ¬ α
    Esercizio 3
    Descrivere brevemente cosa si intende per Semantica Operazionale Strutturata e fornire la regola per il costrutto while del linguaggio WHILE.