Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame28 giugno 2022 Informatica teorica - Tempo a disposizione: 1 ora Esercizio 1 (8 punti) Si definisca un automa a potenza minima per il linguaggio{xcy|x, y∈ {a, b}+ ,|x|= 2|y|oppure 2|x|=|y|}. Soluzione Si tratta di un automa a pila non-deterministico – se ne allega la versione JFLAP (si ricorda cheZsta perZ 0e λperε).Esercizio 2 (8 punti). Chi ha diritto alla riduzione del 30% della prova svolga unica- mente il punto 2.1. 1.Siano dati due automi a pila deterministici con linguaggiL 1e L 2: `e ricorsivo il linguaggio L1∩ L 2? 2.Siano dati due automi a pila deterministici con linguaggiL 1e L 2e una macchina di Turing M: `e decidibile seMcalcolaL 1∩ L 2? Soluzione 1/4 1.S`ı, basta simulare i due APD con una MT e vedere se entrambi accettano la stringa in ingresso. 2.No, per il teorema di Rice: si tratta del consueto problema di determinare la correttezza diuna generica macchinaM. 2/4 Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame28 giugno 2022 Algoritmi e strutture dati - Tempo a disposizione: 1 ora Esercizio 3 (8 punti) Si consideri il problema di stampare, senza duplicati, gli elementi di un arrayanon ordinato din interi strettamente positivi. Per ciascuno dei casi seguenti, si fornisca una soluzione che garantisca la migliore complessit`a asintotica:a)caso ottimo;b)caso medio;c)caso pessimo. Per ciascuna delle soluzioni presentate, si specifichino le complessit`a nei tre casi. Soluzione Nel caso ottimo, basta una semplice scansione con due cicli nidificati: 1o t t i m o ( a ) 2b : = [ t r u e , . . . , t r u e ]/ / a r r a y d inb o o l e a n i 3f o r i : = 1 t o a . l e n g t h 4i f b [ i ] 5p r i n t a [ i ] 6i f i + 1 < = a . l e n g t h 7f o r j : = i + 1 t o a . l e n g t h 8i f a [ i ] = a [ j ] 9b [ j ] : = f a l s e Nel caso pessimo e nel caso medio, la complessit`a `e quadratica a causa dei due cicli nidificati. Nel caso ottimo, se c’`envolte lo stesso numero, la complessit`a `e lineare. Anche l’algoritmo seguente ha la stessa complessit`a nel caso ottimo, ma migliora il costo nel caso medio mediante una hashtable. 1m e d i o ( a ) 2T : = [ N I L , . . . , N I L ]/ / t a b e l l a d i h a s h v u o t a 3f o r i : = 1 t o a . l e n g t h 4i f H A S H - S E A R C H ( T , a [ i ] ) = N I L 5p r i n t ( a [ i ] ) 6H A S H - I N S E R T ( T , a [ i ] ) Nel caso medio, la complessit`a si abbassa aO(n), poich´e la ricerca e l’inserimento hanno com- plessit`aO(1). Idem nel caso ottimo. Nel caso pessimo, la complessit`a `e quadratica, poich´e ricerca e inserimento sono inO(n). Si pu`o migliorare la complessit`a nel caso pessimo preordinando l’array. 1p e s s i m o ( a ) 2s o r t ( a )/ / m e d i a n t e h e a p s o r t 3k : = 0 4f o r i : = 1 t o a . l e n g t h 5i f a [ i ]̸ =k 3/4 6 k : = a [ i ] 7p r i n t ( k ) In tutti i casi, prevale il costo dell’ordinamento, con una complessit`a asintotica diO(nlog(n)). Esercizio 4 (8 punti + bonus). Chi ha diritto alla riduzione del 30% della prova svolga unicamente i punti 4.1 e 4.3. Si consideri il linguaggioL={ww′ |w, w′ ∈ {0,1}+ , h(w′ ) =w}, doveh`e l’omomorfismoh(0) = 1, h(1) = 0. Si descrivano esaurientemente delle macchine dei tipi seguenti che accettinoL, valutandone le complessit`a spaziali e temporali con tutti i criteri di costo disponibili: 1.macchina di Turing a nastro singolo; 2.macchina RAM. Bonus:` E possibile ottenere una complessit`a spaziale costante con la macchina RAM con il criterio di costo costante? Soluzione 1.La macchina di Turing a nastro singolo fa avanti e indietro, marcando i simboli incontratidalle estremit`a fino al centro (rifiutando l’input se la lunghezza della stringa non `e pari). A questo punto riavvolge il nastro, togliendo la marcatura dalla prima met`a dei simboli. Infine controlla le corrispondenze tra i simboli nelle due met`a, facendo avanti e indietro, marcando nuovamente i simboli nella prima met`a e contrassegnando con unblankquelli nella seconda met`a. La complessit`a temporale `e Θ(n2 ) e quella spaziale Θ(n), connlunghezza della stringa in ingresso. 2.La macchina RAM copia la stringa in memoria, sfruttando un contatore, calcolandone quindila lunghezzan. Poi verifica la corrispondenza tra le due met`a con due contatori, uno che inizia da 0 e uno dan/2 mediante accessi diretti. Con il criterio di costo costante, la complessit`a spaziale `eO(n) (2 celle per i contatori eO(n) celle per la stringa) e quella temporale `eO(n). Con il criterio di costo logaritmico, la complessit`a spaziale `e sempreO(n) (anche se i contatori occupanoO(log(n)) celle), mentre quella temporale `eO(nlog(n)) a causa del contatore. Bonus. Si pu`o sfruttare l’inadeguatezza del criterio di costo costante per codificare in una singola cella di memoria tutta la stringa in ingresso, come sequenza di bit. Le operazioni necessarie per leggere e scrivere la sequenza di bit richiedono essenzialmente la gestione di un contatore come nella precedente soluzione; con il criterio di costo costante, questo prevede un costo spaziale costante. 4/4