Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame31 agosto 2022 Informatica teorica Esercizio 1 (7 punti) L={an bm co d;n, m, o∈N, n≥1, o≥0, m= 2n+o}. Utilizzare un formalismo a potenza minima (tra tutti quelli visti a lezione) che caratterizzi il linguaggioL. Soluzione Il linguaggio `e libero dal contesto, riconoscibile da un automa a pila deterministico. Riscrivere la definizione comeL={an b2 n bo co d;n, o∈N, n≥1}rende evidente la natura del linguaggio. Per riconoscerlo `e sufficiente impilare un simbolo per ognia, spilarne uno ogni dueb, fino a quando la pila `e vuota. Per lebsuccessive, impilare un simbolo per ognibe spilare un simbolo per ogni ceffettua il conteggio del valoreo, al termine del quale `e sufficiente riconoscere la presenza della singolad.q 0q 1q 2q 3q 4q 5aZ 0/Z 0AaA/AAbA/A bA/εbA/A bZ 0/Z 0BdZ 0/Z 0bB/BB cB/εcB/ε dZ 0/Z 0Esercizio 2 (9 punti). Chi ha diritto alla riduzione del 30% della prova svolga unica- mente il punto 1. 1.` E possibile determinare se una generica macchina di Turing universale si arresta per ogni ingresso? 2.` E possibile trovare, data la terza (secondo l’enumerazione di G¨odel) macchina di Turing universaleM, almeno un ingresso per cui essa non si arresta? 3.` E possibile, data la macchina di Turing universaleMdi cui sopra, dire se essa si arresta per un generico ingresson? Soluzione 1/5 1.S`ı: `e possibile infatti stabilire che una qualunque MTU non si arresta per qualche input. Una MTU `e in grado di emulare il comportamento di qualunque altra MT, il cui comportamento `e codificato in parte del suo nastro di ingresso. Esiste quindi almeno un ingressonche corrisponde a una MT che non si arresta per alcun input. Di conseguenza, non `e vero che la MTU si arresta per ogni input fornito: essa infatti non si arresta almeno sull’inputn. 2.S`ı, `e sufficiente considerare l’ingresso corrispondente alla codifica del comportamento di unaMT che va sempre in loop. 3.Intuitivamente: no, l’ingressonrappresenta il comportamento di una generica MT di cui servirebbe determinare se si arresta o meno a fronte di un generico ingresso. Pi`u formalmente, `e possibile ridurre la soluzione dell’halting problem alla soluzione del problema in questione.Si supponga che esista un algoritmoA(n), che riceve in ingresso una stringancorrispondente all’input della MTUMe determina seMsi arresta quando eseguita con inputn. Data infatti una generica MTM yed un generico input xdi cui si vuole determinare la terminazione, `e sufficiente codificare la coppia⟨M y, x ⟩nel formato accettato daM, ottenendo la stringa ¯n. A questo punto, invocandoA(¯n) sarebbe possibile risolvere l’halting problem per la generica instanzaM y( x), il che `e assurdo, data l’indecidibilit`a dello stesso. 2/5 Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame31 agosto 2022 Algoritmi e strutture dati Esercizio 3 (8 punti) Si abbiano due numeri interixey, conx < y. Si consideri il problema di partizionare una lista semplice, cio`e con il solo puntatore al nodo successivo, in tre liste contenenti valori rispettivamente minori dix, compresi traxey, e maggiori diy. Si scriva lo pseudo-codice della procedura richiesta e se ne valutino le complessit`a spaziale e temporale. Soluzione 1t r i - p a r t ( x , y , l i s t ) 2l e f t : = c e n t e r : = r i g h t : = N I L 3w h i l e l i s t ! = N I L 4i f l i s t . k e y < x t h e n 5l e f t : = n o d e ( l i s t . k e y , l e f t ) 6i f l i s t . k e y > y t h e n 7r i g h t : = n o d e ( l i s t . k e y , r i g h t ) 8e l s e 9c e n t e r : = n o d e ( l i s t . k e y , c e n t e r ) 10l i s t : = l i s t . n e x t 11r e t u r n ( l e f t , c e n t e r , r i g h t ) Le complessit`a richieste sono entrambe Θ(n), connlunghezza della lista, essendoci un’unica scansione della stessa con copia dei valori contenuti. Esercizio 4 (8 punti). Chi ha diritto alla riduzione del 30% della prova svolga unica- mente il punto 1. Si consideri la seguente funzioneg, che riceve un array di interiae restituisce un intero: 1g ( a ) 2i f a . l e n g t h≤1 3r e t u r n 1 4k : = g ( a [ 1 . . n / 2 ] ) 5j : = g ( a [ n / 2 + 1 . . n ] ) 6f o r h : = 1 t o a . l e n g t h 7i : = 1 8w h i l e i≤a . l e n g t h 9i : = i * 2 10k : = k + i * a [ h ] 11j : = j - i * a [ h ] 3/5 12 r e t u r n ( k + j ) / 2 Dettanla lunghezza dell’arraya, 1.si scriva la ricorrenza associata al codice della funzione; 2.si fornisca un limite asintotico superiore (possibilmente stretto) per la complessit`a temporaledig(a)in funzione din. Soluzione La ricorrenza associata al codice della funzione `e: T(n) =( Θ(1) sen≤1 2T(n/2) + Θ(nlog(n)) sen >1o anche T(n) =( 1 sen≤1 2T(n/2) +nlog 2( n) sen >1 La funzionef(n) =nlog 2( n) cresce pi`u velocemente di Θ(nlog 22 ) = Θ(n), ma non polinomial- mente pi`u velocemente. Pertanto non si pu`o applicare il teorema dell’esperto.Osserviamo cheT(n) cresce pi`u velocemente diT′ (n) = 2T′ (n/2) +nma meno diT′′ (n) = 2T′′ (n/2) +n1+ ϵ , per ogniϵ >0 (le relazioniT(n)≥T′ (n) eT(n)≤T′′ (n) si mostrano per banale induzione). PertantoT(n)∈Ω(nlogn) eT(n)∈O(n1+ ϵ ). Intuitivamente, ha quindi senso ipotizzare una complessit`a che sia pi`u alta di Θ(nlogn), ma non polinomialmente pi`u alta. Formuliamo allora l’ipotesi cheT(n)≤cn(log 2n )2 e procediamo per sostituzione. T(n/2)≤cn/2(log 2( n/2))2 Ipotesi induttiva T(n)≤cn(log 2( n/2))2 +nlog 2( n) Sostituzione cn(log 2( n/2))2 +nlog 2( n)≤cn(log 2n )2 Da verificare asintoticamente c(log 2( n/2))2 + log2( n)≤c(log 2n )2 (n >0) c((log 2n )2 −(log 2( n/2))2 )≥log 2( n) c((log 2n )2 −(log 2n −1)2 )≥log 2( n) c(2 log 2n −1)≥log 2( n) c≥12 +12 2 log 2n −1 Quest’ultima relazione `e sempre soddisfatta pern >1 ec≥1. Nel caso base,c1(log 2(1))2 = 0̸≥T(1) = 1. Tramite la ricorrenza otteniamoT(2) = 2T(1) + 2 log2(2) = 4 e T(3) = 2T(1) + 3 log 2(3) = 2 + 3 log 2(3); inoltre 4 ≤c2(log 22)2 e 2 + 3 log2(3) ≤ c3(log 23)2 valgono entrambe perc≥2 e pern >3 la ricorrenza non dipende pi`u daT(1). La relazione `e soddisfatta anche nel caso base e quindiT(n) =O(n(logn)2 ). Si dimostra analogamente cheT(n)≥dn(log 2n )2 . Questa relazione `e soddisfatta se d≤12 +12 2 log 2n −1, il che vale, ad esempio, perd≤1/2. Nel caso base,T(1) = 1≥d1(log 2(1))2 = 0. Quindi T(n) = Ω(n(logn)2 ). 4/5 Allora complessivamente T(n) = Θ(n(logn)2 ).Un altro modo per risolvere la ricorrenza consiste nell’effettuare un cambio di variabile: T(2m ) = 2T(2m −1 ) + 2m mPoniamom= log 2n e quindin= 2m T(2m )/2m = 2T(2m −1 )/2m +mDividiamo per 2m S(m) = 2T(2m −1 )/2m +mDefiniamoS(m) =T(2m )/2m S(m) =S(m−1) +mQuindiS(m−1) = 2T(2m −1 )/2m S(m) =S(m−2) +m−1 +mProcedo per sostituzioni successive . . . S(m) =S(0) + 1 + 2 +. . .+m−1 +mConS(0) =T(20 )/20 = 1 S(m) = Θ(m2 ) T(2m )/2m = Θ(m2 ) T(n)/n= Θ((logn)2 ) T(n) = Θ(n(logn)2 ) 5/5