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

HOME

Toca consolidar. En aquest mòdul has après quatre estructures (cua FIFO, cua circular, cua de prioritat i deque) i en aquesta lliçó no hi ha teoria nova: hi ha sis exercicis progressius que les posen a treballar juntes —i amb les piles del mòdul 3— sobre problemes reals de TaskFlow. Et recomanem el mètode de sempre: llegeix l'enunciat, decideix primer quina estructura hi encaixa i per què (l'elecció és la meitat de l'exercici), escriu la teva solució, prova-la amb els casos donats, i només llavors compara-la amb la solució comentada. Les solucions reutilitzen les classes del mòdul: Cua (04-02), SafataUrgencies (04-04) i collections.deque (04-05).

Contingut

Exercici 1: notificacions amb reintents
Exercici 2: planificador round-robin amb quantum
Exercici 3: safata d'urgències amb extraccions intercalades
Exercici 4: màxim de tasques completades en finestra lliscant
Exercici 5: generar els binaris d'1 a n amb una cua
Exercici 6: invertir els primers k elements d'una cua
Solucions comentades

Exercicis

Exercici 1: notificacions amb reintents

L'enviament de notificacions de TaskFlow de vegades falla (el servidor de correu no respon). Amplia la idea de la CuaNotificacions de 04-02: escriu una funció processar_amb_reintents(notificacions, enviar, max_intents=3) que rebi una llista de notificacions (dicts amb almenys missatge) i una funció enviar(notif) que retorna True (èxit) o False (fallada). Regles:

Les notificacions es processen en ordre FIFO.
Si un enviament falla, la notificació torna a encuar-se al final (no es reintenta en calent: així un servidor caigut no bloqueja les altres).
Cada notificació s'intenta com a màxim max_intents vegades; superat el límit, va a una llista de descartades.
Retorna la tupla (enviades, descartades) amb les notificacions en l'ordre en què es van resoldre.

Prova-ho amb un enviar que falli sempre per als missatges que continguin "@caigut" i encerti per a la resta.

Exercici 2: planificador round-robin amb quantum

Al mòdul 2, el RepartidorTasques girava sobre una LlistaCircular per repartir torns. Els sistemes operatius fan una cosa més fina: round-robin amb quantum. Escriu planificar_round_robin(tasques, quantum) on cada tasca és un dict amb id, titol i restant (unitats de feina pendents). Regles:

Les tasques esperen en una cua FIFO.
Es desencua la primera, s'hi treballa com a màxim quantum unitats, i:
- si li queda feina, torna al final de la cua;
- si acaba, s'anota a la llista d'acabades.
Retorna la llista d'id en ordre d'acabament i el registre de torns com a llista de tuples (id, unitats_treballades).

Amb tasques = [{id: 1, restant: 5}, {id: 2, restant: 2}, {id: 3, restant: 8}] i quantum = 3, l'ordre d'acabament ha de ser [2, 1, 3].

Exercici 3: safata d'urgències amb extraccions intercalades

Usant heapq amb l'idiom (prioritat, comptador, tasca) de 04-04 (pots usar la classe SafataUrgencies o reescriure-ho a mà), simula aquesta jornada de suport i prediu abans d'executar l'ordre d'atenció:

arriba  ("Backup trencat",      prioritat 2)
arriba  ("Web lenta",           prioritat 3)
ATÉN una tasca
arriba  ("Servidor caigut",     prioritat 1)
arriba  ("Login falla",         prioritat 1)
ATÉN una tasca
ATÉN una tasca
arriba  ("Backup secundari",    prioritat 2)
ATÉN totes les restants

Escriu el codi que reprodueix la simulació i imprimeix l'ordre d'atenció. Comprova la teva predicció, parant atenció a l'empat de prioritat 1.

Exercici 4: màxim de tasques completades en finestra lliscant

A 04-05 vam calcular la mitjana mòbil amb una suma mantinguda. El màxim en finestra és més difícil: quan el dia que surt era justament el màxim, quin és el nou? Recalcular-lo cada dia és O(k). Existeix una tècnica O(1) amortitzat per dia: la deque monòtona decreixent (guarda candidats a màxim de més gran a més petit; parenta del min-stack del mòdul 3).

Escriu maxims_en_finestra(completades_per_dia, k) que retorni, per a cada dia des del dia k, el màxim de tasques completades en els últims k dies. Regles de la deque monòtona (guarda índexs de dies):

Abans d'afegir el dia i, elimina pel final tots els índexs el valor dels quals sigui <= que el del dia i (mai no podran ser màxims havent arribat i, més recent i més gran).
Afegeix i pel final.
Elimina pel front l'índex i - k si encara hi és (ha caducat: ja no és a la finestra).
El màxim de la finestra és el valor de l'índex del front.

Amb completades = [3, 5, 2, 4, 6, 1, 0, 7] i k = 3, el resultat és [5, 5, 6, 6, 6, 7].

Exercici 5: generar els binaris d'1 a n amb una cua

Un clàssic sorprenent: genera les representacions binàries dels números 1 a n sense convertir números (res de bin()), només amb una cua de cadenes. La llavor és "1"; a cada pas es desencua una cadena b, s'emet com a resultat, i s'encuen b + "0" i b + "1". Escriu binaris_fins(n) i explica per què la cua FIFO produeix exactament l'ordre 1, 10, 11, 100, 101... Què sortiria si usessis una pila? (Avançament: aquest patró "processar i encuar els descendents" és exactament el recorregut per nivells/BFS que veuràs en arbres i grafs, mòduls 6 i 7.)

Exercici 6: invertir els primers k elements d'una cua

Integració amb el mòdul 3: escriu invertir_primers(cua, k) que inverteixi l'ordre dels primers k elements d'una Cua, deixant la resta en el seu ordre original, usant només el contracte de la cua, una Pila auxiliar i O(1) variables extra. Amb la cua 1, 2, 3, 4, 5 (front a l'esquerra) i k = 3, ha de quedar 3, 2, 1, 4, 5. Pista: la pila inverteix; per recol·locar la resta sense tocar-ne l'ordre et servirà la rotació completa que vam usar a activitat_recent (04-03). Tracta els casos d'error: k més gran que la mida o negatiu.

Solucions

Solució 1: notificacions amb reintents

from collections import deque

def processar_amb_reintents(notificacions, enviar, max_intents=3):
    cua = deque()                           # deque com a cua FIFO (04-05)
    for notif in notificacions:
        cua.append({**notif, "intents": 0})     # copia + comptador d'intents

    enviades, descartades = [], []
    while cua:
        notif = cua.popleft()               # FIFO: el que mes espera
        notif["intents"] += 1
        if enviar(notif):
            enviades.append(notif)
        elif notif["intents"] < max_intents:
            cua.append(notif)               # al FINAL: no bloqueja els altres
        else:
            descartades.append(notif)       # ha esgotat les seves oportunitats
    return enviades, descartades


# --- Prova ---
def enviar_simulat(notif):
    return "@caigut" not in notif["missatge"]

notifs = [
    {"missatge": "Tasca 1 assignada a anna"},
    {"missatge": "Avis al servidor @caigut"},
    {"missatge": "Tasca 2 completada"},
]
ok, ko = processar_amb_reintents(notifs, enviar_simulat)
print([n["missatge"] for n in ok])   # les dues bones, en ordre d'arribada
print([n["intents"] for n in ko])    # [3]: la fallida ha esgotat els 3 intents

Comentari: els tres punts amb suc són (1) el comptador intents viatja dins de la notificació (amb una còpia {**notif, ...} per no mutar l'entrada del cridador); (2) el reencuament al final implementa la política "no bloquejar": entre reintent i reintent s'atén la resta de la cua, donant temps que el servidor es recuperi; (3) el bucle acaba sempre, perquè cada notificació passa per popleft com a molt max_intents vegades — cost total O(n · max_intents).

Solució 2: round-robin amb quantum

from collections import deque

def planificar_round_robin(tasques, quantum):
    cua = deque(dict(t) for t in tasques)   # copies: no mutem l'entrada
    acabades, torns = [], []

    while cua:
        tasca = cua.popleft()
        treballat = min(quantum, tasca["restant"])    # mai mes del pendent
        tasca["restant"] -= treballat
        torns.append((tasca["id"], treballat))
        if tasca["restant"] > 0:
            cua.append(tasca)               # el seu torn s'ha acabat: al final de la fila
        else:
            acabades.append(tasca["id"])
    return acabades, torns


tasques = [
    {"id": 1, "titol": "Importar les dades", "restant": 5},
    {"id": 2, "titol": "Enviar el resum", "restant": 2},
    {"id": 3, "titol": "Generar l'informe", "restant": 8},
]
fi, torns = planificar_round_robin(tasques, quantum=3)
print(fi)      # [2, 1, 3]
print(torns)   # [(1, 3), (2, 2), (3, 3), (1, 2), (3, 3), (3, 2)]

Comentari: seguim la traça per verificar el [2, 1, 3]. Torn de l'1 (treballa 3, li'n queden 2 → reencua), torn del 2 (treballa 2, acaba), torn del 3 (treballa 3, en queden 5 → reencua), torn de l'1 (treballa 2, acaba), torns del 3 (3 i 2, acaba). La gràcia del round-robin és la justícia: la tasca curta (id 2) no espera que acabi la llarga (id 3), i cap tasca no monopolitza el processador més de quantum seguides. És el RepartidorTasques del mòdul 2 amb contracte de cua en lloc de llista circular: reencuar al final és el gir de l'anell. El min(quantum, restant) evita "treballar de més" i registrar torns negatius — cas frontera fàcil d'oblidar.

Solució 3: urgències intercalades

import heapq
from itertools import count

monticle, c, atencio = [], count(), []

def arriba(titol, prioritat):
    heapq.heappush(monticle, (prioritat, next(c),
                   {"titol": titol, "prioritat": prioritat}))

def aten():
    tasca = heapq.heappop(monticle)[2]
    atencio.append(tasca["titol"])

arriba("Backup trencat", 2)
arriba("Web lenta", 3)
aten()                          # 1a
arriba("Servidor caigut", 1)
arriba("Login falla", 1)
aten(); aten()                  # 2a i 3a
arriba("Backup secundari", 2)
while monticle:
    aten()                      # la resta

print(atencio)
# ['Backup trencat', 'Servidor caigut', 'Login falla', 'Backup secundari', 'Web lenta']

Comentari, atenció per atenció: (1) a la primera només hi ha prioritats 2 i 3 → surt Backup trencat; les urgències de prioritat 1 encara no havien arribat — una cua de prioritat ordena el present, no endevina el futur. (2) i (3): ja amb les dues de prioritat 1 dins, surten totes dues, i l'empat el resol el comptador: Servidor caigut va arribar abans que Login falla (estabilitat). (4) Backup secundari (prioritat 2) avança Web lenta (prioritat 3) encara que va arribar moltíssim després: en una cua de prioritat l'antiguitat només desempata, mai no mana. Si la teva predicció ha fallat, gairebé segur que ha estat a la primera atenció o en l'ordre de l'empat: són els dos punts on la intuïció FIFO traeix.

Solució 4: màxim en finestra amb deque monòtona

from collections import deque

def maxims_en_finestra(completades_per_dia, k):
    candidats = deque()         # indexs de dies, amb valors DECREIXENTS
    maxims = []

    for i, valor in enumerate(completades_per_dia):
        # (1) Expulsar pel final els candidats que 'valor' deixa obsolets:
        #     son mes antics que i I no mes grans que ell → mai no seran maxim.
        while candidats and completades_per_dia[candidats[-1]] <= valor:
            candidats.pop()
        # (2) El dia i entra com a candidat pel final.
        candidats.append(i)
        # (3) Caducar pel front el dia que surt de la finestra.
        if candidats[0] <= i - k:
            candidats.popleft()
        # (4) Amb la finestra completa, el front es el maxim.
        if i >= k - 1:
            maxims.append(completades_per_dia[candidats[0]])
    return maxims


print(maxims_en_finestra([3, 5, 2, 4, 6, 1, 0, 7], k=3))
# [5, 5, 6, 6, 6, 7]

Comentari: l'invariant és que candidats guarda índexs els valors dels quals van de més gran (front) a més petit (final), tots dins de la finestra. El pas (1) el manté: si el dia nou iguala o supera l'últim candidat, aquell candidat ja mai no podrà ser màxim (el nou és igual de gran i caducarà més tard), així que s'elimina — és la mateixa lògica de "descartar dominats" de la PilaAmbMinim del mòdul 3, ara pels dos extrems. El pas (3) usa el front com a data de caducitat. El cost? Cada índex entra una vegada i surt com a molt una vegada (pel final o pel front): O(n) total, O(1) amortitzat per dia — el concepte de 04-02 reapareix. La solució ingènua amb max(finestra) diària seria O(n·k); amb k = 30 dies i anys d'historial, la diferència es nota.

Solució 5: binaris amb una cua

from collections import deque

def binaris_fins(n):
    resultat = []
    cua = deque(["1"])                  # llavor
    for _ in range(n):
        b = cua.popleft()               # el mes antic = el mes curt pendent
        resultat.append(b)
        cua.append(b + "0")             # els seus dos "descendents"
        cua.append(b + "1")
    return resultat

print(binaris_fins(10))
# ['1', '10', '11', '100', '101', '110', '111', '1000', '1001', '1010']

Comentari: per què surt l'ordre numèric correcte? Perquè la cua FIFO processa les cadenes per longitud creixent (totes les d'1 bit, després totes les de 2 bits...), i dins de cada longitud, en l'ordre en què van ser generades, que és l'ordre numèric (de "10" es generen "100" i "101" abans que "11" generi "110" i "111"). És un recorregut per nivells de l'arbre binari implícit de les cadenes — literalment el BFS que formalitzarem als mòduls 6 i 7; aquest exercici és el teu primer BFS sense saber-ho. Amb una pila (LIFO) el recorregut seria en profunditat: 1, 11, 111, 1111... — s'enfonsaria per la branca dels uns i, amb generació infinita, no tornaria mai; acotat a n elements produiria un ordre completament diferent.

Solució 6: invertir els primers k amb una pila

def invertir_primers(cua, k):
    if k < 0 or k > cua.mida():
        raise ValueError("k fora de rang")
    if k <= 1:
        return                          # res per invertir

    pila = Pila()                       # la Pila del modul 3

    # Fase 1: els k primers passen a la pila (queden invertits).
    for _ in range(k):
        pila.apilar(cua.desencuar())

    # Fase 2: la pila torna a la cua PEL FINAL, ja invertida.
    while not pila.esta_buida():
        cua.encuar(pila.desapilar())

    # Fase 3: els n-k restants ara son DAVANT del bloc invertit;
    # una rotacio completa de n-k elements els envia darrere (04-03).
    for _ in range(cua.mida() - k):
        cua.encuar(cua.desencuar())


# --- Prova ---
cua = Cua()
for x in [1, 2, 3, 4, 5]:
    cua.encuar(x)
invertir_primers(cua, 3)
sortida = [cua.desencuar() for _ in range(cua.mida())]
print(sortida)                          # [3, 2, 1, 4, 5]

Comentari, seguint l'exemple 1..5 amb k = 3: després de la fase 1, la cua queda 4, 5 i la pila [1, 2, 3] (3 al cim). La fase 2 desapila 3, 2, 1 i els encua: la cua queda 4, 5, 3, 2, 1 — el bloc està invertit, però al lloc equivocat. La fase 3 rota els n - k = 2 elements del front cap al final: 5, 3, 2, 1, 4 → 3, 2, 1, 4, 5. Llestos. Cada element es mou un nombre constant de vegades → O(n). L'exercici destil·la el mòdul sencer: la pila com a inversora (mòdul 3), la cua com a conservadora de l'ordre (aquest mòdul), i la rotació com a manera de recol·locar sense sortir del contracte. Errors típics: oblidar la fase 3 (deixa el bloc invertit al final), o fer la fase 3 amb k rotacions en lloc de n - k.

Errors Comuns i Consells

Reencuar sense límit (exercicis 1 i 2): tot bucle while cua: que reencua ha de tenir una garantia de progrés — un comptador d'intents, un restant que decreix. Sense ella, un element "immortal" converteix el programa en un bucle infinit. Verifica sempre: quina magnitud decreix estrictament a cada volta?
Mutar els dicts del cridador: les solucions 1 i 2 copien ({**notif, ...}, dict(t)) abans d'afegir camps o restar feina. Retornar dades modificades que el cridador no esperava és font clàssica d'errors difícils de rastrejar.
A la deque monòtona, comparar amb < en lloc de <=: amb <, els empats s'acumulen com a candidats redundants; funciona, però la deque creix més del necessari. Amb <= l'invariant queda estricte. El greu seria expulsar pel front per valor en lloc de per índex caducat: barrejar els dos criteris trenca l'algorisme.
Triar l'estructura per inèrcia: abans de programar, digues en veu alta què necessita el problema: ordre d'arribada (cua)? el més urgent (prioritat)? els dos extrems (deque)? invertir (pila)? Els sis exercicis es resolen malament amb l'estructura equivocada i gairebé sols amb la correcta.
Consell final del mòdul: guarda les teves solucions. El planificador (ex. 2) i la safata (ex. 3) reapareixeran als projectes del mòdul 8, i el patró de l'exercici 5 és el cor del BFS del mòdul 7.

Conclusió

Fi del mòdul 4. Has aplicat la cua FIFO a reintents i planificació round-robin (tancant el cercle amb el RepartidorTasques del mòdul 2), la cua de prioritat amb heapq a una jornada de suport amb empats estables, la deque a la tècnica de la deque monòtona per a màxims en finestra, i has combinat pila i cua per invertir per blocs — a més de descobrir, amb els números binaris, que "encuar els descendents del que processo" genera recorreguts per nivells: la llavor del BFS que germinarà al mòdul 7. Les tres estructures d'accés restringit (pila, cua, deque) ja són teves, contracte i costos inclosos. Però fixa't en una cosa que hem fet tot el mòdul sense qüestionar-la: cada tasca de TaskFlow és un dict, i dins seu saltem de tasca["id"] a tasca["prioritat"] donant per fet que aquesta consulta és instantània. Per què un dict troba una clau entre milers en temps constant, quan cercar en una llista és O(n)? La resposta —funcions hash, col·lisions i una de les idees més influents de la informàtica— és el programa del mòdul 5: taules hash i diccionaris. Ens hi veiem.

Exercicis amb Cues

Contingut

Exercicis

Exercici 1: notificacions amb reintents

Exercici 2: planificador round-robin amb quantum

Exercici 3: safata d'urgències amb extraccions intercalades

Exercici 4: màxim de tasques completades en finestra lliscant

Exercici 5: generar els binaris d'1 a n amb una cua

Exercici 6: invertir els primers k elements d'una cua

Solucions

Solució 1: notificacions amb reintents

Solució 2: round-robin amb quantum

Solució 3: urgències intercalades

Solució 4: màxim en finestra amb deque monòtona

Solució 5: binaris amb una cua

Solució 6: invertir els primers k amb una pila

Errors Comuns i Consells

Conclusió

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Taules Hash i Diccionaris

Mòdul 6: Arbres

Mòdul 7: Grafs

Mòdul 8: Conclusions i Recursos Addicionals