Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell'Informatica Soluzioni al Tema d'esame15 Luglio 2020 1 Informatica teorica Esercizio 1 a)Scrivere una grammatica a potenza generativa minima che generi il linguaggioL 1di tutte le stringhe, sull'alfabetoA=f0;1g, aventi la seguente proprieta: la stringa e non vuota e, se letta da sinistra a destra, e il complemento della stringa letta da destra a sinistra. Per complemento di una stringa si intende la stringa ottenuta scambiando gli 0 con gli 1. b)Scrivere una grammatica a potenza generativa minima che generi il linguaggioL 2di tutte le stringhe, sull'alfabetoA=f0;1g, che non sono palindrome. Una stringa e palindroma se non cambia leggendola da sinistra a destra e da destra a sinistra. c)Con riferimento alle proprieta di chiusura dei vari tipi di linguaggi rispetto alle operazioni insiemistiche, stabilire di che tipo e la grammatica a potenza generativa minima che genera l'intersezione diL 1e L 2. Soluzione a)PerL 1: S!0S1j1S0j01j10 b)PerL2:S !1X0j0X1j0S0j1S1 X!1Xj0Xj c)L'intersezione traL 1e L 2e ancora L 1(nessuna stringa di L 1e palindroma), quindi basta una grammatica non contestuale. Naturalmente questo e compatibile con il fatto che non ci sia chiusura rispetto al l'intersezione tra linguaggi contestuali, il che indica semplicemente che esistono due linguaggi NC la cui intersezione non e NC, ma non vuol dire che l'intersezione di due linguaggi NC non possa essere NC. Esercizio 2 a)Data una generica macchina di Turing non deterministicaMe una generica stringax, e decidibile stabilire se esistono almeno due cammini distinti di computazione eettuati daMche portano all'accettazione della stringax? b)Il problema e semidecidibile? c)Come cambiano le risposte alle domande precedenti seMe un automa a stati niti? Soluzione a)Possiamo esibire una riduzione dal problema del l'arresto al problema in questione, che quindi eindecidibile. Infatti, siaM0 una generica macchina non deterministica. Costruiamo una nuova macchinaM00 uguale aM0 ma con l'aggiunta di un cammino non deterministico che, dal lo stato iniziale, accettaxin modo banale, ossia compiendo un passo verso un nuovo stato per ogni carattere dix. Se potessi decidere seM00 ammette almeno due cammini che accettanoxpotrei al lora decidere se la (generica) macchinaM0 accetta la (generica) stringax. 1/3 b)Il problema e semidecidibile perche, se esistono due cammini che accettano x, prima o poi li trovo provando tutti i possibili cammini con tecnica diagonale (dovetailing). c)Con un FSA il problema diventa decidibile perche posso, ad esempio, enumerare tutti i ( ni-ti) cammini di lunghezzajxjsul l'automa a partire dal lo stato iniziale e vedere se almeno due accettanox. 2 Algoritmi e strutture dati Esercizio 1 Si consideri il problema di convertire valori codi cati in binario in valori codi cati in ottale (cioe in base 8). 1.De nire una MT aknastri che legge da input un valore naturale codi cato in binario (scritto partendo dal bit MENO signi cativo) e scrive in output lo stesso valore, ma codi cato in ottale (scritto sempre a partire dalla cifra MENO signi cativa). Dire quali sono le complessita temporale e spaziale della MT aknastri ideata. 2.De nire una MT a nastro singolo che esegue la trasformazione analoga a quella descritta alpunto 1 (alla ne sul nastro deve rimanere il valore iniziale, ma codi cato in ottale, partendo dalla cifra meno signi cativa). Dire quali sono le complessita temporale e spaziale della MT a nastro singolo ideata. NB:Le de nizioni delle MT si possono dare a parole, ma in modo sucientemente preciso per potere valutare la complessita delle MT ideate. Soluzione 1.Per ottenere la prima trasformazione e suciente leggere i simboli in input a 3 a 3, e trasfor-mare ogni terna nel la corrispondente cifra ottale (per cui 000 diventa 0, 001 diventa 1, 010 diventa 2, ecc.; attenzione che la lettura viene fatta dal bit meno signi cativo). La complessita spaziale e costante, perche nul la viene memorizzato nei nastri di memoria. La complessita temporale e chiaramente(n), connlunghezza del la stringa in input. 2.La seconda trasformazione invece richiede tempon2 (connsempre la lunghezza del la stringa in input). Infatti, non solo ogni terna di cifre binarie in input deve essere convertita in una cifra ottale (in questo caso viene fatta una vera e propria sostituzione, per cui si puo pensare che l'ultima cifra di ogni terna venga trasformata nel la cifra ottale, e le altre 2 vengano invece cancel late, riportandole a blank), ma, al la ne del la conversione del le terne, occorre eliminare gli spazi che si sono creati tra le cifre ottali, e questa operazione richiede un tempo(n2 ). La complessita spaziale e invecen, in quanto al massimo sul nastro si trovanonsimboli. Esercizio 2 Si consideri la struttura datiheap, vista con l'algoritmoheap-sort, e se ne progetti una generalizza- zione (si chiami essa3-heap) con heap ternari anziche binari. Si implementiBUILD-MAX-HEAP per3-heape se ne valuti la complessita, confrontandola con la versione tradizionale, binaria, degli heap. SoluzionePer comodita si usi un array con indicizzazione da 0: in questo caso i tre gli di un nodoisono 3i+ 1(left),3i+ 2(center) e3i+ 3(right), mentre il padre eb(i1)=3c. 2/3 MAX-HEAPIFY risulta quasi identica; va aggiuntoc := CENTER(i)e confrontato con gli altri per calcolare il massimo, inoltre va tenuto conto del l'indice 0, quindi un indice e valido solo se e strettamente minore diheap-size. La complesita risultante eO(log 3( n)). InBUILD-MAX-HEAPsi cambia il ciclo periche va daA.length/3a 0. La valutazione del la complessita e molto simile: altezzah=log 3( n); il numero di nodi ad altezzahed2h=3h +1 e. Si ottiene quindiO(n), con costanti moltiplicative piu basse (si noti cheP 1 h=02 h=3h = 3=2). 3/3