Algoritmo

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En matemáticas y ciencias de la computación, un algoritmo es una secuencia finita de instrucciones bien definidas, típicamente usadas para resolver una clase de problemas específicos o para realizar un cálculo.Los algoritmos se utilizan como especificaciones para realizar cálculos y procesamiento de datos. Al hacer uso de la inteligencia artificial, los algoritmos pueden realizar deducciones automáticas (lo que se conoce como razonamiento automático) y usar pruebas matemáticas y lógicas para desviar el código a través de varias rutas (lo que se conoce como toma de decisiones automatizada). Alan Turing ya practicaba el uso de características humanas como descriptores de máquinas de forma metafórica con términos como "memoria", "búsqueda" y "estímulo".

Por el contrario, una heurística es un enfoque para la resolución de problemas que puede no estar completamente especificado o puede no garantizar resultados correctos u óptimos, especialmente en dominios de problemas donde no hay un resultado correcto u óptimo bien definido.

Como método efectivo, un algoritmo se puede expresar dentro de una cantidad finita de espacio y tiempo, y en un lenguaje formal bien definido para calcular una función. Comenzando desde un estado inicial y una entrada inicial (quizás vacía), las instrucciones describen un cálculo que, cuando se ejecuta, avanza a través de un número finito de estados sucesivos bien definidos, produciendo eventualmente una "salida" y terminando en un estado final final. La transición de un estado al siguiente no es necesariamente determinista; algunos algoritmos, conocidos como algoritmos aleatorios, incorporan entradas aleatorias.

Historia

El concepto de algoritmo existe desde la antigüedad. Los antiguos matemáticos babilónicos utilizaron algoritmos aritméticos, como un algoritmo de división, c. 2500 aC y matemáticos egipcios c. 1550 a.C. Más tarde, los matemáticos griegos usaron algoritmos en el 240 a. C. en la criba de Eratóstenes para encontrar números primos y el algoritmo euclidiano para encontrar el máximo común divisor de dos números. Matemáticos árabes como al-Kindi en el siglo IX utilizaron algoritmos criptográficos para descifrar códigos, basados en análisis de frecuencia.

La palabra algoritmo se deriva del nombre del matemático persa del siglo IX Muḥammad ibn Mūsā al-Khwārizmī, cuya nisba (que lo identifica como de Khwarazm) se latinizó como Algoritmi (persa arabizado الخوارزمی c. 780–850). Muḥammad ibn Mūsā al-Khwārizmī fue un matemático, astrónomo, geógrafo y erudito de la Casa de la Sabiduría en Bagdad, cuyo nombre significa 'el nativo de Khwarazm', una región que formaba parte del Gran Irán y ahora se encuentra en Uzbekistán. Alrededor de 825, al-Khwarizmi escribió un tratado en árabe sobre el sistema numérico hindú-árabe, que se tradujo al latín durante el siglo XII. El manuscrito comienza con la frase Dixit Algorizmi('Así habló Al-Khwarizmi'), donde "Algorizmi" era la latinización del traductor del nombre de Al-Khwarizmi. Al-Khwarizmi fue el matemático más leído en Europa a finales de la Edad Media, principalmente a través de otro de sus libros, el Álgebra. En latín medieval tardío, algorismus, inglés 'algorismo', la corrupción de su nombre, simplemente significaba el "sistema numérico decimal". En el siglo XV, bajo la influencia de la palabra griega ἀριθμός (arithmos), 'número' (cf. 'aritmética'), la palabra latina se modificó a algoritmos, y el término inglés correspondiente 'algoritmo' se atestigua por primera vez en el siglo XVII. siglo; el sentido moderno se introdujo en el siglo XIX.

Las matemáticas indias eran predominantemente algorítmicas. Los algoritmos que son representativos de la tradición matemática india van desde los antiguos Śulbasūtrās hasta los textos medievales de la Escuela de Kerala.

En inglés, la palabra algoritmo se usó por primera vez alrededor de 1230 y luego por Chaucer en 1391. El inglés adoptó el término francés, pero no fue hasta finales del siglo XIX que "algoritmo" adquirió el significado que tiene en inglés moderno.

Otro uso temprano de la palabra es de 1240, en un manual titulado Carmen de Algorismo compuesto por Alexandre de Villedieu. Comienza con:

Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.

que se traduce como:

El algorismo es el arte por el cual actualmente usamos esas cifras indias, que suman dos veces cinco.

El poema tiene unos cientos de líneas y resume el arte de calcular con los dados indios de nuevo estilo (Tali Indorum), o números hindúes.

Una formalización parcial del concepto moderno de algoritmo comenzó con los intentos de resolver el Entscheidungsproblem (problema de decisión) planteado por David Hilbert en 1928. Las formalizaciones posteriores se enmarcaron como intentos de definir "calculabilidad efectiva" o "método efectivo". Esas formalizaciones incluyeron las funciones recursivas de Gödel-Herbrand-Kleene de 1930, 1934 y 1935, el cálculo lambda de Alonzo Church de 1936, la Formulación 1 de Emil Post de 1936 y las máquinas de Turing de Alan Turing de 1936-37 y 1939.

Definición informal

Una definición informal podría ser "un conjunto de reglas que define con precisión una secuencia de operaciones", que incluiría todos los programas de computadora (incluidos los programas que no realizan cálculos numéricos) y (por ejemplo) cualquier procedimiento burocrático prescrito o recetas de libros de cocina..

En general, un programa es solo un algoritmo si finalmente se detiene, aunque a veces pueden resultar deseables bucles infinitos.

Un ejemplo prototípico de un algoritmo es el algoritmo de Euclides, que se utiliza para determinar el máximo común divisor de dos números enteros; un ejemplo (hay otros) se describe en el diagrama de flujo anterior y como ejemplo en una sección posterior.

Boolos, Jeffrey & 1974, 1999 ofrecen un significado informal de la palabra "algoritmo" en la siguiente cita:

Ningún ser humano puede escribir lo suficientemente rápido, lo suficientemente largo o lo suficientemente pequeño† ("más y más pequeño sin límite... estarías tratando de escribir sobre moléculas, átomos, electrones") para enumerar todos los miembros de un conjunto infinitamente enumerable escribiendo sus nombres, uno tras otro, en alguna notación. Pero los humanos pueden hacer algo igualmente útil, en el caso de ciertos conjuntos infinitamente enumerables: pueden dar instrucciones explícitas para determinar el miembro n -ésimo del conjunto, para n finito arbitrario. Tales instrucciones deben darse de manera muy explícita, en una forma en la que puedan ser seguidas por una máquina de computación, o por un ser humano que sea capaz de realizar solo operaciones muy elementales con símbolos.

Un "conjunto infinitamente enumerable" es aquel cuyos elementos se pueden poner en correspondencia uno a uno con los números enteros. Por lo tanto, Boolos y Jeffrey dicen que un algoritmo implica instrucciones para un proceso que "crea" enteros de salida a partir de un entero o enteros arbitrarios de "entrada" que, en teoría, pueden ser arbitrariamente grandes. Por ejemplo, un algoritmo puede ser una ecuación algebraica como y = m + n (es decir, dos "variables de entrada" arbitrarias m y n que producen una salida y), pero los intentos de varios autores por definir la noción indican que la palabra implica mucho más que esto, algo del orden de (para el ejemplo de adición):Instrucciones precisas (en un lenguaje entendido por "la computadora") para un proceso rápido, eficiente y "bueno" que especifica los "movimientos" de "la computadora" (máquina o humano, equipado con la información y las capacidades internas necesarias) para encuentre, decodifique y luego procese enteros/símbolos de entrada arbitrarios m y n, símbolos + y =... y produzca "efectivamente", en un tiempo "razonable", el entero de salida y en un lugar específico y en un formato específico.

El concepto de algoritmo también se utiliza para definir la noción de decidibilidad, una noción que es central para explicar cómo los sistemas formales surgen a partir de un pequeño conjunto de axiomas y reglas. En lógica, el tiempo que requiere un algoritmo para completarse no se puede medir, ya que aparentemente no está relacionado con la dimensión física habitual. De tales incertidumbres, que caracterizan el trabajo en curso, surge la falta de disponibilidad de una definición de algoritmo que se adapte tanto al uso concreto (en cierto sentido) como abstracto del término.

La mayoría de los algoritmos están destinados a ser implementados como programas de computadora. Sin embargo, los algoritmos también se implementan por otros medios, como en una red neuronal biológica (por ejemplo, el cerebro humano implementando la aritmética o un insecto buscando comida), en un circuito eléctrico o en un dispositivo mecánico.

Formalización

Los algoritmos son esenciales para la forma en que las computadoras procesan los datos. Muchos programas de computadora contienen algoritmos que detallan las instrucciones específicas que debe realizar una computadora, en un orden específico, para llevar a cabo una tarea específica, como calcular los cheques de pago de los empleados o imprimir las boletas de calificaciones de los estudiantes. Por lo tanto, un algoritmo puede ser considerado como cualquier secuencia de operaciones que pueda ser simulada por un sistema completo de Turing. Entre los autores que afirman esta tesis se encuentran Minsky (1967), Savage (1987) y Gurevich (2000):

Minsky: "Pero también mantendremos, con Turing... que cualquier procedimiento que "naturalmente" podría llamarse efectivo, puede, de hecho, ser realizado por una (simple) máquina. Aunque esto pueda parecer extremo, los argumentos.... a su favor son difíciles de refutar". Gurevich: "... El argumento informal de Turing a favor de su tesis justifica una tesis más fuerte: todo algoritmo puede ser simulado por una máquina de Turing... según Savage [1987], un algoritmo es un proceso computacional definido por una máquina de Turing".

Las máquinas de Turing pueden definir procesos computacionales que no terminan. Las definiciones informales de algoritmos generalmente requieren que el algoritmo siempre termine. Este requisito hace que la tarea de decidir si un procedimiento formal es un algoritmo sea imposible en el caso general, debido a un teorema importante de la teoría de la computabilidad conocido como problema de detención.

Por lo general, cuando un algoritmo está asociado con el procesamiento de información, los datos se pueden leer desde una fuente de entrada, escribir en un dispositivo de salida y almacenar para su posterior procesamiento. Los datos almacenados se consideran parte del estado interno de la entidad que ejecuta el algoritmo. En la práctica, el estado se almacena en una o más estructuras de datos.

Para algunos de estos procesos computacionales, el algoritmo debe estar rigurosamente definido: especificado en la forma en que se aplica en todas las posibles circunstancias que puedan presentarse. Esto significa que cualquier paso condicional debe tratarse sistemáticamente, caso por caso; los criterios para cada caso deben ser claros (y computables).

Debido a que un algoritmo es una lista precisa de pasos precisos, el orden de cálculo siempre es crucial para el funcionamiento del algoritmo. Por lo general, se supone que las instrucciones se enumeran explícitamente y se describen como comenzando "desde arriba" y yendo "hacia abajo", una idea que se describe más formalmente por flujo de control.

Hasta ahora, la discusión sobre la formalización de un algoritmo ha asumido las premisas de la programación imperativa. Esta es la concepción más común, una que intenta describir una tarea en medios "mecánicos" discretos. Único en esta concepción de algoritmos formalizados es la operación de asignación, que establece el valor de una variable. Deriva de la intuición de la "memoria" como un bloc de notas. Un ejemplo de tal asignación se puede encontrar a continuación.

Para conocer algunas concepciones alternativas de lo que constituye un algoritmo, consulte programación funcional y programación lógica.

Algoritmos de expresión

Los algoritmos se pueden expresar en muchos tipos de notación, incluidos lenguajes naturales, pseudocódigo, diagramas de flujo, diagramas de drakon, lenguajes de programación o tablas de control (procesadas por intérpretes). Las expresiones de lenguaje natural de los algoritmos tienden a ser detalladas y ambiguas, y rara vez se usan para algoritmos complejos o técnicos. El pseudocódigo, los diagramas de flujo, los diagramas de drakon y las tablas de control son formas estructuradas de expresar algoritmos que evitan muchas de las ambigüedades comunes en las declaraciones basadas en el lenguaje natural. Los lenguajes de programación están destinados principalmente a expresar algoritmos en una forma que pueda ser ejecutada por una computadora, pero también se usan a menudo como una forma de definir o documentar algoritmos.

Existe una amplia variedad de representaciones posibles y uno puede expresar un programa de máquina de Turing dado como una secuencia de tablas de máquina (ver máquina de estados finitos, tabla de transición de estado y tabla de control para más información), como diagramas de flujo y diagramas de Drakon (ver diagrama de estado para más), o como una forma de código de máquina rudimentario o código de ensamblaje llamado "conjuntos de cuádruples" (ver Máquina de Turing para más).

Las representaciones de algoritmos se pueden clasificar en tres niveles aceptados de descripción de la máquina de Turing, de la siguiente manera:1 descripción de alto nivel"... prosa para describir un algoritmo, ignorando los detalles de implementación. En este nivel, no necesitamos mencionar cómo la máquina maneja su cinta o cabeza".2 Descripción de la implementación"... la prosa solía definir la forma en que la máquina de Turing usa su cabeza y la forma en que almacena datos en su cinta. En este nivel, no damos detalles de los estados o la función de transición".3 Descripción formalMás detallado, el "nivel más bajo", da la "tabla de estado" de la máquina de Turing.

Para ver un ejemplo del algoritmo simple "Agregar m+n" descrito en los tres niveles, consulte Ejemplos.

Diseño

El diseño de algoritmos se refiere a un método o proceso matemático para la resolución de problemas y algoritmos de ingeniería. El diseño de algoritmos es parte de muchas teorías de solución de la investigación operativa, como la programación dinámica y divide y vencerás. Las técnicas para diseñar e implementar diseños de algoritmos también se denominan patrones de diseño de algoritmos, con ejemplos que incluyen el patrón de método de plantilla y el patrón de decorador.

Uno de los aspectos más importantes del diseño de algoritmos es la eficiencia de los recursos (tiempo de ejecución, uso de memoria); la notación O grande se utiliza para describir, por ejemplo, el crecimiento del tiempo de ejecución de un algoritmo a medida que aumenta el tamaño de su entrada.

Pasos típicos en el desarrollo de algoritmos:

Definición del problema
Desarrollo de un modelo
Especificación del algoritmo
Diseñando un algoritmo
Comprobación de la corrección del algoritmo.
Análisis de algoritmo
Implementación del algoritmo
Prueba de programa
Preparación de la documentación

Algoritmos informáticos

Programas "elegantes" (compactos), programas "buenos" (rápidos): La noción de "simplicidad y elegancia" aparece informalmente en Knuth y precisamente en Chaitin:Knuth: "... queremos buenos algoritmos en un sentido estético vagamente definido. Un criterio... es el tiempo necesario para realizar el algoritmo... Otros criterios son la adaptabilidad del algoritmo a las computadoras, su simplicidad y elegancia, etc."Chaitin: "... un programa es 'elegante', lo que significa que es el programa más pequeño posible para producir el resultado que produce"

Chaitin inicia su definición con: "Te mostraré que no puedes probar que un programa es 'elegante ' "; tal prueba resolvería el problema de la detención (ibíd.).

Algoritmo versus función computable por un algoritmo: Para una función dada pueden existir múltiples algoritmos. Esto es cierto, incluso sin expandir el conjunto de instrucciones disponibles para el programador. Rogers observa que "Es... importante distinguir entre la noción de algoritmo, es decir, procedimiento y la noción de función computable por algoritmo, es decir, mapeo producido por procedimiento. La misma función puede tener varios algoritmos diferentes".

Desafortunadamente, puede haber una compensación entre la bondad (velocidad) y la elegancia (compacidad): un programa elegante puede tomar más pasos para completar un cálculo que uno menos elegante. A continuación se muestra un ejemplo que utiliza el algoritmo de Euclides.

Computadoras (y computadores), modelos de computación: Una computadora (o "computadora" humana) es un tipo restringido de máquina, un "dispositivo mecánico determinista discreto" que sigue ciegamente sus instrucciones. Los modelos primitivos de Melzak y Lambek redujeron esta noción a cuatro elementos: (i) ubicaciones discretas y distinguibles, (ii) contadores discretos e indistinguibles (iii) un agente, y (iv) una lista de instrucciones que son efectivas en relación con la capacidad del agente.

Minsky describe una variación más agradable del modelo "ábaco" de Lambek en su "Bases muy simples para la computabilidad". La máquina de Minsky procede secuencialmente a través de sus cinco (o seis, dependiendo de cómo se cuente) instrucciones a menos que un IF-THEN GOTO condicional o un GOTO incondicional cambie el flujo del programa fuera de secuencia. Además de HALT, la máquina de Minsky incluye tres operaciones de asignación (reemplazo, sustitución): CERO (p. ej., el contenido de la ubicación se reemplaza por 0: L ← 0), SUCESOR (p. ej., L ← L+1) y DECRECIMIENTO (p. ej., L ← L − 1). Rara vez un programador debe escribir "código" con un conjunto de instrucciones tan limitado. Pero Minsky muestra (al igual que Melzak y Lambek) que su máquina es Turing completa con solo cuatro tipos generalesde instrucciones: GOTO condicional, GOTO incondicional, asignación/reemplazo/sustitución y HALT. Sin embargo, también se requieren algunas instrucciones de asignación diferentes (por ejemplo, DISMINUCIÓN, INCREMENTO y ZERO/CLEAR/EMPTY para una máquina Minsky) para la integridad de Turing; su especificación exacta depende en cierta medida del diseñador. El GOTO incondicional es una conveniencia; se puede construir inicializando una ubicación dedicada a cero, por ejemplo, la instrucción " Z ← 0 "; a partir de entonces, la instrucción IF Z=0 THEN GOTO xxx es incondicional.

Simulación de un algoritmo: lenguaje de computadora (computadora): Knuth advierte al lector que "la mejor manera de aprender un algoritmo es probarlo... tomar inmediatamente lápiz y papel y trabajar con un ejemplo". Pero, ¿qué pasa con una simulación o ejecución de la cosa real? El programador debe traducir el algoritmo a un lenguaje que el simulador/computadora/computadora pueda ejecutar efectivamente. Stone da un ejemplo de esto: al calcular las raíces de una ecuación cuadrática, la computadora debe saber cómo sacar una raíz cuadrada. Si no lo hacen, entonces el algoritmo, para ser efectivo, debe proporcionar un conjunto de reglas para extraer una raíz cuadrada.

Esto significa que el programador debe conocer un "lenguaje" que sea efectivo en relación con el agente informático de destino (computadora/computadora).

Pero, ¿qué modelo se debe utilizar para la simulación? Van Emde Boas observa que "incluso si basamos la teoría de la complejidad en máquinas abstractas en lugar de máquinas concretas, la arbitrariedad en la elección de un modelo permanece. Es en este punto que entra la noción de simulación ". Cuando se mide la velocidad, el conjunto de instrucciones importa. Por ejemplo, el subprograma en el algoritmo de Euclid para calcular el resto se ejecutaría mucho más rápido si el programador tuviera una instrucción de "módulo" disponible en lugar de solo una resta (o peor: solo el "decremento" de Minsky).

Programación estructurada, estructuras canónicas: según la tesis de Church-Turing, cualquier algoritmo puede calcularse mediante un modelo conocido como Turing completo y, según las demostraciones de Minsky, la integridad de Turing requiere solo cuatro tipos de instrucciones: GOTO condicional, GOTO incondicional, asignación, HALT. Kemeny y Kurtz observan que, si bien el uso "indisciplinado" de GOTO incondicionales y GOTO IF-THEN condicionales puede dar como resultado un "código espagueti", un programador puede escribir programas estructurados usando solo estas instrucciones; por otro lado, "también es posible, y no demasiado difícil, escribir programas mal estructurados en un lenguaje estructurado". Tausworthe aumenta las tres estructuras canónicas de Böhm-Jacopini: SEQUENCE, IF-THEN-ELSE y WHILE-DO, con dos más: DO-WHILE y CASE.Un beneficio adicional de un programa estructurado es que se presta a pruebas de corrección mediante inducción matemática.

Símbolos de diagramas de flujo canónicos: la ayuda gráfica llamada diagrama de flujo ofrece una manera de describir y documentar un algoritmo (y un programa de computadora de uno). Al igual que el flujo del programa de una máquina Minsky, un diagrama de flujo siempre comienza en la parte superior de una página y continúa hacia abajo. Sus símbolos principales son solo cuatro: la flecha dirigida que muestra el flujo del programa, el rectángulo (SECUENCIA, IR A), el rombo (SI-ENTONCES-SINO) y el punto (O-empate). Las estructuras canónicas de Böhm-Jacopini están hechas de estas formas primitivas. Las subestructuras pueden "anidar" en rectángulos, pero solo si se produce una sola salida desde la superestructura. Los símbolos y su uso para construir las estructuras canónicas se muestran en el diagrama.

Ejemplos

Ejemplo de algoritmo

Uno de los algoritmos más simples es encontrar el número más grande en una lista de números en orden aleatorio. Encontrar la solución requiere mirar cada número en la lista. A partir de esto se sigue un algoritmo simple, que se puede establecer en una descripción de alto nivel en prosa inglesa, como:

Descripción de alto nivel:

Si no hay números en el conjunto, entonces no hay número más alto.
Suponga que el primer número del conjunto es el número más grande del conjunto.
Para cada número restante en el conjunto: si este número es mayor que el número más grande actual, considere este número como el número más grande en el conjunto.
Cuando no queden números en el conjunto para iterar, considere que el número más grande actual es el número más grande del conjunto.

Descripción (cuasi)formal: escrita en prosa pero mucho más cercana al lenguaje de alto nivel de un programa de computadora, la siguiente es la codificación más formal del algoritmo en pseudocódigo o código pidgin:

Algoritmo Número más grande
  Entrada: Una lista de números L.
  Salida: El número más grande en la lista L.

  si  L.size = 0 devuelve nulo
   el mayor ← L [0]
   para cada  elemento  en  L, haz 
    si  el elemento > el mayor, entonces el 
      mayor ← el elemento 
  devuelve el  mayor

"←" denota asignación. Por ejemplo, " elemento ← más grande " significa que el valor del elemento más grande cambia al valor del elemento.
" return " termina el algoritmo y genera el siguiente valor.

Algoritmo de Euclides

En matemáticas, el algoritmo de Euclides, o algoritmo de Euclides, es un método eficaz para calcular el máximo común divisor (MCD) de dos enteros (números), el mayor número que los divide a ambos sin dejar resto. Lleva el nombre del antiguo matemático griego Euclides, quien lo describió por primera vez en sus Elementos (c. 300 a. C.). Es uno de los algoritmos más antiguos de uso común. Se puede utilizar para reducir fracciones a su forma más simple y forma parte de muchos otros cálculos criptográficos y teóricos de números.

Euclides plantea el problema así: "dados dos números no primos entre sí, hallar su mayor medida común". Él define "Un número [para ser] una multitud compuesta de unidades": un número de conteo, un número entero positivo que no incluye el cero. "Medir" es colocar una longitud de medición más corta s sucesivamente (q veces) a lo largo de la longitud más larga l hasta que la porción restante r sea menor que la longitud más corta s. En palabras modernas, resto r = l − q × s, siendo q el cociente, o resto res el "módulo", la parte fraccionaria entera que queda después de la división.

Para que el método de Euclides tenga éxito, las longitudes iniciales deben satisfacer dos requisitos: (i) las longitudes no deben ser cero, Y (ii) la resta debe ser "adecuada"; es decir, una prueba debe garantizar que el menor de los dos números se reste del mayor (o los dos pueden ser iguales para que su resta sea cero).

La demostración original de Euclides añade un tercer requisito: las dos longitudes no deben ser primas entre sí. Euclides estipuló esto para poder construir una prueba reductio ad absurdum de que la medida común de los dos números es de hecho la mayor. Si bien el algoritmo de Nicómaco es el mismo que el de Euclides, cuando los números son primos entre sí, produce el número "1" para su medida común. Entonces, para ser precisos, el siguiente es realmente el algoritmo de Nicómaco.

Lenguaje informático para el algoritmo de Euclides

Solo se requieren unos pocos tipos de instrucciones para ejecutar el algoritmo de Euclid: algunas pruebas lógicas (GOTO condicional), GOTO incondicional, asignación (reemplazo) y resta.

Una ubicación se simboliza con letras mayúsculas, por ejemplo, S, A, etc.
La cantidad variable (número) en una ubicación se escribe en letras minúsculas y (generalmente) se asocia con el nombre de la ubicación. Por ejemplo, la ubicación L al principio podría contener el número l = 3009.

Un programa poco elegante para el algoritmo de Euclides

El siguiente algoritmo se enmarca como la versión de cuatro pasos de Knuth de Euclid y Nicomachus, pero, en lugar de usar la división para encontrar el resto, usa restas sucesivas de la longitud más corta s de la longitud restante r hasta que r es menor que s. La descripción de alto nivel, que se muestra en negrita, está adaptada de Knuth 1973: 2–4:

ENTRADA:

1 [En dos lugares, L y S, coloque los números l y s que representan las dos longitudes]:
  ENTRADA L, S
2 [Inicialice R: haga que la longitud restante r sea igual a la longitud inicial/inicial/de entrada l ]:
  R ← L

E0: [Asegúrese de que r ≥ s.]

3 [Asegúrese de que el menor de los dos números esté en S y el mayor en R]:
  SI R > S ENTONCES
    el contenido de L es el número más grande, así que omita los pasos de intercambio 4, 5 y 6:
    IR AL paso 7
  DEMÁS
    intercambiar los contenidos de R y S.
4    L ← R (este primer paso es redundante, pero es útil para una discusión posterior).
5    R ← S
6    S ← L

E1: [Encontrar el resto]: Hasta que la longitud restante r en R sea menor que la longitud más corta s en S, reste repetidamente el número de medición s en S de la longitud restante r en R.

7 SI S > R ENTONCES
    terminado de medir así
    IR A 10
  DEMÁS
    medir de nuevo,
8    R ← R - S
9    [Remanente-bucle]:
    IR A 7.

E2: [¿El resto es cero?]: O (i) la última medida fue exacta, el resto en R es cero y el programa puede detenerse, O (ii) el algoritmo debe continuar: la última medida dejó un resto en R menor que el número de medición en S.

10 SI R = 0 ENTONCES
     hecho
     IR AL paso 15
   DEMÁS
     CONTINÚE AL PASO 11,

E3: [Intercambio de s y r ]: La nuez del algoritmo de Euclides. Usa el resto r para medir lo que antes era un número más pequeño s; L sirve como una ubicación temporal.

11   L ← D
12   R ← S
13   S ← L
14   [Repita el proceso de medición]:
    IR A 7

SALIDA:

15 [Hecho. S contiene el máximo común divisor]:
   IMPRIMIR S

HECHO:

16 PARAR, FIN, PARAR.

Un programa elegante para el algoritmo de Euclides

La siguiente versión del algoritmo de Euclid requiere solo seis instrucciones básicas para hacer lo que "Poco elegante" requiere trece; peor aún, "poco elegante" requiere más tipos de instrucciones. El diagrama de flujo de "Elegante" se puede encontrar en la parte superior de este artículo. En el lenguaje básico (no estructurado), los pasos están numerados y la instrucción es la instrucción de asignación simbolizada por ←. LET [] = []

  5  REM Algoritmo de Euclides para el máximo común divisor 
  6  PRINT  "Escriba dos enteros mayores que 0" 
  10  INPUT  A, B 
  20  IF  B = 0  THEN  GOTO  80 
  30  IF  A  >  B  THEN  GOTO  60 
  40  LET  B = B - A 
  50  GOTO  20 
  60  LET  A = A - B 
  70  IR A  20 
  80  IMPRIMIR  A 
  90  FIN

Cómo funciona "Elegant": en lugar de un "bucle Euclid" externo, "Elegant" cambia de un lado a otro entre dos "co-loops", un bucle A > B que calcula A ← A − B y un bucle B ≤ A que calcula B ← B − A. Esto funciona porque, cuando por fin el minuendo M es menor o igual que el sustraendo S (diferencia = minuendo − sustraendo), el minuendo puede convertirse en s (la nueva longitud de medición) y el sustraendo puede convertirse en la nueva r (la longitud a medir); en otras palabras, el "sentido" de la resta se invierte.

La siguiente versión se puede utilizar con lenguajes de programación de la familia C:

// Algoritmo de Euclides para el máximo común divisor 
int  euclidAlgorithm  (int  A,  int  B){ 
     A = abs (A); 
     B = abdominales (B); 
     while  (B != 0){ 
          while  (A > B)  A = A - B; 
          B = B - A; 
     } 
     devuelve  A; 
}

Probando los algoritmos de Euclides

¿Hace un algoritmo lo que su autor quiere que haga? Unos pocos casos de prueba suelen dar cierta confianza en la funcionalidad principal. Pero las pruebas no son suficientes. Para casos de prueba, una fuente usa 3009 y 884. Knuth sugirió 40902, 24140. Otro caso interesante son los dos números primos 14157 y 5950.

Pero los "casos excepcionales" deben ser identificados y probados. ¿Funcionará correctamente "Poco elegante" cuando R > S, S > R, R = S? Lo mismo para "Elegante": B > A, A > B, A = B? (Sí a todo). ¿Qué sucede cuando un número es cero, ambos números son cero? ("Poco elegante" calcula para siempre en todos los casos; "Elegante" calcula para siempre cuando A = 0.) ¿Qué sucede si se ingresan números negativos ? ¿Números fraccionarios? Si los números de entrada, es decir, el dominio de la función calculada por el algoritmo/programa, debe incluir solo números enteros positivos incluido cero, entonces las fallas en cero indican que el algoritmo (y el programa que lo instancia) es una función parcial en lugar de una función total. Una falla notable debido a excepciones es la falla del cohete Ariane 5 Flight 501 (4 de junio de

Prueba de la corrección del programa mediante el uso de inducción matemática: Knuth demuestra la aplicación de la inducción matemática a una versión "extendida" del algoritmo de Euclides y propone "un método general aplicable para probar la validez de cualquier algoritmo". Tausworthe propone que una medida de la complejidad de un programa sea la longitud de su prueba de corrección.

Medición y mejora de los algoritmos de Euclides

Elegancia (compacidad) versus bondad (velocidad): con solo seis instrucciones básicas, "Elegant" es el claro ganador, en comparación con "No elegante" con trece instrucciones. Sin embargo, "Poco elegante" es más rápido (llega a HALT en menos pasos). El análisis del algoritmo indica por qué ocurre esto: "Elegant" realiza dos pruebas condicionales en cada ciclo de resta, mientras que "Inelegant" solo realiza una. Como el algoritmo (generalmente) requiere muchos bucles, en promedio se pierde mucho tiempo haciendo un "B = 0?" prueba que se necesita solo después de calcular el resto.

¿Se pueden mejorar los algoritmos? : Una vez que el programador juzga que un programa es "adecuado" y "eficaz", es decir, calcula la función prevista por su autor, la pregunta es si se puede mejorar.

La compacidad de "Poco elegante" se puede mejorar mediante la eliminación de cinco pasos. Pero Chaitin demostró que la compactación de un algoritmo no puede ser automatizada por un algoritmo generalizado; más bien, solo se puede hacer de manera heurística; es decir, por búsqueda exhaustiva (los ejemplos se encuentran en Busy beaver), prueba y error, ingenio, perspicacia, aplicación de razonamiento inductivo, etc. Observe que los pasos 4, 5 y 6 se repiten en los pasos 11, 12 y 13. Comparación con "Elegante" proporciona una pista de que estos pasos, junto con los pasos 2 y 3, pueden eliminarse. Esto reduce el número de instrucciones básicas de trece a ocho, lo que lo hace "más elegante" que "Elegante", en nueve pasos.

La velocidad de "Elegant" se puede mejorar moviendo el botón "B=0?" prueba fuera de los dos bucles de resta. Este cambio requiere la adición de tres instrucciones (B = 0?, A = 0?, GOTO). Ahora "Elegant" calcula los números de ejemplo más rápido; si este es siempre el caso para cualquier A, B y R, S dado, requeriría un análisis detallado.

Análisis algorítmico

Con frecuencia es importante saber cuánto de un recurso en particular (como tiempo o almacenamiento) se requiere teóricamente para un algoritmo dado. Se han desarrollado métodos de análisis de algoritmos para obtener dichas respuestas cuantitativas (estimaciones); por ejemplo, un algoritmo que suma los elementos de una lista de n números tendría un requisito de tiempo de O(n), utilizando la notación O grande. En todo momento, el algoritmo solo necesita recordar dos valores: la suma de todos los elementos hasta el momento y su posición actual en la lista de entrada. Por lo tanto, se dice que tiene un requisito de espacio de O(1), si no se cuenta el espacio requerido para almacenar los números de entrada, u O(n) si se cuenta.

Diferentes algoritmos pueden completar la misma tarea con un conjunto diferente de instrucciones en menos o más tiempo, espacio o 'esfuerzo' que otros. Por ejemplo, un algoritmo de búsqueda binaria (con costo O(log n)) supera a una búsqueda secuencial (costo O(n)) cuando se usa para búsquedas en tablas en listas ordenadas o matrices.

Formal versus empírico

El análisis y estudio de algoritmos es una disciplina de la informática y, a menudo, se practica de forma abstracta sin el uso de un lenguaje de programación o implementación específicos. En este sentido, el análisis de algoritmos se asemeja a otras disciplinas matemáticas en que se enfoca en las propiedades subyacentes del algoritmo y no en los detalles de una implementación en particular. Por lo general, el pseudocódigo se usa para el análisis, ya que es la representación más simple y general. Sin embargo, en última instancia, la mayoría de los algoritmos generalmente se implementan en plataformas de hardware/software particulares y su eficiencia algorítmica finalmente se pone a prueba utilizando código real. Para la solución de un problema "único", la eficiencia de un algoritmo en particular puede no tener consecuencias significativas (a menos que n sea extremadamente grande), pero para los algoritmos diseñados para un uso científico interactivo rápido, comercial o de larga duración puede ser crítico. Escalar de n pequeña a n grande frecuentemente expone algoritmos ineficientes que de otro modo serían benignos.

Las pruebas empíricas son útiles porque pueden descubrir interacciones inesperadas que afectan el rendimiento. Los puntos de referencia pueden usarse para comparar mejoras potenciales antes/después de un algoritmo después de la optimización del programa. Sin embargo, las pruebas empíricas no pueden reemplazar el análisis formal y no son triviales de realizar de manera justa.

Eficiencia de ejecución

Para ilustrar las posibles mejoras posibles incluso en algoritmos bien establecidos, una importante innovación reciente, relacionada con los algoritmos FFT (utilizados en gran medida en el campo del procesamiento de imágenes), puede reducir el tiempo de procesamiento hasta 1000 veces para aplicaciones como imágenes médicas. En general, las mejoras de velocidad dependen de propiedades especiales del problema, que son muy comunes en aplicaciones prácticas. Las aceleraciones de esta magnitud permiten que los dispositivos informáticos que hacen un uso extensivo del procesamiento de imágenes (como cámaras digitales y equipos médicos) consuman menos energía.

Clasificación

Hay varias formas de clasificar los algoritmos, cada una con sus propios méritos.

Por implementación

Una forma de clasificar los algoritmos es por medios de implementación.

int mcd (int A, int B) { si (segundo == 0) devolver A; si no (A > B) devuelve mcd (A - B, B); demás devuelve mcd (A, B - A); }

Implementación recursiva en C del algoritmo de Euclides del diagrama de flujo anterior

recursividadUn algoritmo recursivo es aquel que se invoca (hace referencia) a sí mismo repetidamente hasta que coincide una determinada condición (también conocida como condición de terminación), que es un método común en la programación funcional. Los algoritmos iterativos usan construcciones repetitivas como bucles y, a veces, estructuras de datos adicionales como pilas para resolver los problemas dados. Algunos problemas son naturalmente adecuados para una implementación u otra. Por ejemplo, las torres de Hanoi se entienden bien mediante la implementación recursiva. Cada versión recursiva tiene una versión iterativa equivalente (pero posiblemente más o menos compleja), y viceversa.LógicoUn algoritmo puede verse como una deducción lógica controlada. Esta noción se puede expresar como: Algoritmo = lógica + control. El componente lógico expresa los axiomas que se pueden utilizar en el cálculo y el componente de control determina la forma en que se aplica la deducción a los axiomas. Esta es la base del paradigma de programación lógica. En los lenguajes de programación de lógica pura, el componente de control es fijo y los algoritmos se especifican proporcionando solo el componente lógico. El atractivo de este enfoque es la semántica elegante: un cambio en los axiomas produce un cambio bien definido en el algoritmo.Serie, paralelo o distribuidoLos algoritmos generalmente se discuten con la suposición de que las computadoras ejecutan una instrucción de un algoritmo a la vez. Esas computadoras a veces se llaman computadoras en serie. Un algoritmo diseñado para dicho entorno se denomina algoritmo en serie, a diferencia de los algoritmos paralelos o los algoritmos distribuidos. Los algoritmos paralelos aprovechan las arquitecturas informáticas en las que varios procesadores pueden trabajar en un problema al mismo tiempo, mientras que los algoritmos distribuidos utilizan varias máquinas conectadas a una red informática. Los algoritmos paralelos o distribuidos dividen el problema en subproblemas más simétricos o asimétricos y recopilan los resultados nuevamente. El consumo de recursos en dichos algoritmos no es solo ciclos de procesador en cada procesador, sino también la sobrecarga de comunicación entre los procesadores. Algunos algoritmos de clasificación se pueden paralelizar de manera eficiente, pero su sobrecarga de comunicación es costosa. Los algoritmos iterativos son generalmente paralelizables. Algunos problemas no tienen algoritmos paralelos y se denominan problemas inherentemente seriales.Determinista o no deterministaLos algoritmos deterministas resuelven el problema con una decisión exacta en cada paso del algoritmo, mientras que los algoritmos no deterministas resuelven los problemas adivinando, aunque las conjeturas típicas se hacen más precisas mediante el uso de la heurística.Exacto o aproximadoMientras que muchos algoritmos alcanzan una solución exacta, los algoritmos de aproximación buscan una aproximación más cercana a la solución verdadera. La aproximación se puede alcanzar usando una estrategia determinista o aleatoria. Dichos algoritmos tienen un valor práctico para muchos problemas difíciles. Uno de los ejemplos de un algoritmo aproximado es el problema de la mochila, donde hay un conjunto de elementos dados. Su objetivo es empacar la mochila para obtener el máximo valor total. Cada elemento tiene un peso y un valor. El peso total que se puede transportar no es más que un número fijo X. Por lo tanto, la solución debe considerar los pesos de los artículos, así como su valor.Algoritmo cuánticoSe ejecutan en un modelo realista de computación cuántica. El término generalmente se usa para aquellos algoritmos que parecen inherentemente cuánticos, o usan alguna característica esencial de la computación cuántica, como la superposición cuántica o el entrelazamiento cuántico.

Por paradigma de diseño

Otra forma de clasificar los algoritmos es por su metodología de diseño o paradigma. Hay un cierto número de paradigmas, cada uno diferente del otro. Además, cada una de estas categorías incluye muchos tipos diferentes de algoritmos. Algunos paradigmas comunes son:Búsqueda por fuerza bruta o exhaustivaEste es el método ingenuo de probar todas las soluciones posibles para ver cuál es la mejor.Divide y conquistarasUn algoritmo divide y vencerás reduce repetidamente una instancia de un problema a una o más instancias más pequeñas del mismo problema (generalmente recursivamente) hasta que las instancias son lo suficientemente pequeñas como para resolverlas fácilmente. Un ejemplo de divide y vencerás es la clasificación por fusión. La clasificación se puede realizar en cada segmento de datos después de dividir los datos en segmentos y la clasificación de datos completos se puede obtener en la fase de conquista fusionando los segmentos. Una variante más simple de divide y vencerás se llama algoritmo de disminuir y vencer., que resuelve un subproblema idéntico y utiliza la solución de este subproblema para resolver el problema mayor. Divide y vencerás divide el problema en múltiples subproblemas, por lo que la etapa de conquista es más compleja que los algoritmos de disminución y conquista. Un ejemplo de un algoritmo de disminución y conquista es el algoritmo de búsqueda binaria.Búsqueda y enumeraciónMuchos problemas (como jugar al ajedrez) se pueden representar como problemas en gráficos. Un algoritmo de exploración de gráficos especifica reglas para moverse por un gráfico y es útil para este tipo de problemas. Esta categoría también incluye algoritmos de búsqueda, enumeración de ramas y límites y seguimiento inverso.Algoritmo aleatorizadoDichos algoritmos toman algunas decisiones aleatoriamente (o pseudoaleatoriamente). Pueden ser muy útiles para encontrar soluciones aproximadas para problemas en los que encontrar soluciones exactas puede ser poco práctico (consulte el método heurístico a continuación). Para algunos de estos problemas, se sabe que las aproximaciones más rápidas deben implicar cierta aleatoriedad. Si los algoritmos aleatorios con complejidad de tiempo polinomial pueden ser los algoritmos más rápidos para algunos problemas es una pregunta abierta conocida como el problema P versus NP. Hay dos grandes clases de tales algoritmos:

Los algoritmos de Monte Carlo devuelven una respuesta correcta con alta probabilidad. Por ejemplo, RP es la subclase de estos que se ejecutan en tiempo polinomial.
Los algoritmos de Las Vegas siempre devuelven la respuesta correcta, pero su tiempo de ejecución solo está limitado probabilísticamente, por ejemplo, ZPP.

Reducción de la complejidadEsta técnica implica resolver un problema difícil transformándolo en un problema más conocido para el cual tenemos (con suerte) algoritmos asintóticamente óptimos. El objetivo es encontrar un algoritmo reductor cuya complejidad no esté dominada por los algoritmos reducidos resultantes. Por ejemplo, un algoritmo de selección para encontrar la mediana en una lista sin ordenar implica primero ordenar la lista (la parte cara) y luego extraer el elemento central de la lista ordenada (la parte barata). Esta técnica también se conoce como transformar y conquistar.seguimiento posteriorEn este enfoque, las soluciones múltiples se crean de forma incremental y se abandonan cuando se determina que no pueden conducir a una solución completa válida.

Problemas de optimización

Para problemas de optimización existe una clasificación más específica de algoritmos; un algoritmo para tales problemas puede caer en una o más de las categorías generales descritas anteriormente, así como en una de las siguientes:Programación linealAl buscar soluciones óptimas para una función lineal limitada a restricciones de igualdad y desigualdad lineales, las restricciones del problema se pueden usar directamente para producir las soluciones óptimas. Hay algoritmos que pueden resolver cualquier problema de esta categoría, como el popular algoritmo simplex.Los problemas que se pueden resolver con programación lineal incluyen el problema de flujo máximo para gráficos dirigidos. Si un problema requiere además que una o más de las incógnitas sean números enteros, entonces se clasifica en programación entera. Un algoritmo de programación lineal puede resolver tal problema si se puede probar que todas las restricciones para valores enteros son superficiales, es decir, las soluciones satisfacen estas restricciones de todos modos. En el caso general se utiliza un algoritmo especializado o un algoritmo que encuentra soluciones aproximadas, dependiendo de la dificultad del problema.Programación dinámicaCuando un problema muestra subestructuras óptimas, lo que significa que la solución óptima a un problema se puede construir a partir de soluciones óptimas a subproblemas, y subproblemas superpuestos, lo que significa que los mismos subproblemas se usan para resolver muchas instancias de problemas diferentes, un enfoque más rápido llamado programación dinámicaevita volver a calcular soluciones que ya han sido calculadas. Por ejemplo, el algoritmo de Floyd-Warshall, la ruta más corta a un objetivo desde un vértice en un gráfico ponderado se puede encontrar usando la ruta más corta a la meta desde todos los vértices adyacentes. La programación dinámica y la memorización van de la mano. La principal diferencia entre la programación dinámica y divide y vencerás es que los subproblemas son más o menos independientes en divide y vencerás, mientras que los subproblemas se superponen en la programación dinámica. La diferencia entre la programación dinámica y la recursividad directa está en el almacenamiento en caché o memorización de llamadas recursivas. Cuando los subproblemas son independientes y no hay repetición, la memorización no ayuda; por lo tanto, la programación dinámica no es una solución para todos los problemas complejos. Mediante el uso de la memorización o el mantenimiento de una tabla de subproblemas ya resueltos,El método codiciosoUn algoritmo voraz es similar a un algoritmo de programación dinámica en que funciona examinando subestructuras, en este caso no del problema sino de una solución dada. Dichos algoritmos comienzan con alguna solución, que puede darse o haber sido construida de alguna manera, y la mejoran haciendo pequeñas modificaciones. Para algunos problemas pueden encontrar la solución óptima mientras que para otros se detienen en los óptimos locales, es decir, en soluciones que el algoritmo no puede mejorar pero que no son óptimas. El uso más popular de los algoritmos codiciosos es para encontrar el árbol de expansión mínimo donde es posible encontrar la solución óptima con este método. Huffman Tree, Kruskal, Prim, Sollin son algoritmos codiciosos que pueden resolver este problema de optimización.El método heurísticoEn los problemas de optimización, los algoritmos heurísticos se pueden usar para encontrar una solución cercana a la solución óptima en los casos en que encontrar la solución óptima no es práctico. Estos algoritmos funcionan acercándose cada vez más a la solución óptima a medida que avanzan. En principio, si se ejecutan durante un tiempo infinito, encontrarán la solución óptima. Su mérito es que pueden encontrar una solución muy cercana a la solución óptima en un tiempo relativamente corto. Dichos algoritmos incluyen búsqueda local, búsqueda tabú, recocido simulado y algoritmos genéticos. Algunos de ellos, como el recocido simulado, son algoritmos no deterministas, mientras que otros, como la búsqueda tabú, son deterministas. Cuando se conoce un límite en el error de la solución no óptima, el algoritmo se clasifica además como un algoritmo de aproximación.

Por campo de estudio

Cada campo de la ciencia tiene sus propios problemas y necesita algoritmos eficientes. Los problemas relacionados en un campo a menudo se estudian juntos. Algunas clases de ejemplo son algoritmos de búsqueda, algoritmos de clasificación, algoritmos de combinación, algoritmos numéricos, algoritmos gráficos, algoritmos de cadenas, algoritmos geométricos computacionales, algoritmos combinatorios, algoritmos médicos, aprendizaje automático, criptografía, algoritmos de compresión de datos y técnicas de análisis.

Los campos tienden a superponerse entre sí, y los avances del algoritmo en un campo pueden mejorar los de otros campos, a veces completamente no relacionados. Por ejemplo, la programación dinámica se inventó para optimizar el consumo de recursos en la industria, pero ahora se usa para resolver una amplia gama de problemas en muchos campos.

Por complejidad

Los algoritmos se pueden clasificar por la cantidad de tiempo que necesitan para completarse en comparación con su tamaño de entrada:

Tiempo constante: si el tiempo que necesita el algoritmo es el mismo, independientemente del tamaño de entrada. Por ejemplo, un acceso a un elemento de matriz.
Tiempo logarítmico: si el tiempo es una función logarítmica del tamaño de entrada. Por ejemplo, algoritmo de búsqueda binaria.
Tiempo lineal: si el tiempo es proporcional al tamaño de entrada. Por ejemplo, la poligonal de una lista.
Tiempo polinomial: si el tiempo es una potencia del tamaño de entrada. Por ejemplo, el algoritmo de clasificación de burbujas tiene una complejidad de tiempo cuadrática.
Tiempo exponencial: si el tiempo es una función exponencial del tamaño de entrada. Por ejemplo, búsqueda de fuerza bruta.

Algunos problemas pueden tener múltiples algoritmos de diferente complejidad, mientras que otros problemas pueden no tener algoritmos o no tener algoritmos eficientes conocidos. También hay asignaciones de algunos problemas a otros problemas. Debido a esto, se encontró que era más adecuado clasificar los problemas en sí mismos en lugar de los algoritmos en clases de equivalencia basadas en la complejidad de los mejores algoritmos posibles para ellos.

Algoritmos continuos

El adjetivo "continuo" cuando se aplica a la palabra "algoritmo" puede significar:

Un algoritmo que opera con datos que representan cantidades continuas, aunque estos datos estén representados por aproximaciones discretas; dichos algoritmos se estudian en el análisis numérico; o
Algoritmo en forma de ecuación diferencial que opera continuamente sobre los datos, ejecutándose en una computadora analógica.

Asuntos legales

Los algoritmos, por sí mismos, no suelen ser patentables. En los Estados Unidos, una reivindicación que consiste únicamente en manipulaciones simples de conceptos abstractos, números o señales no constituye "procesos" (USPTO 2006) y, por lo tanto, los algoritmos no son patentables (como en Gottschalk v. Benson). Sin embargo, las aplicaciones prácticas de los algoritmos a veces son patentables. Por ejemplo, en Diamond v. Diehr, se consideró patentable la aplicación de un algoritmo de retroalimentación simple para ayudar en el curado del caucho sintético. La patentación de software es muy controvertida y existen patentes muy criticadas que involucran algoritmos, especialmente algoritmos de compresión de datos, como la patente LZW de Unisys.

Además, algunos algoritmos criptográficos tienen restricciones de exportación (ver exportación de criptografía).

Historia: Desarrollo de la noción de "algoritmo"

Antiguo Cercano Oriente

La evidencia más temprana de algoritmos se encuentra en las matemáticas babilónicas de la antigua Mesopotamia (actual Irak). Una tablilla de arcilla sumeria encontrada en Shuruppak, cerca de Bagdad y fechada alrededor del año 2500 a. C., describe el algoritmo de división más antiguo. Durante la dinastía Hammurabi, alrededor de 1800-1600 a. C., las tablillas de arcilla babilónicas describían algoritmos para calcular fórmulas. Los algoritmos también se utilizaron en la astronomía babilónica. Las tablillas de arcilla babilónicas describen y emplean procedimientos algorítmicos para calcular la hora y el lugar de eventos astronómicos significativos.

Los algoritmos para la aritmética también se encuentran en las matemáticas del antiguo Egipto, que se remontan al papiro matemático Rhind alrededor del año 1550 a. Los algoritmos se utilizaron más tarde en las matemáticas helenísticas antiguas. Dos ejemplos son la criba de Eratóstenes, que se describió en la Introducción a la aritmética de Nicómaco, y el algoritmo de Euclides, que se describió por primera vez en los Elementos de Euclides (c. 300 a. C.).

Símbolos discretos y distinguibles

Marcas de conteo: Para llevar la cuenta de sus rebaños, sus sacos de grano y su dinero, los antiguos usaban el conteo: acumulando piedras o marcas rayadas en palos o haciendo símbolos discretos en arcilla. A través del uso babilónico y egipcio de marcas y símbolos, eventualmente evolucionaron los números romanos y el ábaco (Dilson, p. 16–41). Las marcas de conteo aparecen de manera prominente en la aritmética del sistema de numeración unaria utilizada en los cálculos de la máquina de Turing y de la máquina Post-Turing.

Manipulación de símbolos como "marcadores de posición" para números: álgebra

Muhammad ibn Mūsā al-Khwārizmī, un matemático persa, escribió el Al-jabr en el siglo IX. Los términos "algorismo" y "algoritmo" se derivan del nombre al-Khwārizmī, mientras que el término "álgebra" se deriva del libro Al-jabr. En Europa, la palabra "algoritmo" se usó originalmente para referirse a los conjuntos de reglas y técnicas utilizadas por Al-Khwarizmi para resolver ecuaciones algebraicas, antes de generalizarse más tarde para referirse a cualquier conjunto de reglas o técnicas. Esto eventualmente culminó en la noción de Leibniz del cálculo raciocinador (ca 1680):

Un buen siglo y medio adelantado a su tiempo, Leibniz propuso un álgebra de la lógica, un álgebra que especificaría las reglas para manipular conceptos lógicos de la misma manera que el álgebra ordinaria especifica las reglas para manipular números.

Algoritmos criptográficos

El primer algoritmo criptográfico para descifrar el código cifrado fue desarrollado por Al-Kindi, un matemático árabe del siglo IX, en A Manuscript On Deciphering Cryptographic Messages. Dio la primera descripción del criptoanálisis por análisis de frecuencia, el primer algoritmo de descifrado de códigos.

Dispositivos mecánicos con estados discretos

El reloj: Bolter acredita la invención del reloj impulsado por pesas como "La invención clave [de Europa en la Edad Media]", en particular, el escape de borde que nos proporciona el tic y tac de un reloj mecánico. "La máquina automática precisa" condujo inmediatamente a los "autómatas mecánicos" a partir del siglo XIII y finalmente a las "máquinas computacionales": el motor diferencial y los motores analíticos de Charles Babbage y la condesa Ada Lovelace, a mediados del siglo XIX.A Lovelace se le atribuye la primera creación de un algoritmo destinado al procesamiento en una computadora (el motor analítico de Babbage, el primer dispositivo considerado una verdadera computadora completa de Turing en lugar de solo una calculadora) y, como resultado, a veces se le llama "el primer programador de la historia". aunque una implementación completa del segundo dispositivo de Babbage no se realizaría hasta décadas después de su vida.

Máquinas lógicas 1870 - El "ábaco lógico" y la "máquina lógica" de Stanley Jevons: el problema técnico era reducir las ecuaciones booleanas cuando se presentaban en una forma similar a lo que ahora se conoce como mapas de Karnaugh. Jevons (1880) describe primero un simple "ábaco" de "trozos de madera provistos de alfileres, ideados de modo que cualquier parte o clase de las combinaciones [lógicas] puedan seleccionarse mecánicamente... Más recientemente, sin embargo, he reducido el sistema a una forma completamente mecánica, y así han encarnado todo el proceso indirecto de inferencia en lo que puede llamarse una Máquina Lógica ". Su máquina venía equipada con "ciertas barras de madera móviles" y "al pie hay 21 teclas como las de un piano [etc.]...".

Esta máquina la exhibió en 1870 ante los Fellows de la Royal Society. Otro lógico, John Venn, sin embargo, en su Lógica simbólica de 1881, se volvió ictérico a este esfuerzo: "No tengo una gran estimación del interés o la importancia de lo que a veces se llama máquinas lógicas... no me parece que cualquier artilugio actualmente conocido o probable que se descubra realmente merece el nombre de máquinas lógicas”; ver más en Caracterizaciones de algoritmos. Pero para no quedarse atrás, él también presentó "un plan algo análogo, me temo, al ábaco del Prof. Jevon... [Y] [a] nuevo, correspondiente a la máquina lógica del Prof. Jevons, se puede describir la siguiente invención. Prefiero llamarlo simplemente una máquina de diagramas lógicos... pero supongo que podría hacer de manera muy completa todo lo que se puede esperar racionalmente de cualquier máquina lógica".

Telar Jacquard, tarjetas perforadas Hollerith, telegrafía y telefonía: el relé electromecánico: Bell y Newell (1971) indican que el telar Jacquard (1801), precursor de las tarjetas Hollerith (tarjetas perforadas, 1887), y las "tecnologías de conmutación telefónica" fueron las raíces de un árbol que condujo al desarrollo de las primeras computadoras. A mediados del siglo XIX, el telégrafo, el precursor del teléfono, estaba en uso en todo el mundo, su codificación discreta y distinguible de letras como "puntos y rayas" era un sonido común. A fines del siglo XIX, la cinta de teletipo (ca. 1870) estaba en uso, al igual que el uso de tarjetas Hollerith en el censo de EE. UU. De 1890. Luego vino la teleimpresora (ca. 1910) con su uso de papel perforado del código Baudot en cinta.

Las redes de conmutación telefónica de relés electromecánicos (inventadas en 1835) estuvieron detrás del trabajo de George Stibitz (1937), el inventor del dispositivo de suma digital. Mientras trabajaba en Bell Laboratories, observó el uso "engorroso" de calculadoras mecánicas con engranajes. "Se fue a casa una noche de 1937 con la intención de probar su idea... Cuando terminaron los retoques, Stibitz había construido un dispositivo de suma binaria"..

Davis (2000) observa la particular importancia del relé electromecánico (con sus dos "estados binarios" abierto y cerrado):Fue solo con el desarrollo, a partir de la década de 1930, de calculadoras electromecánicas que utilizan relés eléctricos, que se construyeron máquinas con el alcance que Babbage había previsto".

Matemáticas durante el siglo XIX hasta mediados del siglo XX

Símbolos y reglas: en rápida sucesión, las matemáticas de George Boole (1847, 1854), Gottlob Frege (1879) y Giuseppe Peano (1888–1889) redujeron la aritmética a una secuencia de símbolos manipulados por reglas. Los principios de la aritmética de Peano , presentados por un nuevo método (1888) fue "el primer intento de axiomatización de las matemáticas en un lenguaje simbólico".

Pero Heijenoort le da a Frege (1879) este elogio: el de Frege es "quizás el trabajo individual más importante jamás escrito en lógica... en el que vemos un" 'lenguaje de fórmula', que es una lingua characterica, un lenguaje escrito con símbolos especiales, "para el pensamiento puro", es decir, libre de adornos retóricos... construidos a partir de símbolos específicos que se manipulan de acuerdo con reglas definidas ". El trabajo de Frege fue simplificado y ampliado aún más por Alfred North Whitehead y Bertrand Russell en su Principia Mathematica (1910-1913).

Las paradojas: al mismo tiempo, aparecieron en la literatura varias paradojas inquietantes, en particular, la paradoja de Burali-Forti (1897), la paradoja de Russell (1902-03) y la paradoja de Richard. Las consideraciones resultantes llevaron al artículo de Kurt Gödel (1931) —cita específicamente la paradoja del mentiroso— que reduce completamente las reglas de recursividad a números.

Calculabilidad efectiva: En un esfuerzo por resolver el Entscheidungsproblem definido con precisión por Hilbert en 1928, los matemáticos primero se propusieron definir qué se entendía por "método efectivo" o "cálculo efectivo" o "calculabilidad efectiva" (es decir, un cálculo que tendría éxito).). En rápida sucesión aparecieron los siguientes: Alonzo Church, Stephen Kleene y JB Rosser's λ-calculus una definición finamente perfeccionada de "recursión general" del trabajo de Gödel actuando sobre sugerencias de Jacques Herbrand (cf. Gödel's Princeton conferencias de 1934) y simplificaciones posteriores por Kleene. prueba de la iglesiaque el Entscheidungsproblem no tenía solución, la definición de Emil Post de calculabilidad efectiva como un trabajador que sigue sin pensar una lista de instrucciones para moverse hacia la izquierda o hacia la derecha a través de una secuencia de habitaciones y mientras marca o borra un papel u observa el papel y hace un sí-no decisión sobre la siguiente instrucción. La prueba de Alan Turing de que el Entscheidungsproblem no se podía resolver mediante el uso de su "una máquina [automática]", en efecto, casi idéntica a la "formulación" de Post, la definición de "método efectivo" de J. Barkley Rosser en términos de "una máquina".. La propuesta de Kleene de un precursor de la "tesis de la Iglesia" que llamó "Tesis I", y unos años más tarde, Kleene cambió el nombre de su Tesis a "Tesis de la Iglesia".

Emil Post (1936) y Alan Turing (1936–37, 1939)

Emil Post (1936) describió las acciones de una "computadora" (ser humano) de la siguiente manera:"... están involucrados dos conceptos: el de un espacio de símbolos en el que debe llevarse a cabo el trabajo que conduce del problema a la respuesta, y un conjunto fijo e inalterable de direcciones.

Su espacio de símbolos sería"una secuencia infinita bidireccional de espacios o cajas... El solucionador de problemas o trabajador debe moverse y trabajar en este espacio de símbolos, siendo capaz de estar y operar en una sola caja a la vez... una caja es admitir sólo dos condiciones posibles, es decir, estar vacío o sin marcar, y tener una sola marca en él, digamos un trazo vertical."Se debe señalar una casilla y llamarla punto de partida... un problema específico se debe dar en forma simbólica mediante un número finito de casillas [es decir, ENTRADA] marcadas con un trazo. Asimismo, la respuesta [es decir,, SALIDA] debe ser dada en forma simbólica por tal configuración de casillas marcadas..."Un conjunto de direcciones aplicables a un problema general establece un proceso determinista cuando se aplica a cada problema específico. Este proceso termina solo cuando se trata de la dirección de tipo (C) [es decir, STOP]". Ver más en Máquina Post-Turing

El trabajo de Alan Turing precedió al de Stibitz (1937); se desconoce si Stibitz conocía la obra de Turing. El biógrafo de Turing creía que el uso de Turing de un modelo similar a una máquina de escribir se derivaba de un interés juvenil: "Alan había soñado con inventar máquinas de escribir cuando era niño; la Sra. Turing tenía una máquina de escribir, y bien podría haber comenzado preguntándose qué significaba llamar una máquina de escribir 'mecánica'". Dada la prevalencia del código Morse y la telegrafía, las máquinas de teletipo y los teletipos, podríamos conjeturar que todos fueron influencias.

Turing, su modelo de computación ahora se llama máquina de Turing, comienza, al igual que Post, con un análisis de una computadora humana que reduce a un conjunto simple de movimientos básicos y "estados mentales". Pero va un paso más allá y crea una máquina como modelo de cálculo de números."La computación normalmente se realiza escribiendo ciertos símbolos en papel. Podemos suponer que este papel está dividido en cuadrados como un libro de aritmética para niños... Asumo entonces que la computación se lleva a cabo en un papel unidimensional, es decir, en una cinta dividida en cuadrados También supondré que el número de símbolos que se pueden imprimir es finito...El comportamiento de la computadora en cualquier momento está determinado por los símbolos que está observando y su "estado mental" en ese momento. Podemos suponer que existe un límite B en el número de símbolos o cuadrados que la computadora puede observar en un momento. Si desea observar más, debe utilizar observaciones sucesivas. También supondremos que el número de estados de ánimo que se deben tener en cuenta es finito..."Imaginemos que las operaciones realizadas por la computadora se dividen en 'operaciones simples' que son tan elementales que no es fácil imaginarlas más divididas".

La reducción de Turing produce lo siguiente:"Las operaciones simples deben por lo tanto incluir:"(a) Cambios del símbolo en uno de los cuadrados observados"(b) Cambios de uno de los cuadrados observados a otro cuadrado dentro de L cuadrados de uno de los cuadrados observados previamente.

"Puede ser que algunos de estos cambios invoquen necesariamente un cambio de estado mental. Por lo tanto, la operación individual más general debe tomarse como una de las siguientes:"(A) Un posible cambio (a) de símbolo junto con un posible cambio de estado de ánimo."(B) Un posible cambio (b) de cuadrados observados, junto con un posible cambio de estado de ánimo""Ahora podemos construir una máquina para hacer el trabajo de esta computadora".

Unos años más tarde, Turing amplió su análisis (tesis, definición) con esta contundente expresión del mismo:"Se dice que una función es "efectivamente calculable" si sus valores se pueden encontrar mediante algún proceso puramente mecánico. Aunque es bastante fácil obtener una comprensión intuitiva de esta idea, es deseable tener una definición matemática expresable más definida.... [discute la historia de la definición más o menos como se presentó anteriormente con respecto a Gödel, Herbrand, Kleene, Church, Turing y Post]... Podemos tomar esta declaración literalmente, entendiendo por un proceso puramente mecánico uno que podría ser realizado por una máquina. Es posible dar una descripción matemática, en cierta forma normal, de las estructuras de estas máquinas. El desarrollo de estas ideas lleva a la definición del autor de una función computable, y a una identificación de computabilidad † con calculabilidad efectiva...."† Usaremos la expresión "función computable" para referirnos a una función calculable por una máquina, y dejaremos que "efectivamente calculable" se refiera a la idea intuitiva sin identificación particular con ninguna de estas definiciones".

JB Rosser (1939) y SC Kleene (1943)

J. Barkley Rosser definió un 'método [matemático] efectivo' de la siguiente manera (cursiva añadida):"'Método efectivo' se usa aquí en el sentido bastante especial de un método en el que cada paso está determinado con precisión y que con certeza producirá la respuesta en un número finito de pasos. Con este significado especial, se han dado tres definiciones precisas diferentes hasta la fecha [su nota a pie de página #5; véase la discusión inmediatamente debajo]. El más simple de ellos (debido a Post y Turing) dice esencialmente que existe un método efectivo para resolver ciertos conjuntos de problemas si uno puede construir una máquina que luego resolver cualquier problema del conjunto sin intervención humana más allá de insertar la pregunta y (posteriormente) leer la respuesta. Las tres definiciones son equivalentes, por lo que no importa cuál se use. Además, el hecho de que los tres sean equivalentes es un argumento muy sólido a favor de la corrección de cualquiera de ellos". (Rosser 1939: 225-226)

La nota al pie de página No. 5 de Rosser hace referencia al trabajo de (1) Church y Kleene y su definición de definibilidad de λ, en particular, el uso que Church hace de ella en su An Unsolvable Problem of Elementary Number Theory (1936); (2) Herbrand y Gödel y su uso de la recursividad, en particular, el uso de Gödel en su famoso artículo Sobre proposiciones formalmente indecidibles de Principia Mathematica and Related Systems I (1931); y (3) Post (1936) y Turing (1936-1937) en sus modelos de mecanismos de computación.

Stephen C. Kleene definió como su ahora famosa "Tesis I", conocida como la tesis de Church-Turing. Pero lo hizo en el siguiente contexto (negrita en el original):"12. Teorías algorítmicas... Al establecer una teoría algorítmica completa, lo que hacemos es describir un procedimiento, realizable para cada conjunto de valores de las variables independientes, cuyo procedimiento termina necesariamente y de tal manera que a partir del resultado podemos lea una respuesta definitiva, "sí" o "no", a la pregunta "¿es verdadero el valor del predicado?" (Kleene 1943: 273)

Historia después de 1950

Se han dirigido varios esfuerzos hacia un mayor refinamiento de la definición de "algoritmo", y la actividad continúa debido a problemas relacionados, en particular, con los fundamentos de las matemáticas (especialmente la tesis de Church-Turing) y la filosofía de la mente (especialmente los argumentos sobre inteligencia artificial). Para obtener más información, consulte Caracterizaciones de algoritmos.

Contenido relacionado

Más resultados...