Fondamenti di Informatica, 4 Ottobre 2013

Non e' ammesso l'uso di alcun testo, appunti, calcolatrici, telefonini o 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, comunicarlo immediatamente al docente o all'assistente in aula ed indicarlo chiaramente sull'elaborato che si consegna.
  • I risultati verranno indicati nella pagina web del corso. Date ed orari degli orali, sul Forum.

    • Esercizio 1
    (a) Fornire la definizione precisa di Sistema Formale. Elencare i nomi di almeno quattro sistemi formali.

    (b) Definire la nozioni di Giudizio e Validita' per la semantica operazionale strutturata.

    (c) Supponiamo di voler introdurre nel linguaggio WHILE un nuovo tipo di istruzione della seguente forma:   for X1 do δ
    La semantica informale di tale istruzione e' la seguente: si ripete l'esecuzione di δ tante volte quanto e' il valore della variabile X1, ed ogni volta che si esegue δ il valore di X1 viene decrementato automaticamente, a meno che non venga modificato esplicitamente da un assegnamento. Il ciclo termina quando X1 contiene 0.
    Esercizio 2
    (a) Preso un alfabeto Σ, definire formalmente l'insieme Σ*.
    Dimostrare come, se si considera Σ={a,b,c}, gli elementi dell'insieme Σ* possano venir messi in corrispondenza biunivoca con i numeri naturali.

    (b) Dimostrare che, preso un alfabeto Σ (per esempio il Σ del punto precedente), i linguaggi su Σ non possono venir messi in corrispondenza biunivoca con i numeri naturali.

    (c) Usare il metodo di Diagonalizzazione per dimostrare che ci sono funzioni calcolabili che non sono primitive ricorsive.
    Esercizio 3
    Nella logica dei predicati del primo ordine (calcolo dei predicati), si specifichi una segnatura Σ, una struttura AΣ e la formula ben formata vera in AΣ, corrispondente alla seguente affermazione:
    Tutti i conoscenti comuni a Mario e ad Antonio sono italiani, ma Mario ha anche conoscenti francesi.