El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

Fins aquí has entrenat cada múscul per separat: anàlisi (06-01), disseny (06-02) i optimització (06-03). Els tres projectes d'aquesta lliçó els fan servir tots alhora: són peces completes de RutaBus, de principi a fi, com les que construiries en un equip real.

Com treballar aquesta lliçó: cada projecte porta context, requisits, un pla per fases (amb el mòdul del curs que aplica cadascuna), un esquelet de partida i una llista d'autoavaluació. Implementa el projecte sencer abans de mirar la solució de referència, i fes servir la llista d'autoavaluació com a criteri d'"acabat". La solució de referència no és "la" solució: és una solució correcta i raonada contra la qual contrastar la teva. Si el teu enfocament difereix però compleix la llista, és igual de vàlid.

Contingut

Projecte 1: Planificador de trajectes (M4 + M2).
Projecte 2: Quadre de comandament de la flota (M2 + M4 + M5).
Projecte 3: Planificador de torns i reforços (M3).
Conclusió del curs.

Projecte 1: Planificador de trajectes

Dificultat: mitjana · Integra: Mòdul 4 (Dijkstra, Floyd-Warshall) + Mòdul 2 (anàlisi per decidir).

Context. L'app de RutaBus necessita respondre "com vaig d'A a B?" tenint en compte els transbordaments: canviar de línia en una parada costa 5 minuts. La xarxa:

L1: Plaça Major —3— Estació Nord —4— Hospital Central —6— Parc del Riu
L2: Estació Nord —5— Mercat Vell —4— Universitat —3— Parc del Riu
L3: Plaça Major —7— Universitat —4— Poliesportiu Sud

(els números són minuts entre parades consecutives; totes les línies circulen en tots dos sentits).

Requisits funcionals.

Modelar la xarxa com un graf ponderat que capturi els transbordaments.
millor_trajecte(origen, desti): minuts totals i l'itinerari complet (parades i canvis de línia).
Precalcular la taula de temps tots-amb-tots amb Floyd-Warshall.
Decidir, amb arguments de complexitat, quin enfocament ha de fer servir l'app en producció.

Pla per fases.

Fase	Tasca	Aplica
1	Modelar: el truc és que el node no és la parada, sinó el parell (parada, línia)	01-02, 05-02 (dict vs matriu)
2	Dijkstra amb heap + reconstrucció del camí	04-05
3	Floyd-Warshall sobre els mateixos nodes	04-06
4	Comparar cost/memòria de tots dos i decidir	M2, 05-01

Esquelet de partida.

import heapq

LINIES = {
    "L1": [("Plaça Major", 3), ("Estació Nord", 4),
           ("Hospital Central", 6), ("Parc del Riu", 0)],
    "L2": [("Estació Nord", 5), ("Mercat Vell", 4),
           ("Universitat", 3), ("Parc del Riu", 0)],
    "L3": [("Plaça Major", 7), ("Universitat", 4), ("Poliesportiu Sud", 0)],
}
TRANSBORDAMENT = 5   # minuts per canviar de linia en una mateixa parada

def construeix_xarxa():
    """Retorna dict d'adjacencia: {(parada, linia): {(parada, linia): minuts}}."""
    # TODO: arestes entre parades consecutives de cada linia (tots dos sentits)
    # TODO: arestes de transbordament entre les linies que comparteixen parada

def millor_trajecte(xarxa, origen, desti):
    """Retorna (minuts, [(parada, linia), ...]) o None si no hi ha cami."""
    # TODO: Dijkstra multiorigen (el viatger comenca a la parada, en qualsevol linia)

def floyd_warshall(xarxa):
    """Retorna (nodes, matriu) amb els temps minims tots-amb-tots."""
    # TODO

Criteris d'autoavaluació.

[ ] Un trajecte sense transbordament guanya a un amb transbordament quan els minuts ho justifiquen (Plaça Major → Universitat ha de donar 7 min per L3, no 17 per L1+L2).
[ ] L'itinerari retornat mostra on es canvia de línia.
[ ] Dijkstra fa servir heap i no revisita nodes tancats (04-05).
[ ] Floyd-Warshall i Dijkstra donen els mateixos temps per a tots els parells (prova-ho amb un bucle!).
[ ] La decisió final cita complexitats concretes, no impressions.

Solució de referència

Fase 1 — Modelatge. Si el node fos només la parada, no hi hauria manera de cobrar el transbordament: el graf no sabria en quina línia "ets". La solució estàndard és desdoblar: el node és (parada, línia), amb arestes de viatge dins de cada línia i arestes de transbordament (5 min) entre les línies que comparteixen parada.

from collections import defaultdict

def construeix_xarxa():
    xarxa = defaultdict(dict)
    for linia, parades in LINIES.items():
        for (p1, w), (p2, _) in zip(parades, parades[1:]):
            xarxa[(p1, linia)][(p2, linia)] = w   # anada
            xarxa[(p2, linia)][(p1, linia)] = w   # tornada
    per_parada = defaultdict(list)
    for node in list(xarxa):
        per_parada[node[0]].append(node)
    for nodes in per_parada.values():             # transbordaments
        for a in nodes:
            for b in nodes:
                if a != b:
                    xarxa[a][b] = TRANSBORDAMENT
    return dict(xarxa)

Triem dict d'adjacència i no matriu perquè la xarxa és dispersa: cada node té 2–4 veïns, i com vam veure a 05-02, la matriu només compensa en grafs densos.

Fase 2 — Dijkstra amb reconstrucció. Detall important: el viatger comença "a la parada", sense línia assignada. En lloc d'inventar un node virtual, sembrem el heap amb tots els nodes (origen, línia) a distància 0 (Dijkstra multiorigen: mateix algorisme, diverses llavors):

def millor_trajecte(xarxa, origen, desti):
    inicis = [n for n in xarxa if n[0] == origen]
    dist = {n: 0 for n in inicis}
    previ = {n: None for n in inicis}
    heap = [(0, n) for n in inicis]
    heapq.heapify(heap)
    tancats = set()
    while heap:
        d, node = heapq.heappop(heap)
        if node in tancats:
            continue
        tancats.add(node)
        if node[0] == desti:                      # primera vegada que tanquem
            cami = []                             #   el desti: es optim
            while node is not None:               #   (pesos >= 0, 04-05)
                cami.append(node)
                node = previ[node]
            return d, list(reversed(cami))
        for vei, w in xarxa[node].items():
            nd = d + w
            if vei not in dist or nd < dist[vei]:
                dist[vei] = nd
                previ[vei] = node
                heapq.heappush(heap, (nd, vei))
    return None

xarxa = construeix_xarxa()
print(millor_trajecte(xarxa, "Plaça Major", "Universitat"))
# (7, [('Plaça Major', 'L3'), ('Universitat', 'L3')])
print(millor_trajecte(xarxa, "Hospital Central", "Universitat"))
# (14, [('Hospital Central', 'L1'), ('Parc del Riu', 'L1'),
#       ('Parc del Riu', 'L2'), ('Universitat', 'L2')])

Fixa't en el segon exemple: l'itinerari fa visible el transbordament (Parc del Riu L1 → Parc del Riu L2, +5 min), i Dijkstra va triar transbordar a Parc del Riu (6+5+3 = 14) i no a Estació Nord (4+5+5+4 = 18). Poder acabar tan bon punt es tanca el destí és la propietat de 04-05: amb pesos no negatius, un node tancat ja té la seva distància definitiva.

Fase 3 — Floyd-Warshall. Sobre els mateixos nodes, la versió de 04-06:

def floyd_warshall(xarxa):
    nodes = list(xarxa)
    idx = {n: i for i, n in enumerate(nodes)}
    INF = float("inf")
    n = len(nodes)
    D = [[INF] * n for _ in range(n)]
    for i in range(n):
        D[i][i] = 0
    for a, veins in xarxa.items():
        for b, w in veins.items():
            D[idx[a]][idx[b]] = w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if D[i][k] + D[k][j] < D[i][j]:
                    D[i][j] = D[i][k] + D[k][j]
    return nodes, D

Fase 4 — Decisió. La nostra xarxa té V = 11 nodes: Floyd-Warshall fa 11³ ≈ 1300 operacions i la seva matriu ocupa 121 cel·les — tot trivial. Però l'app aspira a xarxes urbanes reals; escalem amb l'anàlisi de M2 a V ≈ 5000 nodes (2000 parades, diverses línies):

Enfocament	Cost	Memòria	Consulta
Floyd-Warshall precalculat	Θ(V³) ≈ 1,25·10¹¹ ops (minuts o hores)	Θ(V²) ≈ 200 MB	O(1)
Dijkstra sota demanda	—	Θ(V + E) (el graf)	O((V+E) log V) ≈ mil·lisegons

Recomanació: Dijkstra sota demanda. Una consulta en mil·lisegons és de sobres ràpida per a una app mòbil, la memòria és mínima, i —decisiu— la xarxa canvia (talls, reforços): recalcular tot el Θ(V³) per cada incidència és inviable, mentre que Dijkstra sempre treballa sobre el graf vigent. Floyd-Warshall queda per a xarxes petites i estàtiques o per a anàlisi offline (p. ex. detectar els parells de parades més mal connectats de tota la xarxa, on de totes maneres vols la taula completa). I si un dia les consultes dominen, el camí intermedi és desar en memòria cau els parells freqüents — mesurar primer (05-01) dirà si cal.

Projecte 2: Quadre de comandament de la flota

Dificultat: mitjana-alta · Integra: Mòdul 2 (costos) + Mòdul 4 (merge, top-k) + Mòdul 5 (memòria).

Context. Cada autobús bolca al final del dia un fitxer CSV de fitxatges, ordenat per hora: hora;parada;linia;import (p. ex. 07:41:03;Estació Nord;L2;1.20). Amb centenars de busos i milions de línies per dia, operacions vol un quadre de comandament diari que avui rebenta el servidor de memòria.

Requisits funcionals.

Llegir els fitxers sense carregar-los sencers en memòria.
Calcular en una sola passada: fitxatges per línia, fitxatges per parada i recaptació total.
Combinar els k fitxers diaris (cadascun ja ordenat per hora) en un únic flux cronològic, també sense materialitzar-lo.
Obtenir el top-10 de parades per nombre de fitxatges sense ordenar totes les parades.
Justificar la memòria de cada peça i amb quina eina la verificaries.

Pla per fases.

Fase	Tasca	Aplica
1	Ingesta amb generadors	05-02
2	Agregats en streaming amb dict (cost O(1) per accés)	02-01
3	Fusió cronològica de k fluxos ordenats (merge_k amb heap)	04-03, 04-05
4	Top-k amb heap (i per què no quickselect aquí)	04-04
5	Verificació: `tracemalloc` i `timeit`	05-01, 05-02

Esquelet de partida.

import heapq

def llegeix_fitxatges(ruta):
    """Generador que produeix tuples (hora, parada, linia, import)."""
    # TODO: no fer servir readlines()

def resum(fitxatges):
    """Una sola passada: (fitxatges_per_linia, fitxatges_per_parada, recaptacio)."""
    # TODO

def fusiona_dies(rutes, ruta_sortida):
    """Mescla k fitxers ordenats per hora en un de global ordenat."""
    # TODO: memoria O(k), no O(n)

def top_parades(fitxatges_per_parada, k=10):
    """Top-k parades per fitxatges, sense ordenar-les totes."""
    # TODO

Criteris d'autoavaluació.

[ ] llegeix_fitxatges pot processar un fitxer de 10 GB en una màquina de 8 GB (raona-ho; no cal el fitxer).
[ ] resum fa una passada i cap accés dins del bucle no és O(n) (repassa 06-01, exercici 2).
[ ] fusiona_dies manté en memòria com a molt un registre per fitxer obert.
[ ] top_parades és Θ(p log k), no Θ(p log p).
[ ] Saps dir el pic de memòria teòric de cada funció i com confirmar-lo.

Solució de referència

Fases 1 i 2 — Ingesta i agregats en streaming.

def llegeix_fitxatges(ruta):
    with open(ruta, encoding="utf-8") as f:
        for registre in f:                    # el fitxer ja es un iterador
            hora, parada, linia, import_ = registre.rstrip("\n").split(";")
            yield hora, parada, linia, float(import_)

def resum(fitxatges):
    per_linia, per_parada, recaptacio = {}, {}, 0.0
    for hora, parada, linia, import_ in fitxatges:
        per_linia[linia] = per_linia.get(linia, 0) + 1
        per_parada[parada] = per_parada.get(parada, 0) + 1
        recaptacio += import_
    return per_linia, per_parada, recaptacio

Memòria: el generador reté un registre cada vegada (O(1) respecte del fitxer, 05-02); els acumuladors creixen amb el nombre de línies i parades diferents (desenes), no amb els milions de fitxatges. Cada accés al dict és O(1) — amb llistes i in seria el desastre quadràtic de l'exercici 2 de 06-01. Un fitxer de 10 GB passa per una màquina de 8 GB sense immutar-se, perquè mai no és sencer en memòria.

Fase 3 — Fusió cronològica. És la mescla de k llistes ordenades de 04-03 (merge_k), amb el heap mantenint el mínim de les k capçaleres. La llibreria estàndard la porta feta, i accepta iterables mandrosos:

def fusiona_dies(rutes, ruta_sortida):
    fluxos = [llegeix_fitxatges(r) for r in rutes]
    with open(ruta_sortida, "w", encoding="utf-8") as sortida:
        for hora, parada, linia, import_ in heapq.merge(*fluxos):
            sortida.write(f"{hora};{parada};{linia};{import_:.2f}\n")

En memòria només hi viuen k registres (un per flux) més el heap de mida k: O(k), amb k = nombre de busos, tant se val que cada fitxer faci gigabytes. Temps: Θ(n log k) per a n registres totals. Això és, literalment, la fase de mescla de l'ordenació externa que vam esbossar a 04-03. (Les hores amb format HH:MM:SS d'amplada fixa es comparen bé com a cadenes; si el format fos variable, caldria convertir-les a una clau comparable.) I si un fitxer individual arribés gairebé ordenat però amb algun ressagat? sorted() el repararia gairebé en temps lineal gràcies a Timsort (04-02/04-03)… a costa de materialitzar-lo; per a fitxers que caben en memòria és l'opció simple, per als que no, ordenació externa per trossos.

Fase 4 — Top-k.

def top_parades(per_parada, k=10):
    return heapq.nlargest(k, per_parada.items(), key=lambda kv: kv[1])

Θ(p log k) amb p parades: per a p = 2000 i k = 10, unes 2000 comparacions amb un heap de 10, davant del Θ(p log p) d'ordenar-ho tot. I quickselect (04-04, k_mes_primerenques)? És Θ(p) de mitjana, millor asimptòticament… però exigeix la llista completa en memòria i reordenable, no retorna el top ordenat i el seu pitjor cas és Θ(p²). Amb p petit i fluxos mandrosos, el heap és l'eina natural; quickselect brilla quan p és enorme, ja és en memòria i k és gran.

Fase 5 — Verificació. Pic de memòria teòric: llegeix_fitxatges O(1), resum O(línies + parades diferents), fusiona_dies O(k), top_parades O(k). Confirmació: tracemalloc al voltant de cada fase amb un fitxer sintètic (05-02) i timeit per als temps (05-01). Si el pic real no quadra amb el teòric, gairebé sempre hi ha un list(...) o un sorted(...) traïdor materialitzant un generador — l'error silenciós número u d'aquest estil de codi.

Projecte 3: Planificador de torns i reforços

Dificultat: alta · Integra: Mòdul 3 complet (backtracking, greedy amb justificació, PD amb reconstrucció).

Context. Operacions planifica el dissabte: cobrir els torns de conductor, atendre les franges de saturació amb l'únic bus de reforç disponible, i decidir en quines millores d'infraestructura gastar el pressupost anual.

Requisits funcionals.

Torns: assignar un conductor a cadascun dels 6 torns (L1/L2/L3 × matí/nit). Disponibilitat: Anna (matí i nit), Bruno (només matí), Carla (només nit), Diego (matí i nit). Màxim 2 torns per conductor i, per descans obligatori, ningú no pot fer matí i nit el mateix dia. Backtracking amb almenys una poda.
Reforços: donades les franges de saturació previstes [(9, 11), (10, 12), (11, 13), (14, 15), (15, 17), (16, 18)] (hores), triar el màxim nombre de franges que el bus de reforç pot atendre sense solapar-se, justificant que el criteri triat és òptim.
Pressupost: amb 10 k€, triar entre marquesina nova (3 k€, benefici 4), pantalles d'informació (4 k€, benefici 5), wifi a les parades (2 k€, benefici 3) i carril reservat (7 k€, benefici 9), maximitzant el benefici. PD amb taula i reconstrucció de quines millores comprar. Comprova si el greedy per ràtio benefici/cost hauria encertat.

Pla per fases.

Fase	Tasca	Aplica
1	Torns: decidir → recórrer → desfer, amb poda de capacitat	03-04
2	Reforços: criteri greedy + argument d'intercanvi	03-02
3	Pressupost: motxilla 0/1 amb taula i reconstrucció	03-03

Esquelet de partida.

TORNS = [("L1", "Matí"), ("L1", "Nit"), ("L2", "Matí"),
         ("L2", "Nit"), ("L3", "Matí"), ("L3", "Nit")]
DISPONIBILITAT = {"Anna": {"Matí", "Nit"}, "Bruno": {"Matí"},
                  "Carla": {"Nit"}, "Diego": {"Matí", "Nit"}}

def assigna_torns():
    """Dict torn -> conductor, o None si no hi ha assignacio valida."""
    # TODO: backtracking amb poda

def aten_franges(franges):
    """Maxim conjunt de franges sense solapament per al bus de reforc."""
    # TODO: greedy justificat

def pla_millores(millores, pressupost):
    """(benefici_maxim, llista_de_millores_triades)."""
    # TODO: PD amb reconstruccio

Criteris d'autoavaluació.

[ ] assigna_torns desfà sempre les seves decisions en retrocedir (prova: crida-la dues vegades; ha de donar el mateix).
[ ] Hi ha una poda que talla abans de baixar de nivell, no una comprovació final.
[ ] La justificació del greedy és un argument d'intercanvi, no "ho he provat i funciona".
[ ] pla_millores retorna què comprar, no només quant benefici.
[ ] Has comparat la PD contra el greedy per ràtio i saps quin guanya i per què.

Solució de referència

Fase 1 — Torns amb backtracking.

def assigna_torns():
    assignacio, torns_de = {}, {c: [] for c in DISPONIBILITAT}

    def pot(conductor, franja):
        if franja not in DISPONIBILITAT[conductor]:
            return False
        if len(torns_de[conductor]) >= 2:
            return False
        franges_previes = {f for _, f in torns_de[conductor]}
        return not (franges_previes and franja not in franges_previes)  # descans

    def resol(i):
        if i == len(TORNS):
            return True
        linia, franja = TORNS[i]
        # PODA: queda capacitat suficient per a aquesta franja?
        pendents = sum(1 for l, f in TORNS[i:] if f == franja)
        capacitat = sum(2 - len(torns_de[c]) for c in DISPONIBILITAT
                        if pot(c, franja))
        if capacitat < pendents:
            return False
        for c in DISPONIBILITAT:
            if pot(c, franja):
                assignacio[(linia, franja)] = c          # decidir
                torns_de[c].append((linia, franja))
                if resol(i + 1):
                    return True
                torns_de[c].pop()                        # desfer
                del assignacio[(linia, franja)]
        return False

    return dict(assignacio) if resol(0) else None

print(assigna_torns())
# {('L1','Matí'): 'Anna', ('L1','Nit'): 'Carla', ('L2','Matí'): 'Anna',
#  ('L2','Nit'): 'Carla', ('L3','Matí'): 'Bruno', ('L3','Nit'): 'Diego'}

El patró és el d'assigna_torns de 03-04: decidir, recórrer, desfer. La regla de descans s'implementa com a restricció incremental (les franges prèvies del conductor han de coincidir amb la nova), i la poda de capacitat talla la branca quan els torns pendents d'una franja superen la capacitat restant dels conductors que encara la poden prendre — la impossibilitat es detecta nivells abans d'ensopegar-hi. Observa la solució: l'Anna i la Carla absorbeixen els matins i les nits "dobles" i ningú no barreja franges.

Fase 2 — Reforços amb greedy justificat. És estructuralment la selecció d'activitats de 03-02: mateix valor per franja, maximitzar quantes n'hi caben. Criteri: atendre sempre la franja que acaba abans d'entre les compatibles.

def aten_franges(franges):
    triades, fi_actual = [], float("-inf")
    for inici, fi in sorted(franges, key=lambda x: x[1]):
        if inici >= fi_actual:
            triades.append((inici, fi))
            fi_actual = fi
    return triades

print(aten_franges([(9, 11), (10, 12), (11, 13), (14, 15), (15, 17), (16, 18)]))
# [(9, 11), (11, 13), (14, 15), (15, 17)]  -> 4 franges

Justificació (intercanvi): sigui g la primera franja que tria el greedy (la de fi més primerenc) i O una solució òptima qualsevol. La primera franja d'O acaba en algun f ≥ fi(g); si substituïm aquella franja per g, cap franja posterior d'O no se solapa (totes comencen després de f ≥ fi(g)), així que O continua sent vàlida i de la mateixa mida. Iterant l'argument sobre la resta, el greedy assoleix la mida òptima. Cost: Θ(n log n) per l'ordenació. Nota que "començar per la més llarga" o "la que comença abans" fallen — (9,11),(10,12),(11,13) és un contraexemple de la segona si es tria (10,12).

Fase 3 — Pressupost amb PD i reconstrucció. Motxilla 0/1 (03-03) amb capacitat 10:

def pla_millores(millores, pressupost):
    n = len(millores)
    dp = [[0] * (pressupost + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        nom, cost, benefici = millores[i - 1]
        for c in range(pressupost + 1):
            dp[i][c] = dp[i - 1][c]                       # no comprar
            if cost <= c:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - cost] + benefici)
    triades, c = [], pressupost                            # reconstruccio
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i - 1][c]:                       # es va comprar la millora i
            nom, cost, _ = millores[i - 1]
            triades.append(nom)
            c -= cost
    return dp[n][pressupost], list(reversed(triades))

MILLORES = [("marquesina", 3, 4), ("pantalles", 4, 5),
            ("wifi", 2, 3), ("carril reservat", 7, 9)]
print(pla_millores(MILLORES, 10))
# (13, ['marquesina', 'carril reservat'])

Òptim: marquesina + carril reservat = 10 k€ i benefici 13. El greedy per ràtio benefici/cost (wifi 1,5 → marquesina 1,33 → carril 1,29 → pantalles 1,25) compraria wifi + marquesina (5 k€) i després pantalles (9 k€ en total), benefici 12, i ja no pot pagar el carril: es queda a un de l'òptim. L'error és el de sempre (03-02): el criteri local omple el pressupost amb peces "eficients" que bloquegen la combinació bona — exactament el que va motivar motxilla_millores a 03-03. La reconstrucció (comparar dp[i][c] amb dp[i-1][c] cap enrere) és la part que els projectes reals no perdonen: al departament de compres no li val "el benefici màxim és 13"; necessita la llista.

Conclusió del Curs

S'ha acabat el temari. Val la pena mirar enrere i veure l'edifici complet:

Al Mòdul 1 vas posar els fonaments: què és un algorisme, com expressar-lo (pseudocodi, diagrames, Python), la diferència entre iteratiu i recursiu, entre exacte i heurístic, i el llenguatge que ho vertebra tot: la notació asimptòtica i la seva jerarquia, d'O(1) a O(2ⁿ).
Al Mòdul 2 vas aprendre a analitzar: derivar la complexitat temporal línia a línia (amb els costos ocults de Python inclosos), mesurar l'espai auxiliar i el total, i matisar amb millor cas, pitjor cas, cas mitjà i cost amortitzat.
Al Mòdul 3 vas aprendre a dissenyar: divideix i venceràs, greedy (i la seva obligació de demostrar o refutar), programació dinàmica i backtracking amb poda — i, sobretot, a diagnosticar quina demana cada problema.
Al Mòdul 4 vas incorporar els clàssics — cerca binària, inserció, merge sort, quicksort, Dijkstra, Floyd-Warshall — no com a receptes, sinó com a peces el funcionament i els límits de les quals entens i saps adaptar.
Al Mòdul 5 vas aprendre a optimitzar amb mètode: mesurar primer, atacar per ordre (algorisme → codi → memòria → paral·lelitzar) i saber quan parar.
I en aquest Mòdul 6 ho has entrenat tot junt, fins a muntar peces completes de RutaBus: un planificador de trajectes, un quadre de comandament que processa gigabytes sense despentinar-se i un planificador de torns, reforços i pressupost.

El que saps fer ara, dit sense embuts: mirar codi i veure'n el cost; mirar un problema i reconèixer-ne l'estratègia; mirar un sistema lent i saber per on començar. Aquesta tripleta —analitzar, dissenyar, optimitzar— és transversal a qualsevol llenguatge i qualsevol domini: avui ha estat Python i una app d'autobusos; demà serà un altre stack i un altre negoci, i el raonament serà el mateix.

Suggeriments per continuar creixent des d'aquí:

Estructures de dades avançades: arbres equilibrats, tries, taules hash per dins, union-find, grafs amb A* — són el complement natural d'aquest curs, perquè molts "algorismes millors" són en realitat "estructures millors".
Pràctica deliberada: les plataformes de problemes (LeetCode, Codeforces, Advent of Code) mantenen en forma el diagnòstic de l'exercici 5 de 06-02; amb uns quants per setmana n'hi ha prou.
Els teus propis projectes: la pròxima vegada que escriguis un bucle sobre dades de debò, fes-li l'anàlisi de 06-01 abans de prémer executar. Aquest hàbit, sostingut uns mesos, és el que converteix el contingut d'aquest curs en instint.
Lectures: quan vulguis profunditat formal, els textos de referència habituals (Cormen et al., Introduction to Algorithms; Skiena, The Algorithm Design Manual) amplien amb rigor tot el que aquí s'ha presentat amb enfocament pràctic.

La soltesa que anunciàvem en començar aquest mòdul no acaba mai d'arribar del tot — sempre hi ha un problema que es resisteix — però ja no parteix de zero: parteix d'un mètode. Gràcies per arribar fins aquí, i bon viatge. A RutaBus dirien: fi de trajecte; esperem que hagi estat un bon recorregut.

Projectes Finals

Contingut

Projecte 1: Planificador de trajectes

Solució de referència

Projecte 2: Quadre de comandament de la flota

Solució de referència

Projecte 3: Planificador de torns i reforços

Solució de referència

Conclusió del Curs

Curs d'Anàlisi i Disseny d'Algorismes

Mòdul 1: Introducció als Algorismes

Mòdul 2: Anàlisi d'Algorismes

Mòdul 3: Estratègies de Disseny d'Algorismes

Mòdul 4: Algorismes Clàssics

Mòdul 5: Optimització d'Algorismes

Mòdul 6: Pràctiques i Exercicis