Computer Engineering - Algoritmi e Principi dell'Informatica

Second partial exam

Algoritmi e Principi dell'Informatica Seconda Prova in Itinere 3 Febbraio 2016 Avvisi importanti Il tempo a disposizione è di 1 ora e 45 minuti. Esercizio 1 ( punti 6/15 -esimi ) Si consideri il linguaggio L = {c m al1 b a l2 b ... a lm b ... a lz b d n | n, m, l i, z > 0, l m = n}. Per esempio ccaaabaaaabababdddd L. Si descrivano una macchina di Turing e una macchina RAM che accettano L, calcolandone le complessità spaziali e temporali, sia a criterio di costo costante che logaritmico. Esercizio 2 (punt i 11 /15 -esimi) per eliminare un elemento della sequenza di ispezione as sociata a un a chiave k non basta assegnargli il valore NIL, perché altrimenti s i Deleted , in modo tal e che la ricerca di altri eleme nti lungo la sequenza non si debba interrompere. In questo modo però, a lungo andare si genera garbage la memoria disponibile e peggiora anche le prestazioni temporali. Si progetti un algoritmo di Compattamento il quale, per una data tabella T (per semplicità la si consideri una variabile globale), ricevendo come argomento una chiave k , elimini dalla sequenza associata alla chiave k tutti gli elementi marcati come Deleted ricompattando così la sequenza e recuperando la memoria inutilizzata. NB: se elimina anche altri elementi Deleted oltre a quelli indicati, il risulato è ugualmente accettabile (anzi, è addirittura preferibile); purché non interrompa alcuna sequenza. Si rammenta che la notazione T[p] , data una posizione p della tabella, restituisce NIL, Deleted , o k, ossia la chiave contenuta nella posizione, se questa non è né Deleted né vuota. Si assuma inoltre che la funzione h(k, i) sia del tipo h(k, i) = (f(k) + g(i) ) mod m con g(0) = 0 (non si tratta quindi di doppio hashing) con f e g funzioni calcolabili in tempo costante. Si valuti la complessità asintotica . Parte opzionale (ulteriori 2 punti) h sia una funzione di tipo doppio hashing? Giustificare brevemente la risposta. Tracce di soluzi on i Esercizio 1 Entrambe le macchine devono contare i c in ingresso, la MT in unario e la RAM in una cella es. M[1]. Alla prima a, si contano i gruppi di a separati da b -esimo. Si può usare M[1] o il nastro della MT a questo punto per contare il numero di a. Si ignorano i successivi a e b, controllando solo che la sequenza finisca con b d, che devono essere pari al numero memorizzato in M[1] o nel nastro. Complessità: RAM (costo costant e): T(n) = (n), S(n) = (1) RAM (costo logaritmico): T(n) = (n log n), S(n) = (1og n) MT: T(n) = (n), S(n) = (n) Esercizio 2 associata a una chiave k, ossia fino alla marca NIL; quando si incontra una posizione marcata Deleted si mette al suo posto la posizione corrente marcando questa a sua volta come Deleted; quando la posizione corrente raggiunge il NIL le eventuali posizioni ,ormai solo Deleted, e il NIL vengono tutte messe a NIL. In questo modo però si rischia di imbattersi in pos izioni occupate da altre sequenze: in tal caso sarebbe un errore spostarne il contenuto; quindi conv iene accontonare quest i elementi in una lista temporanea e marcarli come Deleted, per poi reinserirli ex -novo a compattamento ultimato . Siccome però la funzione di hash costru isce la stessa sequenza per ogni chiav e con ugual valore di f(k), è possibile e o pportuno eliminare tutti gli el ementi delle sequenze che ha nno la stessa origine . Pseudocodice compact (k) /*compattamento della lista associata alla chiave k; T denota la tabella (variabile globale) algoritmo viene applicato . Sia h(k,i) la funzione di hash ; T [p] indica il contenuto di T nella posizione p, ossia N IL , Deleted, oppure la chiave presente in p . In realt à il presente algoritmo le sequenze che hanno la stessa origine in h(k,0) mediante un semplice test; poiché tali sequenze coincidono non si ris chia di interrom pere impropriamente altre sequenze. Per semplicità si assume che la sequenza termini comunque in un elemento NIL , assunzione garantita, ad esempio, segnalando un overflow se in fase di inserimento si giunge a un punto in cui h(k, i) = h(k, 0). */ { i = 0; Pos Corrente = h(k,i ); while (T[ PosCorrente ] != NIL && T[ PosCorrente ] != Deleted ) {i++; PosCorrente = h(k,i); } if (T[PosCorrente] == NIL ) return ; //non ci sono elementi Deleted else // T[PosCorrente] è Deleted {j = i; ProxDeleted = PosCorrente ; while (T[PosCorrente] != NIL) { while (T[PosCorrente] != NIL ) if (T[PosCorrente] == Deleted ) {j++; PosCorrente = h(k,j) }; else if h(T[PosCorrente ],0)!= h(k,0) {inserisci T[PosCorrente] in una lista temporanea TempL; T[PosCorrente] = Deleted ; /* in questo modo gli elementi che non fanno parte di una delle sequenze che hanno origine in f(k) vengono accontonati j++; PosCorrente = h(k,j) }; /* si giunge a fine sequenza o al primo elemento non NIL e non Deleted di una sequenza che ha origine in h(k,0) */ if (T[PosCorrente] != NIL ) /* cioè PosCorrente appartiene a una sequenza che ha origine in f(k)*/ {T[P rox Deleted] = T[PosCorrente] ; T[PosCorrente] = Deleted; i++; ProxDeleted = h(k, i) } else {T[ProxDeleted] = NIL; } } /* a questo punto tutti gli elementi tra i e j sono deleted e si possono porre a NIL*/ while (i != j ) {T[h( k, i)] = NIL; i++; } } /* a questo punto non rest a che reinserire in tabella gli elementi accantonati che appar tenevano a sequenze non originan ti in f(k) */ Forall elements k in TempL I nsert(T, k) } Si noti che entrambi gli indici, i, e j utilizzati nel programma percorrono tutta la sequenza che parte da h(k, 0), includendo anche gli elementi che non sono stati inserti a partire dalla chiave k ma che si trovano in posizione h(k, i) per qualche i. algoritmo, fin o al reinserimen to in T degli elementi di TempL, è O(n), n essendo la lunghezza complessiva .m ), dove p è la lunghezza di TempL e m , poiché ogni inserimento, nel cas o pessimo costa O(r), con 1