Algoritmo, procedimiento sistemático que produce, en un número finito de pasos, la respuesta a una pregunta o la solución de un problema. El nombre deriva de la traducción latina, Algoritmi de numero Indorum, del tratado de aritmética del matemático musulmán del siglo IX al-Khwarizmi "Al-Khwarizmi sobre el arte hindú del ajuste de cuentas".
informática: algoritmos y complejidad
Un algoritmo es un procedimiento específico para resolver un problema computacional bien definido. El desarrollo y análisis de algoritmos es fundamental.
Para preguntas o problemas con solo un conjunto finito de casos o valores, siempre existe un algoritmo (al menos en principio); Consiste en una tabla de valores de las respuestas. En general, no es un procedimiento tan trivial responder preguntas o problemas que tienen un número infinito de casos o valores a considerar, como "¿Es el número natural (1, 2, 3, …) primo?" o "¿Cuál es el máximo común divisor de los números naturales a y b?" La primera de estas preguntas pertenece a una clase llamada decidible; Un algoritmo que produce una respuesta sí o no se llama procedimiento de decisión. La segunda pregunta pertenece a una clase llamada computable; Un algoritmo que conduce a una respuesta numérica específica se llama procedimiento de cálculo.
Los algoritmos existen para muchas clases infinitas de preguntas; Elementos de Euclides, publicado alrededor de 300 aC, contenía uno para encontrar el máximo divisor común de dos números naturales. Cada estudiante de primaria se perfora en una división larga, que es un algoritmo para la pregunta "Al dividir un número natural a por otro número natural b, ¿cuáles son el cociente y el resto?" El uso de este procedimiento computacional lleva a la respuesta a la pregunta decidible "¿B divide a?" (la respuesta es sí si el resto es cero). La aplicación repetida de estos algoritmos finalmente produce la respuesta a la pregunta decidible "¿Es primo? (la respuesta es no si a es divisible por cualquier número natural más pequeño además de 1).
A veces no puede existir un algoritmo para resolver una clase infinita de problemas, particularmente cuando se hace alguna restricción adicional sobre el método aceptado. Por ejemplo, dos problemas de la época de Euclides que requieren el uso de solo una brújula y una regla (regla sin marcar): la división de un ángulo y la construcción de un cuadrado con un área igual a un círculo dado, se persiguieron durante siglos antes de que se demostrara que eran imposibles. A comienzos del siglo XX, el influyente matemático alemán David Hilbert propuso 23 problemas que los matemáticos resolverían en el próximo siglo. El segundo problema en su lista pedía una investigación de la consistencia de los axiomas de la aritmética. La mayoría de los matemáticos tenían pocas dudas sobre el logro eventual de este objetivo hasta 1931, cuando el lógico nacido en Austria Kurt Gödel demostró el sorprendente resultado de que deben existir proposiciones (o preguntas) aritméticas que no pueden ser probadas o refutadas. Esencialmente, cualquier proposición de este tipo conduce a un procedimiento de determinación que nunca termina (una condición conocida como el problema de detención). En un esfuerzo infructuoso por determinar al menos qué proposiciones son irresolubles, el matemático y lógico inglés Alan Turing definió rigurosamente el concepto poco comprendido de un algoritmo. Aunque Turing terminó demostrando que debe haber proposiciones indecidibles, su descripción de las características esenciales de cualquier máquina de algoritmo de propósito general, o máquina de Turing, se convirtió en la base de la informática. Hoy en día, los problemas de capacidad de decisión y computabilidad son fundamentales para el diseño de un programa de computadora, un tipo especial de algoritmo.
