Algoritmo
131 idiomas
Artículo
Discusión
Leer
Editar
Ver historial
Herramientas
Apariencia
ocultar
Texto
Pequeño
Estándar
Grande
Anchura
Estándar
Ancho
No debe confundirse con Logaritmo.
Los diagramas de flujo sirven para representar algoritmos de
manera gráfica Diagrama de Ada Lovelace de la «nota G», el
primer algoritmo informático publicado
En matemáticas, lógica, ciencias de la computación y disciplinas relacionadas, un algoritmo es un
conjunto de instrucciones o reglas definidas y no-ambiguas, ordenadas y finitas que permite,
típicamente, solucionar un problema, realizar un cómputo, procesar datos y llevar a cabo otras
tareas o actividades.1 Dado 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.2
En la vida cotidiana, se emplean algoritmos frecuentemente para resolver problemas
determinados. Algunos ejemplos son los manuales de usuario, que muestran algoritmos para usar
un aparato, o las instrucciones que recibe un trabajador 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 términos de programación, un algoritmo es una secuencia de pasos lógicos que permiten
solucionar un problema.
Etimología
[editar]
La palabra castellana algoritmo deriva del latín algorithmus, que se acuñaría en el siglo xv a partir
del latín algorismus, con influencia del griego arithmos, que significa «número»,34 o de la
latinización del apellido del matemático persa Al-Juarismi.25La RAE, por su parte, propone que
deriva del latín algobarismus, que derivaría del árabe clásico ḥisābu lḡubār, que significa «cálculo
mediante cifras arábigas».1
Definición
[editar]
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).216789 Sin embargo, cabe notar que algunos algoritmos no tienen
necesariamente 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.10
A lo largo de la historia, varios autores han tratado de definir formalmente los algoritmos
utilizando modelos matemáticos. Esto lo hizo 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 de que se pueden resolver
exactamente los mismos problemas con ambos enfoques.1112 No obstante, 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.62 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:10
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 paso13.
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.14 En particular es posible
considerar una cuarta propiedad que puede usarse 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):14
Aritmetizabilidad. Solamente operaciones innegablemente calculables están disponibles
en el paso inicial.
Medios de expresión de un algoritmo
[editar]
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 suele hacerse en tres niveles:
1. 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.
2. Descripción formal. Se usa un pseudocódigo para describir la secuencia de pasos que
encuentran la solución.
3. 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
[editar]
Diagrama de flujo que expresa un algoritmo para calcular la
raíz cuadrada de un número
Artículo principal: Diagrama de flujo
Los diagramas de flujo son descripciones gráficas de algoritmos; usan símbolos conectados con
flechas para indicar la secuencia de instrucciones y están regidos por ISO.
Los diagramas de flujo se emplean para representar algoritmos pequeños, ya que abarcan mucho
espacio y su construcción es laboriosa. Por su facilidad de lectura se utilizan como introducción a
los algoritmos, descripción de un lenguaje y descripción de procesos a personas ajenas a la
computación.
Pseudocódigo
[editar]
Artículo principal: Pseudocódigo
El pseudocódigo (falso lenguaje, el prefijo pseudo significa falso) es una descripción de alto nivel de
un algoritmo que emplea una mezcla de lenguaje natural con algunas convenciones sintácticas
propias de lenguajes de programación, como asignaciones, ciclos y condicionales, aunque no está
regido por ningún estándar.
El pseudocódigo está pensado para facilitar a las personas el entendimiento de un algoritmo y, por
lo tanto, puede omitir detalles irrelevantes que son necesarios en una implementación.
Programadores diferentes suelen utilizar convenciones distintas, que pueden estar basadas en la
sintaxis de lenguajes de programación concretos. Sin embargo, el pseudocódigo, en general, es
comprensible sin necesidad de conocer o usar un entorno de programación específico, y es a la vez
suficientemente estructurado para que su implementación se pueda hacer directamente a partir
de él.
Así, el pseudocódigo cumple con las funciones antes mencionadas para representar algo abstracto,
los protocolos son los lenguajes para la programación. Busque fuentes más precisas para tener
mayor comprensión del tema.
Sistemas formales
[editar]
La teoría de autómatas y la teoría de funciones recursivas proveen modelos matemáticos que
formalizan el concepto de algoritmo. Los modelos más comunes son la máquina de
Turing, máquina de registro y funciones μ-recursivas. Estos modelos son tan precisos como
un lenguaje máquina, careciendo de expresiones coloquiales o ambigüedad; sin embargo, se
mantienen independientes de cualquier computadora y de cualquier implementación.
Implementación
[editar]
Muchos algoritmos se han ideado para implementarse en un programa. No obstante, los
algoritmos pueden ser implementados en otros medios, como una red neuronal, un circuito
eléctrico o un aparato mecánico y eléctrico. Algunos algoritmos incluso se diseñan especialmente
para implementarse usando lápiz y papel. El algoritmo de multiplicación tradicional, el algoritmo
de Euclides, la criba de Eratóstenes y muchas formas de resolver la raíz cuadrada son solo algunos
ejemplos.
Variables
[editar]
Son elementos que toman valores específicos de un tipo de datos concreto. La declaración de una
variable puede realizarse comenzando con var. Principalmente, existen dos maneras de otorgar
valores iniciales a variables:
1. Mediante una sentencia de asignación.
2. Mediante un procedimiento de entrada de datos (por ejemplo: 'read').
Ejemplo:
...
i:=1;
read(n);
while i < n do begin
(* cuerpo del bucle *)
i := i + 1
end;
...
Estructuras secuenciales
[editar]
La estructura secuencial es aquella en la que una acción sigue a otra en secuencia. Las operaciones
se suceden de tal modo que la salida de una es la entrada de la siguiente y así sucesivamente hasta
el fin del proceso. La asignación de esto consiste en el paso de valores o resultados a una zona de
la memoria. Dicha zona será reconocida con el nombre de la variable que recibe el valor. La
asignación se puede clasificar de la siguiente forma:
1. Simples: Consiste en pasar un valor constante a una variable (a ← 15)
2. Contador: Consiste en usarla como un verificador del número de veces que se realiza un
proceso (a ← a + 1)
3. Acumulador: Consiste en usarla como un sumador en un proceso (a ← a + b)
4. De trabajo: Donde puede recibir el resultado de una operación matemática que involucre
muchas variables (a ← c + b*1/2).
Un ejemplo de estructura secuencial, como obtener el área de un triángulo:
Inicio
...
float b, h, a;
printf("Diga la base");
scanf("%f", &b);
printf("Diga la altura");
scanf("%f", &h);
a = (b*h)/2;
printf("El área del triángulo es %f", a)
...
Fin
Algoritmos como funciones
[editar]
Artículo principal: Teoría de la computabilidad
Esquemática de un algoritmo
que soluciona un problema de ciclo hamiltoniano
Un algoritmo se puede concebir como una función que transforma los datos de
un problema (entrada) en los datos de una solución (salida). Más aún, los datos se pueden
representar a su vez como secuencias de bits, y en general, de símbolos cualesquiera.21215 Como
cada secuencia de bits representa a un número natural (véase Sistema binario), entonces los
algoritmos son en esencia funciones de los números naturales en los números naturales que sí se
pueden calcular. Es decir que todo algoritmo calcula una función donde cada número natural es
la codificación de un problema o de una solución.
En ocasiones los algoritmos son susceptibles de nunca terminar, por ejemplo, cuando entran a
un bucle infinito. Cuando esto ocurre, el algoritmo nunca devuelve ningún valor de salida, y
podemos decir que la función queda indefinida para ese valor de entrada. Por esta razón se
considera que los algoritmos son funciones parciales, es decir, no necesariamente definidas en
todo su dominio de definición.
Cuando una función puede ser calculada por med
