Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

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 f ormule 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. Eser cizio 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) È decidibil e 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( n p /2) ). Esercizio 4 ( 8 punti) Si cons ideri 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 solu zioni Esercizio 1 • F1 : A(x) esprime il fatto che x sia un numero pari positivo • F2 : B(x,y) esprime il fatto che x sia un divisore (non banale) di y • F3 : C(x) esprime il fatto che x sia un numero primo oppure il numero 1 • Quindi la congiunzione FT esprime il fatto che ogni numero pari sia la somma d i due numeri che sono o primi o 1. ( Questo enunciato è simile alla nota congettura di Goldbach , secondo cui ogni numero pari è la somma d i due numeri prim i . ) Esercizio 2 • FT è una formula chiusa: essa è vera o falsa, ma in ogni caso il fatto che sia vera o falsa è decidibile, anche se non ancora deciso. • Analogamente, una formula contenente variabili libere è soddisfacibile se e solo se esiste un assegnamento di valori ad esse (nel dominio di interpretazione) che la rende vera; quindi il problema è “chiuso” anche in questo caso. Inoltre la formula è soddisfatta ad esempio per x = 20, z = 13, w = 7. Esercizio 3 Il Master Theorem non si può applicare poiché è violata la seguente condizione (di “regolarità”): n/2(2+sin(( n p /2) /2)) ≤ cn(2+sin ( n p /2) ), per n grande e c 0). Occorre poi verificare la condizione iniziale, che è soddisfatta, ad esempio con T(1) = 1. Questo conclude la verifica e conferma che T(n ) = O(n). 2) Un secondo modo consiste nel notare come l’espressione f(n) = n(2 + sin( n p /2) ) sia maggiorata da g(n) = 3n. La ricorrenza ottenuta sostituendo n(2 + sin( n p /2) ) con 3n, indicata di seguito con T’, è risolvibile con il teorema dell’esperto: T’(n) = T’(n/2) + 3n R icad iamo infatti nel terzo caso del teorema e otten iamo T’(n)= Θ (n). A questo punto basta osservare che T(n) ≤ T’( n) per concludere che T(n) = O(n). Il fatto intuitivo che T(n) ≤ T’( n) può essere mostrato per induzione come segue. Cas o base: basta porre T ’ (1) = T(1); la relazione T(1) ≤ T’(1) è quindi verificata per costruzione. (Si noti che il teorema dell’esperto non dipende dalla scelta di T’(1), che non ha impatto sul comportamento asintotico di T’(n).) Ipotesi induttiva: T(i) ≤ T’ (i) per tutti i valori di i da 1 a n. Passo induttivo : s e vale l’ipotesi induttiva, allora T(n+1) ≤ T’(n +1). Infatti, espandendo le ricorrenze per T(n+1) e T’(n+1), tutti i termini della prima sono ≤ dei termini della seconda, ossia: T(n+1) = T((n+1)/2) + f(n+1) T’(n+1) = T’((n+1)/2) + g(n+1) laddove T((n+1)/2) ≤ T’((n+1)/2) per ipotesi induttiva e f(n+1) ≤ g(n+1). Esercizio 4 Si memorizza l’automa come grafo e si fa una visita in ampiezza a partire dallo stato iniziale: appena q viene raggiunto, si risp onde positivamente. Se alla fine della visita q non viene raggiunto, si risponde negativamente. La valutazione della complessità è esattamente la stessa di una visita in ampiezza: O(|V|+|E|).