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

HOME

En aquesta primera lliçó posarem els fonaments de tot el curs: què és exactament un algorisme, quines propietats ha de complir per merèixer aquest nom i de quines maneres el podem expressar abans d'escriure ni una sola línia de codi. Entendre bé aquests fonaments és essencial, perquè la resta del curs —anàlisi de complexitat, estratègies de disseny, algorismes clàssics i optimització— es construeix damunt seu. A més, presentarem RutaBus, l'aplicació fictícia de mobilitat urbana que ens acompanyarà com a cas pràctic durant tot el curs.

Contingut

RutaBus: el cas pràctic del curs
Què és un algorisme (i què no ho és)?
Propietats d'un algorisme
Formes d'expressar un algorisme
Del pseudocodi al codi Python: primer exemple a RutaBus
Motivació: hi ha algorismes millors que d'altres

RutaBus: el cas pràctic del curs

Imagina que treballes a l'equip de desenvolupament de RutaBus, una aplicació que ajuda els ciutadans a planificar els seus trajectes en transport públic. L'aplicació gestiona informació com ara:

Parades: punts físics de la ciutat ("Plaça Major", "Estació Nord", "Hospital Central"...), cadascun amb les seves coordenades.
Línies: recorreguts d'autobús (L1, L2, L3...) que connecten seqüències de parades.
Horaris: hores de pas de cada línia per cada parada.
Xarxa de transport: el conjunt de parades i connexions, que més endavant modelarem com un graf.

Gairebé qualsevol funcionalitat de RutaBus amaga un algorisme:

Funcionalitat de RutaBus	Problema algorísmic subjacent
"Quina és la meva parada més propera?"	Cerca del mínim en una col·lecció
"Mostra'm els propers autobusos ordenats per hora"	Ordenació
"Existeix la parada 'Plaça Major'?"	Cerca
"Com vaig d'A a B en el mínim temps?"	Camí mínim en un graf

Al llarg del curs resoldrem aquests problemes de manera progressiva: primer amb solucions senzilles i, a mesura que aprenguem a analitzar-les i dissenyar-les millor, amb solucions cada cop més eficients.

Què és un algorisme (i què no ho és)?

Un algorisme és una seqüència finita i ordenada de passos, definits sense ambigüitat, que transforma unes dades d'entrada en uns resultats de sortida per resoldre un problema concret.

L'analogia clàssica és la recepta de cuina: ingredients (entrada), passos precisos (procés) i plat acabat (sortida). Però l'analogia té límits: "afegir sal al gust" és acceptable en una recepta i no ho seria en un algorisme, perquè és ambigu.

Convé distingir l'algorisme de conceptes propers amb què sovint es confon:

Concepte	Què és?	És un algorisme?
Algorisme	Mètode abstracte de resolució, independent del llenguatge	Sí
Programa	Implementació concreta d'un o més algorismes en un llenguatge	No: n'és la materialització
Heurística informal	"Prova coses fins que funcioni"	No: no garanteix passos definits ni terminació
Especificació	Descriu què cal fer, no com	No: li falta el procés
Procés infinit	Un servidor que atén peticions sense parar	No com a algorisme clàssic: no acaba

Exemples de coses que no són algorismes:

"Busca la millor ruta" → és un objectiu, no un mètode: no diu com.
"Repeteix fins que el resultat sigui bo" → ambigu: què vol dir "bo"?
Un bucle while True sense condició de sortida → no compleix la finitud.

La mateixa idea algorísmica es pot implementar en Python, Java o C i continua sent el mateix algorisme. Aquesta independència del llenguatge és la que ens permetrà, al Mòdul 2, analitzar algorismes sense preocupar-nos de la màquina concreta on s'executen.

Propietats d'un algorisme

Perquè una seqüència de passos sigui un algorisme ha de complir cinc propietats clàssiques (formulades per Donald Knuth):

Finitud: ha d'acabar després d'un nombre finit de passos. Un càlcul que no acaba mai no resol res.
Precisió (definició): cada pas ha d'estar definit sense ambigüitat. Dues persones (o dos ordinadors) que segueixin l'algorisme amb la mateixa entrada han de fer exactament el mateix.
Entrades definides: ha de quedar clar quines dades rep (poden ser zero o més). A RutaBus: la llista de parades i la posició de l'usuari.
Sortides definides: ha de produir com a mínim un resultat, i ha de quedar clar quin és. A RutaBus: la parada més propera.
Efectivitat: cada pas ha de ser prou bàsic per poder-se executar de manera mecànica en temps finit. "Calcular la distància entre dos punts" és efectiu; "intuir quina queda més a mà" no ho és.

Vegem-ho amb un exemple de RutaBus. La instrucció "troba una parada que sigui a prop de l'usuari" incompleix la precisió (què vol dir "a prop"?) i la sortida definida (quina, si n'hi ha diverses?). En canvi:

"Donades les coordenades de l'usuari i la llista completa de parades, retorna la parada la distància euclidiana de la qual a l'usuari sigui mínima; si hi ha empat, la primera de la llista."

...compleix les cinc propietats: acaba (la llista és finita), és precisa (distància euclidiana, criteri de desempat), té entrada i sortida clares, i cada pas és mecanitzable.

Formes d'expressar un algorisme

Un mateix algorisme es pot expressar amb diferents nivells de formalitat. Els tres més habituals són el llenguatge natural, el pseudocodi i el diagrama de flux.

Llenguatge natural

És la forma més accessible, ideal per comunicar la idea general:

Trobar la parada més propera:

Pren la primera parada de la llista i considera-la provisionalment la més propera.

Recorre la resta de parades una per una.

Per a cada parada, calcula'n la distància a l'usuari; si és menor que la de la candidata actual, aquesta parada passa a ser la nova candidata.

En acabar el recorregut, la candidata és la parada més propera.

El seu gran inconvenient: és fàcil caure en ambigüitats i ometre casos límit (i si la llista és buida?).

Pseudocodi

El pseudocodi és un punt intermedi: fa servir estructures de programació (condicionals, bucles, variables) però sense la sintaxi estricta de cap llenguatge. És la forma habitual de descriure algorismes en llibres i documentació tècnica.

ALGORISME parada_mes_propera
ENTRADA:  usuari (coordenades x, y), parades (llista no buida de parades amb nom i coordenades)
SORTIDA:  la parada amb distància mínima a l'usuari

    millor_parada    ← parades[0]
    millor_distancia ← distancia(usuari, parades[0])

    PER A CADA parada DE parades[1..fi] FER
        d ← distancia(usuari, parada)
        SI d < millor_distancia LLAVORS
            millor_distancia ← d
            millor_parada    ← parada
        FI SI
    FI PER A

    RETORNA millor_parada
FI ALGORISME

Observa com el pseudocodi obliga a concretar detalls que el llenguatge natural deixava a l'aire: la inicialització amb la primera parada, la comparació estricta < (que resol els empats a favor de la primera trobada) i el valor retornat.

Diagrama de flux

El diagrama de flux representa gràficament el control de l'algorisme: rombes per a decisions, rectangles per a accions. És molt útil per visualitzar bucles i bifurcacions:

flowchart TD
    A([Inici]) --> B[millor_parada = primera parada<br/>millor_distancia = la seva distància a l'usuari]
    B --> C{Queden parades<br/>per revisar?}
    C -- Sí --> D[Prendre la parada següent<br/>d = distància a l'usuari]
    D --> E{d < millor_distancia?}
    E -- Sí --> F[Actualitzar millor_parada<br/>i millor_distancia]
    E -- No --> C
    F --> C
    C -- No --> G[/Retornar millor_parada/]
    G --> H([Fi])

Comparativa de les tres formes

Forma	Precisió	Facilitat de lectura	Ús típic
Llenguatge natural	Baixa	Molt alta	Comunicar la idea a qualsevol persona
Pseudocodi	Alta	Alta (per a desenvolupadors)	Dissenyar i documentar abans de programar
Diagrama de flux	Alta	Alta (visual)	Visualitzar el flux de control, formació

En la pràctica professional se sol començar pel llenguatge natural (entendre el problema), refinar-lo a pseudocodi (dissenyar la solució) i finalment traduir-lo a codi.

Del pseudocodi al codi Python: primer exemple a RutaBus

Traduïm el pseudocodi anterior a Python. Representarem cada parada com un diccionari amb el seu nom i les seves coordenades (en un pla simplificat de la ciutat):

import math

# Dades fictícies de RutaBus: parades amb coordenades (x, y) en km
parades = [
    {"nom": "Plaça Major",      "x": 0.0, "y": 0.0},
    {"nom": "Estació Nord",     "x": 2.5, "y": 4.0},
    {"nom": "Hospital Central", "x": 1.0, "y": 1.5},
    {"nom": "Parc del Riu",     "x": 3.0, "y": 0.5},
]

def distancia(x1, y1, x2, y2):
    """Distància euclidiana entre dos punts del pla."""
    return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def parada_mes_propera(usuari_x, usuari_y, parades):
    """Retorna la parada més propera a la posició de l'usuari.

    Entrada: coordenades de l'usuari i llista NO buida de parades.
    Sortida: el diccionari de la parada amb distància mínima.
    """
    # Pas 1: la primera parada és la candidata inicial
    millor_parada = parades[0]
    millor_distancia = distancia(usuari_x, usuari_y,
                                 millor_parada["x"], millor_parada["y"])

    # Pas 2: recórrer la resta de parades
    for parada in parades[1:]:
        d = distancia(usuari_x, usuari_y, parada["x"], parada["y"])
        # Pas 3: si millora la candidata, la substitueix
        if d < millor_distancia:
            millor_distancia = d
            millor_parada = parada

    # Pas 4: en acabar el bucle, la candidata és la més propera
    return millor_parada

# L'usuari és a (0.8, 1.0)
resultat = parada_mes_propera(0.8, 1.0, parades)
print(f"Parada més propera: {resultat['nom']}")
# Sortida: Parada més propera: Hospital Central

Analitzem el codi peça a peça:

distancia: funció auxiliar que aplica el teorema de Pitàgores. Encapsular-la en una funció fa l'algorisme principal més llegible i reforça la propietat d'efectivitat: cada pas és una operació bàsica i mecanitzable.
Inicialització amb parades[0]: igual que al pseudocodi, la primera parada és la candidata inicial. Això evita inventar valors artificials com "infinit" i garanteix que sempre retornem una parada real (si la llista no és buida).
for parada in parades[1:]: recorre des de la segona parada fins al final. És la traducció directa del PER A CADA del pseudocodi.
if d < millor_distancia: la comparació estricta fa que, en cas d'empat, es conservi la parada trobada primer — exactament el criteri de desempat que hem definit a l'especificació.
return millor_parada: la sortida definida de l'algorisme.

Fixa't que l'algorisme és el mateix en les tres representacions (natural, pseudocodi, Python): el que canvia és el nivell de detall i la sintaxi, no la idea.

Motivació: hi ha algorismes millors que d'altres

El nostre algorisme funciona, però és bo? Per trobar la parada més propera revisa totes les parades, una per una. Amb les 4 parades de l'exemple és instantani. Però imagina la xarxa real d'una gran ciutat:

Amb 4 parades → 4 distàncies calculades.
Amb 5.000 parades → 5.000 distàncies calculades.
Si a més l'app calcula això per a milers d'usuaris per segon... el cost es multiplica.

I hi ha més d'una manera de resoldre el mateix problema. Per avançar la intuïció: cercar una parada pel seu nom recorrent la llista sencera funciona, però si la llista està ordenada existeix una tècnica (la cerca binària, que veurem al Mòdul 4) que amb 5.000 parades necessita amb prou feines una dotzena de comparacions en lloc de 5.000. Mateix problema, mateix resultat, esforç radicalment diferent.

Aquesta és la gran idea del curs: per a un mateix problema solen existir diversos algorismes correctes, i les diferències d'eficiència entre ells poden ser enormes. Aprendre a comparar algorismes amb rigor, sense cronòmetres ni màquines concretes, és justament l'objectiu de la lliçó de notació asimptòtica (01-03) i de tot el Mòdul 2.

Errors Comuns i Consells

Confondre l'algorisme amb el programa. Si la teva solució només existeix "en Python", et costarà raonar-hi i comparar-la amb alternatives. Consell: acostuma't a esbossar primer el pseudocodi; el codi sortirà gairebé sol.
Deixar passos ambigus. "Triar la millor opció" no és un pas d'algorisme fins que defineixis millor amb un criteri mesurable (distància mínima, hora més primerenca...). Revisa cada pas preguntant-te: podria executar-lo una màquina sense demanar aclariments?
Oblidar els casos límit a les entrades. El nostre parada_mes_propera falla amb una llista buida (parades[0] llança IndexError). Un algorisme ben especificat diu quines entrades admet; un programa robust, a més, les valida.
No definir el criteri de desempat. Si dues parades són a la mateixa distància, quina es retorna? El nostre < estricte ho resol (guanya la primera), però cal decidir-ho conscientment, no per accident.
Escriure codi abans d'entendre el problema. Consell pràctic: escriu primer l'entrada i la sortida esperades amb un exemple concret (com hem fet amb l'usuari a (0.8, 1.0)). Si no pots donar un exemple, encara no entens el problema.

Exercicis

Exercici 1

Indica quines de les descripcions següents compleixen les cinc propietats d'un algorisme i, si no, quina propietat incompleixen:

a) "Recorre les parades de la línia L1 i retorna quantes n'hi ha." b) "Prova rutes a l'atzar fins a topar amb una que t'agradi." c) "Mentre l'autobús no arribi, continua esperant." d) "Donada una llista d'horaris, retorna el primer posterior a l'hora actual; si no n'hi ha cap, retorna None."

Exercici 2

Escriu en pseudocodi (no en Python) un algorisme hi_ha_parada(nom, parades) que retorni CERT si existeix una parada amb aquest nom a la llista i FALS en cas contrari. Assegura't que compleix les cinc propietats.

Exercici 3

Modifica la funció parada_mes_propera en Python perquè retorni les dues parades més properes a l'usuari (la més propera i la segona més propera), sense ordenar la llista completa. Suposa que la llista té com a mínim dues parades.

Solucions

Solució 1:

a) Sí que és un algorisme: entrada (llista de parades de L1), sortida (un nombre), passos precisos, finit i efectiu. b) No: incompleix la precisió ("que t'agradi" és ambigu) i potencialment la finitud (podria no acabar mai). c) No: incompleix la finitud (pot no acabar) i no té sortida definida. d) Sí que és un algorisme: fixa't que la clàusula "si no n'hi ha cap, retorna None" és la que garanteix la sortida definida per a totes les entrades. Sense ella, seria una especificació incompleta.

Solució 2:

ALGORISME hi_ha_parada
ENTRADA:  nom (text), parades (llista de parades, possiblement buida)
SORTIDA:  CERT si alguna parada es diu `nom`, FALS si no

    PER A CADA parada DE parades FER
        SI parada.nom = nom LLAVORS
            RETORNA CERT
        FI SI
    FI PER A
    RETORNA FALS
FI ALGORISME

Comprovació de propietats: acaba (la llista és finita), cada pas és precís i efectiu (comparar textos), l'entrada i la sortida estan definides per a qualsevol llista, inclosa la buida (retorna FALS). Error comú: oblidar el RETORNA FALS final, que deixa la sortida sense definir quan la parada no existeix.

Solució 3:

def dues_parades_mes_properes(usuari_x, usuari_y, parades):
    """Retorna (mes_propera, segona_mes_propera). Requereix len(parades) >= 2."""
    d0 = distancia(usuari_x, usuari_y, parades[0]["x"], parades[0]["y"])
    d1 = distancia(usuari_x, usuari_y, parades[1]["x"], parades[1]["y"])

    # Ordenem manualment les dues primeres candidates
    if d0 <= d1:
        primera, d_primera, segona, d_segona = parades[0], d0, parades[1], d1
    else:
        primera, d_primera, segona, d_segona = parades[1], d1, parades[0], d0

    for parada in parades[2:]:
        d = distancia(usuari_x, usuari_y, parada["x"], parada["y"])
        if d < d_primera:
            # La nova parada desplaça la primera; l'antiga primera passa a segona
            segona, d_segona = primera, d_primera
            primera, d_primera = parada, d
        elif d < d_segona:
            # Només millora la segona
            segona, d_segona = parada, d

    return primera, segona

La clau és mantenir dues candidates i, quan apareix una parada millor que la primera, no perdre l'antiga primera: passa a ocupar el lloc de segona. Un error molt comú és sobreescriure primera sense abans copiar-la a segona.

Conclusió

En aquesta lliçó hem definit què és un algorisme —una seqüència finita, precisa i efectiva de passos amb entrades i sortides ben definides— i què el distingeix d'un programa, d'una heurística vaga o d'una simple especificació. Hem vist tres formes d'expressar-lo (llenguatge natural, pseudocodi i diagrama de flux) i hem recorregut el camí complet fins al codi Python amb el nostre primer problema real de RutaBus: trobar la parada més propera a l'usuari. També hem plantat una llavor important: un mateix problema admet diversos algorismes correctes, i n'hi ha de molt més eficients que d'altres. A la propera lliçó, Tipus d'Algorismes, posarem ordre en aquest univers: classificarem els algorismes segons el seu enfocament (iteratius i recursius), segons el seu propòsit (cerca, ordenació, grafs...) i segons altres dimensions que ens ajudaran a triar l'eina adequada per a cada problema de RutaBus.

Conceptes Bàsics d'Algorismes