Algoritmos


En matemáticas, ciencias de la computación, y disciplinas relacionadas, un algoritmo (del latín, dixit algorithmus y éste a su vez del matemático persa al-Jwarizmi) es una lista bien definida , ordenada y finita de operaciones que permite hallar la solución a un problema. Dado un estado inicial y una entrada, a través de pasos sucesivos y bien definidos se llega a un estado final, obteniendo una solución. Los algoritmos son objeto de estudio de la algoritmia.En la vida cotidiana se emplean algoritmos en multitud de ocasiones para resolver diversos problemas. Algunos ejemplos se encuentran en los instructivos (manuales de usuario), los cuales muestran algoritmos para usar el aparato en cuestión o inclusive en las instrucciones que recibe un trabajador por parte de su patrón. También existen ejemplos de índole matemático, como el algoritmo de la división para calcular el cociente de dos números, el algoritmo de Euclides para calcular el máximo común divisor de dos enteros positivos, o el método de Gauss para resolver un Sistema lineal de ecuaciones



Características de los algoritmos


El científico de computación Donald Knuth ofreció una lista de cinco propiedades, que son ampliamente aceptadas como requisitos para un algoritmo:

Carácter finito. "Un algoritmo siempre debe terminar después de un número finito de pasos".
Precisión. "Cada paso de un algoritmo debe estar precisamente definido; las operaciones a llevar a cabo deben ser especificadas de manera rigurosa y no ambigua para cada caso".
Entrada. "Un algoritmo tiene cero o más entradas: cantidades que le son dadas antes de que el algoritmo comience, o dinámicamente mientras el algoritmo corre. Estas entradas son tomadas de conjuntos específicos de objetos".
Salida. "Un algoritmo tiene una o más salidas: cantidades que tienen una relación específica con las entradas".
Eficacia. "También se espera que un algoritmo sea eficaz, en el sentido de que todas las operaciones a realizar en un algoritmo deben ser suficientemente básicas como para que en principio puedan ser hechas de manera exacta y en un tiempo finito por un hombre usando lápiz y papel".
Knuth admite que, aunque su descripción pueda ser intuitivamente clara, carece de rigor formal, puesto que no está exactamente claro qué significa "precisamente definido", "de manera rigurosa y no ambigua", o "suficientemente básicas", y así sucesivamente..

A partir del carácter finito y de la salida se deduce que ante una misma situación inicial (o valores de entrada) un algoritmo debe proporcionar siempre el mismo resultado (o salida), con excepción de los algoritmos probabilistas






Implementación

En lenguaje C:

int max(int c[], int n){
int i, m = c[0];
for (i = 0; i < n; i++){
if (c[i] > m)
m = c[i];
}
return m;
}
En lenguaje Java:

public int max( int c[] ) {
int n = c.length;
int m = c[0];
for( int i = 0 ; i < n ; i++ ) {
if( c[i] > m ) {
m = c[i];
}
}
return m;
}
En lenguaje Visual Basic 8 (2005):

Public Function max(C As Integer()) As Integer
Dim n As Integer = C.GetLength(0)
Dim m As Integer = C(0)
For i As Integer = 1 To n
If C(i) > m Then
m = C(i)
End If
Next
Return m
End Function
En lenguaje Delphi:

function Max(const ListaNumeros: array of Integer): Integer;
var
vTemp, i: Integer;
begin
vTemp:= 0;

for i:= 1 to High(ListaNumeros) do
if ListaNumeros[i] > vTemp then
vTemp:= ListaNumeros[i];

Result:= vTemp;
end;
En lenguaje Ada

type T_Conjunto is array <> of Integer;
function Maximo
(Conjunto : T_Conjunto) return Integer
is
Temporal : Integer := Conjunto (1);
begin
for I in 2 .. Conjunto'Last loop
if Conjunto (I) > Temporal then
Temporal := Conjunto (I);
end if;
end loop;
return Temporal;
end Maximo;
En lenguaje Python

def max(c):
n=len(c)
m=c[0]
for i in range(0,n):
if c[i]>m: m=c[i]
Return








Historia [editar]La palabra algoritmo proviene del nombre del matemático llamado Muhammad ibn Musa al-Khwarizmi que vivió entre los siglos VIII y IX. Su trabajo consistió en preservar y difundir el conocimiento de la antigua Grecia y de la India. Sus libros eran de fácil comprensión, de ahí que su principal logro no fuera el de crear nuevos teoremas o corrientes de pensamiento, sino el de simplificar la matemática a punto tal que pudieran ser comprendidas y aplicadas por un mayor número de personas. Cabe destacar cómo señaló las virtudes del sistema decimal indio (en contra de los sistemas tradicionales árabes) y cómo explicó que, mediante una especificación clara y concisa de cómo calcular sistemáticamente, se podrían definir algoritmos que fueran usados en dispositivos mecánicos en vez de las manos (por ejemplo, ábacos). También estudió la manera de reducir las operaciones que formaban el cálculo. Es por esto que aún no siendo el creador del primer algoritmo, el concepto lleva aunque no su nombre, sí su pseudónimo.

Así, de la palabra algorismo, que originalmente hacía referencia a las reglas de uso de la aritmética utilizando dígitos árabes, se evolucionó a la palabra latina, derivación de al-Khwarizmi, algobarismus, que más tarde mutaría a algoritmo en el siglo XVIII. La palabra ha cambiado de forma que en su definición se incluye a todos los procedimientos finitos para resolver problemas.

Ya en el siglo XIX, se produjo el primer algoritmo escrito para un computador. La autora fue Ada Byron, en cuyos escritos se detallaban la máquina analítica en 1842. Por ello que es considerada por muchos como la primera programadora aunque, desde Charles Babbage, nadie completó su máquina, por lo que el algoritmo nunca se implementó.

La falta de rigor matemático en la definición de "procedimiento bien definido" para los algoritmos trajo algunas dificultades a los matemáticos y lógicos del siglo XIX y comienzos de XX. Este problema fue en gran parte resuelto con la descripción de la máquina de Turing, un modelo abstracto de computadora formulado por Alan Turing, y la demostración de que cualquier método anticipado por otros matemáticos que pueda encontrarse para describir "procedimientos bien definidos" puede ser emulado en una máquina de Turing (una afirmación conocida como "tesis de Church-Turing").

En la actualidad, el criterio formal para definir un algoritmo es que se trata de un proceso que puede implementarse en una máquina de Turing completamente especificada, o en alguno de los formalismos equivalentes. El interés original de Turing era el problema de la detención: decidir cuándo un algoritmo describe un procedimiento de terminación. En términos prácticos importa más la teoría de la complejidad computacional, que incluye los problemas llamados NP-completos, es decir aquellos sobre los que generalmente se presume que requerirán tiempo más que polinómico para cualquier algoritmo (determinístico). NP denota la clase de los problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinística.