Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame10 gennaio 2023 Informatica teorica Esercizio 1 (8 punti) Si considerino i linguaggi seguenti: •L 1= {an bn cn |n >0} •L 2= {b}∗ .{a, b, c}+ Per ciascuno dei linguaggi indicati di seguito, utilizzare un formalismo a potenza minima (tra tutti quelli visti a lezione) che lo caratterizzi: 1.L=L 1\ L 2, dove il simbolo \indica la differenza insiemistica; 2.L′ =L 1∪ L 2. Chi ha diritto alla riduzione del 30% svolga unicamente il punto 1. Soluzione Il linguaggio sottraendo (L 2) contiene tutte le stringhe di almeno un carattere e quindi contie- ne anche tutte le stringhe del linguaggio minuendo (L 1), pertanto L`e il linguaggio vuoto. Per caratterizzarlo, `e sufficiente una formula MFO insoddisfacibile, come la seguenteφ L: φL: ∃x(a(x)∧ ¬a(x)). Per lo stesso motivo, abbiamoL′ =L 2, che `e chiaramente regolare, in quanto specificato dall’e- spressione regolare (b)∗ .(a|b|c)+ . Tuttavia `e possibile caratterizzareL′ anche mediante una formula MFO, ad esempio con la formulaφ L′ seguente: φL′ : (a(0)∨b(0)∨c(0))∧ ∀x(a(x)∨b(x)∨c(x)). Esercizio 2 (8 punti). Si assuma che le macchine di Turing su alfabeto binario calcolino funzioni daZaZ, interpretando le stringhe sul nastro come numeri in complemento a 2 codificati con il numero minimo di bit necessari. Si considerino i seguenti insiemi e si dica se essi sono ricorsivi, motivando la risposta: 1.S 1= {i| ∃x:f i( x)>0} 2.S 2= {i| ∃x:f i( x)≤0} 3.S 3= S 1∪ S 2 4.S 4= S 1∩ S 2 1/4 Soluzione Sono tutti non ricorsivi per il teorema di Rice, come spiegato in dettaglio nel seguito. 1.S 1contiene tutti e soli gli indici delle funzioni che hanno valore positivo per almeno un input. Questo insieme non `e banale in quanto contiene, ad esempio, l’indice della funzione costante f(x) = 1, ma non quello della funzione costanteg(x) = 0 (si noti che la funzionefnon deve per forza essere totale). 2.S 2contiene tutti e soli gli indici delle funzioni che hanno valore negativo o nullo per almeno un input. Questo insieme non `e banale in quanto contiene, ad esempio, l’indice della funzione g(x) = 0, ma non quello della funzionef(x) = 1. 3.S 3non `e un insieme banale in quanto contiene almeno un indice (`e l’unione di due insiemi non vuoti) e non contiene, ad esempio, l’indice della funzione ovunque non definitah(x) =⊥. 4.S 4sono gli indici delle MT che calcolano funzioni che assumono valori sia positivi che negativi o nulli, ad es. la funzione segno. Dunque `e non banale anch’esso. 2/4 Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame10 gennaio 2023 Algoritmi e strutture dati Esercizio 3 (8 punti) Si consideri il seguente linguaggio su alfabeto{0,1, c}: L={xcy|x, y∈ {0,1}+ ey=xmod 3,sexeysono interpretate come numeri in base 2}. Si assuma chexeysiano numeri naturali codificati (in binario) con la cifra pi`u significativa a sinistra. Si descrivano una macchina di Turing a nastro singolo e una macchina RAM che riconoscanoLe se ne valutino le complessit`a con tutti i criteri di costo applicabili. Chi ha diritto alla riduzione del 30% descriva solamente la macchina di Turing a nastro singolo. Soluzione Il linguaggioL`e regolare. Infatti, ci sono solo 3 resti possibili di una divisione per 3 e per capire a quale classe di modulo appartengax`e sufficiente una scansione lineare dei simboli dixsenza bisogno di usare memoria aggiuntiva. Se una generica stringa binariazha un valoreval(z) tale per cuival(z) mod 3 =p, conp∈ {0,1,2}, allora se alla stessa stringa si accoda il simboloa∈ {0,1}, la sequenzazavarr`a 2val(z) +ae quindi avr`a moduloval(za) mod 3 = (2p+a) mod 3. Per ogni valore dipe ogni simboloa`e quindi definita la nuova classe di modulo, che si pu`o quindi determinare con un semplice automa a stati finiti. Appena viene incontrata lac, si pu`o infine verificare che la classe di modulo cos`ı determinata corrisponda al suffissoydella stringa in ingresso. Sia la MT sia la RAM faranno quindi una scansione lineare della stringa in ingresso (T M T( n) = TRAM( n) = Θ(n)) senza utilizzare memoria aggiuntiva (quindiS M T( n) = Θ(n) per la MT, visto che comunque la memoria sar`a occupata dalla stringa in ingresso, eS RAM( n) = Θ(1)). Si noti che, in questo caso, non c’`e differenza tra il costo della RAM calcolato a criterio di costo costante e quello calcolato a criterio di costo logaritmico. Esercizio 4 (8 punti) Definire un algoritmomaxPitagora(con la migliore complessit`a possibile) che prende in input un arrayAdi elementi interi positivi (quindi strettamente maggiori di 0) e, se esiste inAalmeno un valore tale che il suo quadrato `e la somma dei quadrati di altri 2 valori anch’essi presenti inA, restituisce il massimo di tali valori; altrimenti (se nessun elemento diA`e tale che il suo quadrato `e la somma dei quadrati di altri 2 elementi diA) restituisce 0. Valutare la complessit`a dell’algoritmo ideato. Soluzione Un possibile algoritmo che risolve il problema desiderato `e il seguente. 3/4 maxPitagora (A) 1merge-sort(A) 2allocateBof lengthA.length 3fori:= 1 toB.length 4B[i] :=A[i]∗A[i] 5fori:=B.lengthdownto 3 6ifexact-sum-no-sort(B[1. . i−1], B[i]) 7returnA[i] 8return0 Si noti che l’algoritmoexact-sum-no-sort`e una variante dell’algoritmoexact-sumvisto a eser- citazione, senza per`o l’ordinamento iniziale (in quanto l’array in inputB[1. . i−1] `e gi`a ordinato). Inoltre, si noti che il ciclo delle righe 3-4 copia il contenuto diAin un altro array,B, elevando al contempo ogni valore al quadrato, per tenere traccia del valore iniziale di ogni elemento, prima dell’elevamento al quadrato (il problema chiede di restituire il valore dell’array originale, non il suo quadrato). Si poteva evitare di introdurre un nuovo array di supporto modificando ulteriormente l’algoritmoexact-sumin modo che non solo non venga fatto l’ordinamento, ma il confronto venga fatto tra i quadrati dei valori presenti nell’array, invece che tra i numeri originali. Si ricorda che l’algoritmo diexact-sum, nella parte di ricerca degli elementi, ha complessit`aO(n), quindi l’algo- ritmomaxPitagoraha complessit`aO(n2 ) (la complessit`a dell’algoritmo `e ovviamente dominata dal ciclo 5-7, in quantomerge-sortha complessit`a Θ(nlog(n)), e il ciclo 3-4 ha complessit`a Θ(n)). Per completezza, riportiamo anche la versione che non richiede l’allocazione di un nuovo array (maxPitagora-no-copy) e l’algoritmo diexact-sumsenza ordinamento e che in pi`u esegue il confronto tra i quadrati dei valori (exact-sum-no-sort-squares): maxPitagora-no-copy(A) 1merge-sort(A) 2fori:=A.lengthdownto 3 3ifexact-sum-no-sort-squares(A[1. . i−1], A[i]) 4returnA[i] 5return0 Exact-sum-no-sort-squares(A, x) 1i:= 1 2whilei≤A.lengthand (A[i])2 ≤x2 3i:=i+ 1 4i:=i−1 5ifi