API 2018 07 19

Page 1

Algoritmi e Principi dell’Informatica Appello del 19 luglio 2018 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. Si considerino le seguenti formule del prim’ordine, interpretate sui numeri interi (relativi): • F1: A(x) « $z(z > 0 Ù x = 2 × z) • F2: B(x, y) « x > 1 Ù $z(1 < z < y Ù y = x × z) • F3: C(x) « x > 0 Ù ¬$z(B(z, x)) • F4: "x(A(x) ® $z$w(C(z) Ù C(w) Ù x = z + w)) Esercizio 1 (8 punti) Si consideri ora la formula FT: F4 Ù "x(F3) Ù "x"y(F2) Ù "x(F1) Che proprietà dei numeri interi esprime FT? Spiegare brevemente i motivi della risposta. Esercizio 2 (8 punti) 1. È decidibile il problema di stabilire se FT, interpretata sui numeri interi è vera? 2. Si consideri ora la formula FL: A(x) ® (C(z) Ù C(w) Ù x = z + w) Ù "x(F3) Ù "x"y (F2) Ù "x (F1) È decidibile il problema di stabilire se FL, interpretata sui numeri interi è soddisfacibile? Esercizio 3 (8 punti) Si fornisca un limite asintotico superiore per l’espressione T(n) definita dalla seguente equazione di ricorrenza: T(n) = T(n/2) + n(2 + sin(np/2)). Esercizio 4 (8 punti) Si consideri il seguente problema: dati in ingresso un automa a stati finiti e uno dei suoi stati finali, sia esso q, si deve dire se q è raggiungibile dallo stato iniziale. Si descriva un algoritmo per il problema e se ne valuti la complessità temporale. Tracce delle soluzioni Esercizio 1 • F1: A(x) esprime il fatto che x sia un numero pari positivo • F2: B(x,y) esprime il fatto che x…