KnowSoda
TecnologíaInformática
Algoritmos: datos curiosos y test
Lo esencial en 7 ideas, con datos curiosos, una historia ilustrada y un test para ver cuánto sabes.
Lo esencial
Qué es un algoritmo
Un algoritmo es una serie de pasos claros para resolver un problema, como una receta. Los ordenadores siguen algoritmos, y también las personas cuando se atan los cordones.
Dato clave
La palabra viene de al-Juarismi, un matemático persa del siglo IX.
Buscar
Para encontrar un nombre en una lista ordenada, no empieces por arriba: abre por la mitad, mira en qué mitad está y repite. Eso es la búsqueda binaria.
Dato clave
La búsqueda binaria encuentra un nombre entre un millón en unos 20 pasos.
Ordenar
Ordenar es poner las cosas en orden. Los métodos sencillos comparan elementos vecinos y los intercambian; los más rápidos dividen la lista, ordenan las partes y las vuelven a juntar.
Dato clave
Un ordenador puede ordenar un millón de elementos en una fracción de segundo.
Recomendaciones
Las aplicaciones de streaming y de compras usan algoritmos para adivinar qué te va a gustar, según lo que elegiste tú y la gente parecida a ti.
Dato clave
Las recomendaciones pueden encerrarnos en una burbuja de más de lo mismo.
Algoritmos rápidos y lentos
Dos algoritmos pueden resolver el mismo problema a velocidades muy distintas. Cuando los datos crecen, un método inteligente puede ser millones de veces más rápido que uno ingenuo.
Dato clave
Los informáticos describen la velocidad con la notación «O grande».
Encontrar la mejor ruta
Las aplicaciones de mapas encuentran la ruta más rápida con algoritmos de camino más corto, como el que inventó Edsger Dijkstra en 1956, al parecer en unos 20 minutos.
Dato clave
Dijkstra lo diseñó sin lápiz ni papel, en una cafetería.
Problemas difíciles
Algunos problemas no tienen ningún algoritmo rápido conocido. Encontrar el viaje más corto que pase por muchas ciudades, el problema del viajante, se vuelve muchísimo más difícil con cada ciudad.
Dato clave
Con 20 ciudades hay más de 60 000 billones de recorridos de ida y vuelta posibles.
Datos curiosos
El método de Euclides para hallar el máximo común divisor tiene más de 2000 años, y los ordenadores todavía lo usan.
Para adivinar un número del 1 al 1000 partiendo el rango por la mitad cada vez, nunca hacen falta más de 10 intentos.
El método de ordenación que trae Python, Timsort, mezcla dos métodos: ordenación por mezcla para tramos grandes y ordenación por inserción para los pequeños.
Netflix ofreció una vez un premio de un millón de dólares a quien mejorara sus recomendaciones un 10 %. Un equipo lo ganó en 2009.
Ordenar un millón de elementos comparando cada pareja lleva alrededor de medio billón de pasos; los métodos inteligentes necesitan unos 20 millones.
UPS planifica sus rutas de reparto para evitar, siempre que puede, los giros que cruzan el tráfico, y así ahorra combustible y tiempo.
Demostrar si problemas como este podrán resolverse algún día rápidamente tiene un premio de un millón de dólares.
Historia: El hombre que se convirtió en palabra
El hombre que se convirtió en palabra
Bagdad, hacia el año 825. El sabio Muhammad al-Juarismi escribe un libro sobre cómo calcular con los números indios, incluido el cero.
Tres siglos después se traduce al latín como «Algoritmi sobre los números indios». Algoritmi no es más que su nombre, escrito a la latina.
Los lectores lo tomaron por una palabra para el cálculo paso a paso. «Algorismo» acabó convirtiéndose en «algoritmo», así que cada receta para un ordenador lleva su nombre.
¿Verdadero o falso?
Toca tu respuesta para ver si has acertado, y por qué.
-
Pregunta 1 de 10
Un algoritmo es una secuencia de pasos definida.
Ver la respuesta
Verdadero. Tan clara que cualquiera, persona o máquina, puede seguirla.
-
Pregunta 2 de 10
La búsqueda binaria necesita que la lista esté ordenada.
Ver la respuesta
Verdadero. Si no, no sabes con qué mitad quedarte.
-
Pregunta 3 de 10
Algunos métodos de ordenación dividen la lista en partes más pequeñas.
Ver la respuesta
Verdadero. Como la ordenación por mezcla y el quicksort.
-
Pregunta 4 de 10
Los algoritmos de recomendación aprenden de elecciones pasadas.
Ver la respuesta
Verdadero. Las tuyas y las de gente parecida.
-
Pregunta 5 de 10
Dos algoritmos pueden resolver la misma tarea a velocidades muy distintas.
Ver la respuesta
Verdadero. El método importa más cuanto más crece la tarea.
-
Pregunta 6 de 10
Las aplicaciones de mapas usan algoritmos para encontrar rutas.
Ver la respuesta
Verdadero. Teniendo en cuenta la distancia, el tráfico y el tipo de carretera.
-
Pregunta 7 de 10
Algunos problemas no tienen ningún algoritmo rápido conocido.
Ver la respuesta
Verdadero. Nadie ha encontrado todavía un método rápido para ellos.
-
Pregunta 8 de 10
Todo algoritmo tiene que estar escrito en un lenguaje de programación.
Ver la respuesta
Falso. Una receta escrita con palabras normales también es un algoritmo.
-
Pregunta 9 de 10
La búsqueda binaria revisa todos los elementos uno a uno.
Ver la respuesta
Falso. Parte la lista por la mitad en cada paso.
-
Pregunta 10 de 10
Todos los métodos de ordenación son igual de rápidos.
Ver la respuesta
Falso. Algunos son muchísimo más rápidos con listas grandes.
Sigue en la app
KnowSoda aprende lo que sabes y te recuerda lo que estás a punto de olvidar. En Algoritmos te esperan 6 ideas más en los niveles Avanzado y Experto.
Fuentes
- Khan Academy — Algorithms
- Encyclopaedia Britannica — algorithm, al-Khwarizmi
- Clay Mathematics Institute — P vs NP problem
- Communications of the ACM (2001) — interview with Edsger Dijkstra
- Brin & Page (1998), the anatomy of a large-scale hypertextual web search engine
- Cloudflare — LavaRand: randomness from lava lamps
