API 2017 09 29

Page 1

Algoritmi e Principi dell’Informatica Appello del 29 settembre 2017 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 2 ore. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 in 1 ora. NB: i punti attribuiti ai singoli esercizi hanno senso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (8 punti) Si specifichi in logica del prim’ordine la funzione unaria f, definita per tutti gli interi non negativi: detto n l’argomento della funzione f, essa restituisce la somma degli interi da 1 a n. Ad esempio, f(5) vale 15 (cioè 1+2+3+4+5). Oltre ai connettivi logici, quantificatori e punteggiatura consentiti nella logica del prim’ordine, nella specifica si può fare uso esclusivamente dei seguenti simboli:  La funzione binaria di somma (da indicarsi con il consueto simbolo + e notazione infissa);  La funzione binaria di sottrazione (come sopra, con il simbolo –);  I predicati binari ‘=’, di uguaglianza e ‘>’, di confronto tra interi;  Le costanti 0 e 1. Esercizio 2 (8 punti) Sia m una funzione binaria che, dato un indice di macchina di Turing (MT) y e un ingresso x, restituisce il numero di mosse che impiega tale MT a terminare l’esecuzione su tale ingresso; m è indefinita qualora la macchina non termini. 1. La funzione m è calcolabile? 2. È decidibile il problema di stabilire se, data una generica MT con indice y, esista un ingresso x tale per cui a. m(y,x) = 0? b. m(y,x)  y? c. m(y,x)  ? Spiegare brevemente ma esaurientemente e con chiarezza le risposte. Esercizio 3 (6 punti) Si consideri il linguaggio Lc = {x.y in {0,1,2} * | con |x| = |y|, e tali che x e y coincidano…