Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell'Informatica Soluzioni al Tema d'esame27 Gennaio 2021 1 Informatica teorica Esercizio 1 Si considerino i seguenti linguaggi sull'alfabetoA=fa; b; cg: L1= A
fbg (A
(A fag)
A
fbg) (1) L2= A (A
(A fbg)
A ) (2) L3= L 1
L 2(3) dove e la stella di Kleene,e la dierenza insiemistica e
e la concatenazione. Utilizzare un formalismo a potenza minima (tra tutti quelli visti a lezione) che caratterizzi il linguaggio L3. Soluzione Si puo facilmente veri care cheL 1= a
beL 2= b . PertantoL 3= a
b+ . E quindi un linguaggio regolare (caratterizzato, per l'appunto, dall'espressione regolare data). Tuttavia si tratta anche di un linguaggio di tipostar-free, poiche, come si vede dalle espressioni originali, la stella di Kleene e applicata solo sull'intero alfabetoA. Si puo quindi formalizzare il linguaggioL 3 mediante una formula MFO, come segue: 9x(x= 0^(a(x)_b(x))) all'inizio c'e unaao unab ^ 8x(a(x)! 9y(y=x+ 1^(a(y)_b(y)))) dopo unaac'e unaao unab ^ 8x(b(x)!(last(x)_ 9y(y=x+ 1^b(y)))) dopo unabc'e unabo e l'ultimo carattere ^ 9x(b(x)^last(x)) l'ultimo carattere e unab(congiunto ridondante) Esercizio 21.Dire se e decidibile il problema di stabilire se, data una MT deterministica e una sequenzadi suoi stati, esiste una stringa x in ingresso tale che la MT attraversa esattamente, uno per uno, la sequenza di stati desiderata durante il riconoscimento di x. 2.Dire se e semidecidibile il problema del punto 1. 3.Dire se e decibile il problema di stabilire se, data una MT deterministica e una sequenza disuoi stati, esiste una stringa x in input tale che la MT, durante il riconoscimento x, attraversa gli stati desiderati nell'ordine desiderato, ma potrebbe, tra uno stato desiderato e il successivo della sequenza, attraversarne anche altri. 1/3 Soluzione 1.Decidibile: se esiste la stringax, essa puo essere ricostruita seguendo le mosse che la MT dovrebbe fare per attraversare la sequenza di stati. 2.Semidecidibile, per quanto detto sopra. 3.Indecidibile: e suciente notare che, prendendo come coppia di stati da cui partire ed in cuiarrivare lo stato iniziale e uno stato nale, possiamo determinare se la funzione calcolata dalla MT e de nita in almeno un punto, problema notoriamente indecidibile (come si puo evincere anche applicando il teorema di Rice). 2 Algoritmi e strutture dati Esercizio 3 Si consideri il seguente problema: data una stringaxcostruita su un alfabetoA, restituire il primo simbolo dixche NON compare piu di una volta inx. 1.Si descriva una MT aknastri che risolve il problema dato, e se ne diano le complessita temporale e spaziale. 2.Si descriva una macchina RAM che risolve il problema dato, e se ne diano le complessitatemporale e spaziale, sia a costo costante che a costo logaritmico. Soluzione ˆSi osservi che i possibili stati della computazione attraversati dalla MT sono in numero nito. In particolare essi sono determinati dal memorizzare le seguenti informazioni: {per ogni carattere dell'alfabeto, se esso e stato visto nessuna, una o piu di una volta. L'informazione e codi cabile in modo semplice in 3j Aj distinti valori. {L'ordine con cui vengono visti i caratteri. L'informazione e codi cabile in (jAj)! distinti valori. Ricordando che l'alfabeto ha cardinalita nita, e suciente un automa a stati niti con 3j Aj (jAj)! stati per eseguire il calcolo. L'automa utilizza la memoria a stati niti per tenere traccia di tutte le informazioni necessarie mano a mano che scorre la stringa. La complessita temporale eO(n), quella spaziale e costante. La MT desiderata emula il comportamento dell'automa a stati niti. ˆCome sopra. E suciente emulare un automa a stati niti tramite la macchina RAM. Esercizio 4Si consideri un suggeritore per cercare parole che rimano con una parola data all'interno di un dizionario. In particolare, e possibile interagire con il suggeritore tramite due funzioni. ˆaggiungi(p): viene fornita al suggeritore una parolapda aggiungere al dizionario. Si denoti connlunghezza della parola. 2/3 ˆ trovarime(p; r): il suggeritore stampa tutte le parole che rimano con la parolapdata (di lunghezzan) per i loro ultimircaratteri. Si realizzino le due funzioni,aggiungi,trovarime. Soluzione E possibile memorizzare il dizionario come un albero con branching factor pari al numero di lettere dell'alfabeto. I nodi dello stesso hanno quindi un numero di puntatori pari alle lettere dell'alfabeto. Ogni nodo contiene anche un campo a valore booleano che indica se il nodo e corrispondente all'inizio di una parola. Ogni parola viene memorizzata, letta dalla ne all'inizio, come un percorso all'interno dell'albero con il seguente procedimento: 1.si imposta la radice come nodo corrente e l'ultima lettera della parola come lettera corrente 2.si aggiunge, se non gia presente, un nodo comei-esimo glio del nodo corrente, doveie il numero d'ordine della lettera corrente. 3.si imposta il nodo corrente a quello appena aggiunto (o a quello che si sarebbe dovutoaggiungere ed era gia presente) 4.se la lettera corrente non e la prima della parola si torna al punto 2, altrimenti si imposta ilvalore booleano avero. Il costo di una chiamata aaggiungie quindi lineare nella lunghezza della parola da aggiungere. La funzionetrovarime(p; r), e realizzata con il seguente procedimento: 1.partendo dalla radice dell'albero come nodo corrente, e dall'ultima lettera della parola comelettera corrente, perrvolte (a)controlla se e presente l'i-esimo glio del nodo corrente, doveie il numero d'ordine della lettera corrente. (b)se non e presente, la funzione termina la sua esecuzione senza stampare nulla, altrimentiimposta il glio come nodo corrente e la lettera precedente nella parola a quella corrente 2.eettua una visita in profondita dell'albero, a partire dal nodo raggiunto stampando ognipercorso no ad ogni nodo con valore booleano impostato averoin ordine inverso, seguito dalle ultimerlettere della parolap. Le parole stampate sono tutte e sole quelle che hanno un susso darcaratteri comune alla parola data. Il costo della funzione e proporzionale ai nodi dell'albero visitati, dunque lineare nella somma dei caratteri delle parole che rimano con quella data. 3/3