Paradigmas algorítmicos

¿Qué es un paradigma?

La palabra paradigma proviene del griego “paradeigma” (modelo, ejemplo). En ciencias de la computación y en programación, se usa para describir un enfoque general, un patrón de pensamiento o un conjunto de técnicas recurrentes que nos guían a diseñar algoritmos.

No es un algoritmo específico, sino una forma de ver el problema y estructurar la solución.

Ejemplo: en vez de aprender solo “cómo hacer Dijkstra”, se habla del paradigma de programación dinámica o de divide y vencerás, que abarcan familias de problemas.

Breve historia

  • Años 1950–1970: nacen los primeros algoritmos clásicos (Dijkstra, Kruskal, Ford-Fulkerson) y con ellos la idea de que ciertos tipos de problemas comparten un mismo enfoque.
  • Años 1980–2000: con el auge de algoritmos y estructuras de datos en educación (libros como Cormen CLRS, Aho–Hopcroft–Ullman), se cristaliza el término paradigma algorítmico.
  • Programación competitiva (ICPC, Olimpiadas) lo adopta como una forma didáctica de clasificar: “este problema es de greedy”, “este es de backtracking”, “este es de flujo”.

Principales paradigmas

Aunque la lista puede variar, los clásicos son:

  1. Divide and Conquer (Divide y vencerás)
    • Idea: partir un problema grande en subproblemas más pequeños, resolverlos y combinar resultados.
    • Ejemplo: mergesort, quicksort, FFT.
    • Funciona porque muchos problemas tienen estructura recursiva.
  2. Greedy (Avaro)
    • Idea: tomar decisiones locales óptimas esperando llegar a una solución global.
    • Ejemplo: algoritmo de Kruskal, Huffman coding.
    • Funciona cuando el problema cumple la propiedad de subestructura óptima y intercambio.
  3. Dynamic Programming (Programación dinámica)
    • Idea: guardar resultados de subproblemas y reutilizarlos.
    • Ejemplo: knapsack, Floyd-Warshall, secuencia común más larga (LCS).
    • Funciona cuando hay subproblemas superpuestos y estructura óptima.
  4. Backtracking y Búsqueda Exhaustiva
    • Idea: explorar el espacio de soluciones con poda inteligente.
    • Ejemplo: n-reinas, sudoku, generar combinaciones/permutaciones.
    • Funciona porque reduce el espacio de búsqueda descartando caminos inválidos.
  5. Transformación de problemas / Reducciones
    • Idea: convertir un problema a otro conocido que ya sabemos resolver.
    • Ejemplo: un problema de asignación → matching bipartito → algoritmo de flujo.
    • Funciona porque muchos problemas tienen representaciones equivalentes.
  6. Grafos como paradigma transversal
    • No es un “paradigma” en sí, pero en CP se considera porque gran cantidad de problemas se modelan con grafos y luego se aplican paradigmas sobre ellos (greedy, DP, flujo).

Otros paradigmas que también se consideran

  • Algoritmos de flujo y corte (un submundo en sí mismo).
  • Algoritmos geométricos (barridos, convex hull, etc.).
  • Aleatorización y probabilísticos (ej. algoritmo de Monte Carlo para primalidad).
  • Heurísticos / metaheurísticos (genéticos, simulated annealing, etc., más de investigación que de CP clásica).
  • Paralelización / HPC (divide and conquer en GPUs, paradigmas de map-reduce).

Mapa de Paradigmas Algorítmicos

Paradigma Idea central Cuándo aplicarlo Ejemplo clásico Problema típico en CP/Olimpiadas
Divide and Conquer Partir el problema en subproblemas más pequeños, resolverlos y combinar. Cuando el problema tiene estructura recursiva y se puede dividir en mitades u otras fracciones. Mergesort, Quicksort, FFT. Encontrar el par de puntos más cercanos en un plano (Closest Pair).
Greedy (Avaro) Tomar siempre la decisión localmente óptima. Cuando el problema tiene subestructura óptima y cumple la propiedad de intercambio. Kruskal, Prim, Huffman coding. Seleccionar actividades en un horario sin traslape (Activity Selection).
Dynamic Programming (DP) Resolver subproblemas, guardar resultados y reutilizarlos. Cuando hay subproblemas superpuestos y estructura óptima. Floyd-Warshall, Knapsack, LCS. Máxima suma de subsecuencia, caminos mínimos en un grid.
Backtracking / Búsqueda exhaustiva Explorar todas las soluciones posibles con poda. Cuando el espacio de búsqueda es grande pero hay reglas que permiten descartar. N-reinas, Sudoku solver. Generar todas las permutaciones de una cadena con restricciones.
Transformación / Reducciones Convertir el problema a otro ya conocido. Cuando identificas que tu problema es equivalente a flujo, matching, SAT, etc. Asignación de tareas → Matching bipartito. “Maximum Bipartite Matching” para emparejar estudiantes y proyectos.
Algoritmos de Grafos Modelar entidades como nodos y relaciones como aristas. Cuando el problema involucra redes, conexiones, caminos, jerarquías. BFS, DFS, Dijkstra, Bellman-Ford. Encontrar el camino más corto en un mapa de ciudades.
Flujo / Corte mínimo Maximizar el flujo en una red, o encontrar el cuello de botella. Cuando el problema es de asignación, transporte, emparejamiento. Ford-Fulkerson, Edmonds-Karp. Organizar un torneo con restricciones de horarios.
Geometría computacional Usar algoritmos especializados para el plano/espacio. Cuando el problema involucra coordenadas, distancias, áreas. Convex Hull, Line Sweep. Determinar si dos polígonos se intersectan.
Aleatorización / Probabilísticos Introducir azar para simplificar o acelerar. Cuando una solución determinista es muy costosa. Algoritmo de Miller-Rabin (primalidad). Encontrar un hash perfecto con probabilidad alta.

Cómo usar este mapa

  1. Clasificación inicial: cuando ves un problema, pregúntate si se parece más a optimización, búsqueda, geometría, o redes.
  2. Reconocer estructuras: si el problema menciona “subproblemas”, piensa en DP; si menciona “elegir actividades”, piensa en greedy; si hay “relaciones”, piensa en grafos.
  3. Mezclas son comunes: un problema puede requerir DP + greedy (ej. knapsack con reconstrucción de solución), o geometría + divide and conquer.

Ejemplo de aplicación

  • Problema: “Tienes N trabajos con tiempos de inicio y fin, selecciona el máximo número de trabajos sin traslape.”
    • Paradigma correcto → Greedy (ordenar por tiempo de finalización y tomar el primero que encaje).
  • Problema: “Camino más corto en una grilla de N x N con obstáculos.”
    • Paradigma correcto → Grafos (modelar la grilla como grafo y aplicar BFS/Dijkstra).

Esto funciona muy bien porque da un mapa mental: en vez de memorizar algoritmos sueltos, se ven familias de problemas que responden al mismo “patrón de pensamiento”.