Dividir i Vèncer: Algorismes i Recurrències (EDA)

I 0 flashcards i 3 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 de Dividir i Vèncer d'Estructures de Dades i Algorismes (FIB): cerca binària, merge-sort, quick-sort, Karatsuba, exponenciació i mètode d'Strassen.

APREN.AI Índex 1 Fonaments del disseny algorítmic i Cerca Binària Esquema bàsic del mètode Cerca binària (o dicotòmica) 2 Algoritmes d'Ordenació: Merge-Sort i Quick-Sort Ordenació per fusió (Merge-Sort) Ordenació ràpida (Quick-Sort) 3 Aritmètica Eficient: Karatsuba, Exponenciació i Strassen Multiplicació de Karatsuba Exponenciació ràpida Multiplicació de matrius d'Strassen 4 Formulari Esquema general i cerca binària Algorismes d'ordenació Aritmètica eficient 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.

Dividir i Vèncer: Algorismes i Recurrències (EDA) 1 1 Fonaments del disseny algorítmic i Cerca Binària EN ACABAR SABRÀS Definir les etapes clau de l'esquema de dividir i vèncer. Formular la recurrència temporal associada a la cerca binària. Executar pas a pas la cerca dicotòmica sobre un vector ordenat. PENSA-HI ABANS DE LLEGIR 1 Com podem trobar una paraula en un diccionari sense haver de llegir totes les pàgines d'una en una? El paradigma de dividir i vèncer és una estratègia de resolució de problemes fonamentada en la descomposició sistemàtica. Quan una instància és massa complexa per solucionar-se directament, es fragmenta en parts menors fins a assolir casos prou simples.

Esquema bàsic del mètode La tècnica s'estructura exactament en tres etapes consecutives: PROCÉS Fases de dividir i vèncer 1 Dividir Descompon en subproblemes menors 2 Resoldre Aplica recursió o resol directament 3 Combinar Uneix les solucions parcials obtingudes Cerca binària (o dicotòmica) Aquest mètode s'aplica per localitzar la posició d'un element dins d'un vector prèviament ordenat en sentit creixent. La funció retorna l'índex on es troba l'element, o bé -1 si no hi és present. Dividir: es fragmenta el problema principal en un conjunt de subproblemes de menor grandària. 1 Resoldre: es resol cada subproblema.

Si aquests mantenen la mateixa naturalesa estructural que l'original, s'aplica el procediment de manera recursiva. En arribar a subproblemes amb una mida prou petita (cas base), es resolen de manera directa sense subdivisions addicionals. 2 Combinar: s'agrupen i s'integren les solucions individuals dels subproblemes per generar el resultat complet del problema inicial. 3 x T Dividir i Vèncer: Algorismes i Recurrències (EDA) 2 Codi recursiu de la cerca binària en llenguatge C++ El funcionament compara amb la posició central . Si coincideix, la cerca finalitza amb èxit. Si , es descarta la meitat dreta i es continua explorant el subvector esquerre.

Si , es descarta l'esquerra i es processa el subvector dret. Diagrama de traces de la cerca binària per a un valor La recurrència temporal corresponent és: x k = 2 i+j x < a[k] x > a[k] T(n) = { θ(1) T(n/2) + θ(1) si n = 1 si n > 1 Dividir i Vèncer: Algorismes i Recurrències (EDA) 3 ERROR FREQÜENT Oblidar que el vector ha d'estar estrictament ordenat abans d'executar la cerca binària. Si s'aplica sobre una seqüència desordenada, descartar un dels intervals produeix resultats incorrectes sense generar cap avís de compilació. COMPROVA-HO 2 Què succeeix a la cerca binària si l'element buscat és superior al valor central del subvector actual?

IDEES CLAU El mètode de dividir i vèncer descompon el problema en subproblemes menors, els resol recursivament i en combina les respostes. Després d'un nombre finit de subdivisions, cal trobar un cas base directe. La cerca dicotòmica requereix un vector prèviament ordenat de forma creixent. L'equació de recurrència de la cerca binària és . COMPROVA EL QUE HAS APRÈS 3. Quines són les tres etapes de la tècnica de dividir i vèncer? 4. Quin valor retorna l'algoritme de cerca binària si l'element no pertany al vector? Test Encercla la resposta correcta. Les solucions són al final. 5. Quin és el requisit previ indispensable per aplicar la cerca binària sobre un vector? 6.

Quantes crides recursives es fan a cada pas de la cerca binària? 7. Com es defineix el cas base en dividir i vèncer? T(n) = T(n/2) + θ(1) Que no contingui valors repetits a) Que la mida sigui potència de dos b) Que les dades estiguin ordenades creixentment c) Que tots els elements siguin positius d) Dues crides simultànies a) Una única crida recursiva b) Tantes crides com elements c) Cap crida recursiva d) Un subproblema solucionable directament a) La crida recursiva més profunda b) El pas on es combinen solucions c) Un subproblema divisible indefinidament d) Dividir i Vèncer: Algorismes i Recurrències (EDA) 4 8. Quina recurrència descriu la cerca binària per a n > 1?

2 Algoritmes d'Ordenació: Merge-Sort i Quick-Sort EN ACABAR SABRÀS Comparar l'esforç de còmput a les fases de dividir i combinar de merge-sort i quick-sort. Expressar les recurrències temporals associades a cada mètode d'ordenació. Identificar el mecanisme de partició en la reordenació de vectors. PENSA-HI ABANS DE LLEGIR 9 És millor ordenar les cartes dividint el munt a cegues o classificant-les abans segons un valor límit? L'ordenació de vectors és un dels àmbits paradigmàtics de dividir i vèncer. Dos dels mètodes més destacats són el merge-sort (ordenació per fusió) i el quick-sort (ordenació ràpida), els quals prioritzen diferents etapes del procés.

Ordenació per fusió (Merge-Sort) Aquest mètode fragmenta el vector original en dues meitats equilibrades, les ordena recursivament i després les unifica: T(n) = 2T(n/2) + Θ(1) a) T(n) = T(n/2) + Θ(1) b) T(n) = 2T(n/2) + Θ(n) c) T(n) = T(n/2) + Θ(n) d) T Dividir: segmenta el vector de elements en dos subvectors d'aproximadament elements cadascun. 1 T n n/2 Resoldre: ordena de forma recursiva ambdós subvectors mitjançant el mateix procediment. 2 Combinar: fusiona les dues meitats ja ordenades per reconstruir la seqüència global completa.

3 Dividir i Vèncer: Algorismes i Recurrències (EDA) 5 Esquema gràfic de les etapes de divisió i fusió a merge-sort La relació de recurrència temporal corresponent és: Ordenació ràpida (Quick-Sort) A diferència de merge-sort, aquest algorisme inverteix l'esforç de computació: dedica molt treball a la divisió i pràcticament cap a la combinació.

T(n) = { θ(1) 2T(n/2) + θ(n) si n = 1 si n > 1 Dividir i Vèncer: Algorismes i Recurrències (EDA) 6 Implementació de la partició i de l'algoritme recursiu quick-sort La recurrència de quick-sort s'expressa com: Algoritme Esforç en Dividir Esforç en Combinar Estratègia de memòria Merge- sort Trivial (tall a ) Alt (fusió ordenada amb cost lineal) Requereix vector auxiliar Quick-sort Alt (reorganització al voltant del pivot) Nul (treball ja fet) Ordenació in situ Dividir: reorganitza el vector en dos subvectors no buits de manera que cada element del primer bloc sigui menor o igual que qualsevol element del segon bloc. El càlcul del punt de tall forma part d'aquesta divisió.

1 Resoldre: crida recursivament quick-sort per ordenar cadascun dels dos fragments. 2 Combinar: com que el reordenament es fa directament in situ sobre l'estructura, no cal cap operació per unir les solucions. 3 T(n) = { θ(1) T(k) + T(n k) + θ(n), amb 1 k n 1 si n = 1 si n > 1 n/2 B Dividir i Vèncer: Algorismes i Recurrències (EDA) 7 ERROR FREQÜENT Assumir que quick-sort divideix sempre a la posició central . A quick-sort el punt de partició depèn del valor dels elements i de la funció partition , podent generar subvectors de mides asimètriques i . COMPROVA-HO 10 Quina és la diferència fonamental de cost entre merge-sort i quick-sort pel que fa a l'etapa de combinació?

IDEES CLAU Merge-sort divideix de forma equilibrada a i inverteix el seu esforç principal en la fusió ordenada. Quick-sort reorganitza els elements durant la divisió amb una funció de partició i no requereix feina en la combinació. Merge-sort empra un vector auxiliar de suport, mentre que quick-sort opera in situ. La recurrència de merge-sort és . COMPROVA EL QUE HAS APRÈS 11. Per què quick-sort no necessita cap operació específica en la fase de combinar? 12. Com és la recurrència de merge-sort per a ? Test Encercla la resposta correcta. Les solucions són al final. 13. En quina fase recau la major part del cost computacional a quick-sort? 14.

Quin cost temporal té l'operació de fusionar dos subvectors a merge-sort? 15. Quina característica diferencia la gestió de memòria entre aquests dos mètodes? n/2 k n k n/2 T(n) = 2T(n/2) + θ(n) n > 1 Al càlcul del cas base a) A la còpia al vector auxiliar b) A la combinació final dels blocs c) A la divisió mitjançant partició d) Cost constant Θ(1) a) Cost quadràtic Θ(n²) b) Cost lineal Θ(n) c) Cost logarítmic Θ(log n) d) Merge-sort empra un vector auxiliar a) Quick-sort necessita memòria addicional proporcional b) Merge-sort opera sense recursió c) Tots dos ordenen sense auxiliars d) Dividir i Vèncer: Algorismes i Recurrències (EDA) 8 16.

A quick-sort, quina condició compleixen els elements després de la partició? 3 Aritmètica Eficient: Karatsuba, Exponenciació i Strassen EN ACABAR SABRÀS Calcular termes intermedis en la multiplicació de nombres mitjançant Karatsuba. Formular la reducció de passos a l'exponenciació ràpida segons la paritat. Identificar la relació de recurrència de l'algoritme d'Strassen per a matrius. PENSA-HI ABANS DE LLEGIR 17 Com podem calcular una potència elevada com sense fer 63 multiplicacions consecutives? El mètode de dividir i vèncer permet reduir el nombre d'operacions bàsiques en càlculs numèrics i algebraics d'alta complexitat.

Multiplicació de Karatsuba Considerem dos nombres naturals i representats per bits (amb parell).

Si es descompon cadascun en meitats: El producte algebraic directe generaria 4 multiplicacions de subblocs: Reorganització algebraica del producte en l'algoritme de Karatsuba Tots els elements queden ordenats a) Ambdós subvectors tenen exactament la mateixa mida b) Els del primer subvector són menors o iguals que els del segon c) El vector queda invertit d) 264 x y n n x = 2 × n/2 x + E x i y = D 2 × n/2 y + E y D xy = 2 (x y ) + n E E 2 (x y + n/2 E D x y ) + D E x y D D Dividir i Vèncer: Algorismes i Recurrències (EDA) 9 Karatsuba optimitza el terme intermedi calculant només 3 multiplicacions recursives: Aleshores, el terme central s'obté mitjançant sumes i restes: .

El resultat final s'expressa com: La recurrència temporal obtinguda és: Exponenciació ràpida Calcula la potència amb un cost molt inferior al producte iteratiu estàndard. Redueix el temps de càlcul a cost . Implementació en codi C++ del càlcul de potències L'esquema de descomposició segons la paritat de l'exponent és: Si : retorna 1. Si és parell: calcula i retorna . Si és senar: calcula i retorna .

a = x y E E b = x y D D c = (x + E x )(y + D E y ) D x y + E D x y = D E c a b xy = 2 × n a + 2 (c n/2 a b) + b T(n) = 3T(n/2) + θ(n) xn θ(log n) n = 0 n y = potencia(x, n/2) y × y n y = potencia(x, n/2) y × y × x Dividir i Vèncer: Algorismes i Recurrències (EDA) 10 EXEMPLE Per calcular es realitzen les subdivisions següents: La recurrència associada a aquest mètode és: Multiplicació de matrius d'Strassen La multiplicació tradicional de dues matrius quadrades de mida mitjançant tres bucles aniuats requereix un cost de : Funció clàssica de producte de dues matrius de mida n L'algoritme d'Strassen millora aquesta complexitat subdividint la matriu de elements en submatrius de mida i efectuant 7 multiplicacions recursives (en lloc de les 8 de la formulació clàssica).

La seva relació de recurrència és: ERROR FREQÜENT Confondre el nombre de subproblemes a la recurrència d'Strassen utilitzant el factor 8 propi de la definició matricial bàsica. L'algoritme d'Strassen destaca precisament per reduir les multiplicacions de submatrius a 7. COMPROVA-HO 18 Com aconsegueix Karatsuba reduir les 4 multiplicacions originals a només 3? x62 x = 62 (x ) , x = 31 2 31 (x ) × 15 2 x, x = 15 (x ) × 7 2 x x = 7 (x ) × 3 2 x, x = 3 x × 2 x, x = 1 × x T(n) = T(n/2) + θ(1) n × n θ(n ) 3 n n/2 T(n) = 7T(n/2) + θ(n ) 2 Dividir i Vèncer: Algorismes i Recurrències (EDA) 11 IDEES CLAU Karatsuba redueix la multiplicació de naturals de mida a només 3 crides de mida meitat: .

L'exponenciació ràpida aprofita el quadrat de aconseguint un cost de . El producte convencional de matrius requereix un cost temporal de . L'algoritme d'Strassen fa 7 subdivisions recursives amb una recurrència . COMPROVA EL QUE HAS APRÈS 19. Quantes multiplicacions de subblocs calcula l'algoritme de Karatsuba? 20. Quin cost temporal assoleix l'algoritme d'exponenciació ràpida? Test Encercla la resposta correcta. Les solucions són al final. 21. Quin és el cost temporal del producte tradicional de matrius? 22. Quantes multiplicacions de submatrius de mida n/2 efectua l'algoritme d'Strassen? 23. Com actua l'algoritme d'exponenciació ràpida quan l'exponent n és senar? 24.

Quina és la recurrència de Karatsuba?

n T(n) = 3T(n/2) + θ(n) xn/2 θ(log n) θ(n ) 3 T(n) = 7T(n/2) + θ(n ) 2 Θ(n log n) a) Θ(n) b) Θ(n²) c) Θ(n³) d) 2 multiplicacions a) 4 multiplicacions b) 7 multiplicacions c) 8 multiplicacions d) Finalitza amb resultat 1 a) Retorna directament y * y b) Retorna y * y * x c) Calcula n operacions consecutives d) T(n) = 7T(n/2) + Θ(n²) a) T(n) = 3T(n/2) + Θ(n) b) T(n) = 2T(n/2) + Θ(1) c) T(n) = 4T(n/2) + Θ(n) d) Dividir i Vèncer: Algorismes i Recurrències (EDA) 12 4 Formulari Esquema general i cerca binària Fórmula o procediment Significat dels símbols Quan s'utilitza Dividir problema Resoldre subproblemes (recursivament o cas base) Combinar solucions parcials Passos generals de la tècnica de dividir i vèncer Resolució de problemes fragmentables en subinstàncies de la mateixa naturalesa Comparar amb el punt mig Descartar meitat invàlida Repetir sobre el subvector restant : element cercat; : límits de cerca; : posició central Localització d'un valor dins d'un vector prèviament ordenat creixentment : nombre d'elements; cost constant de comparació i càlcul del punt mitjà Recurrència del cost temporal de la cerca binària ( ) Algorismes d'ordenació Fórmula o procediment Significat dels símbols Quan s'utilitza Merge-sort: Dividir a Ordenar meitats recursivament Fusionar ordenadament amb vector auxiliar Divisió immediata al punt mitjà i combinació mitjançant fusió lineal Ordenació de vectors assegurant un cost temporal asimptòtic òptim Dues crides recursives de mida meitat i pas de fusió de cost lineal Recurrència temporal de l'algorisme merge-sort ( ) Quick-sort: Particionar vector segons pivot Ordenar subvectors recursivament in situ Combinació nul·la Partició amb reordenament segons pivot i sense feina de fusió posterior Ordenació in situ sobre el mateix vector sense memòria auxiliar : mides dels subvectors obtinguts a la partició ( ) Recurrència temporal de l'algorisme quick-sort Aritmètica eficient Fórmula o procediment Significat dels símbols Quan s'utilitza Karatsuba: , , Multiplicació eficient de naturals de bits amb només 3 productes recursius x k = 2 i+j x i, j k T(n) = T(n/2) + θ(1) n θ(log n) n/2 T(n) = 2T(n/2) + θ(n) θ(n log n) T(n) = T(k) + T(n k) + θ(n) k, n k 1 k n 1 xy = 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 Dividir i Vèncer: Algorismes i Recurrències (EDA) 13 Fórmula o procediment Significat dels símbols Quan s'utilitza 3 subproblemes de mida meitat i sumes o desplaçaments lineals Recurrència temporal del mètode de multiplicació de Karatsuba Exponenciació ràpida: Calcular Retornar si és parell, o si és senar : base real; : exponent enter Càlcul ràpid de potències amb cost sublineal Una única crida recursiva sobre l'exponent reduït a la meitat Recurrència de l'exponenciació ràpida ( ) Strassen: 7 multiplicacions de submatrius de mida i sumes de cost quadràtic Multiplicació de matrius quadrades millorant el cost cúbic convencional Errors típics Executar la cerca binària sobre dades no ordenades, fet que produeix resultats incorrectes sense llençar errors d'execució.

Assumir que quick-sort divideix sempre el vector de forma simètrica a la meitat com fa merge-sort. Oblidar que merge-sort requereix memòria addicional per a un vector auxiliar durant la fusió, mentre que quick-sort treballa in situ. Confondre el nombre de subproblemes a Strassen utilitzant el valor 8 del producte habitual en lloc de 7. T(n) = 3T(n/2) + θ(n) y = potencia(x, ) 2 n y × y n y × y × x x n T(n) = T(n/2) + θ(1) θ(log n) T(n) = 7T(n/2) + θ(n ) 2 n/2 θ(n ) 3 Dividir i Vèncer: Algorismes i Recurrències (EDA) 14 Solucions de les preguntes de repàs 1. Obrint per la meitat aproximada, comparant alfabèticament i descartant directament la meitat on és impossible que es trobi. 2.

Es descarta immediatament tota la meitat esquerra del subvector i es realitza una crida recursiva exclusivament sobre l'interval dret desplaçant l'índex inferior a k + 1. 3. Dividir el problema en subproblemes, resoldre recursivament cada subproblema (o directament si és elemental) i combinar les solucions per construir la del problema original. 4. Retorna -1 quan l'interval de cerca esdevé invàlid ( ). 5. c) Que les dades estiguin ordenades creixentment. La propietat d'ordenació creixent permet descartar una de les meitats a cada comparació. 6. b) Una única crida recursiva. Només s'explora el subvector on potencialment es troba el valor (esquerra o dreta). 7.

a) Un subproblema solucionable directament. El cas base s'assoleix quan el problema és prou reduït per resoldre's sense subdividir més. 8. b) T(n) = T(n/2) + Θ(1). Només es resol un subproblema de mida meitat amb un cost constant de comparació. 9. Dividir a cegues obliga a unificar amb compte al final (merge-sort), mentre que separar per un valor límit fa innecessari fusionar després (quick-sort). 10. Merge-sort inverteix un cost lineal de fusió dels dos subvectors ordenats, mentre que quick-sort no requereix cap operació en combinar en ordenar in situ. 11.

Perquè la redistribució dels valors respecte al pivot s'ha realitzat prèviament a la fase de partició directament sobre el propi vector (ordenació in situ). 12. És , on el terme lineal correspon a la fusió dels elements. 13. d) A la divisió mitjançant partició. Quick-sort reorganitza els elements durant la partició, fent que combinar sigui gratuït. 14. c) Cost lineal Θ(n). La combinació a merge-sort recorre els elements dels subvectors amb cost lineal. 15. a) Merge-sort empra un vector auxiliar. Merge-sort necessita un espai addicional per efectuar la fusió correctament. 16. c) Els del primer subvector són menors o iguals que els del segon.

La partició garanteix que qualsevol element de l'esquerra és menor o igual que els de la dreta. 17. Calculant i multiplicant el resultat per ell mateix, repetint el procés de dividir l'exponent entre dos a cada pas. 18. Calcula el producte de les sumes (c) i recupera la suma creuada restant els altres dos productes ja calculats (c - a - b), substituint una multiplicació per addicions. 19. Calcula exactament 3 multiplicacions de mida , aconseguint el terme intermedi mitjançant . 20. Té un cost de gràcies a la relació . 21. d) Θ(n³). El codi clàssic implementa tres bucles aniuats de 0 a n, generant una complexitat cúbica. 22. c) 7 multiplicacions.

Strassen aconsegueix calcular el producte utilitzant 7 multiplicacions recursives en comptes de les 8 convencionals. i > j T(n) = 2T(n/2) + θ(n) 232 n/2 c a b θ(log n) T(n) = T(n/2) + θ(1) Dividir i Vèncer: Algorismes i Recurrències (EDA) 15 23. c) Retorna y * y * x. Quan n és senar, y = , per tant cal elevar y al quadrat i multiplicar pel valor base x. 24. b) T(n) = 3T(n/2) + Θ(n). L'algoritme resol 3 subproblemes de mida meitat i fa operacions lineals de suma i desplaçament. xn/2 Dividir i Vèncer: Algorismes i Recurrències (EDA) 16