Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame12 luglio 2022 Informatica teorica - Tempo a disposizione: 1 ora Esercizio 1 (8 punti) Si costruisca una grammatica o automa o formula logica a potenza minima per il seguente linguaggio: {a2 n Σ+ b3 n |n >0} ∪ {Σ+ b3 n |n >0}, con Σ ={a, b}. Soluzione Il linguaggio `e aperiodico (o “star-free”), in quanto{a2 n Σ+ b3 n |n >0} ⊂ {Σ+ b3 n |n >0}= Σ+ .b3 . Si pu`o dunque esprimere con la seguente formula MFO: ∃y(y >0∧b(y)∧b(y+ 1)∧b(y+ 2)∧last(y+ 2)). Esercizio 2 (8 punti). Chi ha diritto alla riduzione del 30% della prova svolga solo il punto 3. 1.Dire se `e decidibile il problema di stabilire se due programmi, uno scritto in C e uno scrittoin Java, calcolano la stessa funzione. 2.Dire se `e decidibile il problema di stabilire se due programmi, entrambi scritti in C, sonoidentici, salvo per il fatto che i nomi delle variabili usate sono diversi tra un programma e l’altro. 3.Dire se `e decidibile il problema di stabilire se, dato un programma C che fa uso di puntatori,esiste un’esecuzione in cui, ad un certo punto, due variabili puntano entrambe allo stesso indirizzo (fenomeno dell’aliasing). Soluzione 1.L’equivalenza di programmi C e Java `e indecidibile, si pu`o vedere riducendo il problemadell’equivalenza tra due programmi C a quella tra un programma C e un programma Java: ogni programma C pu`o essere trasformato in un equivalente programma Java, e se fosse decidibile l’equivalenza tra programma Java e programma C, allora potremmo anche decidere l’equivalenza tra programmi C, che non `e possibile. 1/4 2.Il problema `e decidibile, in quanto si tratta di leggere i 2 programmi parola per parola. Laddove si trovano dichiarazioni di variabili (che devono essere in corrispondenza una con l’altra), si memorizza una corrispondenza tra la variabilev 1del programma P 1e quella (chiamiamolav 2) del programma P 2, e si controlla poi che ogni volta che nel programma P 1 compare la variabilev 1, nel programma P 2compare v 2. In questo modo, dopo aver letto per intero i programmiP 1e P 2, se non si sono trovate discrepanze, si conclude che i programmi sono effettivamente identici a meno dei nomi delle variabili, altrimenti no. 3.Il problema non `e decidibile, lo si pu`o vedere per riduzione dal problema della terminazionedei programmi C. Pi`u precisamente, si consideri un generico programmaP, espresso inC. Nel caso in cuiPusi puntatori, `e possibile sempre ri-esprimere lo stesso calcolo in C senza usare puntatori: assumiamo dunque chePnon ne faccia uso. Dato quindi il programmaPed un generico suo inputa, possiamo scrivere un nuovo pro- grammaP′ che prende come inputae, in sequenza •dichiara due puntatori,xey(che non compaiono inP, dato che inPnon compare alcun puntatore); •assegna loro due valori diversi; •eseguePsuae, se la computazione termina, assegnaxay, creando quindi un alias tra xey. ChiaramentePtermina su inputase, e solo se, inP′ ad un certo puntoxeypuntano allo stesso indirizzo. Quindi, se il problema desiderato fosse decidibile, lo sarebbe anche quello della terminazione diPsu un generico inputa, il che `e impossibile. 2/4 Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame12 luglio 2022 Algoritmi e strutture dati - Tempo a disposizione: 1 ora Esercizio 3 (8 punti) Sia dato un albero binario di ricerca, contenentenchiavi intere, dove sono presenti chiavi duplicate. •Si realizzi la proceduraTrueSuccessorche, dato un riferimento ad un nodoxdell’albero restituisce un elemento contenente la pi`u piccola chiave strettamente maggiore dix.key. •Si realizzi la proceduraBSTToQueueche, dato un BST con duplicati, lo trasforma in una coda di elementi, senza duplicati, ordinata, dove il primo elemento in coda `e l’elemento con chiave minima. Si fornisca lo pseudocodice di tutte le procedure e se ne valuti la complessit`a temporale. Soluzione La proceduraTrueSuccessor(x) si limita ad invocare la proceduraSuccessor(x) fino a quando il nodo successore non ha effettivamente chiave diversa da quello di partenza. TrueSuccessor(x) 1y←Successor(x) 2whiley̸ = NILandy.key=x.key 3y←Successor(y) 4returny La complessit`a risultaT(n)∈ O(n): nel caso pessimo l’albero `e completamente sbilanciato e l’unica chiave `e ripetuta in ogni nodo.La proceduraBSTToQueueutilizzaTrueSuccessorper scandire il BST in una singola passata, dall’elemento pi`u piccolo al pi`u grande, accodando gli elementi. BSTToQueue(T) 1ifT= NIL 2returnNIL 3i←min(T) 4Enqueue(Q, i) 5i←TrueSuccessor(i) 6whilei̸ = NIL 7Enqueue(Q, i) 8i←TrueSuccessor(i) 9returnQ L’attraversamento indotto daBSTToQueuecorrisponde a un attraversamento simmetrico, che visita i nodi in ordine crescente del valore di chiave e richiede pertanto tempo Θ(n). 3/4 Esercizio 4 (8 punti). Chi ha diritto alla riduzione del 30% della prova analizzi unica- mente il punto 3. Si considerino le seguenti ricorrenze e se ne fornisca un limite superiore asintotico 1.T(n) = 3T(n27 ) + 2 √n 2.T(n) = 16T(n2 ) + n5 3.T(n) = 2T(n2 ) + ( ncos(n))2 Soluzione 1.Master theorem, caso 3,n crit= log 27(3) =13 . Condizione di regolarit`a automaticamente soddisfatta in quantof(n) `e un polinomio.T(n)∈Θ(2 √n ) 2.Master theorem, caso 3,n crit= log 2(16) = 4. Condizione di regolarit`a automaticamente soddisfatta in quantof(n) `e un polinomio.T(n)∈Θ(n5 ). 3.Master theorem non applicabile poich´ef(n) = (ncos(n))2 non `e polinomialmente n´e pi`u grande, n´e pi`u piccolo dinlog 2(2) =n, n´e in Θ(n), a causa delle oscillazioni del coseno. Si osservi per`o che cos(n) `e limitato superiormente da 1 (ovviamente anche pern→+∞). Abbiamo quindi cheT(n) sar`a limitato superiormente daT′ (n) = 2T(n2 ) + n2 , il che si mostra semplicemente per induzione. Applicando il MT aT′ (n) (caso 3) otteniamo cheT′ (n)∈Θ(n2 ) e quindiT(n)∈ O(n2 ). 4/4