A la lliçó anterior vas aprendre a triar estructura amb criteri; en aquesta mirarem enrere amb calma. Repassarem el curs complet explicant-lo com el que realment ha estat: la història de TaskFlow, una aplicació que va començar sent un simple diccionari de Python i ha acabat amb tauler, desfer, notificacions, índexs, jerarquies i un planificador de dependències. Veure tot el camí d'una tirada fixa el mapa mental millor que qualsevol llista de definicions, i el test d'autoavaluació final et dirà amb honestedat què portes ben lligat i què convé repassar abans dels projectes.

1. L'evolució de TaskFlow, mòdul a mòdul
2. Taula-xuleta: tot el que hem construït
3. Els cinc conceptes transversals
4. Què saps fer ara que no sabies en començar
5. Autoavaluació tipus test

TaskFlow va néixer com un dict humil: {"id": 1, "titol": "...", "prioritat": 2, "estat": "pendent"}. Abans de construir res vam aprendre a pensar: la diferència entre el contracte d'un TAD i la seva implementació, la notació Big O d'O(1) a O(n²), la taula de costos de list/dict/set, i com mesurar de debò amb timeit. També vam mirar la memòria de cara: un array és contigüitat pura (base + i × mida, i d'aquí l'accés O(1)), la list de Python és un array dinàmic, i insert(0)/pop(0) amaguen un O(n) que perseguiríem durant tot el curs.

Primer problema real: inserir i esborrar tasques del tauler sense pagar desplaçaments. Amb Node i LlistaEnllacada vam construir el tauler de TaskFlow i vam acceptar el tracte de les llistes enllaçades: inserció O(1) al cap a canvi d'accés O(n) per posició. NodeDoble i LlistaDoblementEnllacada van donar l'HistorialTasques navegable en tots dos sentits, i la LlistaCircular el RepartidorTasques round-robin. De torna, els clàssics: invertir la llista, detectar cicles amb Floyd (llebre i tortuga), fusionar ordenades i inserir_ordenat.

"Ctrl+Z" és l'operació estrella de qualsevol editor, i la seva estructura és la pila: l'últim que has fet és el primer que es desfà. Sobre Pila i PilaEnllacada vam muntar l'HistorialAccions i el GestorDesferRefer amb dues piles (desfer empeny a refer, i viceversa). Vam veure que la pila també valida (filtre_balancejat), calcula (avaluar_postfixa, infixa_a_postfixa), recorda extrems (PilaAmbMinim) i sosté la mateixa execució del programa: la pila de crides explica la recursió, el RecursionError i com convertir recursió en iteració amb una pila explícita.

Les notificacions exigien justícia FIFO: Cua sobre LlistaEnllacada va donar la CuaNotificacions, i pel camí vam demostrar que dues piles fan una cua (CuaAmbDuesPiles). La CuaCircular (ring buffer) va resoldre el RegistreEsdeveniments amb memòria fixa. Quan "per ordre d'arribada" va deixar de bastar, van arribar les cues de prioritat: de la versió ingènua a heapq amb tuples (prioritat, comptador, tasca) a la SafataUrgencies. I collections.deque va demostrar ser la navalla suïssa dels extrems: HistorialAmbLimit amb maxlen, FinestraProductivitat de mitjana mòbil i el deque monòton.

Cercar una tasca per id recorrent llistes era O(n); la màgia O(1) del dict va deixar de ser màgia quan vam construir una taula hash des de zero: TaulaHashIngenua, hash polinòmic, col·lisions per encadenament, factor de càrrega 0.75 i rehashing a TaulaHash. A la pràctica: claus hashables, defaultdict, Counter, l'índex invertit etiqueta→ids del CercadorEtiquetes, memoïtzació i two-sum. I el límit honest que va obrir el mòdul següent: el hash no coneix l'ordre ni entén d'intervals.

Els projectes contenen tasques que contenen subtasques: jerarquia pura. NodeArbre va modelar l'arbre general i pressupostar va mostrar el poder del postordre (els fills abans que el pare). Amb NodeBinari van arribar els tipus d'arbre, la representació en array (fills a 2i+1/2i+2) i els quatre recorreguts, també iteratius amb pila. L'ArbreCerca (ABC) va resoldre per fi "prioritat entre 1 i 3" amb interval, l'ArbreAVL va garantir O(log n) amb rotacions, els arbres B/B+ van explicar els índexs de les bases de dades, i el Monticle propi (flotar/enfonsar) va reconstruir heapq per dins per a la SafataUrgencies 2.0. Clàssics: es_abc, reconstruir, top_k.

"La tasca B no pot començar fins a acabar l'A" no és jerarquia: és un graf. La classe Graf (llista d'adjacència com a dict de dicts, amb la convenció "aresta A→B = B depèn d'A") va modelar el DAG de TaskFlow. BFS amb deque, DFS recursiu i iteratiu, hi_ha_cicle amb colors blanc/gris/negre i l'ordre_topologic de Kahn van ordenar la feina; components_connexes va agrupar; dijkstra, bellman_ford i la menció a Floyd-Warshall van mesurar camins; prim, kruskal i UnionFind van teixir xarxes mínimes. La cirereta: el planificador complet amb nivells paral·lels i ruta_critica, més suggerir_collaboradors, pagerank i els grafs implícits en graella.

Aquest mòdul: el mètode de les set preguntes, l'arbre de decisió, la gran taula, i els projectes que vindran.

El teu índex de referència ràpida. Si algun nom no t'evoca immediatament la seva idea, aquella és la lliçó a repassar.

Més importants que qualsevol estructura concreta, perquè són els que continuaràs fent servir quan apareguin estructures que aquest curs no cobreix:

1. TAD davant d'implementació. La pila és un contracte (push/pop/peek); list, PilaEnllacada o un deque són maneres de complir-lo. Programa contra el contracte i podràs canviar la implementació sense tocar la resta del codi.
2. Big O com a idioma. No és matemàtica decorativa: és la manera de predir si un codi que funciona amb 100 elements sobreviurà a 100 000. La diferència entre in sobre list (O(n)) i sobre set (O(1)) decideix si el teu bucle és lineal o quadràtic.
3. Recursió ↔ iteració. Tota recursió és una pila implícita; tota recursió es pot reescriure amb una pila explícita (i de vegades convé, recorda el RecursionError). Recorreguts d'arbres i DFS són el mateix patró amb dos vestits.
4. Estructures que construeixen estructures. La cua sobre llista enllaçada, la cua amb dues piles, la pila amb mínim, el monticle sobre array, el graf sobre dict de dicts, la memòria cau LRU amb dict + llista doble... Compondre és l'habilitat; memoritzar, només la drecera.
5. Mesurar en lloc de suposar. timeit va ser la primera eina del curs i ha de ser l'última paraula en qualsevol discussió de rendiment. La teoria orienta; les dades reals decideixen.

Llista honesta: tot això ho has fet, no només llegit.

• Llegir i escriure anàlisis Big O del teu propi codi, i verificar la teoria amb timeit.
• Implementar des de zero, en Python, llistes enllaçades (simple, doble, circular), piles, cues, ring buffers, taules hash amb col·lisions i rehashing, ABC, AVL, monticles i grafs.
• Triar entre list, dict, set, deque i heapq sabent què hi ha a sota i què costa cada operació.
• Reconèixer patrons: LIFO → pila, FIFO → cua, "el més urgent" → monticle, clau exacta → hash, intervals → arbre, dependències → graf.
• Aplicar els algorismes clàssics: Floyd, recorreguts d'arbres, BFS/DFS, detecció de cicles, ordre topològic, Dijkstra, Bellman-Ford, Prim, Kruskal.
• Combinar estructures coordinades per complir diversos requisits de cost alhora.
• I el que encara no saps (ordenació en profunditat, programació dinàmica, tries...): ho tens localitzat, i la lliçó següent et dona el mapa per arribar-hi.

• Confondre "em sona" amb "ho sé". El test de sota només és útil si el fas sense mirar; el repàs passiu produeix una falsa sensació de domini.
• Repassar estructures com fitxes aïllades. Repassa problemes: "com faria el desfer?", "com detectaria el cicle?". L'estructura ha de venir a tu des del problema, no a l'inrevés.
• Saltar-se els perquès. Saber que el dict és O(1) sense recordar el hash polinòmic i el rehashing és coneixement fràgil: cau a la primera pregunta de seguiment d'una entrevista.
• No reimplementar de memòria. Abans dels projectes, prova de reescriure sense mirar una Pila, una CuaCircular i el BFS. Allà on t'encallis, allà hi ha el teu buit real.

Autoavaluació tipus test. Respon sense consultar les lliçons i després contrasta amb les solucions raonades.

1. En una list de Python amb 1 000 000 d'elements, quina d'aquestes operacions és la més cara? (a) llista[500000] (b) llista.append(x) (c) llista.insert(0, x) (d) llista.pop()
2. El GestorDesferRefer fa servir dues piles. En executar "desfer", què passa exactament?
3. Per què la SafataUrgencies encua tuples (prioritat, comptador, tasca) i no (prioritat, tasca)?
4. Un company guarda els ids de tasques completades en una list i comprova id in completades dins d'un bucle sobre 50 000 tasques. Quin és el cost total i com ho arregles?
5. Quina estructura respon "dona'm totes les tasques amb prioritat entre 1 i 3" en O(log n + k), i per què un dict no pot?
6. Insereixes en un ABC les claus 1, 2, 3, 4, 5, en aquest ordre. Quina forma té l'arbre i quin cost té ara cercar el 5? Quina estructura ho evita?
7. Quin recorregut va fer servir pressupostar per sumar el cost de projectes → tasques → subtasques, i per què precisament aquell?
8. Al DAG de dependències de TaskFlow, quin algorisme et dona un ordre vàlid d'execució i quin senyal t'avisa que no existeix tal ordre?
9. Vertader o fals? "Un monticle manté tots els seus elements completament ordenats."
10. Quines dues estructures combinava la memòria cau del "mode repàs" (exercici 3 de la lliçó anterior) i què hi aporta cadascuna?

1. (c) insert(0, x) és O(n): desplaça el milió d'elements una posició. (a) és O(1) per contigüitat (base + i × mida); (b) i (d) són O(1) (amortitzat en l'append) perquè toquen només el final.
2. Es fa pop de la pila de desfer (l'acció més recent), se'n reverteix l'efecte i aquella acció es fa push a la pila de refer. Si després l'usuari executa una acció nova, la pila de refer es buida: la història alternativa deixa de ser vàlida.
3. Dues raons: el comptador desempata prioritats iguals garantint l'ordre d'arribada (FIFO dins de la mateixa prioritat) i, a més, evita que heapq intenti comparar els dicts de tasca entre si (els dict no són comparables i llançaria un TypeError).
4. in sobre list és O(n); dins del bucle, O(n·m) — amb 50 000 tasques, de l'ordre de milers de milions de comparacions. Converteixes completades en set un sol cop (O(m)) i cada consulta passa a O(1): el total queda en O(n + m).
5. Un ABC/AVL (o una llista ordenada amb bisect): baixes fins a l'inici de l'interval en O(log n) i recorres en inordre els k resultats. El dict no pot perquè la funció hash dispersa a propòsit: destrueix tota relació d'ordre entre claus per aconseguir l'O(1) per clau exacta.
6. Degenera en una "llista" inclinada a la dreta: cada clau és més gran que l'anterior, així que tots pengen del fill dret. Cercar el 5 costa O(n). Ho evita l'AVL, que rota en detectar desequilibri i garanteix alçada O(log n) arribi com arribi l'entrada.
7. Postordre: processa els fills abans que el pare, de manera que quan toca calcular el pressupost d'un node, els pressupostos de tots els seus subarbres ja estan calculats i n'hi ha prou de sumar-los.
8. L'ordre topològic (Kahn: anar extraient nodes amb grau d'entrada 0). Si l'algorisme acaba sense haver processat tots els vèrtexs —o si el DFS de colors troba una aresta cap a un node gris—, hi ha un cicle de dependències i no existeix ordre vàlid.
9. Fals. El monticle només garanteix la propietat de monticle: cada pare ≤ els seus fills (en un min-heap). El mínim és a l'arrel, però els germans no guarden ordre entre si; per això inserir i extreure són O(log n) i no O(n) — és un ordre "suficient", no total.
10. Un dict id→node (localitzar en O(1)) i una llista doblement enllaçada amb l'ordre d'ús (moure un node al cap i expulsar per la cua en O(1)). El dict no sap d'ordre; la llista no sap cercar: juntes, totes les operacions són O(1).

Interpretació: 9-10 encerts, a punt per als projectes; 6-8, repassa les lliçons de les preguntes fallades; menys de 6, torna als exercicis dels mòduls fluixos abans de continuar — els projectes finals assumeixen tot això.

TaskFlow ha passat d'un dict solt a un sistema amb set famílies d'estructures treballant coordinades, i tu has passat de fer servir list "perquè sí" a justificar cada tria amb operacions i costos. El mapa és complet: els fonaments (mòdul 1), les estructures lineals (2-4), els índexs (5), les jerarquies (6), les xarxes (7) i el criteri (8). A la lliçó següent et deixo la biblioteca: els recursos amb què continuar creixent pel teu compte quan aquest curs s'acabi.