Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame10 febbraio 2023 Informatica teorica Esercizio 1 (8 punti) Si consideri il linguaggioL={0n |n∈Ne 0n appare nell’espansione decimale diπ}. Il linguaggio L`e regolare? Si motivi esaurientemente la risposta. Soluzione Si danno solamente due casi: 1.esiste una sequenza “massima” 0k che appare nell’espansione decimale diπtale per cui la sequenza 0m , conm > k, non appare nell’espansione decimale diπ; 2.qualunque sequenza di 0, di qualunque lunghezza, appare nell’espansione decimale diπ. In entrambi i casi il linguaggio `e regolare, in quanto esprimibile mediante un’espressione regolare. Nel primo caso, l’espressione regolare `eε|0|00|. . .|0k ; nel secondo, 0∗ . Esercizio 2 (8 punti).Dato un linguaggioLdefinito su un alfabetoI, si consideri l’ipotetica macchina di TuringM La knastri, che ignora la stringa in input e stampa sul nastro di output la sequenzal 0⋄ l 1⋄ l 2⋄ . . ., dovel i∈ L, i∈Ne⋄`e un simbolo non presente inI. Le parole diLcompaiono una ed una sola volta nell’output diM L, in un ordine non noto a priori. 1.Si dimostri che, seM Lesiste, allora L`e semidecidibile. 2.Si consideri il caso in cuiM Lesiste e le parole l i∈ Lcompaiono in ordine lessicografico nel nastro di output diM L. Si indichi se L`e decidibile, semidecidibile o indecidibile e lo si dimostri. Chi ha diritto alla riduzione del 30% della prova, svolga unicamente il primo dei due punti. Soluzione 1.L’esistenza diM Lconsente di ricavare direttamente un semi-algoritmo (ovvero una procedura algoritmica di decisione che termina unicamente nel caso in cui la risposta sia 1) che calcola la funzione caratteristica diL(ovvero la funzione che vale 1 sex∈L, 0 altrimenti),c L( x), se xappartiene aL: `e sufficiente emulareM Lispezionando il nastro di output e, nel momento in cuixcompare su di esso, restituire 1. Dato che tutte le parole diLcompaiono sul nastro di output, in un tempo arbitrariamente grande, ma finito, comparir`a anchex. 1/5 2. L`e almeno semidecidibile per quanto gi`a mostrato al punto precedente. Si pu`o dimostrare cheL`e decidibile costruendo un algoritmo a partire daM Lche calcola c L( x): `e sufficiente emulareM Lfino a quando si incontra xo una parolayche seguexin ordine lessicografico. Nel primo caso si restituisce 1 (xappartiene aL), nel secondo caso 0 (xnon appartiene adL in quantoxsarebbe dovuta comparire prima diynell’output diM L). 2/5 Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame10 febbraio 2023 Algoritmi e strutture dati Esercizio 3 (8 punti) Si consideri il seguente linguaggioLdefinito sull’alfabetoIdelle parentesi tonde e quadre. Una parolal∈L`e ottenuta partendo da una sequenza ben parentetizzata di sole parentesi tondete da una sequenza ben parentetizzata di sole parentesi quadreqconcatenando in ordine un simbolo di te uno diq. A titolo di esempio, partendo dat= ()(()) eq= [][[]], otteniamol= ([)]([([)])]. Si descrivano un algoritmo per macchina di Turing ak= 1 nastri ed uno per macchina RAM che, data una generica stringa di parentesi tonde e quadre, restituiscono 1 se essa appartiene aL, 0 altrimenti. Si privilegino soluzioni a complessit`a temporale minima. Si descrivano le complessit`a spaziali e temporali di entrambi, con tutti i criteri di costo applicabili.Chi ha diritto alla riduzione del 30% della prova, descriva ed analizzi unicamente l’algoritmo per macchina di Turing ak= 1 nastri. Soluzione Un schema di algoritmo per macchina di Turing ak= 1 nastri `e il seguente: 1.Il nastro di lavoro della MT conterr`a due contatori binari che tengono traccia delle parentesi(tonde e quadre) aperte non ancora accoppiate ad una chiusa. I due contatori sono separati da un simbolocdiverso da 0 e 1. Il simbolocviene quindi posizionato sul nastro di lavoro come prima mossa. 2.Per ogni simbolo letto dal nastro di input:•Se si tratta di una parentesi aperta, la testina del nastro di lavoro si sposta sul bit meno significativo del contatore relativo al tipo di parentesi letta (tonda o quadra) ed incrementa il contatore binario. Se necessario, sposta tutti i simboli del contatore (e di quello adiacente) per far posto ad un eventuale riporto. •Se si tratta di una parentesi chiusa, la testina del nastro di lavoro si sposta sul bit meno significativo del contatore opportuno e controlla se il contatore vale 0. In questo caso la macchina si arresta restituendo 0. Se il contatore ha un valore maggiore di zero, calcola un decremento del contatore.` E possibile flicompattare” i contatori nel caso di un prestito dalla cifra pi`u significativa, ma non migliora la complessit`a asintotica del procedimento. 3.Controlla se sul nastro di lavoro sono rimasti due contatori con valore 0, nel qual casorestituisce 1, altrimenti restituisce 0. La complessit`a temporale dell’algoritmo `eO(nlog(n)): si ha infatti che, per ogni parentesi letta, viene effettuato un incremento o decremento di un contatore binario (costo log2( n)) e, nel caso sia necessario, uno spostamento di due contatori binari (costoO(log(n))). La complessit`a spaziale dell’algoritmo `eO(log(n)) . 3/5 L’algoritmo per la macchina RAM `e analogo, con l’unica differenza che i contatori binari sono salvati in due celle di memoria della macchina RAM. Si ha quindi che la complessit`a temporale dell’algoritmo per la macchina RAM a criterio di costo costante `eO(n), mentre quella spaziale `e O(1), dato che vengono impiegate solo due celle di memoria. La complessit`a temporale e spaziale dell’algoritmo per macchina RAM coincidono con quelle della MT aknastri nel caso sia utilizzato il criterio di costo logaritmico. Esercizio 4 (8 punti)Si consideri una struttura datiQche possa funzionare sia da coda che da pila, usando una lista semplice, cio`e dove ogni nodo possiede un unico puntatore all’elemento successivo. Si implementino in pseudo-codice le seguenti operazioni e se ne valutino le complessit`a temporali: 1.dequeue(Q): rimuove daQ, restituendolo, il nodo di lista che `e rimasto nella collezioneQpi`u a lungo; 2.pop(Q): rimuove daQ, restituendolo, l’ultimo nodo inserito nella collezioneQ; 3.insert(Q, x): inserisce un nodoxnella collezioneQ; 4.append(Q, Q′ ): fonde le due collezioniQeQ′ inQ(l’effetto dev’essere lo stesso che si otterrebbe inserendo ciascun elemento diQ′ , dal pi`u vecchio al pi`u recente, inQ). Soluzione Qha due attributi,tailehead, che puntano rispettivamente all’ultimo e al primo elemento della lista contenente i dati. dequeue(Q):x := Q.head Q.head := x.next return x pop(Q):x := Q.head y := x.next while y != Q.tailx := y y := y.next x.next := NIL Q.tail := x return y insert(Q, x):Q.tail.next := x Q.tail := x append(Q, Q’):Q’.tail.next := Q.head Q.head := Q’.head 4/5 Le complessit`a temporali sono tutte costanti, a parte popche `e Θ(|Q|). 5/5