Apunts d'Estructures de Dades i Algorismes (FIB)

I 0 flashcards i 4 preguntes més al document.

Text del document

APUNTS ESTRUCTURES DE DADES I ALGORISMES Grau en Enginyeria Informàtica Universitat Politècnica de Catalunya AprenAI 2026-2027 Apunts complets d'EDA a la FIB (UPC): anàlisi asimptòtica, teoremes mestres, dividir i vèncer, taules de dispersió, arbres binaris de cerca i arbres AVL.

APREN.AI Índex 1 Anàlisi d'Algorismes i Notació Asimptòtica Mesura de l'eficiència algorísmica Classes de complexitat i notació asimptòtica Càlcul del cost en estructures no recursives Algorismes recursius i teoremes mestres 2 Paradigma de Dividir i Vèncer i Algorismes d'Ordenació Estratègia de dividir i vèncer Ordenació: Mergesort Ordenació: Quicksort Algorismes numèrics i matricials optimitzats 3 Tipus Abstracte Diccionari i Taules de Dispersió El Tipus Abstracte de Dades Diccionari Fonaments de les taules de dispersió i col·lisions Tècniques de construcció de funcions de dispersió Implementació del Diccionari amb taula de dispersió en C++ 4 Arbres Binaris de Cerca i Arbres AVL Arbres Binaris de Cerca (ABC) Mecanisme d'esborrat en un ABC Arbres equilibrats AVL Reequilibri mitjançant rotacions 5 Formulari Anàlisi asimptòtica i teoremes mestres Dividir i vèncer Taules de dispersió Arbres binaris de cerca (ABC) i AVL Errors típics Solucions de les preguntes de repàs Aquests apunts poden contenir errors o omissions.

Són un material de suport i no substitueixen el temari oficial ni el professorat: contrasta la informació important. Apunts d'Estructures de Dades i Algorismes (FIB) 1 1 Anàlisi d'Algorismes i Notació Asimptòtica EN ACABAR SABRÀS Distingir les definicions formals i propietats de les notacions O, Omega i Theta. Calcular el temps d'execució d'estructures de programació no recursives. Resoldre recurrències substractives i divisores utilitzant els teoremes mestres. PENSA-HI ABANS DE LLEGIR 1 Com podem anticipar matemàticament el temps d'un programa sense necessitat d'executar-lo en un ordinador concret?

Mesura de l'eficiència algorísmica L'anàlisi de l'eficiència d'un algorisme avalua el consum de recursos segons la mida de l'entrada . La mida d'una entrada es defineix com la quantitat de símbols que calen per representar-la. En el cas de seqüències com llistes o vectors, la mida és el seu nombre total d'elements. Per a un nombre natural, depèn de la seva codificació: si es codifica en valor absolut, la mida de 15 és 15; si es fa en binari, la mida correspon al nombre de dígits binaris ( , és a dir, 4 símbols). El cost computacional d'un algorisme s'expressa mitjançant una funció .

Com que diferents entrades d'una mateixa mida poden comportar temps d'execució diversos, distingim tres escenaris fonamentals: Pitjor cas ( ): representa el temps màxim d'execució per a qualsevol entrada de mida : . Millor cas ( ): temps mínim possible: . Cas mitjà ( ): mitjana ponderada pel producte de la probabilitat de cada entrada pel seu cost: . COMPROVA-HO 2 Per què la representació d'un nombre natural en binari varia la seva mida d'entrada respecte a la representació en valor? Classes de complexitat i notació asimptòtica La notació asimptòtica classifica les funcions d'acord amb el seu ritme de creixement a mesura que l'entrada tendeix a infinit.

Disposem de tres conjunts principals: Fita superior asimptòtica ( gran): conjunt de funcions dominades superiorment per una funció a partir d'un cert llindar. Formada per . Fita inferior asimptòtica ( ): conjunt de funcions fitades inferiorment: .

x 15 = 10 1111 2 A T : E R+ n T (n) pitjor n T (n) = pitjor max{T(x) x E x = n} T (n) millor T (n) = millor min{T(x) x E x = n} T (n) mig T (n) = mig Pr(x)T(x) x E, x =n O g O(g) = {f : N R + c R , n + 0 N, n n , f(n) 0 c g(n)} Ω Ω(g) = {f : N R + c R , n + 0 N, n n , f(n) 0 c g(n)} Apunts d'Estructures de Dades i Algorismes (FIB) 2 Fita ajustada asimptòtica ( ): conjunt de funcions acotades simultàniament per dalt i per baix per la mateixa funció: . Relació asimptòtica Criteri mitjançant límits ( ) Equivalència lògica El límit és igual a 0 El límit és El límit és una constant finita Entre les propietats d' gran destaquen la reflexivitat ( ) i la transitivitat ( ). A més, si , aleshores .

Respecte a les operacions algebraiques, es compleix la propietat del producte ( ) i de la suma ( ), així com la invariància per constants positives: per a tot . La notació satisfà exactament les mateixes propietats estructurals. Les classes estàndard ordenades de menor a major ritme de creixement són: COMPROVA-HO 3 Si demostrem que el quocient asimptòtic entre dues funcions tendeix a una constant estrictament positiva, què podem concloure sobre el seu ordre de creixement? Càlcul del cost en estructures no recursives Una operació elemental té un cost constant .

S'inclouen dins d'aquesta categoria la declaració de variables, assignacions, operacions aritmètiques, increments, decrements, lectures, escriptures, comparacions i l'accés directe a les posicions d'un vector per índex. De la mateixa manera, el pas de paràmetres per referència té un cost de . En canvi, construir o duplicar un vector de mida requereix un cost . L'avaluació de qualsevol expressió o d'una sentència de retorn ( return E ) és la suma del cost d'avaluar l'expressió més la despesa de copiar el resultat obtingut. La composició de codi no recursiu segueix tres patrons: Composició seqüencial: el cost d'executar consecutivament blocs amb costos és la seva suma directa: .

Composició alternativa (if-else): si avaluar la condició costa , i les branques costen i respectivament, el temps global és . Composició iterativa (bucles): en un bucle amb iteracions, la condició s'avalua vegades. El cost total equival a , on i són els costos del cos i de la condició en l'intent . Θ Θ(g) = {f : N R + c , c 1 2 R , n + 0 N, n n , c 0 1 g(n) f(n) c 2 g(n)} lim n g(n) f(n) f O(g) g Ω(f) f Ω(g) g O(f) f Θ(g) c > 0 f O(g) f Ω(g) O f O(f) h O(g) g O(f) h O(f) g O(f) O(g) O(f) g 1 g 2 O(f 1 f ) 2 g + 1 g 2 O(f + 1 f ) 2 O(f) = O(c f) c R+ Θ Θ(1) Θ(log n) Θ( ) n Θ(n) Θ(n log n) Θ(n ) 2 Θ(n ) 3 Θ(n ) k Θ(k ) n Θ(1) Θ(1) n Θ(n) c , c , …

, c 1 2 n c i=1 n i B D C 1 C 2 Θ(max{C + 1 D, C + 2 D}) N N + 1 (C + i=1 N i D ) + i D N +1 Ci D i i Apunts d'Estructures de Dades i Algorismes (FIB) 3 ERROR FREQÜENT Oblidar comptar l'última avaluació de la condició d'un bucle while o for . Quan la condició finalment s'avalua a fals per sortir de l'estructura iterativa, aquesta avaluació addicional consumeix temps computacional i s'ha de sumar a la despesa de les iteracions que sí que s'han executat. Algorismes recursius i teoremes mestres El cost d'un algorisme recursiu es modela mitjançant una recurrència: una expressió matemàtica on el valor d'una funció es defineix a partir de si mateixa aplicada a arguments d'una mida inferior.

Per deduir-la cal identificar el paràmetre de recursió (sovint la mida de l'entrada) i el cost del cas inductiu: el nombre de crides recursives, el volum de les noves mides i la feina addicional no recursiva. EXEMPLE Si tenim la recurrència definida per: Podem expandir-la per desplegament successiu: Segons la forma com es redueix la mida del subproblema en cada crida, classifiquem les recurrències en dos grups resolubles mitjançant teoremes mestres: 1. Teorema mestre de recurrències substractives S'aplica quan les crides redueixen la mida mitjançant una resta constant : per a , amb i . El comportament depèn estrictament del valor de les crides : 2.

Teorema mestre de recurrències divisores S'utilitza quan la mida de l'entrada es divideix per un factor : per a , amb i . Definim l'exponent crític com .

La complexitat s'obté comparant amb : n C(n) = { 1 C(n 1) + n si n = 1 si n 2 C(n) = C(n 1) + n = C(n 2) + (n 1) + n = = i = i=1 n 2 n(n + 1) Θ(n ) 2 c 1 T(n) = a T(n c) + g(n) n n 0 g(n) Θ(n ) k k 0 a T(n) Θ(n ) k Θ(n ) k+1 Θ(a ) n/c si a < 1 si a = 1 si a > 1 b > 1 T(n) = a T(n/b) + g(n) n n 0 g(n) Θ(n ) k k 0 α = log (a) b α k T(n) Θ(n ) k Θ(n log n) k Θ(n ) α si α < k si α = k si α > k Apunts d'Estructures de Dades i Algorismes (FIB) 4 COMPROVA-HO 4 Quina és la complexitat d'un algorisme que divideix el problema per la meitat, fa 2 crides recursives i realitza un treball no recursiu d'ordre lineal?

PROCÉS Passos per deduir una recurrència recursiva 1 Identificar paràmetre Fixar la variable n que representa la mida de l'entrada 2 Comptabilitza r crides Determinar el factor a de branques recursives i la mida n/b o n-c 3 Avaluar treball addicional Calcular el cost no recursiu de combinació g(n) 4 Aplicar teorema mestre Obtenir la classe asimptòtica comparant paràmetres IDEES CLAU La mida de l'entrada reflecteix el nombre de símbols necessaris per codificar-la en el sistema escollit. Les notacions asimptòtiques , i representen fites superiors, inferiors i exactes de creixement. El teorema mestre divisor resol equacions del tipus comparant amb . COMPROVA EL QUE HAS APRÈS 5.

En quins tres casos asimptòtics es divideix la solució del Teorema Mestre Substractiu per a ? 6. Què estableix la regla de límits per determinar que ? Test Encercla la resposta correcta. Les solucions són al final. 7. Quin cost té una operació d'accés directe a una component d'un vector per índex? 8. Com varia la mida d'un nombre representat en binari respecte al seu valor? O Ω Θ T(n) = a T(n/b) + Θ(n ) k α = log (a) b k T(n) = a T(n c) + Θ(n ) k f(n) Θ(g(n)) Ordre quadràtic a) Ordre logarítmic b) Ordre lineal c) Ordre constant d) És igual al seu valor a) Creix logarítmicament b) Creix de forma quadràtica c) És sempre constant d) Apunts d'Estructures de Dades i Algorismes (FIB) 5 9.

A quina classe pertany una recurrència divisora quan l'exponent crític alfa és superior a k? 10. Quin és el cost de duplicar un vector complet que conté n elements? 2 Paradigma de Dividir i Vèncer i Algorismes d'Ordenació EN ACABAR SABRÀS Analitzar el funcionament i la complexitat de Mergesort tant en versió recursiva com bottom- up. Distingir el cost de Quicksort en el seu millor cas, cas mitjà i pitjor cas. Calcular la millora asimptòtica d'algorismes com Karatsuba, Strassen i l'exponenciació ràpida. PENSA-HI ABANS DE LLEGIR 11 Com podem multiplicar dos enters llargs més de pressa que amb el mètode d'operacions que aprenem a l'escola?

Estratègia de dividir i vèncer El disseny mitjançant dividir i vèncer aborda la resolució d'un problema estructurant-lo en tres fases consecutives: La recurrència associada és , resoluble mitjançant el teorema mestre divisor. Un exemple bàsic n'és la cerca binària sobre un vector ordenat de rang . El paràmetre de recursió és . L'algorisme fa una única crida sobre una meitat ( , ) i realitza comparacions en temps constant ( ). L'equació és . Com que , el cost final és . COMPROVA-HO 12 Quina és la raó que la cerca binària tingui un cost logarítmic en lloc de lineal?

Theta d'n elevat a k log n a) Theta exponencial d'a elevat a n b) Theta d'n elevat a alfa c) Theta d'n elevat a k d) Ordre constant a) Ordre logarítmic b) Ordre quasilineal c) Ordre lineal d) Dividir: es descompon l'entrada en subproblemes de mida menor ( ). 1 a n/b Vèncer: es resolen aquests subproblemes de manera recursiva (o directa si s'arriba a casos base). 2 Combinar: s'acoblen les solucions individuals obtingudes per produir la resposta completa del problema original.

3 T(n) = a T(n/b) + Θ(n ) k [i, j] n = j i + 1 a = 1 b = 2 k = 0 T(n) = T(n/2) + Θ(1) α = log (1) = 2 0 = k T(n) Θ(log n) Apunts d'Estructures de Dades i Algorismes (FIB) 6 Ordenació: Mergesort L'algorisme Mergesort parteix el vector en dues meitats simètriques ( ), ordena recursivament cadascuna d'elles i posteriorment combina les dues seqüències ordenades mitjançant una operació de fusió ( merge ). Esquema del procés de partició, ordenació i fusió a Mergesort. El procediment es recolza en dues funcions principals. La funció recursiva s'invoca dues vegades ( ), mentre que el procediment de combinació lineal requereix recórrer els elements per ordenar- los, amb un cost de .

Cost de les funcions mergesort recursiva i merge de combinació. L'expressió que en descriu el cost és . Com que , i , tenim , fet que garanteix un cost global . També existeix la variant iterativa bottom-up: en lloc de fer particions des de la totalitat, s'agrupen i fusionen directament parelles de subvectors contigus de mida creixent ( ) fins a completar el vector original, evitant la pila recursiva. COMPROVA-HO 13 Quina tasca concreta realitza la funció merge en el Mergesort i quina és la seva despesa computacional? n/2 2 T(n/2) Θ(n) T(n) = 2T(n/2) + Θ(n) a = 2 b = 2 k = 1 α = log (2) = 2 1 = k T(n) Θ(n log n) m = 1, 2, 4, …

Apunts d'Estructures de Dades i Algorismes (FIB) 7 Ordenació: Quicksort L'algorisme Quicksort és l'ordenador genèric més ràpid a la pràctica. Tria un valor anomenat pivot ( ) i particiona el vector restant en dos conjunts disjunts: el subconjunt (elements menors o iguals que ) i el subconjunt (elements superiors o iguals que ). Després ordena cadascun de manera recursiva i finalment encadena els resultats. Esquema de la partició al voltant del pivot en Quicksort. La recurrència genèrica és , on representa la mida de la primera partició.

El comportament asimptòtic depèn fortament de l'equilibri que s'aconsegueixi amb el pivot: Cas d'anàlisi Condició del pivot Recurrència Complexitat resultant Pitjor cas El pivot és l'element mínim o màxim absolut ( , amb un subproblema de cost constant) Millor cas El pivot divideix el vector exactament en dues meitats iguals Cas mitjà Totes les posicions tenen una probabilitat equiprobable x T 1 x T 2 x T(n) = T(i) + T(n i) + Θ(n) i i = 1 T(n) = T(n 1) + Θ(n) Θ(n ) 2 T(n) = 2T(n/2) + Θ(n) Θ(n log n) n 1 1 T(n) = T(j) + n 1 2 j=1 n 1 cn Θ(n log n) Apunts d'Estructures de Dades i Algorismes (FIB) 8 ERROR FREQÜENT Donar per fet que el Quicksort és sempre d'ordre .

Si el pivot no és equilibrat i s'escull sistemàticament el mínim o el màxim (com en vectors ja ordenats amb seleccions ingènues), la partició es degenera i el temps assoleix una complexitat quadràtica . Algorismes numèrics i matricials optimitzats Exponenciació ràpida El càlcul d'una potència mitjançant multiplicacions repetides requereix operacions, amb cost . Mitjançant dividir i vèncer podem aprofitar la paritat de l'exponent: Codi de la implementació recursiva de l'exponenciació ràpida. Aquesta formulació redueix la recursió a una única instància dividida per dos: , la qual cosa rebaixa el temps d'execució fins a .

Multiplicació de Karatsuba La multiplicació tradicional de dos nombres de dígits requereix operacions.

Dividint cada nombre en dues meitats de dígits ( , ), l'expansió algebraica estàndard requereix 4 productes recursius: Karatsuba va reduir el còmput a només 3 multiplicacions gràcies a les variables intermèdies: Θ(n log n) Θ(n ) 2 xn n 1 Θ(n) x = n { (x ) n/2 2 (x ) x (n 1)/2 2 si n s parell e ˊ si n s senar e ˊ T(n) = T(n/2) + Θ(1) Θ(log n) n Ω(n ) 2 n/2 X = X e 2 + n/2 X d Y = Y e 2 + n/2 Y d X Y = 2 X Y + n e e 2 (X Y + n/2 e d X Y ) + d e X Y d d A = X Y e e B = X Y d d C = (X + e X )(Y + d e Y ) d Apunts d'Estructures de Dades i Algorismes (FIB) 9 Reorganitzant els termes com , la recurrència esdevé . Com que , el cost disminueix a .

Multiplicació matricial d'Strassen Per multiplicar dues matrius quadrades , la definició directa necessita un cost d'ordre cúbic . Dividint les matrius per blocs de dimensió : L'enfocament d'Strassen calcula 7 productes matricials auxiliars: La matriu resultant s'expressa exclusivament mitjançant combinacions lineals d'aquests 7 productes: Aquesta transformació dona l'equació recursiva . Aplicant el teorema mestre, amb , s'obté una complexitat de .

PROCÉS Passos del mètode de dividir i vèncer 1 Dividir Fragmentar el problema en subinstàncies de mida n/b 2 Vèncer Resoldre les instàncies menors mitjançant crides recursives 3 Combinar Acoblar les respostes obtingudes per donar la solució global IDEES CLAU Dividir i vèncer descompon un problema en subproblemes menors, els resol recursivament i en fusiona les solucions. Mergesort garanteix un cost fins i tot en el pitjor cas gràcies a particions sempre equilibrades. El rendiment de Quicksort oscil·la entre el cas mitjà i el pitjor cas . Els algorismes de Karatsuba i Strassen aconsegueixen rebaixar els exponents asimptòtics reduint el nombre de productes recursius.

X Y = 2 A + n 2 (C n/2 A B) + B T(n) = 3T(n/2) + Θ(n) α = log (3) 2 1,585 > 1 Θ(n ) log 3 2 Θ(n ) 1,585 n × n Z = ij X Y k=1 n ik kj Θ(n ) 3 n/2 × n/2 X = , Y = [ A C B D ] [ E G F H ] P = 1 A(F H) P = 2 (A + B)H P = 3 (C + D)E P = 4 D(G E) P = 5 (A + D)(E + H) P = 6 (B D)(G + H) P = 7 (A C)(E + F ) X Y = [ P + P P + P 5 4 2 6 P + P 3 4 P + P 1 2 P + P P P 1 5 3 7 ] T(n) = 7T(n/2) + Θ(n ) 2 α = log (7) 2 2,81 > 2 Θ(n ) log 7 2 Θ(n ) 2,81 Θ(n log n) Θ(n log n) Θ(n ) 2 Apunts d'Estructures de Dades i Algorismes (FIB) 10 COMPROVA EL QUE HAS APRÈS 14. Quantes multiplicacions i sumes matricials fa l'algorisme de Strassen en cada nivell de recursió? 15.

Per què el cas pitjor de Quicksort té una recurrència ? Test Encercla la resposta correcta. Les solucions són al final. 16. Quina és la complexitat asimptòtica del Mergesort en el seu pitjor cas? 17. Quantes multiplicacions de nombres de n/2 dígits efectua l'algorisme de Karatsuba? 18. Quin cost s'obté en calcular x elevat a n mitjançant l'algorisme d'exponenciació ràpida? 19. Quin és el cost temporal en el pitjor cas de Quicksort? 3 Tipus Abstracte Diccionari i Taules de Dispersió EN ACABAR SABRÀS Definir el tipus abstracte de dades diccionari i conèixer cadascuna de les seves operacions bàsiques. Calcular índexs de dispersió mitjançant el mètode de divisió i el mètode de multiplicació.

Analitzar el comportament temporal de l'encadenament en funció del factor de càrrega. PENSA-HI ABANS DE LLEGIR 20 Com podem trobar dades en temps constant sense tenir prou espai físic per a un índex directe de cada clau?

T(n) = T(n 1) + Θ(n) Theta lineal d'n a) Theta logarítmica b) Theta d'n log n c) Theta d'n quadrat d) Quatre multiplicacions a) Set multiplicacions b) Tres multiplicacions c) Dues multiplicacions d) Ordre logarítmic a) Ordre lineal b) Ordre constant c) Ordre quasilineal d) Ordre logarítmic a) Ordre quadràtic b) Ordre lineal c) Ordre n log n d) Apunts d'Estructures de Dades i Algorismes (FIB) 11 El Tipus Abstracte de Dades Diccionari Un diccionari és una col·lecció finita de parelles formades per (clau, valor) , amb la restricció indispensable que la clau ha de ser única dins del conjunt.

El conjunt d'operacions primitives que el defineixen inclou: Assignar (assign): insereix la parella (clau, info) . Si la clau ja existia prèviament al diccionari, en sobreescriu la informació associada. Esborrar (erase): retira la parella associada a una clau donada. Si aquesta clau no hi és present, no efectua cap acció. Present (contains): funció booleana que indica si una clau determinada es troba present. Cerca / Consulta (query): localitza la clau i en retorna una referència (o referència a la informació vinculada). Si no existeix, llença una excepció d'error. Talla (size): retorna el cardinal total d'elements continguts en l'estructura.

COMPROVA-HO 21 Quina acció duu a terme l'operació d'assignació quan es repeteix una clau ja present? Fonaments de les taules de dispersió i col·lisions Una taula de dispersió (o taula de hash) és una estructura pensada per representar diccionaris amb un cost esperat excel·lent. Transforma una clau genèrica mitjançant una funció de dispersió en una posició entera d'un vector: . L'element es guarda a la posició d'una taula de mida , on normalment essent el nombre potencial de claus. Esquema del mapatge de claus mitjançant una funció de dispersió i col·lisió. Quan dues claus diferents compleixen , es produeix una col·lisió.

La via més senzilla per gestionar aquest conflicte és la resolució per encadenament (chaining): cada cel·la de la taula emmagatzema un punter a una llista enllaçada amb tots els elements que han donat el mateix índex de dispersió . k h h : K {0, 1, 2, … , m 1} T[h(k)] m m < n n k = 1 k 2 h(k ) = 1 h(k ) 2 T[i] i Apunts d'Estructures de Dades i Algorismes (FIB) 12 Resolució de col·lisions mitjançant llistes encadenades a la taula.

Definim el factor de càrrega de la taula com la relació entre elements emmagatzemats i nombre de ranures disponibles: L'eficiència de les operacions a la taula depèn directament d'aquest factor i de la qualitat de la dispersió: Cas pitjor: totes les claus col·lisionen a la mateixa casella generant una única llista de mida . El cost de cerca, assignació i esborrat degenera a . Cas esperat / mitjà: sota una dispersió uniforme, la llargada mitjana de cada cadena és . El cost mitjà és ; si la mida de la taula es manté proporcional al nombre d'elements ( ), el cost esperat passa a ser . ERROR FREQÜENT Confondre el cost esperat amb el pitjor cas d'una taula de hash.

Encara que el seu cost típic sigui d'ordre constant , en el cas pitjor totes les claus van a parar a la mateixa cubeta, esdevenint una llista seqüencial de cost . Tècniques de construcció de funcions de dispersió Les claus se solen interpretar com a nombres naturals. Destaquen dues metodologies per calcular la funció : 1. Mètode de la divisió Aplica directament l'operació de mòdul respecte a la grandària de la taula: . EXEMPLE Si la taula té posicions i la clau és , calculem l'índex com . La clau s'emmagatzemarà a la posició 4 de la taula.

α = m n n Θ(n) α Θ(1 + α) α O(1) Θ(1) Θ(1) Θ(n) h(k) m h(k) = k mod m m = 12 k = 100 h(100) = 100 mod 12 = 4 Apunts d'Estructures de Dades i Algorismes (FIB) 13 És una operació ràpida en maquinari, però cal evitar escollir certs valors per a , com ara potències exactes de 2 (ja que deixarien la dispersió en mans dels bits de menys pes). És altament aconsellable triar valors de que siguin nombres primers no gaire propers a potències de 2. 2.

Mètode de la multiplicació Consisteix a multiplicar la clau per una constant real compresa entre 0 i 1 ( ), extreure la part fraccionària resultant i finalment multiplicar-la per per aplicar-hi la funció part sencera inferior: En aquest mètode el valor de no és crític per a la uniformitat, i sovint es trien potències de 2 per simplificar el càlcul binari. Tot i ser un procediment computacionalment més lent que la divisió simple, s'obté un excel·lent repartiment si s'utilitza com a suggerència la raó àuria: Implementació del Diccionari amb taula de dispersió en C++ Codi complet d'una classe C++ de diccionari amb taula de hash.

L'estructura allotja un vector de llistes STL: vector<list<pair<Key, Info>>> t . Cadascuna de les operacions bàsiques ( assign , erase , query , contains ) obté l'índex fent el mòdul i invoca una recerca auxiliar sobre la llista corresponent t[h] , mantenint un temps proporcional a la llargada de la cadena. m m k A 0 < A < 1 m h(k) = m(kA mod 1) = m(kA kA ) m A = 2 1 5 0,61803398 …

h = hash(key)%m Apunts d'Estructures de Dades i Algorismes (FIB) 14 CAUSES I CONSEQÜÈNCIES Espai finit de taula El rang de ranures m és estrictament menor que el domini de claus possibles Funció hash no injectiva Dues claus diferents acaben donant exactament el mateix índex numèric Col·lisions a taules de hash Formació de llistes Els elements en conflicte s'enllacen en una mateixa cel·la Augment del temps Les cerques poden degradar-se fins a temps d'ordre lineal en el pitjor cas IDEES CLAU Un diccionari emmagatzema correspondències clau-valor amb garantia de claus úniques. Les taules de dispersió projecten claus en posicions enteres mitjançant una funció hash .

La resolució de col·lisions per encadenament manté una llista enllaçada a cada cel·la de la taula. El factor de càrrega determina el temps de cerca esperat . COMPROVA EL QUE HAS APRÈS 22. Quin tipus de valor és preferible escollir com a grandària m al mètode de la divisió? 23. Com influeix el factor de càrrega en la complexitat de cerca quan s'usa encadenament? Test Encercla la resposta correcta. Les solucions són al final. 24. Com es defineix el factor de càrrega alfa d'una taula de dispersió? 25. Quin cost temporal té en el pitjor cas la cerca en una taula amb encadenament? 26. Quin és el cost esperat de consulta si mantenim el factor de càrrega fitat per una constant? 27.

Quin valor per a la constant A es recomana al mètode de multiplicació? h(k) α = n/m Θ(1 + α) α Nombre de claus dividit per posicions a) Nombre de posicions dividit per claus b) Nombre total de col·lisions acumulades c) Llargada de la llista més gran d) Ordre quasilineal a) Ordre constant b) Ordre logarítmic c) Ordre lineal d) Theta d'n quadrat a) Theta d'1 b) Theta d'n c) Theta de log n d) El nombre pi dividit per dos a) Arrel de dos b) (Arrel de 5 menys 1)/2 c) 0,5 exactament d) Apunts d'Estructures de Dades i Algorismes (FIB) 15 4 Arbres Binaris de Cerca i Arbres AVL EN ACABAR SABRÀS Explicar la propietat d'invariant que regeix els arbres binaris de cerca.

Aplicar el mètode d'esborrat de nodes segons la presència de zero, un o dos fills. Reconèixer arbres AVL i corregir desequilibris mitjançant rotacions simples o dobles. PENSA-HI ABANS DE LLEGIR 28 Per què un arbre binari de cerca pot arribar a ser tan lent com una simple llista? Arbres Binaris de Cerca (ABC) Un arbre binari de cerca (ABC) és una estructura jeràrquica recursiva utilitzada per implementar diccionaris de manera ordenada. Es defineix formalment com: Un arbre buit és un ABC.

Si no és buit, els fills esquerre i dret són també ABCs, i per a cada node amb clau es manté la invariant d'ordenació: totes les claus del subarbre esquerre són estrictament menors ( ) i totes les del subarbre dret són estrictament majors ( ). Arbre binari de cerca que mostra les claus menors a l'esquerra. Si es recorre un ABC en inordre (subarbre esquerre, arrel, subarbre dret), s'obtenen tots els elements ordenats de manera ascendent. Les operacions bàsiques s'implementen seguint el camí descendent de comparacions: Crear: inicialitza un arbre buit en cost constant . Cerca, Inserció i Esborrat: tenen un cost proporcional a l'alçada de l'arbre ( ).

Segons l'equilibri de l'arbre, la complexitat varia notablement: X X < e X X < X d Θ(1) h Apunts d'Estructures de Dades i Algorismes (FIB) 16 Cas Configuració de l'arbre Complexitat temporal Millor cas L'element cercat és l'arrel de l'arbre Cas mitjà L'arbre manté una alçada proporcional al logaritme ( ) Pitjor cas L'arbre es degenera en una llista encadenada unifilar ( ) COMPROVA-HO 29 Quina propietat fonamental compleixen els elements d'un ABC quan es visiten mitjançant un recorregut en inordre? Mecanisme d'esborrat en un ABC Per suprimir un node amb clau sense infringir les propietats d'un ABC, es presenten 3 situacions estructurals: Esborrat d'un node fulla sense fills en un ABC.

Esborrat d'un node amb un únic subarbre no buit en un ABC. Θ(1) h log n Θ(log n) h = n Θ(n) X El node no té fills (és una fulla): els dos subarbres són buits. S'elimina el node directament actualitzant el punter del seu pare a nul. 1 El node té exactament un fill (un subarbre és buit i l'altre no): se substitueix el node pel seu únic fill no buit, enllaçant-lo directament al pare del node esborrat. 1 Apunts d'Estructures de Dades i Algorismes (FIB) 17 Substitució per predecessor o successor per a un node amb dos fills. COMPROVA-HO 30 Quin element pot substituir la clau d'un node que s'esborra quan aquest té dos fills no buits?

Arbres equilibrats AVL Per evitar la degeneració lineal de l'alçada a , sorgeixen els arbres AVL (arbres binaris de cerca autoequilibrats). Un AVL satisfà les mateixes condicions que un ABC amb una fita addicional: DEFINICIÓ Un arbre AVL és un arbre binari de cerca on, per a qualsevol node, la diferència entre les alçades dels seus dos subarbres és com a màxim 1. Aquesta propietat assegura una alçada controlada de o . El node té dos fills (cap subarbre és buit): se substitueix el valor de la clau pel del seu predecessor en inordre (el màxim del subarbre esquerre) o pel seu successor en inordre (el mínim del subarbre dret).

Posteriorment s'esborra recursivament aquell node substitut, que per construcció cau sempre en un dels dos casos anteriors. 1 Θ(n) H log(n) H log(n + 1) Apunts d'Estructures de Dades i Algorismes (FIB) 18 Arbre binari equilibrat AVL amb alçades controlades. Gràcies a l'equilibri, el pitjor cas per a cerca, inserció i esborrat passa a ser sempre d'ordre . ERROR FREQÜENT Confondre l'orientació de les rotacions simples i dobles. La rotació simple s'aplica quan el desequilibri es produeix en el mateix sentit de la branca (dreta-dreta o esquerra-esquerra). Si el desequilibri forma un ziga-zaga (dreta-esquerra o esquerra-dreta), cal aplicar obligatòriament una rotació doble.

Reequilibri mitjançant rotacions En fer insercions o esborrats, l'arbre pot quedar coix (diferència d'alçades ). Es distingeixen quatre casos de reequilibri organitzats en dues tècniques: 1. Rotacions simples Rotació simple dreta (Dreta-Dreta): s'aplica en inserir a la branca esquerra del fill esquerre. Esquema d'execució d'una rotació simple dreta en un AVL. Rotació simple esquerra (Esquerra-Esquerra): s'aplica en inserir a la branca dreta del fill dret. Θ(log n) 2 Apunts d'Estructures de Dades i Algorismes (FIB) 19 Esquema d'execució d'una rotació simple esquerra en un AVL. 2.

Rotacions dobles Consten de dues rotacions simples consecutives sobre l'eix afectat: Rotació doble dreta (Dreta-Esquerra): s'aplica en inserir un subarbre esquerre al fill dret d'un node. Primer es fa una rotació sobre el fill i després una en sentit oposat sobre l'arrel afectada. Seqüència d'ajust d'una rotació doble dreta en un AVL. Rotació doble esquerra (Esquerra-Dreta): s'aplica en inserir un subarbre dret al fill esquerre d'un node. Seqüència d'ajust d'una rotació doble esquerra en un AVL.

Apunts d'Estructures de Dades i Algorismes (FIB) 20 ESQUEMA Casos d'esborrat en un ABC IDEES CLAU En un ABC, la clau d'un node és estrictament més gran que les de l'esquerra i menor que les de la dreta. El cost de les operacions en un ABC és , degradant-se a si l'arbre queda desequilibrat. Els arbres AVL limiten la diferència d'alçades dels fills a un màxim d'1, garantint . Els desequilibris en un AVL es corregeixen en temps logarítmic mitjançant rotacions simples o dobles. COMPROVA EL QUE HAS APRÈS 31. Quin tipus de rotació s'aplica quan es produeix un desequilibri de tipus Esquerra-Dreta en un arbre AVL? 32. Per què el pitjor cas d'un ABC convencional pot assolir una despesa d'ordre lineal?

Test Encercla la resposta correcta. Les solucions són al final. 33. Quina condició sobre la diferència d'alçades defineix un arbre binari de cerca AVL? 34. Quin recorregut sobre un arbre binari de cerca visita els nodes ordenats en sentit ascendent?

Esborrat a l'ABC Eliminar un element clau mantenint la propietat de cerca Node fulla Cap fill: s'elimina directament l'enllaç del pare Node amb un fill Se substitueix pel subarbre fill existent Node amb dos fills Substitució pel predecessor o successor inordre Θ(h) Θ(n) h log n És com a molt log n a) Ha de ser exactament zero b) És com a molt 2 c) És com a molt 1 d) Preordre a) Per nivells b) Inordre c) Postordre d) Apunts d'Estructures de Dades i Algorismes (FIB) 21 35. Quin és el temps del pitjor cas per a la cerca d'un element en un arbre AVL de mida n? 36. Com s'esborra un node d'un arbre binari de cerca quan aquest té un únic fill?

5 Formulari Anàlisi asimptòtica i teoremes mestres Fórmula o procediment Què significa cada símbol Quan s'utilitza , , mitjançant ; ; Classificació asimptòtica de funcions de cost segons el seu creixement límit. ; ; Resolució de recurrències substractives amb decreixement constant . : ; ; Resolució de recurrències divisores mitjançant l'exponent crític . Dividir i vèncer Fórmula o procediment Què significa cada símbol Quan s'utilitza Partir en dues meitats ( ) Ordenar recursivament cada meitat Fusionar ordenadament ( merge ) Cost recursiu ; resultat Ordenació garantida en el pitjor cas mitjançant Mergesort.

Triar pivot Particionar en i Ordenar recursivament i Concatenar Pitjor cas: (pivot extrem); millor i mitjà: Ordenació interna ràpida a la pràctica mitjançant Quicksort. si parell; si senar Càlcul eficient de potències en temps logarítmic. , , ; cost Multiplicació de nombres grans de dígits amb 3 productes recursius (Karatsuba). Producte de matrius per blocs amb 7 multiplicacions auxiliars Multiplicació matricial ràpida d'Strassen davant el cost cúbic clàssic .

Theta d'n quadrat a) Theta d'1 b) Theta de log n c) Theta d'n d) Se substitueix directament pel fill a) S'elimina tot el subarbre sencer b) Es posa el node a zero c) Cal convertir l'arbre a fulla d) O(g) Ω(g) Θ(g) lim n g(n) f(n) 0 f O(g) f Ω(g) c > 0 f Θ(g) T(n) = aT(n c) + Θ(n ) k a < 1 Θ(n ) k a = 1 Θ(n ) k+1 a > 1 Θ(a ) n/c c 1 T(n) = aT(n/b) + Θ(n ) k α = log (a) b α < k Θ(n ) k α = k Θ(n log n) k α > k Θ(n ) α α n/2 T(n) = 2T(n/2) + Θ(n) Θ(n log n) Θ(n log n) x T 1 x T 2 x T1 T 2 Θ(n ) 2 Θ(n log n) x = n (x ) n/2 2 n (x ) (n 1)/2 2 x n T(n) = T(n/2) + Θ(1) Θ(log n) X Y = 2 A + n 2 (C n/2 A B) + B A = X Y e e B = X Y d d C = (X + e X )(Y + d e Y ) d Θ(n ) log 3 2 Θ(n ) 1,585 n P , …

, P 1 7 T(n) = 7T(n/2) + Θ(n ) 2 Θ(n ) log 7 2 Θ(n ) 2,81 Θ(n ) 3 Apunts d'Estructures de Dades i Algorismes (FIB) 22 Taules de dispersió Fórmula o procediment Què significa cada símbol Quan s'utilitza : nombre d'elements; : nombre de ranures de la taula Càlcul del factor de càrrega; determina el cost mitjà esperat en encadenament. : clau entera; : grandària de la taula (preferentment primer) Dispersió pel mètode de la divisió; cal evitar potències de 2 per a . , recomanat Dispersió pel mètode de la multiplicació; insensible a l'elecció de .

Arbres binaris de cerca (ABC) i AVL Fórmula o procediment Què significa cada símbol Quan s'utilitza Esborrat en ABC: 0 fills eliminar enllaç pare; 1 fill connectar el pare directament al fill; 2 fills substituir per predecessor o successor inordre i esborrar el duplicat Cost proporcional a l'alçada ( en el pitjor cas; cas mitjà) Eliminació d'una clau mantenint la invariant . Diferència d'alçades entre subarbres fills com a màxim 1; garanteix Condició d'equilibri que defineix un arbre AVL. Desequilibri en una branca: aplicar rotació simple (Dreta o Esquerra) Es reorienten 2 nodes per reduir l'alçada del camí descompensat Reequilibri AVL quan la inserció es fa en el mateix sentit (LL o RR).

Desequilibri en ziga-zaga: aplicar rotació doble (Dreta-Esquerra o Esquerra-Dreta) Rotació simple sobre el fill seguit de rotació inversa sobre l'arrel Reequilibri AVL quan la inserció forma un canvi de direcció (LR o RL). Errors típics Oblidar l'última avaluació del bucle: la condició d'un while o for s'avalua vegades quan el cos s'executa vegades. Pitjor cas de Quicksort: assumir que sempre és ; si el pivot triat és reiteradament el mínim o el màxim absolut, el cost degenera a . Cost pitjor en taules de dispersió: creure que una taula de hash té sempre accés ; en el pitjor cas totes les claus col·lisionen a la mateixa ranura i el cost és .

α = m n n m Θ(1 + α) h(k) = k mod m k m m h(k) = m(kA kA ) 0 < A < 1 A = 2 1 5 0,61803398 m Θ(h) Θ(n) Θ(log n) X < e X < X d h esquerre h dret 1 H log n N + 1 N Θ(n log n) Θ(n ) 2 Θ(1) Θ(n) Apunts d'Estructures de Dades i Algorismes (FIB) 23 Solucions de les preguntes de repàs 1. Mesurant el nombre d'operacions fonamentals en funció de la mida de les dades d'entrada i calculant el seu comportament límit. 2. Perquè en valor la mida creix proporcionalment al valor mateix, mentre que en binari la mida correspon al nombre de bits requerits per codificar-lo, creixent de forma logarítmica respecte al valor. 3.

Podem afirmar que les dues funcions creixen exactament al mateix ritme asimptòtic, és a dir, que pertanyen a la classe Theta mútua. 4. Com que a=2, b=2 i k=1, tenim que l'exponent crític alfa és log_2(2) = 1. En complir-se alfa = k, el cost asimptòtic resultant és Theta(n log n). 5. Es divideix segons el nombre de crides: si el cost és ; si s'afegeix un grau a la mida polynomial quedant ; i si la complexitat passa a ser exponencial de la forma . 6. Exigeix que el límit de quan tendeix a infinit convergeixi cap a una constant real diferent de zero i d'infinit. 7. d) Ordre constant.

L'accés directe a la memòria mitjançant l'índex d'un vector és una operació bàsica d'execució immediata i temps fix. 8. b) Creix logarítmicament. El nombre de bits necessaris per escriure un valor creix de forma logarítmica respecte a la magnitud del nombre. 9. c) Theta d'n elevat a alfa. Quan el terme de les crides recursives domina el treball no recursiu (alfa > k), el cost queda determinat per . 10. d) Ordre lineal. Copiar o construir una estructura contígua de n elements requereix recórrer cadascun d'ells en temps proporcional a n. 11. Descomponent els nombres en meitats i reorganitzant els càlculs algebraics per estalviar una de les quatre multiplicacions necessàries. 12.

Perquè a cada iteració es descarta exactament la meitat del rang de recerca amb un cost constant de comparació, fent només una crida recursiva (a=1). 13. Fusiona de manera ordenada dos fragments contigus prèviament ordenats en temps lineal Theta(n). 14. Executa exactament 7 multiplicacions recursives de submatrius de mida meitat i sumes o restes en temps quadràtic d'ordre . 15. Perquè quan el pivot és l'element mínim o màxim del conjunt, una de les particions conté elements i l'altra en conté 0, impedint que el problema es divideixi simètricament. 16. c) Theta d'n log n.

Com que Mergesort divideix sempre el vector en meitats perfectes, manté una fita ajustada Theta(n log n) en qualsevol circumstància. 17. c) Tres multiplicacions. Karatsuba redueix les quatre multiplicacions de la fórmula desplegada a únicament tres productes independents. 18. a) Ordre logarítmic. En dividir l'exponent per dos a cada pas recursiu i fer una sola crida, el cost final és d'ordre Theta(log n). 19. b) Ordre quadràtic. En generar particions completament desequilibrades de mida n-1 i 0, la suma acumulada de treballs genera un temps d'ordre n quadrat. 20. Utilitzant una funció matemàtica de dispersió que tradueix l'espai infinit de claus a un rang reduït de caselles en una taula.

a < 1 Θ(n ) k a = 1 Θ(n ) k+1 a > 1 Θ(a ) n/c f(n)/g(n) n C > 0 nalfa Θ(n ) 2 n 1 Apunts d'Estructures de Dades i Algorismes (FIB) 24 21. Sobreescriu el camp d'informació antic associat a aquesta clau amb el nou valor proporcionat. 22. És preferible triar un nombre primer que es trobi allunyat de potències de 2 per afavorir una distribució uniforme de les restes. 23. Representa la mida mitjana de les llistes enllaçades; si creix per sobre d'un valor constant, les cerques s'alenteixen proporcionalment a . 24. a) Nombre de claus dividit per posicions. El factor de càrrega és el quocient n/m, que mesura la densitat d'elements per cada posició de la taula. 25. d) Ordre lineal.

Si totes les dades cauen a la mateixa ranura, cal recórrer una llista amb els n elements en temps lineal. 26. b) Theta d'1. Amb un bon repartiment i alfa fitat constantment, la longitud mitjana de cadena és petita i la cerca és Theta(1). 27. c) (Arrel de 5 menys 1)/2. La fracció inversa de la raó àuria (aprox. 0,61803398) ofereix una distribució altament dispersa i uniforme de les claus. 28. Perquè si les dades s'insereixen ordenades, els nodes creixen en una sola branca sense bifurcacions, assolint una alçada lineal. 29. Es visiten en ordre estrictament creixent segons el valor de les seves claus. 30.

El predecessor en inordre (màxim de l'esquerra) o el successor en inordre (mínim de la dreta), indistintament. 31. Cal aplicar una rotació doble esquerra, que consisteix en reorientar primer el subarbre fill i finalment la posició del node arrel desequilibrat. 32. Perquè si les insercions es fan de manera ordenada creixent o decreixent, l'arbre no obre branques laterals i degenera en una llista unifilar d'alçada . 33. d) És com a molt 1. La propietat d'equilibri d'un AVL exigeix que entre els dos fills de qualsevol node la diferència d'alçades sigui 0 o 1. 34. c) Inordre. El recorregut en inordre (esquerra, arrel, dreta) produeix la seqüència de claus en ordre creixent. 35. c) Theta de log n.

Com que l'alçada d'un AVL es manté estrictament fitada al logaritme del nombre de nodes, la cerca mai no supera Theta(log n). 36. a) Se substitueix directament pel fill. Si el node té un sol fill, aquest es connecta directament al pare de l'element que s'elimina. α n Apunts d'Estructures de Dades i Algorismes (FIB) 25