Se ha dicho que vivimos en “la civilización de los algoritmos”; estos se han convertido en el “carbono” de la sociedad moderna. Los que trabajamos con datos los utilizamos constantemente: cada uno de nosotros tiene una “biblioteca” particular de ellos y según el problema al que se enfrenta usa uno u otro. Otras veces probamos varios y nos quedamos con el que mejor funciona.
Los algoritmos resuelven problemas muy habituales en las compañías como medir la propensión de compra de productos, proponer recomendaciones de contenidos, anticipar el volumen de ventas futuro o segmentar a los clientes para diseñar productos diferenciados.
Pero no hace falta ser científico de datos para consumir algoritmos. Cuando buscamos algo en Internet, compramos un billete de avión, traducimos un texto o utilizamos el navegador del coche estamos aprovechándonos de la labor de muchos de ellos: los algoritmos nos hacen la vida más fácil.
Con la irrupción de big data ha llegado también la computación de datos en paralelo. Ahora es factible procesar grandes cantidades de datos y esto ha puesto de moda nuevas técnicas. Un ejemplo es el deep learning, que engloba un conjunto de algoritmos conocidos como redes neuronales, que imitan la forma de pensar del ser humano y que han demostrado ser prácticamente imbatibles en problemas de reconocimiento de imágenes.
Un algoritmo es una rutina: una lista de instrucciones del tipo “haga primero esto y luego esto otro”. A los ordenadores se les da muy bien seguir instrucciones sin salirse de un camino marcado, por eso se llevan bien con los algoritmos.
Para entender mejor qué son los algoritmos y algunos conceptos alrededor de ellos, vamos a analizar uno de los más famosos de la historia: el algoritmo de Euclides para calcular el máximo común divisor (mcd) de dos números enteros, es decir, el mayor número por el que ambos son divisibles. Por ejemplo, el máximo común divisor de 84 y 18 es 6.
El máximo común divisor se enseña a calcular mediante la descomposición en factores primos. Por ejemplo, los factores primos de 84 son 22, 3 y 7 y los factores primos de 18 son 2 y 32. Ahora es cuando aplicamos lo de escoger los factores comunes elevados al menor exponente. Ambas descomposiciones tienen 2 y 3 como factor común y esos son los menores exponentes (por ejemplo, 22 es solo factor de 84). Así pues, el máximo común divisor de 84 y 18 es el producto de estos números, es decir mcd (84, 18)=2×3=6.
Cuando los números son muy grandes, factorizarlos en números primos puede resultar prácticamente imposible. Hoy en día no existe de hecho ningún algoritmo eficiente que lo haga, pero hay una manera muy eficiente y hermosa de calcular el mcd de dos números sin necesidad de factorizarlos: la descubrió Euclides 300 años antes de Cristo. Euclides publicó su algoritmo en el libro 7 de sus Elementos, una de las obras más importantes de la historia de la ciencia, que sirvió de fuente de inspiración para los mayores genios de las matemáticas así como para enseñar esta disciplina durante 2.000 años.
Dados dos números enteros m y n (con m ? n), ésta es la rutina del algoritmo:
- Calcula el resto de dividir m por n y llámalo r
- Siempre que r sea distinto de 0, haz lo siguiente:
- Asigna a m el valor de n
- Asigna a n el valor de r
- Calcula el resto de dividir m por n y llámalo r
- El resultado es n
Vamos a aplicar estas instrucciones a nuestro ejemplo, en el que m=84 y n=18
- Cuando dividimos 84 entre 18, nos queda un resto de 12 (porque 84=18×4+12); entonces r=12
- Como r=12 es distinto de 0
- hacemos m=18, n=12 y calculamos el nuevo resto r=6 (puesto que 18=12×1+6)
- Como r=6 es distinto de 0
- hacemos m=12, n=6 y calculamos el nuevo resto r=0 (puesto que 12=6×2+0)
- Como r=0 ya salimos del paso 2 y entonces mcd (84,18)=6 (el último valor de r calculado)
Euclides evita, así, la factorización y convierte el cálculo del máximo común divisor en una sucesión de restas y divisiones.
Hay un concepto importantísimo en cualquier algoritmo, que es el criterio de parada. Como su nombre indica, es la regla que detiene el algoritmo. En este caso, es el momento en que el resto que se calcula entre m y n es 0. No siempre hay un criterio exacto de parada como éste y otras veces los algoritmos paran cuando han estado un tiempo suficiente trabajando. En esos casos las soluciones que devuelven no son óptimas, pero probablemente sean una muy buena aproximación, y eso vale en muchas ocasiones. Esos algoritmos se llaman heurísticos y son la única opción cuando el problema es computacionalmente complejo, como el estudiadísimo Problema del Viajante.
Así pues, otro concepto importante en todo algoritmo es la complejidad, que es una medida de cuánto le cuesta llegar a la solución óptima. Intuitivamente, en el caso del algoritmo de Euclides, la complejidad se puede medir como el número de divisiones necesarias para llegar a la solución óptima. En nuestro caso, calcular el mcd de 84 y 18 nos ha costado tres divisiones. Ése es el número de divisiones necesario para calcular el mcd de todas las posibles parejas de números del 1 al 10:
La pareja más difícil es 5 y 8, cuyo mcd cuesta calcular cuatro divisiones. Éste es el gráfico de todas las parejas del 1 al 200 (un azul más oscuro significa mayor número necesario de divisiones):
Los patrones que aparecen en el gráfico son interesantes. Algunos son fáciles de entender, como la diagonal de color claro, ya que sólo hace falta una división para calcular el mcd de dos números iguales, pero otras líneas son mucho más sorprendentes. Se ha demostrado que las parejas que necesitan más divisiones son números consecutivos de la sucesión de Fibonacci (5 y 8 son una de estas parejas).
La complejidad de un algoritmo se mide en términos de los ingredientes con los que trabaja. En el ejemplo de Euclides los ingredientes son los dos números de entrada y se ha calculado que el número de divisiones no supera cinco veces el número de dígitos del mayor de ellos. Para entender si esto es alto o bajo, imaginad que sois un profesor y le habéis prestado el bolígrafo a alguno de vuestros 30 alumnos pero no recordáis a cuál:
- Si para descubrirlo preguntáis a cada alumno si lo tiene él o cada uno de sus 29 compañeros, en el peor de los casos serían 302 preguntas. En este caso, para una clase de N alumnos, la complejidad de orden N2 o cuadrática en el argot matemático.
- Si para descubrirlo preguntáis a cada alumno si lo tiene exclusivamente él, en el caso peor serían 30 preguntas y la complejidad sería de orden N, o lineal.
- Si para descubrirlo dividís la clase en dos grupos iguales (o que se diferencien por un alumno cuando el total sea impar), preguntáis qué grupo lo tiene, y repetís el proceso con éste (descartando siempre el que no) hasta que queda un alumno, en el peor caso haríais cinco preguntas. La complejidad sería de orden log (N) o logarítmica.
- Si preguntáis en alto quién tiene el bolígrafo, sólo necesitareis una pregunta y la complejidad sería entonces de orden 1 o constante.
El algoritmo de Euclides es del tercer tipo, logarítmico, una clase de algoritmos muy eficiente. Por eso después de más de 2.300 años sigue utilizándose. Es antiguo, eficiente y elegante.
Para que un ordenador ejecute un algoritmo hay que programarlo en algún lenguaje. Éste es el código que calcula el máximo común divisor de dos números según el algoritmo de Euclides en R, uno de los lenguajes de programación más importantes para un científico de datos:
mcd = function(x,y)
{
a=max(x,y)
b=min(x,y)
r=a%%b
while(r > 0) {
a=b
b=r
r=a%%b
}
return(b)
}
Imagen: Laineys Repertoire
Gráficos: Antonio Sánchez Chinchón
