Algoritmo informático
En
matemáticas, lógica, ciencias de la computación y disciplinas relacionadas, un
algoritmo (del griego y latín, dixit algorithmus y éste a su vez del matemático
persa Al-Juarismi) es un conjunto prescrito de instrucciones o reglas bien
definidas, ordenadas y finitas que permite llevar a cabo una actividad mediante
pasos sucesivos que no generen dudas a quien deba hacer 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 multiplicación, para
calcular el producto, 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 el método de Gauss para resolver un sistema de
ecuaciones lineales.
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).
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. 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. 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.
Aritmetizabilidad: Solamente operaciones innegablemente calculables están
disponibles en el paso inicial.
No hay comentarios:
Publicar un comentario