03 02 2016

Page 1

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 = {cm al1 b al2 b ... alm b ... alz b dn | n, m, li, z > 0, lm = 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 (punti 11/15-esimi) per eliminare un elemento della sequenza di ispezione associata a un a chiave k non basta assegnargli il valore NIL, perché altrimenti s i Deleted, in modo tale che la ricerca di altri elementi 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…