ALGORITMOS · De la teoría de juegos al agente que razona

John von Neumann publica Zur Theorie der Gesellschaftsspiele en 1928, con 25 años, en Berlín. El teorema minimax prueba que en cualquier juego de suma cero entre dos jugadores con información perfecta, existe una estrategia óptima: minimiza tu pérdida máxima posible. La formulación es puramente matemática — no requiere ordenador. Pero setenta años después se convierte en el corazón de Deep Blue (1997) y AlphaGo (2016): los árboles de búsqueda adversaria que vencen a campeones mundiales ejecutan variantes del mismo principio.

Edsger Dijkstra escribe el algoritmo del camino más corto en un café de Ámsterdam en 1956, en aproximadamente 20 minutos, sin papel ni lápiz ("lo diseñé sin papel, lo que creo que es una de las razones por las que es tan elegante"). Lo publica en 1959 en Numerische Mathematik. El algoritmo recorre un grafo dirigido con pesos y encuentra el camino de menor coste desde un nodo origen a todos los demás. Complejidad: O(V²) en la versión original, O(E + V log V) con heap de Fibonacci.

Sin el algoritmo de Dijkstra no hay routing de internet (OSPF, IS-IS), no hay GPS, no hay planificación de red de telecomunicaciones. Los grafos de redes neuronales también heredan su lógica de recorrido. Dijkstra trabajaba en el Mathematisch Centrum de Ámsterdam con un computador ARMAC — es el primer algoritmo diseñado con una aplicación real de computación en mente.

C. A. R. Hoare (Tony Hoare) publica Quicksort en 1962 en The Computer Journal, con 28 años. El algoritmo: divide el array en torno a un pivote, ordena recursivamente cada mitad. Complejidad media: O(n log n). Peor caso: O(n²) — pero en la práctica es el algoritmo de ordenación más rápido para datos aleatorios durante décadas. La recursividad aquí no es un truco: es la estructura del problema. Hoare trabaja en Elliott Brothers, fabricante de ordenadores, cuando lo diseña — la necesidad era práctica. El patrón divide-and-conquer se convierte en técnica fundamental de diseño de algoritmos, de Mergesort a FFT.

Donald Knuth publica el Vol. 1 de The Art of Computer Programming (TAOCP) en 1968, en Stanford. Antes de Knuth, los algoritmos se describían informalmente, sin análisis de coste. Knuth formaliza la notación O() (aunque Landau la había introducido en 1909, Knuth la populariza en CS), el análisis amortizado, y el análisis probabilístico. Inventa MIX, un computador hipotético estándar para análisis comparativo. El Vol. 4B (el más reciente) se publicó en 2022 — el proyecto lleva más de 50 años activo. Knuth interrumpió la redacción en 1977 para crear TeX porque la composición tipográfica de los manuscritos era inaceptable. TeX es ahora el estándar de publicación científica.

Stephen Cook (Universidad de Toronto) y Leonid Levin (Moscú, independientemente) demuestran en 1971 el teorema Cook-Levin: el problema de satisfacibilidad booleana (SAT) es NP-completo. Consecuencia: si SAT es resoluble en tiempo polinomial, entonces todos los problemas de NP también lo son. Define la frontera entre P (tratable) y NP (verificable en tiempo polinomial). La pregunta P=NP sigue abierta en 2026 — el Clay Mathematics Institute ofrece 1 millón de dólares por su resolución. Cook recibe el Premio Turing en 1982. La teoría de la complejidad se vuelve herramienta para demostrar que ciertos problemas (viajante, coloración de grafos, scheduling) no tienen solución eficiente general conocida.

Whitfield Diffie y Martin Hellman publican "New Directions in Cryptography" en noviembre de 1976. Proponen el primer protocolo de intercambio de claves sin canal seguro previo: dos partes que nunca se han comunicado antes pueden establecer un secreto compartido en presencia de un adversario que escucha todo. La seguridad descansa en la dificultad del logaritmo discreto. Antes de Diffie-Hellman, para comunicarte cifrado necesitabas haber intercambiado la clave en persona previamente. Con Diffie-Hellman, la web cifrada es posible. Sin este paper no hay HTTPS, no hay e-commerce, no hay mensajería cifrada moderna. Reciben el Premio Turing en 2015.

Ron Rivest, Adi Shamir y Leonard Adleman (MIT) publican RSA en 1977. Primer sistema de cifrado de clave pública completamente funcional: mensaje cifrado con clave pública, descifrado solo con clave privada. La seguridad descansa en la dificultad de factorizar el producto de dos primos grandes. Rivest inventa RSA en una noche de insomnio tras una fiesta de Pésaj, según su propio relato. El algoritmo estaba clasificado en el Reino Unido (GCHQ lo había desarrollado independientemente en 1973, clasificado) hasta que Clifford Cocks lo desclasificó en 1997. RSA es hoy el algoritmo de clave pública más desplegado del mundo — y está directamente bajo amenaza del algoritmo de Shor (1994), que lo rompe en tiempo polinomial con un ordenador cuántico suficientemente grande.

Leonard Adleman (USC) publica "Molecular Computation of Solutions To Combinatorial Problems" en Science en noviembre de 1994. Resuelve el problema del camino hamiltoniano para un grafo de 7 nodos usando cadenas de DNA: cada posible camino se codifica como una cadena de nucleótidos, las cadenas se mezclan en un tubo de ensayo, y la bioquímica selecciona por complementariedad las que son válidas. El cómputo tarda días, pero funciona. El mismo Adleman de RSA aplica ahora la dureza computacional de NP a un sustrato biológico. Demuestra el principio fundamental: la computación no requiere silicio — cualquier sustrato que procese información puede computar.

Larry Page y Sergey Brin (Stanford) publican "The Anatomy of a Large-Scale Hypertextual Web Search Engine" en enero-abril de 1998. Trabajo iniciado en 1996 como "BackRub". PageRank calcula la importancia de una página web como el eigenvector dominante del grafo de hiperenlaces: una página es importante si páginas importantes enlazan a ella. El algoritmo convierte un problema de búsqueda en un problema de álgebra lineal sobre un grafo de miles de millones de nodos. Page y Brin fundan Google ese mismo año. Sin PageRank, el directorio Yahoo o el AltaVista basado en keywords seguirían siendo la norma.

Jeffrey Dean y Sanjay Ghemawat (Google) publican el paper de MapReduce en 2004, en OSDI. El patrón: distribuir un cómputo masivo en dos fases — map (aplicar una función a cada elemento en paralelo) y reduce (agregar los resultados). La elegancia está en que el programador escribe solo esas dos funciones; el sistema se encarga de la distribución, la tolerancia a fallos y el balanceo de carga en miles de máquinas. Inspira Hadoop (2006, Yahoo/Doug Cutting), Spark (2009, AMPLab Berkeley), y todo el ecosistema big data de la siguiente década. Google usaba MapReduce para construir el índice web completo — el problema que PageRank resuelve teóricamente, MapReduce lo ejecuta a escala.

Satoshi Nakamoto — identidad desconocida — publica "Bitcoin: A Peer-to-Peer Electronic Cash System" en octubre de 2008. Resuelve el problema del teniente bizantino a escala global: ¿cómo llegan a un consenso N nodos desconfiados sin autoridad central? La solución: proof-of-work como mecanismo de selección aleatoria pesado por poder computacional. El primero en resolver un puzzle criptográfico impone el siguiente bloque; la cadena más larga es la válida. Primera vez que un sistema distribuido sin administrador central mantiene estado consistente entre millones de nodos desconocidos entre sí. Funda la era cripto y abre la pregunta sobre consenso descentralizado más allá de la moneda.

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser y Illia Polosukhin (Google Brain / Google Research) publican "Attention Is All You Need" en junio de 2017. El mecanismo de atención escalado por producto-punto ya existía en formas previas (Bahdanau 2015), pero este paper lo convierte en la primitiva central: reemplaza convolucioon y recurrencia por atención multi-cabeza, posibilitando paralelización completa durante el entrenamiento. Sin esto no hay Transformer; sin Transformer no hay GPT, Claude, Gemini ni Llama.

La cadena que va de ReAct (Yao et al., Princeton/Google, 2022) a Tree-of-Thoughts (Yao et al., 2023), MCTS sobre LLMs, tool use estructurado (Anthropic, OpenAI, 2023-2024) y planning con verificación (múltiples equipos). El patrón que emerge: los LLMs actúan como heurísticas dentro de bucles de búsqueda clásica. Tree-of-Thoughts aplica búsqueda en árbol (el minimax de Von Neumann, 1928) pero con un LLM evaluando los nodos. MCTS (Monte Carlo Tree Search) — el mismo algoritmo que AlphaGo usó en Go — se combina con modelos de lenguaje para razonamiento complejo. La IA generativa regresa a los algoritmos de búsqueda clásica como estructura; el LLM aporta la heurística que antes tenía que programarse a mano.