Algoritmo
Los diagramas de
flujo sirven para representar algoritmos de
manera gráfica.
En matemáticas, ciencias
de la computación y disciplinas relacionadas,
un algoritmo (del griego y latín, dixit algorithmus y
este a su vez del matemático persa Al-Juarismi ) es un conjunto preescrito de instrucciones o reglas
bien definidas, ordenadas y finitas que permite realizar una actividad mediante
pasos sucesivos que no generen dudas a quien deba realizar dicha
actividad. Dados un estado inicial y una entrada, siguiendo los pasos
sucesivos se llega a un estado final y se obtiene una solución. Los algoritmos
son el objeto de estudio de la algoritmia.
En la vida cotidiana, se
emplean algoritmos frecuentemente para resolver problemas. Algunos ejemplos son
los manuales de usuario, que muestran algoritmos para usar un aparato, o las
instrucciones que recibe un trabajador por parte de su patrón.
Algunos ejemplos en matemática son
el algoritmo de la división para
calcular el cociente de dos números, el algoritmo de Euclides para obtener el máximo común divisor de dos enteros positivos,
o elmétodo de Gauss para resolver
un sistema lineal de ecuaciones.
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 problema abstracto, es decir, que un número finito de pasos convierten los
datos de un problema (entrada) en una solución (salida). 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.
A lo largo de la
historia varios autores han tratado de definir formalmente a los algoritmos
utilizando modelos matemáticos como máquinas de Turing entre
otros.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. 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:
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. 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):
Aritmetizabilidad. Solamente operaciones innegablemente calculables están disponibles en el
paso inicial.
Los algoritmos pueden
ser expresados de muchas maneras, incluyendo al lenguaje natural, pseudocódigo, diagramas
de flujo y lenguajes de programación entre otros. Las descripciones en lenguaje natural
tienden a ser ambiguas y extensas. El usar pseudocódigo y diagramas de flujo
evita muchas ambigüedades del lenguaje natural. Dichas expresiones son formas
más estructuradas para representar algoritmos; no obstante, se mantienen
independientes de un lenguaje de programación específico.
La descripción de un
algoritmo usualmente se hace en tres niveles:
Descripción de alto nivel. Se establece el problema, se selecciona
un modelo matemático y se explica el algoritmo de manera verbal, posiblemente
con ilustraciones y omitiendo detalles.
Descripción formal. Se usa pseudocódigo para describir la secuencia de
pasos que encuentran la solución.
Implementación. Se muestra el algoritmo expresado en un lenguaje de programación
específico o algún objeto capaz de llevar a cabo instrucciones.
También es posible
incluir un teorema que demuestre que el algoritmo es correcto, un
análisis de complejidad o ambos.
Diagrama de flujo
