Definición
En general, no existe ningún consenso definitivo en cuanto a la definición formal de algoritmo. Muchos autores los señalan como listas de instrucciones para resolver un
cálculo o un
problema abstracto, es decir, que un número finito de pasos convierten los datos de un problema (entrada) en una solución (salida).
[1]
[2]
[3]
[4]
[5]
[6] Sin embargo cabe notar que algunos algoritmos no necesariamente tienen que terminar o resolver un problema en particular. Por ejemplo, una versión modificada de la
criba de Eratóstenes que nunca termine de calcular números primos no deja de ser un algoritmo.
[7]
A lo largo de la historia varios autores han tratado de definir formalmente a los algoritmos utilizando modelos matemáticos. Esto fue realizado por
Alonzo Church en 1936 con el concepto de "calculabilidad efectiva" basada en su
cálculo lambda y por
Alan Turing basándose en la
máquina de Turing. Los dos enfoques son equivalentes, en el sentido en que se pueden resolver exactamente los mismos problemas con ambos enfoques.
[8]
[9] Sin embargo, estos modelos están sujetos a un tipo particular de datos como son números, símbolos o
gráficas mientras que, en general, los algoritmos funcionan sobre una vasta cantidad de
estructuras de datos.
[3]
[1] En general, la parte común en todas las definiciones se puede resumir en las siguientes tres propiedades siempre y cuando no consideremos
algoritmos paralelos:
[7]
- Tiempo secuencial. Un algoritmo funciona en tiempo discretizado –paso a paso–, definiendo así una secuencia de estados computacionales por cada entrada válida (la entrada son los datos que se le suministran al algoritmo antes de comenzar).
- Estado abstracto. Cada estado computacional puede ser descrito formalmente utilizando una estructura de primer orden y cada algoritmo es independiente de su implementación (los algoritmos son objetos abstractos) de manera que en un algoritmo las estructuras de primer orden son invariantes bajo isomorfismo.
- Exploración acotada. La transición de un estado al siguiente queda completamente determinada por una descripción fija y finita; es decir, entre cada estado y el siguiente solamente se puede tomar en cuenta una cantidad fija y limitada de términos del estado actual.
En resumen, un algoritmo es cualquier cosa que funcione paso a paso, donde cada paso se pueda describir sin ambigüedad y sin hacer referencia a una computadora en particular, y además tiene un límite fijo en cuanto a la cantidad de datos que se pueden leer/escribir en un solo paso. Esta amplia definición abarca tanto a algoritmos prácticos como aquellos que solo funcionan en teoría, por ejemplo el
método de Newton y la
eliminación de Gauss-Jordan funcionan, al menos en principio, con números de precisión infinita; sin embargo no es posible programar la precisión infinita en una computadora, y no por ello dejan de ser algoritmos.
[10] En particular es posible considerar una cuarta propiedad que puede ser usada para validar la
tesis de Church-Turing de que toda función calculable se puede programar en una máquina de Turing (o equivalentemente, en un lenguaje de programación suficientemente general):
[10]
CARACTERISTICAS DE LOS ALGORITMOS
Un algoritmo, además de ser una secuencia de acciones lógicas que hay que realizar para completar un procesotambien requieren cumplir con las 5 condiociones siguiente:
1.- Finitud. Un algoritmo debe terminar en un número finito de pasos-
2.- Definitividad. Cada paso del algoritmo debe definirse de modo preciso; las acciones a realizar deben de estar especificadas rigurosamente y sin ambiguuedad para cada caso.
3.- Entrada. Un algoritmo tiene cero o mas entradas. Esto es las cantidades de datos de inicio se generan en el mismo algoritmo o se conocen previamente.
4.- Salida. Un algoritmo tiene una o más salidas. Es decir, hay datos o cantidades al término del algoritmo que tiene una relación especifica con los datos o conatidades de entrada.
5.- Efectividad. El algoritmo debe de ser efectivo. Esto significa que todad las operaciones deben ser suficientemente sencillas para poder en principio ser realizadas de modo exacto y en un tiempo finito por un procesador.
