strutture succinte

Question 1

come funziona una struttura di select e ranking?

Answer 1

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

Question 2

qual’è la definizione di albero binario?

Answer 2

un albero binario è o l’insieme vuoto o una coppia (L,R) di alberi binari

Question 3

cosa si intende con danti ancillari?

Answer 3

con dati ancillari si intendono i dati associati o ai nodi interni o alle foglie

Question 4

cosa dice il teroema AT degli alberi binari? come si dimostra?

Answer 4

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

Question 5

che teoremi abbiamo visto per gli alberi binari?

Answer 5

teorema AT per determinare la proporzione nodi interni/foglie e il teorema catalano, per il theorical lower bound (enumerazione)

Question 6

cosa dice il teorema catalano? cosa dice il corollario?

Answer 6

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

Question 7

cosa dice approssimazione sterling?

Answer 7

l’approssimazione di sterling dice che x!~ (sqrt(2pix)*(x/e)^x

Question 8

come rappresento un albero binario?

Answer 8

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

Question 9

come posso trovare i nodi figli grazie al padre?

Answer 9

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

Question 10

come posso trovare il nodo padre grazie a uno dei figli?

Answer 10

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.

Question 11

quanto spazio occupa un albero succinto ?

Answer 11

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

Question 12

come gestisco dati ancillari negli alberi binari?

Answer 12

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))

Question 13

cosa sono sequenze monotone? cosa devo memorizzare in che modo?

Answer 13

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

Question 14

come divido la sequnza monotona per memorizzarla?

Answer 14

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)

Question 15

come memorizzo la parte bassa? (sequenza elias-Fano)

Answer 15

la parte bassa viene memorizzata in maniera esplicita

Question 16

come memorizzo parte alta? (elias-Fano)

Answer 16

memorizzo per differenze ( sequenza ordinata crescente) e codifico in unario.

Question 17

come ri-costruisco numero data posizione? (elias-Fano)

Answer 17

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.

Question 18

come ottengo spazio occupato totalmente in elias fano?

?

Answer 18

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

Question 19

come ottengo spazio occupato falla parte alta della struttura? (elias-fano)

Answer 19

distinguo con pot di 2 e non pot 2.
caso uno tolgo ceil e risolvo
caso 2 tolgo ceil, moltiplico * 1/2 e risolvo

Question 20

come faccio a trovarei il numero di possbili elementi memorizzabili per poi ricavare theoretical lower bound in (elias fano)

Answer 20

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.

Question 21

che passaggi algebrici sono necessari per ricavare theretical lowe bound? a quanto ammonta? (elias-fano)

Answer 21

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).

Question 22

quando vale l’analisi fatta sul elias fano?

Answer 22

quando ci si trova nel caso sparso (struttura quasi implicita), in particolare n <= radice di u

Question 23

che cosa sono le parole di dyck?

Answer 23

le parole di dyck sono delle parole prese da un alfabeto fatto solo di parentesi aperte e chiuse.

Question 24

cos’è la funzione di eccesso associata alle parole di dyck?

Answer 24

e(i) ritorna ll numero di parentesi aperte <i></i>

Question 25

come determino l’appertenenza al linguaggio?

Answer 25

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

Question 26

quali sono le primitive delle parole di dyck?

Answer 26

find open, find close e enclose

Question 27

come costruisco la struttura per memorizzare le parole di dyck?

Answer 27

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)

Question 28

cosa dice il teorema dei pionieri? come si dimostra?

Answer 28

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

Question 29

come effettuo una find_close sulla struttura?

Answer 29

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)

Question 30

come effettua una enclsoed sulla struttura?

Answer 30

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.

Question 31

come si ricava il theoretical lower bound?

Answer 31

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)

Question 32

quali sono gli isomorfismi? come si ricavano?

Answer 32

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.

Question 33

cosa trovano fin close e enclose negli alberi ricavati dagli isomorfismi?

Answer 33

find close trova figli/fratelli, serve per esplorare. enclose trova il padre.