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>
come determino l’appertenenza al linguaggio?
il numero di parentesi aperte è = al numero di parentesi chiuse , e in ogni momento invece il numero di parentesi aperte viste è >= partentesi chiuse. possibile esprimere anche con la funzione di eccesso
quali sono le primitive delle parole di dyck?
find open, find close e enclose
come costruisco la struttura per memorizzare le parole di dyck?
divido la mia parola in blocchi, lunghi n/log n, ognuno grosso log n quindi. quindi memorizzo: la stringa, un vettore lungo quanto n con 1 in corrispondenza delle pioniere (aperte e chiuse), un vettore E con il costo inizale di ogni blocco, un vettore O con la prima parentesi di grado minore rispetto al minimo di ogni blocco (sempre per ogni blocco) e M che ad ogni pioniera associa la reciproca. lo pspazio totale occupato dalla struttura è di 8n o(n)
cosa dice il teorema dei pionieri? come si dimostra?
il nuemro di coppie di pioniere è <= 2k-3; per dimostrarlo si considerano due casi, quello separabile ( e li si lavora per induzione andando a dividere la parola in due parole) e quello non separabile (si toglie semplicemente la coppia di pioniere che lo rende non seprabile e poi induzione
come effettuo una find_close sulla struttura?
calcoro il grado del blocco dell’elemento (e la distanza di questo dalla pioniera, per trovare la pioniera rank(el).) utilizzo e per lo scopo. se elemento -> parentesi corta -> aposto (stesso grado). altrimenti guardo in M la pioniera reciproca, trovo blocco, e cerco parentesi chiusa distante dalla pioniera quanto lo era l’elemento iniziale (tologo parentesi corte)
come effettua una enclsoed sulla struttura?
parto da elemento, calcolo eccessi, guardo se essite parentesi aperta nel blocco con grado = grado-1. in caso così non sia guardo la reciproca (find close) e cerco nel blocco di là una chisua con grado = grado-1. se non trovo allora elemento ha rank minimo del blocco, utilizzo array O.
come si ricava il theoretical lower bound?
applicando una serie di isomorfismi che permettono di mappare la stringa lunga 2n in un albero binario con n nodi interni; poi si applica numero di catalano. theoretical lower bound : n+Olog(n)
quali sono gli isomorfismi? come si ricavano?
gli isomorfismi sono fi, che passa da foresta (o albero generalizzato) a albero binario. funzionamento: f<> -> nodo, f(albero1,albero2 albero3 albero4,) = primo nodo albero 1 con a sinistra fi figlio albero 1 e a destra fi(albero2,albero3…). altro isoformismo è psi, psi(epsilon) = <>, psi(tante parloe ) = psi -> parola singola e psi((parola)) = nodo con figlio psi(parola). così si passa da stringa dick a foresta.
cosa trovano fin close e enclose negli alberi ricavati dagli isomorfismi?
find close trova figli/fratelli, serve per esplorare. enclose trova il padre.
