Qué es un algoritmo

El método para hallar el máximo común divisor del Libro VII de los Elementos de Euclides, escrito hace unos 2300 años, sigue funcionando hoy en las computadoras.

Un método que siempre funciona

Supón que necesitas el mayor número que divide a la vez a 1071 y a 462. Podrías probar todos los números de 462 hacia abajo hasta 1 y parar en el primero que divida a los dos. Funciona, pero puede llevar cientos de intentos. Hay un camino más corto. Divide 1071 entre 462 y quédate con el residuo, 147. Ahora divide 462 entre 147 y quédate con el residuo, 21. Divide 147 entre 21: el residuo es 0, así que la respuesta es 21. Tres divisiones en lugar de varios cientos.

Ese camino más corto es un algoritmo: una lista finita de pasos precisos que toma una entrada y produce la salida correcta. Este es el algoritmo de Euclides para el máximo común divisor, y aparece en el Libro VII de los Elementos, escrito hacia el 300 a. C. Euclides lo describió restando longitudes una y otra vez en lugar de dividir, pero la idea es la misma, y la versión con residuos es la que usan hoy los programas.

function gcd(a, b) {
  while (b !== 0) {
    const r = a % b;   // residuo
    a = b;
    b = r;
  }
  return a;
}
console.log(gcd(1071, 462)); // 21

Qué convierte una lista de pasos en un algoritmo

Libros de texto como el de Cormen, Leiserson, Rivest y Stein describen un algoritmo como un procedimiento bien definido que convierte una entrada en una salida. En esa descripción caben tres cosas, y cada una importa cuando escribes código.

• Preciso. Cada paso significa una sola cosa. "Divide a entre b y quédate con el residuo" es preciso; "haz los números más pequeños de alguna manera" no lo es.
• Finito. Tiene que terminar. En el algoritmo de Euclides el residuo siempre es menor que el número entre el que dividiste, así que se achica en cada vuelta y tiene que llegar a 0.
• Correcto. Para toda entrada permitida, la salida es la respuesta correcta, no solo para los ejemplos que probaste.

Una receta de cocina se suele dar como ejemplo cotidiano, y es un buen ejemplo: los ingredientes son la entrada, el platillo es la salida y los pasos van en orden. La diferencia está en cuánto completa quien la lee. Un cocinero decide qué significa "una pizca". Una computadora no decide nada, y por eso los algoritmos para computadoras se escriben con cada paso explicado.

El mismo problema, distintos algoritmos

Un problema suele tener muchos algoritmos correctos, y pueden diferir muchísimo en cuánto trabajo hacen. Para el máximo común divisor de 1071 y 462, probar todos los números desde 462 hacia abajo necesita 442 intentos antes de llegar a 21, mientras que el método de Euclides necesita 3 divisiones. Los dos son correctos. Solo uno es rápido. Buena parte de este curso trata de esa segunda pregunta: una vez que un método es correcto, ¿cuántos pasos lleva, y cómo crece ese número cuando la entrada se hace más grande?

Para responderla, los informáticos cuentan pasos básicos (una comparación, un intercambio, una división) en lugar de segundos. Los segundos dependen de la máquina. Un conteo de pasos depende solo del algoritmo y de la entrada, así que permite comparar dos métodos con justicia. El laboratorio de abajo cuenta las comparaciones por ti mientras ordena una fila de barras. Prueba el mismo orden inicial con dos métodos distintos y observa los contadores.

Entradas, salidas y los pasos intermedios

Antes de escribir un algoritmo, anota exactamente qué entra y qué debe salir. Para el máximo común divisor: la entrada son dos números enteros positivos, y la salida es un número entero que divide a los dos, sin que ningún número mayor haga lo mismo. Esa descripción te dice cómo comprobar el resultado, y a menudo da pistas sobre los pasos. También deja ver los casos límite: ¿y si uno de los números es 0? (El bucle de arriba devuelve el otro número, que es la respuesta correcta). ¿Y si los dos números son iguales? Pensar en los casos límite antes de ejecutar el código atrapa muchos errores.