Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell’Informatica Appello del 9 Settembre 2019 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 2 ore. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 in 1 ora. NB: i punti attribuiti ai singoli esercizi hanno senso solo con riferimento all’esame integrato e hanno valore puramen te indicativo. Esercizio 1 ( 10 punti) Si vuole modellare il comportamento di una macchina che vende bottiglie di latte. La macchina accetta 2 tipi di monete: da 50 centesimi e da 1 euro. Nel momento in cui la macchina ha almeno 1 euro di credito, essa produce automaticamente un a bottiglia di latte. Dopo che l'utente ha preso il latte, si può ricominciare a inserire monete nella macchina . Inoltre, l’utente può chiedere di avere indietro il resto che è presente in quel momento nella macchina. Il com portamento della macchina viene modellato descrivendo sequenze di “eventi” rilevanti. Più precisamente, gli eventi di interesse sono i seguenti: • in50c , e in1 , che corrispondono al fatto che viene inserita una moneta da 50¢ o 1€, rispettivamente; • cred0 , e c red50 , che corrispondono al fatto che il credito presente nella macchina è di 0 o 50, centesimi, rispettivamente (si noti che nel momento in cui si inserisce una moneta che farebbe aumentare il credito fino a essere uguale a o più di 1€, viene erogato il l atte, quindi il credito è subito consumato); • latte , che corrisponde al fatto che viene erogato il latte; • resto , che corrisponde al fatto che si richie de il resto presente in quel momento. Le sequenze di simboli che descrivono il comportamento della macchin a sono alternanze di simboli corrispondenti a comandi dati alla macchina ( in50c , in1 , resto ) e simboli che rappresentano il credito residuo ( cred0 , cred50 ) . Se però l’inserimento di una nuova moneta port a all’erogazione del latte (perché si raggiungerebbe l’ammontare di 1€), allora il comando di inserimento è subito seguito dal simbolo latte che indica l’erogazione del latte , che a sua volta è seguito d a ll’ i ndicazione del credito residuo. Le sequenze di simboli i nizia no e termina no con credito uguale a 0. Immaginiamo, per esempio, una sequenza in cui l’utente inserisce prima una moneta da 50¢, poi un’altra da 50¢ (a questo punto la macchina avrebbe raggiunto 1€, quindi deve essere erogato il latte e aggiornato il credito), poi una da 50¢, poi una da 1€ (nel qual caso, di nuovo viene subito erogato il latte ) , poi viene chiesto il resto , poi viene inserita una moneta da 50¢, poi di nuovo viene chiesto il resto , e a questo punto la sequenza termina. Tale sequenza corrisponde alla segue nte sequenza di simboli: cred0 , in 50 c , cred5 0 , in50c , latte , cred 0 , in50c , cred50 , in1 , latte , cred50 , resto , cred0 , in50c , cred50 , resto , cred0 Si formalizzino in logica i seguenti vincoli e proprietà: 1. All’inizio e alla fine il credito è 0. 2. Un simbolo rappresentante un credito, se non è l’ultimo della sequenza, deve essere subito seguito da un simbolo rappresentante un comando. 3. L’effetto dell’inserimento di una moneta sul credito , cioè come cambia il credito in seguito all’inserimento di una moneta, ed eventualmente l’emissione del latte (si noti che, in caso di emissione del latte, prima viene erogato il latte e poi viene segnalato il nuovo credito). 4. L’effetto di un comando di re sto. Il punteggio sarà tanto più alto, quan t o meno potente è il formalismo usato per definire le sequenze. Esercizio 2 ( 7 punti) 1. È decidibile il problema di stabilire se, dato un programma C generico, esso è in grado di discriminare tra le sequenze di “eventi” che rispettano i vincoli formalizzati al punto 1, e quelle che non lo sono? 2. È decidibile il problema di stabilire se le s equenze accettate dal seguente automa a stati finiti rispettano il vincolo 2 (cioè il fatto che un simbolo di credito è seguito da un simbolo di comando) ? 3. È decidibile il problema di stabilire se le sequenze accettate da un generico automa a stati fi niti rispettano il vincolo 2 ( cioè il fatto che un simbolo di credito è seguito da un simbolo di comando )? Esercizio 3 ( 8 punti) Si consideri la seguente variazione della tradizionale macchina di Turing a k nastri: la macchina non può modificare il contenuto di una cella dopo averci scritto. Questo tipo di macchina può riconoscere qualsiasi linguaggio riconosciuto da una MT tradizio nale? In caso positivo, dette T(n) e S(n) le complessità temporale e spaziale della macchina originaria, con che complessità può effettuare il riconoscimento la macchina “non cancellante”? Esercizio 4 ( 8 punti) Si vuole implementare un vocabolario, ossia un insieme di stringhe statico , in cui si effettuano principalmente due operazioni: 1. Exact - Search: data una stringa w, verificare se la stringa è contenuta nel vocabolario 2. Range - Search: date due stringhe w1, w2, restituire tutte le parole w del vocabolario tali che w1 w2 La ricerca di w1 costa O(log(n)), mentre la scansione dei successori costa O(m+log (n)). Infatti, sebbene l'algoritmo di calcolo del successore costa O(log(n)) nel caso pessimo, in questo caso applicandolo ripetutamente si visitano al più O(log(n)) nodi che non sono compresi tra w1 e w2, ovvero i nodi antenati di w1 le cui stringhe non s ono maggiori di w1. In conclusione, l'operazione di Range - Search può essere effettuata con costo O(m+log(n)); tuttavia il costo della ricerca esatta diventa O(log(n)), dovuto alla ricerca della stringa nell'albero. Si può ritornare a un costo O(1) per la r icerca esatta memorizzando i nodi dell'albero binario in una tabella di hash: in questo caso, ogni cella contiene la chiave e due puntatori, che puntano alle celle della tabella contenenti i figli destro e sinistro nell'albero di ricerca. Mantenendo un pun tatore alla cella della tabella che contiene la radice dell'albero, è possibile visitare la tabella come fosse un albero binario di ricerca, preservando l'efficienza delle Range - Search; allo stesso tempo, le ricerche esatte possono essere effettuate con co sto O(1) tramite una usuale ricerca della stringa nella tabella hash.