La palabra Algoritmo procede del vocablo "algoritm", que, a su vez, es la traducción latina del nombre árabe de Al-Khwarizmi , matemático árabe del siglo IX (Abu Ja'far Muhammad ibn Musa Al-Khwarizmi nació en Bagdad en 780 y murió en 850). En realidad, se denominaba algoritmo en la Europa Medieval al sistema posicional de cálculo, pues era conocido a través de la traducción desde el latin, de la obra de Al-Khwarizmi.

Algoritmo:

La noción de algoritmo es una de las centrales en la actual matemática, principalmente, de la matemática computacional.

Digamos que podemos entender como algoritmo el orden exacto que prefija el proceso de cálculo que comienza con un dato inicial arbitrario (comprendido entre un conjunto posible de datos iniciales) y está destinado a obtener un resultado totalmente determinado por dicho dato inicial. El cálculo o proceso desarrollado se denomina Cálculo Algorítmico o bien Proceso Algorítmico, el cuál va, hoy dia, indisolublemente unido a la programación de ordenadores, pues el proceso mecánico que conlleva la realización del algoritmo, la no necesidad de ideas creativas para su puesta en práctica, nos permite dejarlo en "las manos" de una máquina.

Durante un proceso algorítmico no tiene que suponerse necesariamente que el resultado se obtiene siempre al final del proceso y a partir de un dato inicial concreto, sino que puede terminarse sin resultado alguno (en este caso se diría que el algoritmo ha tenido una parada sin resultado).

Un algoritmo se dice aplicable si tal algoritmo acaba, con o sin resultado, y se dice que se trata de un algoritmo no aplicable si el proceso algorítmico no se acaba.

Entre las reglas o algorítmos clásicos más comunes podemos citar el algoritmo de la división de números reales, el de la obtención de la raiz cuadrada de un número real, el de la Regla de Ruffini para división polinómica por binomios de primer grado, la Regla de Cramer para resolución de Sistemas de ecuaciones lineales, el método de reducción de Gauss para el mismo fin, etc., todos ellos conocidos en nuestra edad escolar.

Hoy se pueden crear algoritmos de complejidad creciente debido a la enorme capacidad de los ordenadores actuales para el proceso de los datos, y podemos usar objetos constructivos iniciales de, prácticamente, cualquier tipo, desde números, palabras, señales telefónicas, estructuras vectoriales o matriciales, etc., con procesos que pueden tener o no carácter lineal, pudiendo en definitiva diseñarse algorítmos de cualquier tipo, desde algorítmos de cálculo, traducción de lenguajes, de control de procesos electromecánicos, etc.

Es corriente en la actualidad la generación algoritmica de imágenes fractales mediante ordenador como instrumento utilisimo en el estudio de la Teoría del Caos, y, así, pueden encontrarse en internet programas de uso libre-freeware- como son, por citar algún ejemplo, el Fractint, creado por Stone Soap Group, en http://www.fractint.org, o Ultra Fractal, de F. Slijkerman, en http://www.ultrafractal.com, también podemos mencionar a Fractal Orbis, de P. Packard, que puede encontrarse en http://spanky.triumf.ca/www/welcome1.html.

Es necesario también citar el papel del algoritmo en la composición musical. En esta tarea, ya se comenzó en 1955 a utilizar la computación para crear estructuras musicales, con los trabajos del químico y compositor Lejaren Hiller, en la Universidad de Illinois (EEUU), que publicó en 1957 la llamada "Suite Illiac", en honor de aquel arcaico ordenador que utilizó para su construcción. Esta obra fué realmente la primera en la historia creada totalmente mediante computación algorítmica, utlizando Hiller para el diseño de los correspondientes algoritmos el proceso matemático de las Cadenas de Markov.

Estructuración:

El proceso es realmente el de la transformación sucesiva de los objetos constructivos iniciales, que transcurre por pasos discretos, y cada paso consiste en la sucesión de objetos constructivos, sustituyendose los objetos constructivos anteriores por nuevos objetos constructivos, determinándose cada objeto constructivo nuevo por el objeto constructivo precedente.

Estrictamente, es necesario suponer que el paso directo de cada objeto constructivo al siguiente es lo suficientemente elemental para que tenga solamente el carácter de una transformación local, esto es, que no afecte a todo el objeto constructivo, sino solamente a una parte del mismo, que estaría delimitada de antemano por un algoritmo dado, determinándose la propia transformación solo por esa parte limitada del objeto constructivo.

Esto quiere decir que además de los datos iniciales y de los posibles resultados, cada algorítmo contiene un bloque de posibles resultados intermedios que se constituye en el medio de trabajo en donde se desarrolla todo el proceso algorítmico.

En general podemos establecer siete parámetros clave en la estructura del proceso algorítmico:

p₁. Conjunto de los posibles datos iniciales.
p₂. Conjunto de los resultados posibles.
p₃. Conjunto de los posibles resultados intermedios.
p₄. Regla de inicio del proceso algorítmico.
p₅. Regla del proceso directo.
p₆. Regla de finalización del proceso.
p₇. Regla de obtención del resultado

Especificaciones:

En realidad, la noción de algoritmo es una de las nociones fundamentales de la matemática que no admiten definición en términos más sencillos. Esto es, el intento de específicar eventualmente la noción de algoritmo conduce a limitaciones de la propia noción.

Se podría establecer una elección definiendo el ámbito de variación de cada uno de los parámetros algorítmicos. Así, podríamos establecer C₁ como el conjunto de posibles valores del parámetro p₁, C₂ como el conjunto de los valores posibles de p₂, ....

Una elección de este tipo definiría una clase de algoritmos, que sería obviamente la clase de todos los algorítmos cuyos parámetros se mantienen en los ámbitos establecidos, C₁, C₂, ..., C₇.

Cuando para una elección dada C, de ambitos de validez de los parámetros C₁, C₂, ... C₇ puede siempre encontrarse en la clase correspondiente de algoritmos, un algoritmo equivalente de un algoritmo dado cualquiera de dicha clase, es decir, puede encontrarse otro algoritmo con el mismo posible conjunto de datos iniciales y el mismo conjunto de resultados posibles, es cuando decimos que tal elección es una especificación. Esta es la hipótesis fundamental que permite especificar clases de algoritmos.

Alan M.Turing

Las primeras especificaciones se propusieron en 1936 por E. L. Post y por A. M. Turing, estableciendo las construcciones básicas que fueron el orígen de las ideas en las que se apoya el uso de las computadoras digitales de la actualidad. Turing publicó en abril de 1936 el artículo "On computable numbers, with an application to the Entscheidungsproblem" en el que introduce por primera vez el concepto de algoritmo que hoy manejamos, probando que existen problemas sin solución algorítmica y que resultó ser uno de los cimientos más importantes de la teoría de la computación. También fueron de gran importancia las especificaciones planteadas por A. A. Markov y A. N. Kolmogorov. En concreto, Kolmogorov propuso la interpretación de los objetos constructivos como complejos topológicos de determinada forma, a fin de precisar el carácter "local" de las transformaciones.

La Teoría de Algoritmos:

La Teoría de Algoritmos es la parte de la Matemática en la que se desarrolla el estudio de las propiedades de los algoritmos.

En realidad, los fenómenos que dan origen al concepto de algoritmo se han observado y estudiado a lo largo de la historia, aún cuando tal concepto se comenzó a usar en el siglo XX y ya se bosquejaba en las obras de algunos representantes del intuicionismo, como L.E.J. Brouwer y H. Weyl.

El concepto de función calculable fué precisado por primera vez en 1936, por A. Church, dando también el primer ejemplo de función no calculable, e identificando el concepto de función con la recursión general.

Sin embargo, fué cuando E. L. Post y Alan M. Turing especificaron el concepto de algorimo cuando dió comienzo del desarrollo sistemático de la teoría, por obra de algunos autores como S. C. Kleene y el mismo A. A. Markov, que al utilizar la idea de algoritmo normal estableción un enfoque generalizado que ha permitido precisar claramente la noción de algoritmo.

Los algoritmos se refieren siempre a objetos constructivos que a su vez dan origen a otros objetos constructivos a lo largo del proceso algorítmico. Cuando aplicamos la Teoria de Algoritmos a objetos no constructivos se hace necesario nombrar o numerar a éstos como objetos constructivos, por lo que la Teoría de la Numeración se convierte en un interesante apartado de la Teoría de Algoritmos.


BIBLIOGRAFÍA:

A. Aho; J. Hopcroft; J. Ullman. Estructuras de datos y algoritmos. Editorial Addison_Wesley Americana, 1988.
G. Brassard; P. Bratley. Fundamentos de Algoritmia. Prentice Hall, 1997.
X. Franch Gutiérrez. Estructuras de datos. Especificación, diseño e implementación. Edicions UPC, 1993.
R. Guerequeta; A. Vallecillo. Técnicas de Diseño de Algoritmos. Servicio de Publicaciones de la Universidad de Málaga, 1997.

Carlos S. CHINEA
casanchi@teleline.es
29 enero 2005