Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell'Informatica Soluzioni al Tema d'esame07 Settembre 2020 1 Informatica teorica Esercizio 1 SianoA=f0;1;2geB=f0;1g. Si considerino i linguaggiL 1= fx1xR jx2A+ geL 2= B+ 212B+ . 1.Si dica quali sono i modelli apotenza minimaperL 1ed L 2, motivando adeguatamente la risposta. 2.Si descriva il funzionamento di un automa (o si de nisca una grammatica) a potenza minimaper l'intersezione tra L1 e L2. Soluzione 1.Rispettivamente automa a pila non deterministico e automa a stati niti. 2.Solito automa a piladeterministicoche impila i caratteri inB, no ad arrivare al primo 2; dopo il secondo 2 spila control lando la corrispondenza col carattere letto. Esercizio 2Si dica, motivando opportunamente la risposta, se i problemi seguenti sono decidibili: 1.Stabilire se, dato un generico automa a stati niti, esso riconosce tutte le stringhe inA , con A=f0;1g; 2.Stabilire se, dato un generico automa a stati niti, esso riconosce tutte e sole le stringhe checodi cano numeri primi espressi in notazione binaria, conA=f0;1g. Come cambierebbe la risposta ai quesiti precedenti se fosse data una macchina di Turing al posto di un automa a stati niti? Soluzione 1.Decidibile poiche e decidibile l'equivalenza tra FSA, quindi basta disegnarne uno che accettituttoA . 2.Decidibile poiche la risposta e sempre no (nessun FSA e in grado di riconoscere il linguaggiodato). Le varianti con TM sono tutte indecidibili per il teorema di Rice. 1/3 2 Algoritmi e strutture dati Esercizio 1 Si considerino i formalismi delle Macchine di Turing deterministiche a 1 nastro di memoria (MT-1) e degli Automi a 2 Pile deterministici (A2P). Un A2P e un automa a pila deterministico che ha a disposizione una pila aggiuntiva. Mostrare come una MT-1 puo simulare il comportamento di un A2P e stabilire la complessita, nel caso pessimo, della MT-1 in funzione della complessita dell'A2P simulato, motivando opportunamente la risposta. SoluzioneSi indichi conT A2P( n)la complessita di un generico A2P. Per simulare un A2P con una MT-1 e suciente usare il nastro di memoria per simulare il contenuto del le due pile, per esempio mettendo prima il contenuto del la prima pila, seguito da un simbolo separatore, seguito da contenuto del la seconda pila. La simulazione del la singola mossa del l'A2P richiede di scorrere il nastro di memoria no a giungere al la cima del la pila di sinistra, proseguire no a giungere al la cima del la pila di destra, e modi care opportunamente il nastro per simulare il cambiamento dei simboli in cima al la pila. A questo proposito, se le pile aumentano o diminuiscono di lunghezza, occorre scorrere il nastro di memoria, opportunamente spostando i simboli (per esempio, in caso di aggiunta di 2 simboli in cima al la pila di sinistra, il contenuto del la pila di destra va tutto spostato di 2 posizioni a destra; viceversa, se il simbolo in cima al la pila di sinistra va cancel lato, occorre spostare tutto il contenuto del la pila di destra di una posizione a sinistra). Questo richiede, nel caso pessimo, complessitaO(T A2P( n)), quindi la complessita totale di una MT-1 che simula un A2P eO((T A2P( n))2 ). Esercizio 1 Si consideri il caso di una tabella di hash di 8 elementi, le cui chiavi sono costituite da numeri interi, gestita con la disciplina dell'indirizzamento aperto (open addressing). Per semplicita, si rappresenti lo stato di una tabella vuota nel seguente modo[,,,,,,,] considerando il bucket (slot) piu a sinistra come quello di indice 0 e quello piu a destra come quello di indice 7. Si indichi conh(k; i) la funzione di hashh:NN! f0; : : : ;7gdovekindica il valore della chiave eil' indice del passo di ispezione (alla prima ispezionei= 0). 1.Si mostri lo stato della tabella, dopo ognuna delle seguenti operazioniInserimento di 2 Inserimento di 10 Inserimento di 18 Cancellazione di 10 Inserimento di 26 considerandoh(k; i) = (k+i) mod 8 2.Si consideri l'uso della seguente funzione di hashh(k; i) = (k+h 2( k)i) mod 8, dove la funzione h2( k):a)codi cakin binario naturale,b)toglie tutti gli zeri consecutivi presenti nelle posizioni meno signi cative della codi ca binaria dik,c)interpreta il risultato come la codi ca in binario naturale di un intero. La funzione indicata rappresenta una buona scelta per la tabella di cui sopra, ovvero consente alla sequenza di ispezione di visitare tutti i bucket? 2/3 Soluzione 1.Stato del la tabel la:Inserimento di 2:[,,2,,,,,] Inserimento di 10:[,,2,10,,,,] Inserimento di 18:[,,2,10,18,,,] Cancel lazione di 10:[,,2, ,18,,,] Inserimento di 26:[,,2,26,18,,,] 2.La funzioneh 2( k)ha la proprieta di garantire un risultato dispari (a tutti gli eetti, rimuove il fattore2i ; i2Ndal la fattorizzazione dik), tranne nel caso in cui il valore dato in ingresso sia zero. Si ha di conseguenza che la strategia di double hashing indicata avra una sequenza di ispezione che tocca tutte le cel le del la tabel la di hash, in quanto il risultato dih 2( k)e coprimo con la lunghezza del la tabel la, salvo appunto nel caso dih(0; i)per qualunque valore dii. La funzione di hash non e quindi una buona funzione di hash, considerando il criterio del raggiungimento di tutti i bucket (slot) durante le ispezioni. 3/3