Algorismes i Estructures de Dades amb Python¶

Recull d'implementacions dels algorismes i estructures de dades fonamentals que tot programador hauria de conèixer. Els exercicis estan organitzats en una ruta d'aprenentatge progressiva de cinc nivells, de menor a major complexitat.

Ruta d'aprenentatge¶

Nivell 1 — Fonaments
    └─ Arrays · Fibonacci · Manipulació de bits

Nivell 2 — Estructures de dades lineals
    └─ Node · Llista enllaçada · Pila · Cua · Taules de hash

Nivell 3 — Ordenació
    └─ Ordenació lineal (bit-sort) · Merge Sort · Quick Sort

Nivell 4 — Grafs
    └─ Graf no dirigit (matriu) · Graf dirigit (llista)
       Graf ponderat (Dijkstra, Prim) · Conjunts disjunts

Nivell 5 — Tècniques avançades
    └─ Programació dinàmica · Backtracking · Flux màxim · Envolupant convexa

Nivell 1 — Fonaments¶

Conceptes bàsics imprescindibles. Punt de partida per a qualsevol estudiant.

Arrays i operacions bàsiques¶

arrays/array.py

Operacions fonamentals sobre llistes de Python: append, pop, index, remove, reverse, sort. Complexitats habituals: O(1) per a append/pop al final, O(n) per a cerca i inserció al mig.

# Exemple d'ús
a = [5, 3, 8, 1, 9]
a.sort()       # O(n log n)
a.reverse()    # O(n)
a.pop()        # O(1)

Fibonacci iteratiu¶

experiments/fib_improved.py

Càlcul de la seqüència de Fibonacci de forma iterativa amb desempaquetament de tuples. Complexitat O(n) temporal i O(1) espacial, en contraposició a la versió recursiva naïve O(2^n).

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Manipulació de bits¶

[bit_manipulation/bits.py)[bit_manipulation/bits.py]

Operacions a nivell de bit: distància de Hamming, pes de Hamming, activar/desactivar bits, rotació i aritmètica. Totes O(1) o O(log n). Útil per a problemes d'optimització i criptografia.

Operació	Exemple
Activar bit k	`n \\| (1 << k)`
Desactivar bit k	`n & ~(1 << k)`
Comprovar bit k	`(n >> k) & 1`
Comptar bits a 1	`bin(n).count('1')`

Nivell 2 — Estructures de dades lineals¶

Estructures que organitzen els elements de manera seqüencial.

Node¶

linked_lists/node.py

Classe Node bàsica: conté un valor (data) i un punter al node següent (next). Bloc de construcció per a llistes enllaçades, piles i cues.

Llista enllaçada¶

linked_lists/linked_list.py ·linked_lists/main.py

Implementació d'una LinkedList amb les operacions:

Mètode	Complexitat
`push(data)`	O(1)
`pop()`	O(n)
`append(data)`	O(n)
`contains(data)`	O(n)
`delete(data)`	O(n)

La llista enllaçada és més eficient que un array per a insercions/eliminacions al principi, però pitjor per a accés aleatori.

Pila i cua¶

graphs/queue-stack.py

Demostracions de pila (LIFO) i cua (FIFO) amb collections.deque i queue.LifoQueue. Ambdues estructures ofereixen O(1) per a inserció i extracció en l'extrem correcte.

from collections import deque

# Cua (FIFO)
cua = deque()
cua.append(1)       # enqueue
cua.popleft()       # dequeue — O(1)

# Pila (LIFO)
pila = deque()
pila.append(1)      # push
pila.pop()          # pop — O(1)

Taules de hash¶

hashes/hash-test.py

Prova de distribució d'una funció de hash polinòmica sobre un corpus de text real (tale-of-two-cities.txt). Compara la distribució de col·lisions amb mòdul primer vs. no primer. Complexitat amortitzada O(1) per a cerques i insercions.

Nivell 3 — Ordenació¶

Els algorismes d'ordenació fonamentals i les seves complexitats.

Ordenació lineal (bit-sort)¶

puzzles/sorting_linear.py· puzzles/sorting_linear_optimized.py · puzzles/generate_numbers.py

Ordenació d'enters en temps O(n + k) usant un array de bits. Cada enter es marca com a "present" en una posició del bitmap; després es llegeix en ordre. Òptim per a grans volums d'enters sense repeticions dins d'un rang conegut.

generate_numbers.py genera 9 milions d'enters únics aleatoris en un fitxer per provar l'algorisme.

Comparativa d'ordenació de 9M d'enters:
  Quick Sort:  O(n log n) ~  1.5 s
  Bit-sort:    O(n + k)   ~  0.3 s

Merge Sort¶

merge_sort/merge_sort.py · merge_sort/main.py

Algorisme de dividir i conquerir. Divideix el vector per la meitat recursivament i combina les meitats ordenades.

Millor/Pitjor/Mig cas: O(n log n)
Espai: O(n) addicional
Estable: sí

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    return merge(left, right)

Quick Sort¶

quick_sort/quick_sort.py · quick_sort/main.py

Ordenació in-place amb pivot aleatori i particionament de Lomuto/Hoare.

Cas mig: O(n log n)
Pitjor cas: O(n²) (pivot sempre el mínim/màxim)
Espai: O(log n) per la pila de recursió
Estable: no

La selecció aleatòria del pivot evita el pitjor cas en la pràctica.

Nivell 4 — Grafs¶

Estructures no lineals per modelar relacions entre elements.

Graf no dirigit — representació matricial¶

graphs/undirected_graph_matrix.py

Graf no dirigit amb matriu d'adjacència. Implementa:

DFS recursiu i iteratiu
BFS
Comprovació de grafs bipartits

Operació	Complexitat
Afegir aresta	O(1)
Comprovar aresta	O(1)
DFS / BFS	O(V²)
Espai	O(V²)

Adequat per a grafs densos (moltes arestes).

Graf dirigit — representació per llistes¶

graphs/directed_graph_list.py

Graf dirigit amb llistes d'adjacència. Implementa:

DFS i BFS — O(V + E)
Ordenació topològica
Detecció de cicles
Components fortament connexos (Kosaraju/Tarjan)

Operació	Complexitat
Afegir aresta	O(1)
DFS / BFS	O(V + E)
Espai	O(V + E)

Adequat per a grafs esparsos.

Graf ponderat — Dijkstra i Prim¶

graphs/undirected_graph_weighted.py

Graf no dirigit amb pesos a les arestes. Implementa dos algorismes clàssics:

Dijkstra — camí mínim des d'un origen a tots els vèrtexs:

Complexitat: O(E log V) amb cua de prioritat
Restricció: pesos no negatius

Prim — arbre d'expansió mínim (MST):

Complexitat: O(E log V)
Minimitza el cost total per connectar tots els nodes

Conjunts disjunts (Union-Find)¶

disjoint-sets/disjoint-sets.py

Estructura de dades per gestionar particions d'un conjunt. Amb unió per pes i compressió de camins, les operacions find i union costen quasi O(1) amortitzat (α(n), funció d'Ackermann inversa).

Usos habituals: detecció de cicles en grafs, algorisme de Kruskal per a MST, components connexos.

Nivell 5 — Tècniques avançades¶

Tècniques de disseny d'algorismes per a problemes complexos.

Programació dinàmica — Subsucessió creixent màxima¶

dynamic_programming/maximum_increasing_subsequence.py

Troba la subsucessió creixent no contigua més llarga d'una seqüència. Exemple clàssic de programació dinàmica: es construeix una taula de solucions parcials per evitar recalcular.

Complexitat temporal: O(n²)
Complexitat espacial: O(n)

Entrada: [3, 1, 4, 1, 5, 9, 2, 6]
Sortida: [1, 4, 5, 9]  (longitud 4)

Backtracking — Generació de subconjunts¶

backtracking/subsets.py

Genera tots els 2^n subconjunts d'un conjunt explorant recursivament l'arbre de decisions (incloure o no cada element). Complexitat O(2^n) inevitablement, ja que la sortida té 2^n elements.

Entrada: {1, 2, 3}
Sortida: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

Flux màxim — Ford-Fulkerson¶

maximum_flow/max-flows.py

Algorisme de Ford-Fulkerson per calcular el flux màxim en una xarxa de transport. Usa DFS per trobar camins augmentants. Complexitat O(E · f_max) on f_max és el flux màxim.

Aplicacions: xarxes de transport, assignació de tasques, tall mínim en grafs.

Envolupant convexa — Gift Wrapping¶

convex-hull/convex-hull.py

Algorisme de Gift Wrapping (Jarvis March) que calcula l'envolupant convexa d'un conjunt de punts 2D: el polígon convex mínim que conté tots els punts.

Complexitat: O(n · h), on h és el nombre de punts a l'envolupant
Útil en geometria computacional, visió per computador i robòtica

Experiments i aplicacions pràctiques¶

Demostracions d'aplicació de conceptes en problemes reals.

Concurrència — Fils d'execució¶

experiments/threads.py · experiments/threads2.py

threads.py: creació de 10 fils amb threading.Thread, temps d'espera aleatoris.
threads2.py: sincronització amb threading.Lock per protegir l'accés a una base de dades compartida (exclusió mútua).

Machine Learning bàsic¶

machine-learning/k-nearest-neighbors.py

Classificador KNN (k=1) amb distància euclidiana sobre el dataset Iris. Entrena en O(1) i prediu en O(n). Exemple introductori d'aprenentatge supervisat.

machine-learning/statistics.py

Generació d'histogrames de distribució amb Counter i matplotlib. Visualització bàsica de dades estadístiques.

machine-learning/neural-net.py

Xarxa neuronal profunda amb TensorFlow/Keras (3 capes ocultes: 10-20-10 neurones) entrenada sobre el dataset Iris. Exemple introductori de Deep Learning.

Taula resum¶

Nivell	Fitxer	Algorisme / Estructura	Complexitat
1	`arrays/array.py`	Operacions sobre arrays	O(1)–O(n)
1	`experiments/fib_improved.py`	Fibonacci iteratiu	O(n) temps, O(1) espai
1	`bit_manipulation/bits.py`	Manipulació de bits	O(1)–O(log n)
2	`linked_lists/`	Llista enllaçada	O(1) inserció inici, O(n) cerca
2	`graphs/queue-stack.py`	Pila i cua	O(1)
2	`hashes/hash-test.py`	Taula de hash	O(1) amortitzat
3	`puzzles/sorting_linear.py`	Bit-sort	O(n + k)
3	`merge_sort/`	Merge Sort	O(n log n)
3	`quick_sort/`	Quick Sort	O(n log n) mig, O(n²) pitjor
4	`graphs/undirected_graph_matrix.py`	Graf matriu + DFS/BFS	O(V²)
4	`graphs/directed_graph_list.py`	Graf llista + Topological	O(V + E)
4	`graphs/undirected_graph_weighted.py`	Dijkstra + Prim	O(E log V)
4	`disjoint-sets/`	Union-Find	O(α(n)) ≈ O(1)
5	`dynamic_programming/`	Subsucnessió creixent màxima	O(n²)
5	`backtracking/subsets.py`	Generació de subconjunts	O(2^n)
5	`maximum_flow/max-flows.py`	Ford-Fulkerson	O(E · f_max)
5	`convex-hull/convex-hull.py`	Gift Wrapping	O(n · h)