
TecnologíaMatemáticas
La receta de todo
Algoritmos, complejidad y lo incomputable
Detrás de cada búsqueda, cada ruta y cada recomendación hay una receta de pasos. Algunas son rapidísimas, otras tardarían más que la edad del universo, y otras no pueden existir. Descubre la diferencia.
Empezar ahora
12 enseñanzas · te llevas 12 conceptos usables
Fundamento
El mecanismo desnudo- 1AlgoritmoAl-Juarismi escribió en el siglo IX métodos paso a paso para hacer cálculos, y su nombre, latinizado, terminó convertido en "algoritmo". La idea es anterior a los computadores: cualquier receta precisa que siempre funciona cabe en ella.
- Cuenta gratisComplejidadCon una lista corta, casi cualquier método es instantáneo. La diferencia aparece cuando los datos crecen: unos algoritmos se demoran el doble cuando los datos se duplican, y otros se demoran cuatro veces, o muchísimo más.
- RecursiónEn el juego de las Torres de Hanói hay que pasar discos de un poste a otro sin poner nunca uno grande sobre uno pequeño. La solución más elegante no describe cada movimiento: describe cómo reducir el problema a uno igual pero con un disco menos.
- Fuerza brutaNo hace falta ingenio: basta con empezar en 000 y seguir hasta 999. Tarde o temprano se abre. Esa estrategia, simple y segura, tiene un problema serio que aparece apenas el número de opciones crece.
Mecanismo
El concepto chocando con otros- Caso: problema del viajanteCon cinco ciudades se pueden revisar todas las rutas en un minuto. Con veinte, el número de rutas posibles es tan grande que ni el computador más rápido del mundo terminaría de revisarlas por fuerza bruta en toda una vida.Te llevas: problema del viajante
- Duelo: heurísticaCuando encontrar la solución óptima tardaría siglos, insistir en ella es inútil. Los ingenieros aceptan un trato distinto: una respuesta muy buena, lista en segundos, aunque no sea la mejor posible.Te llevas: heurística
- Problema NPComprobar que cada fila, columna y cuadro tiene todos los números es mecánico y rápido. Encontrar esos números desde cero es otra historia. Esa asimetría entre verificar y resolver define una de las familias de problemas más importantes de la computación.
- P versus NPEn el año 2000, el Instituto Clay de Matemáticas eligió siete problemas abiertos y ofreció un millón de dólares por resolver cada uno. Uno de ellos pregunta si todo lo que es fácil de verificar también es fácil de resolver.
Dominio
Lo contraintuitivo y cuándo NO aplica- Problema de la paradaNo por falta de velocidad ni de memoria, sino por una razón lógica. En 1936, antes de que existieran los computadores modernos, Alan Turing demostró que ciertas tareas son imposibles para cualquier algoritmo, sin importar cuánto tiempo tenga.
- Límites: la potencia no lo resuelve todoEs tentador pensar que cualquier problema difícil de hoy será fácil mañana, cuando las máquinas sean más potentes. Pero la historia de este tema muestra dos muros que ninguna mejora de hardware derriba.Te llevas: más potencia no vence lo exponencial
- Caso: algoritmo de ordenamientoOrdenar parece la tarea más aburrida del mundo, pero está en todas partes: listas de notas, resultados de búsqueda, precios, contactos. Y es uno de los mejores ejemplos de cuánto cambia el resultado al elegir un algoritmo u otro.Te llevas: algoritmo de ordenamiento
- Duelo: pensamiento algorítmicoAlgoritmo, complejidad, recursión, fuerza bruta, problema del viajante, heurística, problema NP, P versus NP, problema de la parada, el límite de la potencia y el ordenamiento. Juntas forman un mapa para enfrentar cualquier problema que se quiera resolver con una máquina.Te llevas: pensamiento algorítmico
Empiezas la primera sin cuenta. Las 12 completas, gratis, con solo registrarte.