Invatare Atomica

Aplicatii cu cozi: simulari si procesare in ordine

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei aplica structura FIFO a cozii pentru a rezolva probleme reale: simularea proceselor, procesarea datelor in ordine de sosire si parcurgerea BFS a grafurilor.

Dupa aceasta lectie vei putea:

  • Sa implementezi simulari pas-cu-pas folosind o coada (ghiseu, imprimanta)
  • Sa procesezi date in ordinea sosirii cu collections.deque din Python
  • Sa explici de ce BFS foloseste o coada si nu o stiva
  • Sa implementezi BFS complet pe un graf in Python
  • Sa distingi intre deque dublu-capat si coada simpla
  • Sa folosesti std::queue si std::deque din C++ STL EXCLUSIV INTENSIV

Incearca singur!

Provocare de gandire:

Un supermarket are 3 case de marcat. Daca doriti sa aflati care client iese primul, ce informatii aveti nevoie despre fiecare coada?

💡 Ai nevoie de un indiciu?

Trebuie sa stiti cat timp dureaza servirea fiecarui client. Clientul care termina primul are suma minima: (timp pana la el) + (timp propriu de servire). Aceasta este esenta simularii cu cozi multiple!

1

1. Recapitulare: coada FIFO si deque in Python

O coada (queue) este o structura FIFO: primul element intrat este primul care iese. In Python, collections.deque implementeaza o coada eficienta cu O(1) la ambele capete.
Analogie: randul la ghiseu

Prima persoana venita este prima servita. Ordinea de intrare = ordinea de iesire. Nu poti sari sau intra pe la spate.

from collections import deque

coada = deque()
coada.append("Ana")      # enqueue: adaugam la spate  O(1)
coada.append("Bogdan")
coada.append("Cristi")

print("Coada initiala:", list(coada))
print("Lungime:", len(coada))
print("
Servire clienti:")
while coada:
    client = coada.popleft()  # dequeue: scoatem din fata  O(1)
    print(f"  Servit: {client}  |  Ramas in coada: {list(coada)}")
Output real (python coada_test1.py):
Coada initiala: ['Ana', 'Bogdan', 'Cristi']
Lungime: 3

Servire clienti:
  Servit: Ana  |  Ramas in coada: ['Bogdan', 'Cristi']
  Servit: Bogdan  |  Ramas in coada: ['Cristi']
  Servit: Cristi  |  Ramas in coada: []
⚠
De ce NU list.pop(0)?

list.pop(0) este O(n): deplaseaza toate elementele. deque.popleft() este O(1). Pentru cozi cu mii de elemente, diferenta este critica.

Operatielist Pythoncollections.deque
Adaugare la spateappend(x) — O(1)append(x) — O(1)
Extragere din fatapop(0) — O(n)popleft() — O(1)
Acces la primul element[0] — O(1)[0] — O(1)
2

2. Simulare: coada de imprimanta

Simularea cu coada modeleaza un sistem real unde evenimentele se proceseaza in timp, in ordine FIFO. Joburile de imprimanta se proceseaza in ordinea sosirii, indiferent de utilizator.
from collections import deque

imprimanta = deque()
imprimanta.append({"id": 1, "pagini": 3, "utilizator": "Ana"})
imprimanta.append({"id": 2, "pagini": 1, "utilizator": "Bogdan"})
imprimanta.append({"id": 3, "pagini": 5, "utilizator": "Cristi"})

print("Joburi in coada imprimantei:")
for i, job in enumerate(imprimanta):
    print(f"  [{i+1}] Job#{job['id']} - {job['pagini']} pagini - {job['utilizator']}")

print("
Procesare:")
total_pagini = 0
while imprimanta:
    job = imprimanta.popleft()
    total_pagini += job["pagini"]
    print(f"  Tiparit Job#{job['id']} ({job['pagini']} pagini) - {job['utilizator']}")
    print(f"       In asteptare: {len(imprimanta)} joburi")

print(f"
Total pagini tiparite: {total_pagini}")
Output real (python coada_test2.py):
Joburi in coada imprimantei:
  [1] Job#1 - 3 pagini - Ana
  [2] Job#2 - 1 pagini - Bogdan
  [3] Job#3 - 5 pagini - Cristi

Procesare:
  Tiparit Job#1 (3 pagini) - Ana
       In asteptare: 2 joburi
  Tiparit Job#2 (1 pagini) - Bogdan
       In asteptare: 1 joburi
  Tiparit Job#3 (5 pagini) - Cristi
       In asteptare: 0 joburi

Total pagini tiparite: 9
Complexitate
Fiecare job procesat exact o data: O(n) timp, O(n) spatiu.

Tiparul general al simularii cu coada: (1) Initializam coada; (2) Cat timp coada nu e vida: extragem, procesam, optional adaugam elemente noi; (3) Colectam rezultatele.

3

3. BFS (Breadth-First Search) — coada la lucru pe grafuri

BFS (parcurgere in latime) viziteaza toate nodurile unui graf nivel cu nivel. Coada garanteaza ca un nod la distanta d este procesat inaintea oricarui nod la distanta d+1.
Analogie: undele de apa

O piatra aruncata intr-un lac produce unde circulare. Toate punctele la raza 1 sunt atinse inainte de cele la raza 2. BFS functioneaza identic: exploreaza valuri concentrice pornind de la nodul sursa.

Graf exemplu: noduri 1–6, muchii: 1–2, 1–3, 2–4, 2–5, 3–6

from collections import deque

graf = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [], 5: [], 6: []
}

def bfs(start):
    vizitat = set()
    coada = deque()
    ordine = []
    coada.append(start)
    vizitat.add(start)
    while coada:
        nod = coada.popleft()
        ordine.append(nod)
        print(f"  Vizitat: {nod}  |  Coada: {list(coada)}")
        for vecin in graf[nod]:
            if vecin not in vizitat:
                vizitat.add(vecin)
                coada.append(vecin)
    return ordine

print("BFS pornind din nodul 1:")
rezultat = bfs(1)
print(f"
Ordine vizitare: {rezultat}")
Output real (python coada_test3.py):
BFS pornind din nodul 1:
  Vizitat: 1  |  Coada: []
  Vizitat: 2  |  Coada: [3]
  Vizitat: 3  |  Coada: [4, 5]
  Vizitat: 4  |  Coada: [5, 6]
  Vizitat: 5  |  Coada: [6]
  Vizitat: 6  |  Coada: []

Ordine vizitare: [1, 2, 3, 4, 5, 6]
🔎
De ce vizitat este un set si nu o lista?

Verificarea vecin not in vizitat trebuie sa fie O(1). Un set ofera acces O(1) in medie. O lista ar face aceasta verificare O(n), incetinind BFS-ul de la O(V+E) la O(V·E).

Complexitate BFS
Timp: O(V + E) — fiecare nod vizitat exact o data, fiecare muchie examinata exact o data. Spatiu: O(V) pentru coada si multimea vizitat.
4

4. Deque: coada cu doua capete si fereastra glisanta

Un deque (double-ended queue, pronuntat “deck”) permite adaugarea si stergerea elementelor la ambele capete in O(1). Util cand avem nevoie de flexibilitate mai mare decat o coada simpla.
from collections import deque

d = deque([10, 20, 30])
print("Deque initial:", list(d))
d.appendleft(5)
print("Dupa appendleft(5):", list(d))
d.append(40)
print("Dupa append(40):", list(d))
stanga = d.popleft()
print(f"popleft() = {stanga}, deque ramas: {list(d)}")
dreapta = d.pop()
print(f"pop() = {dreapta}, deque ramas: {list(d)}")
# maxlen: fereastra glisanta de dimensiune fixa
fereastra = deque(maxlen=3)
for val in [1, 2, 3, 4, 5]:
    fereastra.append(val)
    print(f"  append({val}) -> {list(fereastra)}")
Output real (python coada_test4.py):
Deque initial: [10, 20, 30]
Dupa appendleft(5): [5, 10, 20, 30]
Dupa append(40): [5, 10, 20, 30, 40]
popleft() = 5, deque ramas: [10, 20, 30, 40]
pop() = 40, deque ramas: [10, 20, 30]
  append(1) -> [1]
  append(2) -> [1, 2]
  append(3) -> [1, 2, 3]
  append(4) -> [2, 3, 4]
  append(5) -> [3, 4, 5]

Parametrul maxlen creeaza o fereastra glisanta: cand deque-ul este plin, adaugarea unui element nou elimina automat elementul de la celalalt capat. Util pentru: media ultimelor N valori, log-uri de dimensiune fixa.

Atentie
Accesul la mijlocul unui deque (d[i] pentru i interior) este O(n), nu O(1). Daca aveti nevoie de acces aleator frecvent, folositi o lista. Deque este optim doar pentru operatii la capete.
5

5. C++ STL: std::queue — simulare clienti EXCLUSIV INTENSIV

Aceasta sectiune este destinata exclusiv profilului mat-info intensiv. La profilul standard, Python cu collections.deque este suficient.
In C++, <queue> din STL ofera std::queue<T> pentru cozi FIFO. Operatii: push(x), pop(), front(), back(), empty(), size().
Diferenta cruciala fata de Python
In C++, queue::pop() NU returneaza elementul eliminat. Trebuie sa cititi cu front(), stocati valoarea, apoi apelati pop(). Uitarea acestui detaliu produce bug-uri silentioase.
#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
    queue<string> coada;
    coada.push("Ana");
    coada.push("Bogdan");
    coada.push("Cristi");
    cout << "Coada are " << coada.size() << " clienti." << endl;
    cout << "Primul la rand: " << coada.front() << endl;
    cout << "Ultimul la rand: " << coada.back() << endl;
    cout << "
Servire clienti:" << endl;
    while (!coada.empty()) {
        cout << "  Servit: " << coada.front()
             << "  |  Ramas: " << (coada.size() - 1) << endl;
        coada.pop();
    }
    return 0;
}
Output real (g++ -std=c++17 coada_cpp1.cpp -o coada_cpp1.exe && ./coada_cpp1.exe):
Coada are 3 clienti.
Primul la rand: Ana
Ultimul la rand: Cristi

Servire clienti:
  Servit: Ana  |  Ramas: 2
  Servit: Bogdan  |  Ramas: 1
  Servit: Cristi  |  Ramas: 0
6

6. BFS si std::deque in C++ EXCLUSIV INTENSIV

BFS in C++ este cerut la concursuri (OJI, ONI, Baraj). Varianta cu matrice de adiacenta este cea mai simpla de implementat in timp limitat.

BFS complet in C++ cu matrice de adiacenta:

#include <iostream>
#include <queue>
using namespace std;
int adj[7][7] = {0};
int main() {
    adj[1][2]=1; adj[1][3]=1;
    adj[2][4]=1; adj[2][5]=1;
    adj[3][6]=1;
    bool vizitat[7] = {false};
    queue<int> coada;
    coada.push(1); vizitat[1] = true;
    cout << "BFS din nodul 1:" << endl;
    while (!coada.empty()) {
        int nod = coada.front(); coada.pop();
        cout << "  Vizitat: " << nod << endl;
        for (int v = 1; v <= 6; v++) {
            if (adj[nod][v] && !vizitat[v]) {
                vizitat[v] = true; coada.push(v);
            }
        }
    }
    return 0;
}
Output real (g++ -std=c++17 coada_cpp2.cpp -o coada_cpp2.exe && ./coada_cpp2.exe):
BFS din nodul 1:
  Vizitat: 1
  Vizitat: 2
  Vizitat: 3
  Vizitat: 4
  Vizitat: 5
  Vizitat: 6

std::deque — operatii la ambele capete:

#include <iostream>
#include <deque>
using namespace std;
int main() {
    deque<int> d = {10, 20, 30};
    d.push_front(5); d.push_back(40);
    cout << "pop_front() = " << d.front() << endl; d.pop_front();
    cout << "pop_back() = " << d.back() << endl; d.pop_back();
    cout << "Final: ";
    for (int x : d) cout << x << " ";
    cout << endl;
    return 0;
}
Output real (g++ -std=c++17 coada_cpp3.cpp -o coada_cpp3.exe && ./coada_cpp3.exe):
pop_front() = 5
pop_back() = 40
Final: 10 20 30
Operatiestd::queuestd::dequeComplexitate
Adauga la spatepush(x)push_back(x)O(1)
Adauga la fataNU existapush_front(x)O(1)
Scoate din fatapop()pop_front()O(1)
Scoate din spateNU existapop_back()O(1)
Peek fatafront()front()O(1)
Acces indexNU existad[i]O(1)

Exercitii practice

Exercitiul 1 (Nivel minim) — Simulare ghiseu

Scrieti un program Python care simuleaza un ghiseu bancar. Adaugati 5 clienti in coada (ID: 101–105), serviti-i pe rand afisand "Clientul [ID] a fost servit. Raman [N] clienti." Folositi collections.deque.

Vezi rezolvarea

Program complet, cu collections.deque ca la Atomul 1:

  1. from collections import deque
  2. coada = deque() apoi for id_client in range(101, 106): coada.append(id_client) — adauga clientii 101..105.
  3. while coada: client = coada.popleft(); print(f"Clientul {client} a fost servit. Raman {len(coada)} clienti.")

Rezultat asteptat (in ordine):

  1. Clientul 101 a fost servit. Raman 4 clienti.
  2. Clientul 102 a fost servit. Raman 3 clienti.
  3. Clientul 103 a fost servit. Raman 2 clienti.
  4. Clientul 104 a fost servit. Raman 1 clienti.
  5. Clientul 105 a fost servit. Raman 0 clienti.

Exercitiul 2 (Nivel standard) — BFS cu calcul distante

Modificati BFS din Atomul 3 pentru a calcula si afisa distanta de la nodul de start la fiecare nod. Pastrati un dictionar dist unde dist[vecin] = dist[nod] + 1. Afisati "Distanta de la 1 la [nod]: [d]" pentru toate nodurile.

Vezi rezolvarea

Pornim de la codul BFS al Atomului 3 (graf = {1:[2,3], 2:[4,5], 3:[6], 4:[], 5:[], 6:[]}) si adaugam dictionarul dist:

  1. La initializare: dist = {start: 0}, alaturi de vizitat si coada.
  2. Cand descoperim un vecin nou (in bucla for vecin in graf[nod], ramura if vecin not in vizitat), inainte de coada.append(vecin) scriem dist[vecin] = dist[nod] + 1.
  3. La final: for nod in sorted(dist): print(f"Distanta de la 1 la {nod}: {dist[nod]}").

Rezultat asteptat, pornind din nodul 1:

  1. Distanta de la 1 la 1: 0
  2. Distanta de la 1 la 2: 1
  3. Distanta de la 1 la 3: 1
  4. Distanta de la 1 la 4: 2
  5. Distanta de la 1 la 5: 2
  6. Distanta de la 1 la 6: 2

Explicatie: 2 si 3 sunt vecini directi ai lui 1 (distanta 1); 4 si 5 se descopera din 2, iar 6 din 3, deci toate trei ajung la distanta 2.

Exercitiul 3 (Nivel performanta) — Fereastra glisanta maxim cu deque O(n)

Dat un sir de n numere si un numar k, gasiti maximul din fiecare fereastra de dimensiune k. Solutia naiva O(n·k); solutia optima cu deque O(n). Testati pe [1, 3, -1, -3, 5, 3, 6, 7] cu k=3; rezultat asteptat: [3, 3, 5, 5, 6, 7].

Vezi rezolvarea

Atentie: lectia arata doar deque(maxlen=k) pentru o fereastra de dimensiune fixa (Atomul 4), NU tehnica de calcul al maximului in O(n) — aceea trebuie construita pornind de la ce stii despre deque, nu e data gata.

  1. Solutia naiva O(n*k): pentru fiecare pozitie de start a ferestrei, ia subsirul de k elemente si calculeaza max() direct.
  2. Solutia optima O(n): pastreaza in deque INDICII elementelor (nu valorile), astfel incat valorile corespunzatoare sa ramana mereu in ordine descrescatoare de la fata la spate.
  3. Pentru fiecare indice i din sir: (a) scoate din fata cu popleft() indicii iesiti din fereastra (indice <= i-k); (b) scoate din spate cu pop() indicii a caror valoare este mai mica sau egala cu sir[i] — nu mai pot fi niciodata maximul cat timp sir[i] e in fereastra; (c) adauga i la spate cu append(i); (d) cand indicele i este mai mare sau egal cu k-1, maximul ferestrei curente este sir[deque[0]].
  4. Verificare pe exemplul din cerinta: [1,3,-1,-3,5,3,6,7] cu k=3 trebuie sa produca [3, 3, 5, 5, 6, 7].

Criterii de evaluare: complexitatea reala trebuie sa fie O(n) (fiecare indice intra si iese din deque o singura data, nu la fiecare fereastra); rezultatul trebuie sa coincida exact cu [3, 3, 5, 5, 6, 7]; capcana tipica e sa uiti pasul (b) — fara el deque-ul nu mai e monoton si maximul din fata devine gresit.

Ce ai invatat astazi

  • collections.deque: coada eficienta in Python, O(1) pentru append/popleft
  • Simulare cu coada: init → while coada: popleft → procese → eventual append
  • BFS foloseste coada pentru explorare nivel cu nivel — O(V+E) timp, O(V) spatiu
  • Deque cu maxlen implementeaza fereastra glisanta de dimensiune fixa in O(1)
  • [intensiv] std::queue: push/pop/front/back; pop() NU returneaza valoarea
  • [intensiv] std::deque: push_front/push_back/pop_front/pop_back, acces direct []

Vrei mai mult?

Provocare: Modifica functia bfs din atomul 3 ca sa retina si un dictionar parinte (parinte[vecin] = nod la fiecare descoperire). Scrie apoi o functie reconstruieste_drum(parinte, start, tinta) care urca prin dictionar de la tinta inapoi la start si returneaza drumul complet. Testeaza pe graful din lectie: drumul de la nodul 1 la nodul 6.

De ce? BFS gaseste intotdeauna drumul cu cel mai mic numar de muchii intr-un graf neponderat. De ce garanteaza asta coada (FIFO), in timp ce o parcurgere cu stiva (DFS) nu ofera aceeasi garantie?

Deschidere: Aplicatiile de rutare (tip Google Maps) folosesc variante de BFS extins cu costuri (Dijkstra) ca sa gaseasca cel mai scurt traseu. Retelele sociale folosesc BFS pentru "gradele de separare" - de exemplu, cati pasi separa doi utilizatori prin prietenii lor comuni.

Urmatoarea lectie

Continua cu Lectia 5: Introducere grafuri — terminologie, noduri, muchii, grade, graf orientat vs neorientat.

Lectia 5: Grafuri →