Algoritmos

Un algoritmo es una secuencia finita y bien definida de pasos o instrucciones que resuelve un problema o realiza un cálculo. No es un programa ni una máquina: es el procedimiento abstracto que puede ejecutar tanto una persona con lápiz y papel como un ordenador. La receta para hacer pan o el método que aprendemos en la escuela para dividir dos números son, en este sentido, algoritmos.

El término procede de al-Juarismi (Muhammad ibn Musa al-Juarismi), matemático persa del siglo IX que trabajó en la Casa de la Sabiduría de Bagdad; la latinización medieval de su nombre, «Algoritmi», acabó designando los métodos de cálculo. La idea, sin embargo, es más antigua: el algoritmo de Euclides para el máximo común divisor tiene más de dos milenios. Fuente primaria.

Propiedades de un algoritmo

Donald Knuth, en «The Art of Computer Programming», fija cinco propiedades que todo algoritmo debe cumplir. Finitud: termina siempre tras un número finito de pasos. Definición precisa (definiteness): cada paso está especificado de forma rigurosa y sin ambigüedad. Entrada: recibe cero o más datos iniciales tomados de un conjunto definido. Salida: produce uno o más resultados con una relación precisa con la entrada. Efectividad: sus operaciones son lo bastante básicas como para ejecutarse exactamente y en tiempo finito. Un procedimiento que no termina, o cuyos pasos son ambiguos, no es un algoritmo.

Ejemplos clásicos

Los algoritmos de ordenación, como quicksort y mergesort, reorganizan una lista de menor a mayor. La búsqueda binaria localiza un elemento en una lista ordenada partiéndola por la mitad en cada paso. El algoritmo de Euclides, ejemplo predilecto de Knuth, calcula el máximo común divisor de dos números mediante restas o divisiones sucesivas. Todos comparten la misma anatomía: entrada definida, pasos precisos, salida y final garantizado. Fuente primaria.

Complejidad

Un mismo problema admite varios algoritmos, y no todos cuestan lo mismo. La complejidad mide los recursos que consume un algoritmo a medida que crece el tamaño de la entrada: el tiempo (número de operaciones) y el espacio (memoria). Se expresa con la notación O grande (Big O), una cota superior de ese crecimiento. La búsqueda binaria es O(log n), muy eficiente; ordenar con quicksort o mergesort ronda O(n log n). Esta medida permite comparar algoritmos con independencia del ordenador concreto que los ejecute. Fuente primaria.

Algoritmos e IA

Los algoritmos de aprendizaje automático —el descenso de gradiente, la retropropagación, k-medias— son un tipo de algoritmo, no algo distinto. Conviene, eso sí, distinguir el algoritmo (el procedimiento de entrenamiento) del modelo que produce (el conjunto concreto de parámetros ajustados a unos datos). El descenso de gradiente ajusta los pesos para minimizar el error; la retropropagación calcula cómo hacerlo en una red neuronal; k-medias agrupa datos sin etiquetar. La IA moderna es, en el fondo, un catálogo de algoritmos aplicados a datos.