Diferencia entre revisiones de «Algoritmo»

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 [[Números enteros|enteros]] positivos, o el [[eliminación de Gauss-Jordan|método de Gauss]] para resolver un [[Sistema lineal de ecuaciones]].

 

La importancia de un algoritmo radica en mostrar la manera de llevar a cabo procesos y resolver mecánicamente [[Problema matemático|problemas matemáticos]] o de otro tipo. Al igual que las [[Función matemática|funciones matemáticas]], los algoritmos reciben una entrada y la transforman en una salida, comportándose como una [[caja negra (sistemas)|caja negra]]. Sin embargo, no toda caja negra que convierta una entrada en una salida se puede considerar un algoritmo: para que un algoritmo pueda ser considerado como tal, debe ser una secuencia ordenada, finita y definida (formalización de su comportamiento) de instrucciones. De este modo se puede seguir y predecir el comportamiento del algoritmo para cualquier entrada posible (salvo algoritmos probabilistas, que tiene usualmente una salida distinta), a partir del seguimiento de esa secuencia de instrucciones, que como es ordenada y definida, no da lugar a ambigüedades y puede seguirse su traza.

 

Cuando un programa de computadora es grande o complejo, este será desarrollado con mucho esfuerzo, ya que se debe comprender y definir el problema a ser resuelto, manejando su complejidad, y descomponiéndolo en partes más pequeñas que puedan resolverse más fácilmente. A menudo, muchos de los algoritmos que se necesitan, después de la descomposición son triviales al instrumento.

 

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''".

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 [[Algoritmo probabilista|algoritmos probabilistas]].

 

{{AP|Teoría de la computabilidad}}

Formalmente, un algoritmo calcula a una función. Como cualquier conjunto finito es numerable, y cualquier conjunto numerable se puede expresar en términos del conjunto de los números naturales (infinito, pero numerable, de hecho no existe otro conjunto más grande que sea también numerable), en esencia, todo algoritmo calcula a funciones definidas en los números naturales. En este punto, una función está parcial o totalmente definida. Una función es parcial cuando hay números naturales que no pertenecen a su dominio (es decir, hay números naturales sobre los que no está definida la función), y una función es total en caso contrario.