Historia de los algoritmos

¿QUÉ SON LOS ALGORITMOS?
Un algoritmo es un conjunto finito de instrucciones precisas que realizan una tarea,
la cual, dado un estado inicial, culminará por arrojar un estado final reconocible.
Esta definición asume que la ejecución del algoritmo concluye en algún momento,
dejando fuera los procedimientos que ejecutan permanentemente sin detenerse. Para
incluir a éstos en la definición,algunos autores prefieren obviar la condición de que
la ejecución concluya, con lo cual basta con que un procedimiento sea una secuencia
de pasos que puede ser ejecutada por una entidad para que se lo considere algoritmo.
En el caso que no haya un estado final reconocible, el éxito del algoritmo no
puede definirse como la culminación del proceso con un resultado significativo.
En cambio, serequiere una definición de éxito que contemple secuencias ilimitadas de resultados, por ejemplo, un sistema de compresión/descompresión de
datos en tiempo real (como los utilizados en el manejo de voz sobre IP); en este
caso, el algoritmo no define por sí mismo la finalización del proceso, debiendo
seguir su funcionamiento mientras haya datos para procesar. El éxito del algoritmo estará dado por elhecho de que los datos, una vez descomprimidos, sean
iguales que antes de comprimirse.
El concepto de algoritmo se ilustra frecuentemente comparándolo con una receta:
al igual que las recetas, los algoritmos habitualmente están formados por secuencias
de instrucciones que probablemente se repiten (iteran) o que requieren decisiones
(comparaciones lógicas) hasta que completan su tarea. Unalgoritmo puede no ser
correcto, con lo cual, por más que sus pasos se lleven a cabo correctamente, el estado final no será el esperado.
Normalmente, cuando un algoritmo está asociado con el procesamiento de información, se leen datos de una fuente o dispositivo de entrada, se procesan y se emiten por
un dispositivo de salida, o bien se almacenan para su uso posterior. Los datos almacenados seconsideran parte del estado interno de la entidad que ejecuta el algoritmo.
Dado que un algoritmo es una lista precisa de pasos, el orden de ejecución será casi siempre crítico para su funcionamiento. En general, se asume que las instrucciones se enumeran explícitamente, y deben ejecutarse “desde arriba hacia abajo”, lo
cual se establece más formalmente según el concepto de flujo de control.
Estaforma de “pensar” el algoritmo asume las premisas del paradigma de programación imperativa. Dicho paradigma es el más común, e intenta describir las tareas
en términos “mecánicos” y discretos. Los paradigmas de la programación funcional
y de la programación lógica describen el concepto de algoritmo en una forma ligeramente diferente (en el Capítulo 2 se detallan los distintos tipos deparadigmas).
Hasta aquí hemos dado una definición ciertamente informal del concepto de algoritmo. Para definirlo en forma matemáticamente precisa, Alan Mathison Turing
–famoso matemático inglés (1912-1954), cuyas contribuciones en el campo de la
matemática y de la teoría de la computación le han valido ser considerado uno de
los padres de la computación digital– ideó un dispositivo imaginario al quedenominó máquina de computación lógica (LCM, Logical Computing Machine), pero
que ha recibido en su honor el nombre de máquina de Turing. Lo que confiere a
este supuesto dispositivo su extraordinaria importancia es que es capaz de resolver
cualquier problema matemático, a condición de que el mismo haya sido reducido
a un algoritmo. Por este motivo, se considera que algoritmo es cualquier conjuntode operaciones que pueda ser ejecutado por la máquina de Turing (o, lo que es lo
mismo, por un sistema Turing completo, tal como se explica más adelante).
La máquina de Turing
Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de
datos. En cada instante, la máquina puede leer un único dato de la secuencia (generalmente un carácter) y realizar ciertas acciones en...