El mòdul 6 es va tancar amb una promesa: el cas d'estudi el tries tu. Durant sis mòduls has vist com Rutalia —la nostra empresa fictícia de logística d'última milla— convertia problemes reals en models, els models en algorismes i els algorismes en decisions mesurables. Ara et toca recórrer aquest mateix camí amb un problema propi. Aquesta primera lliçó del projecte final té un únic objectiu: que en surtis amb una especificació escrita, validada i realista del teu projecte. Sembla poc, però és la fase on més projectes autodidactes moren: qui comença a programar sense especificació sol acabar amb un script enorme que no respon cap pregunta. Aquí definirem què fa bo un projecte final, veurem un catàleg d'idees, aprendràs a escriure l'especificació amb una plantilla concreta, i l'aplicarem completa al projecte de referència de Rutalia que ens acompanyarà durant tot el mòdul.
Contingut
- Què fa bo un projecte final: integrador, mesurable, acotat
- Catàleg d'idees de projecte
- La plantilla d'especificació
- El projecte de referència de Rutalia, especificat complet
- Validar l'especificació abans d'escriure codi
Què fa bo un projecte final
Un projecte final d'aquest curs no és "un programa que funciona". És un experiment algorísmic documentat: planteges un problema, el resols combinant tècniques del curs i demostres amb números que la teva solució és millor que una alternativa simple. Tres propietats el defineixen:
Integrador
Ha de combinar tècniques d'almenys 2-3 mòduls diferents del curs. Això no és un caprici acadèmic: al mòdul 6 vas veure que els problemes reals no es resolen mai amb un sol algorisme. El dia operatiu de Rutalia (06-01) va encadenar clustering, algorisme hongarès, veí més proper i 2-opt; el sistema de recomanació (06-04) va barrejar filtratge col·laboratiu amb mètriques de classificació. Un projecte que només implementa Dijkstra és un exercici d'una lliçó, no un projecte final.
Mesurable
Ha d'existir una mètrica d'èxit numèrica i una línia base contra la qual comparar-la. La línia base és la solució més ximple que resol el problema de cap a cap: rutes en ordre aleatori, predicció "sempre la mitjana", assignació per ordre d'arribada. Sense línia base no pots afirmar res: un 18 % d'error és bo? Depèn de si la solució trivial dona un 19 % o un 60 %.
Acotat
Entre 20 i 40 hores de feina. Menys, i no dona temps a integrar diversos mòduls amb mesurament seriós; més, i l'estudiant autodidacta l'abandona. L'eina per acotar és la secció "fora d'abast" de l'especificació: escriure explícitament el que no faràs és tan important com escriure el que sí.
| Propietat | Pregunta de control | Senyal d'alarma |
|---|---|---|
| Integrador | Quants mòduls del curs faig servir de debò? | "Només necessito un algorisme del mòdul X" |
| Mesurable | Quin número compararé contra quina línia base? | "Ja es veurà que funciona bé" |
| Acotat | Cap en 20-40 hores amb el que ja sé? | "Primer he d'aprendre Kubernetes" |
Catàleg d'idees de projecte
Pots seguir el projecte de referència de Rutalia tal qual, adaptar-lo a un altre domini o triar una idea diferent. Aquest catàleg et dona vuit punts de partida contrastats; totes compleixen les tres propietats si s'acoten bé. La dificultat és orientativa (★ = assequible en ~20 h, ★★★ = exigeix les 40 h).
| # | Domini | Problema | Algorismes del curs implicats | Dificultat |
|---|---|---|---|---|
| 1 | Logística | Planificador de repartiment amb predicció de temps (el de referència) | Regressió (05-03), clustering (05-05), aparellament (03-06), heurístiques TSP + 2-opt (06-01), anàlisi de complexitat (01-02) | ★★ |
| 2 | Xarxes socials | Detector de comunitats i usuaris influents en un graf sintètic d'interaccions | BFS (03-02), PageRank i comunitats (06-02), similitud de Jaccard (06-02), representació de grafs (03-01) | ★★ |
| 3 | Dades massives | Motor d'agregació de logs que no caben en memòria (top-K d'errors, deduplicació) | External merge sort, filtre de Bloom, top-K amb heap (06-03), estructures avançades (01-04) | ★★ |
| 4 | ML | Predictor d'abandonament de clients sobre dataset sintètic, amb anàlisi de biaix | Classificació i mètriques (05-02), validació creuada (05-01), xarxa neuronal pròpia (05-04), ètica i drift (06-04) | ★★ |
| 5 | Jocs/trencaclosques | Solucionador de trencaclosques lliscants (8-puzzle/15-puzzle) amb comparació d'heurístiques | A* i espais d'estats (04-03), backtracking i B&B (02-03), heaps (01-04), complexitat (01-02) | ★ |
| 6 | Planificació | Generador d'horaris (torns o aules) amb restriccions dures i toves | Programació lineal entera (02-01, 06-01), backtracking (02-03), algorismes genètics com a alternativa (02-04) | ★★★ |
| 7 | Infraestructura | Disseny de xarxa de fibra de cost mínim amb anàlisi de punts febles | MST (03-04), flux màxim/min-cut (03-05), camins mínims (03-03) | ★★ |
| 8 | Optimització | Comparativa seriosa de metaheurístiques (genètic vs. formigues vs. B&B) sobre instàncies de motxilla o TSP | Mòdul 2 complet, mesurament rigorós (01-01/01-02), cerca sobre la resposta (04-01) | ★★★ |
Consells per triar:
- Tria un domini que coneguis o que t'atregui. Hi passaràs 20-40 hores; la motivació és el recurs més escàs de l'autodidacta.
- No triïs per dificultat, tria per claredat de la mètrica. El projecte 5 (★) ben mesurat val més que el 6 (★★★) a mitges.
- Traslladar el de referència al teu domini és legítim i recomanable: el mateix esquema "predir → agrupar → assignar → ordenar → comparar" funciona per a repartiments, tècnics de manteniment, visites comercials o recollida de residus.
La plantilla d'especificació
L'especificació és un document d'una o dues pàgines que escrius abans de la primera línia de codi. Copia-la literalment i omple cada camp:
# Especificació del projecte: <nom>
## 1. Objectiu
Una frase: quin problema resolc i per a qui (fictici).
## 2. Dades d'entrada
- Quines dades necessito (entitats, camps, volum aproximat).
- Com les obtinc: GENERADES SINTÈTICAMENT (preferit) o dataset
públic amb llicència clara. MAI dades personals reals: ni de
clients, ni de companys, ni obtingudes amb scraping. Si el domini
demana noms o adreces, s'inventen valors genèrics (client_0042,
zona_C).
- Llavor aleatòria fixa perquè la generació sigui reproduïble.
## 3. Algorismes previstos
| Fase | Tècnica | Lliçó del curs |
|---|---|---|
| ... | ... | ... |
## 4. Mètrica d'èxit
El número (o els 2-3 números) que decidiran si el projecte funciona,
i sobre quines instàncies es calcula.
## 5. Línia base
La solució trivial de cap a cap contra la qual comparo.
## 6. Fora d'abast
Llista explícita del que NO inclou aquest projecte.
## 7. Pla de fites
| Fita | Lliurable verificable | Hores estimades |
|---|---|---|
| H0 | ... | ... |Dues notes sobre els camps que més es descuiden:
- Dades (camp 2). L'opció per defecte en aquest curs és generar-les sintèticament, com vam fer amb el dataset de 2000 lliuraments del mòdul 5: controles el volum, la distribució i la llavor, i no hi ha cap risc ètic ni legal. Si fas servir dades públiques, comprova la llicència i que estiguin anonimitzades d'origen. Fer servir dades reals de persones —encara que "només sigui per provar"— queda fora d'aquest projecte, sense excepcions.
- Fites (camp 7). Cada fita ha de produir alguna cosa executable o mesurable, no "avançar en X". "H2: el model de regressió prediu temps amb MAE < 4 min en test" és una fita; "H2: treballar en el model" no ho és.
El projecte de referència: planificador de repartiment amb predicció de temps
Apliquem la plantilla, completa i sense buits, al projecte que desenvoluparem a 07-02 i avaluarem a 07-03. Fixa't en el nivell de concreció: aquest és l'estàndard que ha d'assolir la teva especificació.
# Especificació del projecte: Planificador de repartiment amb
# predicció de temps per a Rutalia
## 1. Objectiu
Planificar la jornada de repartiment de Rutalia (assignar comandes a
repartidors i ordenar les seves rutes) fent servir temps de viatge
PREDITS a partir de dades històriques, en lloc de distàncies fixes,
i demostrar quant millora respecte d'una planificació ingènua.
## 2. Dades d'entrada
- Històric sintètic de 3000 trajectes: origen, destinació (coordenades
en una retícula de 10x10 km), hora del dia, dia de la setmana,
temps real de viatge en minuts. El temps es genera com a
distància/velocitat + penalització per hora punta + soroll gaussià.
- Instàncies de jornada: 80 comandes amb coordenades i 5 repartidors,
generades amb la mateixa retícula.
- Tot sintètic, generat per un script propi amb numpy,
llavor = 42. Sense dades personals: les comandes són comanda_001..080.
## 3. Algorismes previstos
| Fase | Tècnica | Lliçó del curs |
|---|---|---|
| Estimar el temps per tram | Regressió lineal amb descens de gradient | 05-03 |
| Matriu de temps | Aplicació del model a tots els parells | 05-03 |
| Agrupar comandes per zona | k-means (k = nre. de repartidors) | 05-05 |
| Assignar grups a repartidors | Algorisme hongarès | 03-06 |
| Ordenar cada ruta | Veí més proper + millora 2-opt | 06-01 |
| Predir i verificar el cost | Anàlisi asimptòtica + mesurament | 01-01, 01-02 |
## 4. Mètrica d'èxit
- Temps total de ruta (suma dels 5 repartidors, en minuts)
sobre 10 instàncies de jornada amb 5 llavors diferents.
- MAE del model de temps sobre un 20 % de test (objectiu < 4 min).
- Èxit global: reduir el temps total >= 30 % respecte de la línia base.
## 5. Línia base
Assignació per ordre d'arribada (comandes repartides en blocs de 16
consecutives a cada repartidor) i ruta en l'ordre original, amb
temps estimats com a distància euclidiana / velocitat mitjana fixa.
## 6. Fora d'abast
- Finestres horàries de lliurament i capacitats de vehicle (VRP complet).
- Trànsit en temps real; el model és estàtic per hora del dia.
- Interfície gràfica i mapes reals; tot són coordenades sintètiques.
- OR-Tools o altres solvers externs: s'implementa amb el que s'ha vist
al curs (se citarà com a treball futur).
## 7. Pla de fites
| Fita | Lliurable verificable | Hores estimades |
|---|---|---|
| H0 | Generador de dades + línia base executable de cap a cap | 4 |
| H1 | Regressió de temps entrenada, MAE en test reportat | 6 |
| H2 | Clustering + assignació hongaresa integrats al pipeline | 6 |
| H3 | Veí més proper + 2-opt, comparació completa amb la base | 6 |
| H4 | Experiments amb 5 llavors, taules de resultats, informe | 6 |
| Total | | 28 |Validar l'especificació
Abans de donar l'especificació per bona, sotmet-la a aquesta checklist de viabilitat. Cada "no" és una revisió obligatòria, no un detall:
- [ ] Existeix una línia base trivial? L'has de poder escriure en menys d'una tarda. Si ni tan sols la solució ximple és fàcil, el problema està mal acotat.
- [ ] La mètrica es pot calcular amb un script? Si mesurar l'èxit requereix judici humà ("les rutes semblen raonables"), no és una mètrica.
- [ ] Les dades es poden generar o obtenir en menys d'1 hora? Un generador sintètic de 50 línies de numpy compleix; "ja trobaré un dataset per internet" no compleix fins que el dataset estigui descarregat i carregat.
- [ ] Cada algorisme previst té la seva lliçó a la taula? Si hi apareix una tècnica que el curs no ha cobert, o la substitueixes o la justifiques com a extensió petita.
- [ ] La suma d'hores de les fites està entre 20 i 40? I cap fita no supera les 8 hores: si una ho fa, divideix-la.
- [ ] La secció "fora d'abast" té almenys 3 entrades? Si no se te n'acudeixen, és que encara no has pensat en tot el que el projecte podria empassar-se't.
Una tècnica útil: escriu la darrera taula de l'informe final abans de començar (columnes: variant, temps total, millora %, temps de còmput). Si saps exactament quina taula vols poder omplir al final, tota decisió intermèdia es torna més fàcil.
Errors Comuns i Consells
- Error: el projecte-plataforma. "Faré una web amb login on es pengin comandes i…" — això és un projecte de desenvolupament web, no d'algorismes. Tot el que no sigui generar dades, executar algorismes i mesurar resultats va a "fora d'abast".
- Error: la mètrica retroactiva. Decidir com mesurar després d'implementar convida a l'autoengany: acabaràs triant la mètrica en què la teva solució queda bé. Mètrica i línia base es fixen aquí, per escrit.
- Error: dades reals "perquè són més autèntiques". A més del problema ètic i legal (recorda 06-04: biaix, privacitat, Reglament europeu d'IA), les dades reals porten una neteja infinita que consumeix el pressupost d'hores. Les sintètiques et deixen controlar la dificultat.
- Error: abast en expansió silenciosa. El símptoma és la frase "ja que hi soc, hi afegeixo…". L'antídot és rellegir la secció 6 de la teva especificació cada vegada que la pronunciïs.
- Consell: especificació curta i congelada. Una-dues pàgines. Quan la validis amb la checklist, tracta-la com un contracte amb tu mateix: els canvis s'anoten i es justifiquen, no s'improvisen.
- Consell: si dubtes entre dues idees, especifica-les totes dues. Són 30 minuts per plantilla, i la checklist gairebé sempre decideix tota sola quina és viable.
Exercicis
Els exercicis d'aquest mòdul són les fites del teu propi projecte: no tenen una única solució, sinó criteris d'autoavaluació.
Exercici 1: tria i justifica
Tria el teu projecte (del catàleg, adaptat o propi) i escriu un paràgraf justificant que és integrador (quins 2-3 mòduls combina i com s'encadenen les seves sortides?), mesurable (quin número, contra quina base?) i acotat (què deixes fora?).
Exercici 2: escriu l'especificació completa
Omple la plantilla de les 7 seccions per al teu projecte, amb el nivell de detall de l'exemple de Rutalia: taula d'algorismes amb lliçons, mètrica amb instàncies i objectiu numèric, i pla de fites amb hores.
Exercici 3: valida i corregeix
Passa la checklist de viabilitat a la teva especificació. Per cada punt que falli, modifica l'especificació (no la checklist) i anota què has canviat.
Solucions
Exercici 1 — criteris d'autoavaluació. El teu paràgraf és sòlid si: (a) anomena lliçons concretes, no mòduls vagues ("faig servir k-means de 05-05", no "faig servir ML"); (b) explica l'encadenament — la sortida d'una tècnica és l'entrada de la següent, com matriu de temps → clustering → assignació a Rutalia; (c) la mètrica cap en una frase amb un número objectiu. Senyal de fallada: si en rellegir-lo no sabries per on començar a programar, és massa vague.
Exercici 2 — solució orientativa. Compara el teu document amb el de Rutalia secció a secció i pregunta't: la meva secció és igual de concreta? En particular: la secció de dades ha d'incloure volum, camps i llavor; la taula d'algorismes ha de tenir una fila per fase del pipeline; cada fita ha de ser verificable per un tercer que només llegeixi el lliurable. Si la teva especificació completa ocupa menys de mitja pàgina, hi falta concreció; si supera dues pàgines, hi sobra plataforma.
Exercici 3 — criteris d'autoavaluació. El resultat esperat és que alguna cosa hagi canviat: a la pràctica, cap primera especificació no passa la checklist neta. Els ajustos més habituals (i bon senyal que estàs validant de debò) són: retallar l'abast de les dades, substituir un algorisme no cobert per un del curs i partir una fita de 12 hores en dues. Si la teva checklist ha sortit perfecta a la primera, revisa amb més duresa el punt de la línia base trivial: és on més s'esmuny l'optimisme.
Conclusió
Ja tens el més difícil: un projecte triat i una especificació validada que cap en una pàgina i en 20-40 hores. Hem vist que un bon projecte final és integrador (2-3 mòduls encadenats), mesurable (mètrica + línia base fixades per endavant) i acotat (amb un "fora d'abast" explícit), i hem deixat el projecte de referència de Rutalia —el planificador de repartiment amb predicció de temps— completament especificat com a vara de mesurar. A la propera lliçó (07-02) toca convertir el paper en codi: muntarem l'estructura del projecte, construirem primer la línia base que funciona de cap a cap i hi afegirem les capes algorísmiques una a una, mesurant a cada fita. L'especificació que acabes d'escriure serà el mapa; no el perdis de vista.
Algorismes Avançats
Mòdul 1: Introducció als Algorismes Avançats
- Conceptes Bàsics i Notació
- Anàlisi de Complexitat
- Recursió i Programació Dinàmica
- Estructures de Dades Avançades
Mòdul 2: Algorismes d'Optimització
- Programació Lineal
- Algorismes d'Optimització Combinatòria
- Backtracking i Branch and Bound
- Algorismes Genètics
- Optimització de Colònia de Formigues
Mòdul 3: Algorismes en Grafs
- Representació de Grafs
- Cerca en Grafs: BFS i DFS
- Algorismes de Camins Mínims
- Arbres d'Expansió Mínima
- Algorismes de Flux Màxim
- Algorismes d'Aparellament en Grafs
Mòdul 4: Algorismes de Cerca i Ordenació
Mòdul 5: Algorismes d'Aprenentatge Automàtic
- Introducció a l'Aprenentatge Automàtic
- Algorismes de Classificació
- Algorismes de Regressió
- Xarxes Neuronals i Deep Learning
- Algorismes de Clustering
Mòdul 6: Casos d'Estudi i Aplicacions
- Optimització a la Indústria
- Aplicacions de Grafs a les Xarxes Socials
- Cerca i Ordenació en Grans Volums de Dades
- Aplicacions d'Aprenentatge Automàtic a la Vida Real
