Sobre el algoritmo, su origen y definición

Vivimos desde hace años en la era de la información. Toneladas de datos se agolpan ante nuestras caras en cantidad y velocidad que no nos permiten clasificarlos, evaluarlos o simplemente mirarlos. Libros, videos, noticias, fotografías o mensajes compartidos que van aumentando día a día en volumen. Necesitamos mecanismos de filtrado, categorizado e incluso de valoración. Los programas de computación han salido al rescate.

Si se preguntan ¿por qué una página de Internet sale antes de que otra?. ¿Por qué el sistema de streamming de audio o video nos recomienda un conjunto de opciones determinadas?  La culpa la tiene el algoritmo. Pero también los algoritmos se encuentran en aplicaciones financieras, la producción industrial, predicción meteorológica, sistemas bancarios y casi todo ámbito que se nos pueda ocurrir.

Programas, algoritmos, palabras que forman parte de nuestro vocabulario diario. Misteriosas y mágicas. Qué es realmente un algoritmo? Es lo mismo que un programa? 

Primera aproximación: Definición de diccionario.

Cuando eramos chicos y no conocíamos una palabra nos mandaban a buscar en el diccionario. Entonces, podemos comenzar ahí. La palabra "programa" según la Real Academia española tiene más de 15 acepciones. Entre ellas:

 "Conjunto unitario de instrucciones que permite a una computadora realizar funciones diversas, como el tratamiento de textos, el diseño de gráficos, la resolución de problemas matemáticos, el manejo de bancos de datos, etc." - RAE

Una definición poco satisfactoria. No se debe definir con ejemplos. Además, en matemática de conjuntos, se define conjunto unitario a aquel formado por un único elemento. Por lo tanto, el programa esta compuesto por una única instrucción ( o la repetición de esa única instrucción). Tenemos acá entonces una definición tipo caja negra. El programa es una instrucción de computadora que hace algo. Pero no sabemos nada sobre él.

Tenemos además dos definiciones más que nos pueden salvar la anterior:

"Serie ordenada de operaciones necesarias para llevar a cabo un proyecto." - RAE

Podemos entonces inferir que un programa está conformado por operaciones con un objetivo.
Veamos la siguiente definición:

Cada una de las operaciones que, en un orden determinado, ejecutan ciertas máquinas. - RAE

Acá nuevamente entra el concepto de máquina o computadora (que es una máquina también). Nuevamente habla de un concepto unitario (volvemos a la caja negra). Pero entramos a un embrollo: Se define a un programa como una operación. Si tomamos la primera definición, instrucción y operación son sinónimos. En la segunda definición se habla de una serie ordenada de operaciones. Por lo que no tenemos definiciones compatibles entre si.

No sacamos mucho en claro yendo al diccionario. Veamos si tenemos más suerte con el concepto de algoritmo:

Conjunto ordenado y finito de operaciones que permite hallar la solución de un problema. -RAE

Método y notación en las distintas formas del cálculo. - RAE

La definición en este caso es más formal (y más decente). Habla de un conjunto de operaciones que se ejecutan en un orden y que son acotadas. Además indica que tienen un objetivo determinado. También lo suscribe a un método de cálculo, es decir al área de la aritmética. Se puede ver que tiene un parecido a la segunda definición de programa. Aun así, quedamos con poca sustancia.

Para tener mejores definiciones, tendremos que buscar en otras fuentes.

Buscando el significado en el tiempo: Números polvorientos

El origen de la palabra misma "algoritmo" es bastante pintoresco. Se la suele identificar rápidamente con la raíz griega "arithmos" que significa "números" (de ahí aritmética). Pero, esto es un error común, de hecho, uno bastante antiguo (y que ha dejado huellas).

La real academia española mediante una aclaración de la palabra algoritmo dice:

Quizá del lat. tardío *algobarismus, y este abrev. del ár. clás. ḥisābu lḡubār 'cálculo mediante cifras arábigas'.

Es decir, considera que es una traducción de una traducción (pasando del árabe clásico al latín tardío y luego a nuestra lengua). Nuevamente esto, no es del todo correcto. Pero, nos pone en contacto con el idioma que dio origen al nombre.
Ciertamente hisab (حساب), significa en árabe cálculo o cuenta. Por otro lado, como nos cuenta Oystein Ore en su libro "Number theory and its history", (Mc Graw Hill 1948), se conoció como "numeración gobar" a una manera decimal basada en el sistema hindú que apareció en España. Su más antigua representacion conservada data del año 976 d.e.c. El nombre gobar proviene del árabe ghabar (غبار) que significa polvo. Esto se debe a la costumbre hindú de realizar los cálculos en el suelo o en una tabla polvorienta. Se podría inferir - entonces - que según esta teoría, el nombre provendría del calculo usando el sistema de numeración antes descripto.

Si bien es una respuesta plausible, existen otras explicaciones, un poco más elegantes,.

Tenemos que retroceder un siglo más atrás, IX d.e.c. En esos años el Islam se había convertido en un una potencia que conquistó grandes áreas del antiguo imperio romano. Dentro de sus fronteras quedaron las obras de los sabios griegos y romanos. Comienza una tarea de traducción, resignificación y nuevos aportes de origen persas, hindues y chinas. Los sabios árabes cobran renombre. Al mismo tiempo en las tierras cristianas se producía una retracción cultural y científica en lo que se dio a conocer como "oscurantismo". En ese contexto se crean academias promovidas por diferentes califas. En una de ellas llamada Bayt al-Hikmah (بيت الحكمة) ("la Casa de la sabiduría") - ubicada en Bagdad - fue contratado por el califa al-Ma'mūn un matemático llamado Mohamed ben Musa.

El matemático de Khwārizm

Página del libro Conciso sobre el
Cálculo por Completación y Balance

Khwārizm está situada en el curso inferior del rio Amū Daryā. Actualmente es parte del territorio de república de Uzbekistán, en la provincia de Jiva. Desde allí partió Mohamed ben Musa. En honor a su origen, paso a autodenominarse como Mohamed ben Musa al-Khwārizmī. Es decir "el de Khwārizm".

La obra de al-Khwārizmī fue muy influyente. Para ejemplificar, basta decir que la palabra "Álgebra" - rama de la matemática que estudia la combinación de elementos de estructuras abstractas acorde a ciertas reglas - debe su existencia a este matemático. Kitāb al-mukhtasar fī hisāb al-ğabr wa-l-muqābalah (كتاب المختصر في حساب الجبر والمقابلة)  es el nombre original de su obra cuya traducción es "Libro Conciso sobre el Cálculo por Completación y Balance".

Mohamed ben Musa vivió entre el 780 y el 840 aproximadamente. Dentro de la academia tuvo acceso y tradujo obras del griego y el latín. Pero, su aporte fundamental fueron sus propios escritos. En ellos explicaba como resolver tipos de problemas matemáticos en forma genérica (y no en casos particulares como era la norma). Además proponía la utilización del sistema de numeración hindú. El mismo era un sistema posicional decimal (y el sistema que utilizamos hoy en día). La norma era utilizar los números romanos, cuyas operaciones matemáticas eran mas complejas de realizar.

Mohamed ben Musa

Su libro Kitāb al-ğam' wa-l-tafrīq bi-hisāb al-hind (كتاب الجمع والتفريق بحساب الهند) (Libro de la suma y la división según el cálculo de los hindúes) detalla las ventajas del sistema de calculo con números hindúes. Tiene un profundo impacto. Es traducido al latín en el siglo XII por Adelardo de Bath, entre otros autores. En varias de las traducciones no le dieron título a la obra. Sin embargo, comenzaban con la frase "Dixit algorizmi" ("como dijo algorizmi" ). La traducción más conocida fue titulada "Algoritmi de numero Indorum" ("Algoritmi sobre los números de los hindúes") en 1857 por Baldassarre Boncompagni.

Es en manos de sus traductores que la latinización del gentilicio del autor, pasa a convertirse en la expresión del sistema numérico y los métodos para resolver los problemas algebraicos. Un ejemplo temprano de esto se puede ver en la obra titulada "Carmen de Algorismo" (Poema de algorismo) de 1240 compuesto por Alexandre de Villedieu que comienza de la siguiente forma:

Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.
(La presente técnica llamada Algorismus, en la que se utiliza dos veces cinco las figuras hindúes)

Y luego resumía varios métodos de operatoria algebraica como:

Extrahe radicem semper sub parte sinistra
(Extraiga siempre la raíz cuadrada comenzando por la izquierda)

La influencia de Mohamed ben Musa fue tan grande que incluso en español su nombre se transformó en sinónimo de número: guarismo (deformación de al-Khwārizmī).

Generalización del concepto

El término algoritmo, que manejamos hoy día para cualquier procedimiento (no solamente matematico), tuvo más caminos por recorrer. En el siglo XVII en Francia sufre un cambio en su forma de escribirse al moderno "algorithm". Seguramente y equivocadamente al relacionarlo al griego "arithmos" (números). De allí es tomado por el idioma Ingles, y luego regresará al español.

Es en el siglo XVIII-XIX que toma su utilización actual y más general. El "algoritmo" no solo se aplica en procedimientos matemáticos (por ejemplo en medicina se entiendo como algoritmo a un "diagrama orientador que sirve para tomar decisiones diagnósticas o terapéuticas."). Se puede definir por lo tanto como toda clase de procedimientos utilizados con el propósito de resolver problemas o realizar determinadas tareas.

Con la aparición de las primeras computadoras programables en el siglo XX y su posterior masificación, el concepto de algoritmo pasa a quedar relacionado fuertemente con las computadoras. Pero, como se nombra anteriormente, la vida del concepto algoritmo es mucho más extensa que el de los programas de computación.

Augusta Ada King,
Condesa de Lovelace

Se considera que el primer programa de computación - y por lo tanto - el primer "programador" fue Ada Lovelace en 1843. Augusta Ada King, Condesa de Lovelace (tal su nombre completo), hija del poeta Lord Byron, fue una mujer apasionada por las matemáticas en una época donde por su condición de tal las ciencias le eran vedadas. Ada conoció a Charles Babbage quien crearía teóricamente su máquina analítica en 1837 para resolver problemas generales.

Ada fascinada por este invento realiza la traducción de un informe de Luigi Federico Menabrea, que es publicado en la revista Scientific Memoirs con el nombre de "Sketch of the analytical engine invented by Charles Babbage". Dentro de esta publicación agrega extensas notas, entre ellas un algoritmo escrito en el lenguaje de la máquina analítica que generaba los números de Bernoulli.

Por diferentes problemas esta máquina nunca fue construida. Recién 100 años después "computadoras" de prestaciones similares comenzarían a construirse. Con esto, tenemos ayuda para definir con más precisión el termino programa de computadora. Son algoritmos escritos para que puedan ejecutarse mediante instrucciones de una determinada computadora. Nos queda definir, por lo tanto, formalmente "algoritmo"

La definición de Knuth.

Donald Knuth

La definición moderna de algoritmo (atada a la informática) más extendida es la dada por Donald Knuth en su libro "Art of Computer Programming, Volume 1: Fundamental Algorithms". Un algoritmo es un conjunto finito de reglas que proporciona una secuencia de operaciones para resolver un tipo específico de problema y que cumple con las siguientes características:

1. Finitud: Un algoritmo debe siempre terminar luego de un número finito de pasos.
2. Cada paso de un algoritmo debe definirse con precisión; Las acciones a realizar deben ser especificadas de forma rigurosa e inequívoca para cada caso. 
3. Un algoritmo tiene cero o más entradas: Valores que se le otorga inicialmente antes de la ejecución del mismo.
4. Un algoritmo tiene una o más salidas: Valores que tienen una relación específica con las entradas y calculadas siguiendo las reglas.
5. Eficacia: Sus operaciones deben ser todas lo suficientemente básicas para que, en principio, puedan ser realizadas de manera precisa y en un tiempo finito por alguien que use lápiz y papel.

Cabe mencionar que está definición no es formal. Los conceptos de "suficientemente básicas" y "definirse con precisión" no son rigurosos. Además, varios autores ponen en duda el concepto de finitud, indicando la existencia de programas que no se conoce si finalizarán. No obstante es la definición más fácil de comprender y más abarcativa.

Palabras especiales merece el requerimiento que pueda resolverse por alguien utilizando un papel y lápiz. Esto implica que cualquier algoritmo - y en consecuencia programa de computadora - puede ser realizado por una persona (seguramente en un tiempo mayor). Lo cual no implica lo contrario (que cualquier proceso realizado por una persona la pueda realizar una computadora. Diferencia de vital importacia dentro del campo de la inteligencia artificial. Donde esta diferencia es objecto de controversia y debate.

No fue Knuth quien propone el ejercicio del lápiz y papel. Sino Alan Turing, uno de los padres de la informática e inteligencia artificial. Pero eso ya merece un artículo aparte.