strutture succinte Flashcards
come funziona una struttura di select e ranking?
una struttura di questo tipo mette a disposizione due operazioni, la select che ritorna l’indice prima del quale sono stati visti un determinato numero di uni e la rank che dato un indice ritorna il numero di uni che lo precedeono
qual’è la definizione di albero binario?
un albero binario è o l’insieme vuoto o una coppia (L,R) di alberi binari
cosa si intende con danti ancillari?
con dati ancillari si intendono i dati associati o ai nodi interni o alle foglie
cosa dice il teroema AT degli alberi binari? come si dimostra?
il teoriema AT degli alberi binari dice che il numero di foglie è pari al numero di nodi interni +1. per dimostrarto si usa induzione. caso base -> banale, caso induttivo: considera l’albero dato dalla coppia (L,R), i nodi esterni di questo albero sono i nodi esterni di L + i nodi esterni di R. per induzione i nodi esterni di L sono nodi interni di L +1 e quelli esterni di R sono interni di R +1. i nodi interni di (L,R) sono i nodi interni di L + quelli di R + il pardre int (L,R)+1. la differenza fra nodi interni e nodi esterni è quindi 1
che teoremi abbiamo visto per gli alberi binari?
teorema AT per determinare la proporzione nodi interni/foglie e il teorema catalano, per il theorical lower bound (enumerazione)
cosa dice il teorema catalano? cosa dice il corollario?
il teorema catalano dice che il numero di alberi possibili con n nodi è 1/n+1 * (2n sceglie n). il corollario attraverso i calcoli dimostra che il thoerical lower bound è 2nO(logn). necessaria approssiamzione sterling
cosa dice approssimazione sterling?
l’approssimazione di sterling dice che x!~ (sqrt(2pix)*(x/e)^x
come rappresento un albero binario?
lo rappresento utilizzando un vettore di 2n+1 bit (dove n è il numero di nodi interni).I nodi interni saranno rappresentati come 1 mentre le foglie come 0. Su questo le operazioni vengono svolte grazie a rank e select
come posso trovare i nodi figli grazie al padre?
si utilizza rank; basta pensare che il primo figlio (q) è il numero di nodi che ci sono prima di lui, che quindi sono i nodi interni dell’albero precedente * 2 +1. Si può intuire che i nodi interni dell’albero fino a q siano i nodi interni precedenti a p, dove p è il padre. i nodi precedenti interni di p sono rank(p); quindi il primo figlio è 2rank(p)+1 e 2rank(p)+2
come posso trovare il nodo padre grazie a uno dei figli?
basta fare la select di ceil[p/2-1/2]. per ricavarlo basta partire dalla formula per trovare i figli dal padre e fare l’inversa.
quanto spazio occupa un albero succinto ?
dato n (nodi interni) occupa 2n+1+ o(2n+1) (rank e select). rispetto al teoretical lower bound c’è una differenza di o(n) -> struttura succinta
come gestisco dati ancillari negli alberi binari?
se dati -> ogni nodo , memorizzo in un vettore e accedo all’indice corrispondente. se dati -> nodi interni, creo un vettore con i dati e le posizioni sono date dal rank. se dati -> nodi esterni come nodi interni ma faccio rank sugli zeri (i-rank_1(i))
cosa sono sequenze monotone? cosa devo memorizzare in che modo?
sequenze di n elementi che possono andare da 0 a u-1 (u universo). devo memorizzare una sequenza di questo tipo ed essere in grado di tornare un elemento data la sua posizione nella sequenza
come divido la sequnza monotona per memorizzarla?
2 parti, una alta e una bassa, bassa = max[0,ceil(log (u/n))], assumo u >=n, sparsità. la parte alta sono logu-l bit. la parte bassa di un elmento viene trovata facendo il modulo per 2^l mentre la parte alta dividendolo per 2^l (ceil)
come memorizzo la parte bassa? (sequenza elias-Fano)
la parte bassa viene memorizzata in maniera esplicita
come memorizzo parte alta? (elias-Fano)
memorizzo per differenze ( sequenza ordinata crescente) e codifico in unario.
come ri-costruisco numero data posizione? (elias-Fano)
data posizione effettuo select(posizoine)-posizione. infatti unario per ogni elemento aggiunge una quantita di bit pari a n+1. quindi, la select (n) mi tornerà la somma degli n numeri + n. dato che ho memorizzato le differenze somma n numeri è il numero che cerco. a questo punto faccio una shift di l e aggiungo a tutto la parte bassa, memorizzata esplicitamente.
come ottengo spazio occupato totalmente in elias fano?
?
abbiamo o(n) da select, ln da parte bassa e 2n o 3n da parte alta. soistuiendo l con floor(log u/n) ricavo formula come (2+floor(log(u/n)))n
come ottengo spazio occupato falla parte alta della struttura? (elias-fano)
distinguo con pot di 2 e non pot 2.
caso uno tolgo ceil e risolvo
caso 2 tolgo ceil, moltiplico * 1/2 e risolvo
come faccio a trovarei il numero di possbili elementi memorizzabili per poi ricavare theoretical lower bound in (elias fano)
biezione (corrispondente) sottinsiemi di multi insieme di cardinalità n insieme universo.
ri-scrivo considerando u variabili c, ognuna con il conteggio di ogni valroe nel multi-insieme, numero solizioni inntere e non negative di somma delle c =n. poi barrette ( ogni c -> barretta, per ogni valore di c metto tot asterischi sulla destra). quidni stringa (2 caratteri, lunga n)-> permutazione di u-1 +n caratteri con n ,u-1 ripetizioni. poi rischivo come u+n-1 sceglie n.
che passaggi algebrici sono necessari per ricavare theretical lowe bound? a quanto ammonta? (elias-fano)
fromula sul log combinazione, assunzione di sparsità (tolgo seconda parte), raccolta di u/n, x~ln(1+x) e spostamento a ln e ri-assunzione sparsità (tengo solo prima parte). quindi confronto con la size della struttura pratica (/n da entrambe le parti).
quando vale l’analisi fatta sul elias fano?
quando ci si trova nel caso sparso (struttura quasi implicita), in particolare n <= radice di u
che cosa sono le parole di dyck?
le parole di dyck sono delle parole prese da un alfabeto fatto solo di parentesi aperte e chiuse.
cos’è la funzione di eccesso associata alle parole di dyck?
e(i) ritorna ll numero di parentesi aperte <i></i>
