De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

Diagrama de flujo de un algoritmo ( algoritmo de Euclides ) para calcular el máximo común divisor (MCD) de dos números a y b en lugares denominadas A y B. El algoritmo procede por sustracciones sucesivas en dos bucles: Si la prueba B ≥ produce un "sí" o "verdadero" (más exactamente, el número b en la ubicación B es mayor o igual que el número a en la ubicación A) ENTONCES, el algoritmo especifica B ← B - A (es decir, el número b - a reemplaza al antiguo b). De manera similar, SI A> B, ENTONCES A ← A - B. El proceso termina cuando (el contenido de) B es 0, produciendo el mcd en A. (Algoritmo derivado de Scott 2009: 13; símbolos y estilo de dibujo de Tausworthe 1977) .
Diagrama de Ada Lovelace de la "nota G", el primer algoritmo informático publicado

En matemáticas y ciencia de la computación , un algoritmo ( / æ l ɡ ə r ɪ ð əm / ( escuchar )Sobre este sonido ) es una secuencia finita de bien definida , instrucciones de ordenador implementable, típicamente para resolver una clase de problemas o para llevar a cabo un cálculo . [1] [2] Los algoritmos son siempre inequívocos y se utilizan como especificaciones para realizar cálculos , procesamiento de datos , razonamiento automatizado y otras tareas.

Como método eficaz , un algoritmo puede expresarse dentro de una cantidad finita de espacio y tiempo, [3] y en un lenguaje formal bien definido [4] para calcular una función . [5] A partir de un estado inicial y una entrada inicial (quizás vacía ), [6] las instrucciones describen un cálculo que, cuando se ejecuta , procede a través de un número finito [7] de estados sucesivos bien definidos, que eventualmente producen "salida" [ 8] y termina en un estado final final. La transición de un estado al siguiente no es necesariamente determinista.; algunos algoritmos, conocidos como algoritmos aleatorios , incorporan entrada aleatoria. [9]

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 antes de Cristo. [10] Los matemáticos griegos utilizaron más tarde algoritmos en el 240 a. C. en el tamiz de Eratóstenes para encontrar números primos, [11] y el algoritmo euclidiano para encontrar el máximo común divisor de dos números. [12] Matemáticos árabes como al-Kindi en el siglo IX utilizaron algoritmos criptográficos para descifrado de códigos , basado en análisis de frecuencia . [13]

La palabra algoritmo en sí se deriva del nombre del matemático del siglo IX Muḥammad ibn Mūsā al-Khwārizmī , cuyo nisba (que lo identifica como de Khwarazm ) fue latinizado como Algoritmi . [14] Una formalización parcial de lo que se convertiría en el 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 la " calculabilidad efectiva " [15] o " método eficaz ". [16] Esas formalizaciones incluyeron el Gödel -Herbrand - Kleene funciones recursivas de 1930, 1934 y 1935, Alonzo Church 's cálculo lambda de 1936, Emil post ' s Formulación 1 de 1936, y Alan Turing 's máquina de Turing de 1936 a 1937 y 1939.

Etimología [ editar ]

La palabra 'algoritmo' tiene sus raíces en latinizar la nisba, indicando su origen geográfico, del nombre del matemático persa Muhammad ibn Musa al-Khwarizmi a algorismus . [17] [18] Al-Khwārizmī ( arabizado persa الخوارزمی c. 780-850) fue un matemático, astrónomo , geógrafo y erudito en la Casa de la Sabiduría en Bagdad , [11] cuyo nombre significa 'el nativo de Khwarazm ', una región que era parte del Gran Irán y ahora se encuentra en Uzbekistán . [19] [20]

Hacia el año 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. [21] 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 . [22] En latín medieval tardío, algorismus , ' algorism ' en inglés, la corrupción de su nombre, simplemente significaba "sistema numérico decimal ".[23] En el siglo XV, bajo la influencia de la palabra griega ἀριθμός ( arithmos ), 'número' ( cf. 'aritmética'), la palabra latina se modificó a algorítmo , y el término inglés correspondiente 'algoritmo' se atestigua por primera vez en el siglo 17; el sentido moderno se introdujo en el siglo XIX. [24]

En inglés, se utilizó 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 el inglés moderno. [25]

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, en qua / Talibus Indorum fruimur bis quinque figuris.

que se traduce en:

El algoritmo es el arte con el que en la actualidad utilizamos esas figuras indias, que suman dos por cinco.

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

Definición informal [ editar ]

Una definición informal podría ser "un conjunto de reglas que definen con precisión una secuencia de operaciones", [27] [se necesita una cita para verificar ] 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 [28] o receta de libro de cocina . [29]

En general, un programa es sólo un algoritmo si se detiene eventualmente [30] , aunque a veces los bucles infinitos pueden resultar deseables.

Un ejemplo prototípico de algoritmo es el algoritmo euclidiano , 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 en moléculas, en átomos, en electrones") para enumerar todos los miembros de una enumeración infinita establecido escribiendo sus nombres, uno tras otro, en alguna notación. Pero los humanos pueden hacer algo igualmente útil, en el caso de ciertos conjuntos enumerablemente infinitos: pueden dar instrucciones explícitas para determinar el miembro n del conjunto , para n finitos arbitrarios . Tales instrucciones deben ser dadas de manera bastante explícita, en una forma en la que puedan ser seguidas por una máquina de computación o por un humano que sea capaz de realizar solo operaciones muy elementales sobre símbolos. [31]

Un "conjunto enumerablemente infinito" es aquel cuyos elementos se pueden poner en correspondencia uno a uno con los números enteros. Así, Boolos y Jeffrey están diciendo que un algoritmo implica instrucciones para un proceso que "crea" enteros de salida a partir de un entero o enteros de "entrada" arbitrarios que, en teoría, pueden ser arbitrariamente grandes. Por ejemplo, un algoritmo puede ser una ecuación algebraica tal como y = m + n (es decir, dos arbitraria "variables de entrada" m y n que producen una salida y ), pero los intentos varios autores para 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") [32] para un proceso rápido, eficiente, "bueno" [33] que especifica los "movimientos" de "la computadora" (máquina o humano, equipado con lo necesario internamente información contenida y capacidades) [34] para encontrar, decodificar, y luego procesar números enteros de entrada arbitrarias / símbolos m y n , símbolos + y = ... y "eficacia" [35] de productos, en un tiempo "razonable", [36] de salida -integer 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 surgen los sistemas formales 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 al abstracto del término.

Formalización [ editar ]

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 una computadora debe realizar, 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 tanto, se puede considerar que un algoritmo es cualquier secuencia de operaciones que pueda ser simulada por un sistema completo de Turing . Los autores que afirman esta tesis incluyen a Minsky (1967), Savage (1987) y Gurevich (2000):

Minsky: "Pero también mantendremos, con Turing ... que cualquier procedimiento que pueda" naturalmente "llamarse efectivo, puede, de hecho, ser realizado por una máquina (simple). Aunque esto pueda parecer extremo, los argumentos ... a su favor son difíciles de refutar ". [37]

Gurevich: "... el argumento informal de Turing a favor de su tesis justifica una tesis más fuerte: cada 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". [38]

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 imposible la tarea de decidir si un procedimiento formal es un algoritmo en el caso general, debido a un importante teorema de la teoría de la computabilidad conocido como el problema de la detención .

Normalmente, cuando un algoritmo está asociado con el procesamiento de información, los datos pueden leerse desde una fuente de entrada, escribirse en un dispositivo de salida y almacenarse para su posterior procesamiento. Los datos almacenados se consideran parte del estado interno de la entidad que realiza 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 pudieran surgir. 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 asume que las instrucciones se enumeran explícitamente y se describen comenzando "desde arriba" y yendo "hacia abajo", una idea que se describe de manera más formal mediante el flujo de control .

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

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

Expresando algoritmos [ editar ]

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 (procesados ​​por intérpretes ). Las expresiones de lenguaje natural de los algoritmos tienden a ser detalladas y ambiguas, y rara vez se utilizan para algoritmos complejos o técnicos. Pseudocódigo, diagramas de flujo, diagramas de drakony las tablas de control son formas estructuradas de expresar algoritmos que evitan muchas de las ambigüedades comunes en las declaraciones basadas en 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 utilizan a menudo como una forma de definir o documentar algoritmos.

Existe una amplia variedad de representaciones posibles y se puede expresar un programa de máquina de Turing dado como una secuencia de tablas de máquina (ver máquina de estado finito , 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 obtener más información), o como una forma de código de máquina rudimentario o código de ensamblaje llamado "conjuntos de cuádruples" (consulte la máquina de Turing para obtener más información).

Las representaciones de algoritmos se pueden clasificar en tres niveles aceptados de descripción de la máquina de Turing, de la siguiente manera: [39]

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 cabezal ".
2 Descripción de la implementación
“… Prosa utilizada para definir la forma en que la máquina de Turing usa su cabezal y la forma en que almacena datos en su cinta. En este nivel, no damos detalles de estados o función de transición ".
3 Descripción formal
Más detallado, "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 de algoritmo # .

Diseño [ editar ]

El diseño de algoritmos se refiere a un método o proceso matemático para la resolución de problemas y los algoritmos de ingeniería. El diseño de algoritmos es parte de muchas teorías de solución de la investigación de operaciones , como la programación dinámica y el 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, [40] con ejemplos que incluyen el patrón del método de plantilla y el patrón del 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 usa 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:

  1. Definición del problema
  2. Desarrollo de un modelo
  3. Especificación del algoritmo
  4. Diseñando un algoritmo
  5. Comprobando la corrección del algoritmo
  6. Análisis de algoritmo
  7. Implementación de algoritmo
  8. Prueba del programa
  9. Preparación de la documentación [ aclaración necesaria ]

Implementación [ editar ]

Algoritmo lógico NAND implementado electrónicamente en el chip 7400

La mayoría de los algoritmos están pensados ​​para implementarse 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 aritmética o un insecto en busca de comida), en un circuito eléctrico o en un dispositivo mecánico.

Algoritmos informáticos [ editar ]

Ejemplos de diagrama de flujo de las estructuras canónicas de Böhm-Jacopini : la SECUENCIA (rectángulos que descienden de la página), el MIENTRAS-HACES y el SI-ENTONCES-ELSE. Las tres estructuras están compuestas por el primitivo condicional GOTO ( IF test THEN GOTO step xxx, mostrado como diamante), el incondicional GOTO (rectángulo), varios operadores de asignación (rectángulo) y HALT (rectángulo). El anidamiento de estas estructuras dentro de bloques de asignación da como resultado diagramas complejos (cf. Tausworthe 1977: 100, 114).

En sistemas informáticos , un algoritmo es básicamente una instancia de lógica escrito en software por los desarrolladores de software, para ser eficaz para el destinados ordenador "objetivo" (s) para producir salida de dado (tal vez null) de entrada . Un algoritmo óptimo, incluso ejecutándose en hardware antiguo, produciría resultados más rápidos que un algoritmo no óptimo (mayor complejidad de tiempo ) para el mismo propósito, ejecutándose en hardware más eficiente; es por eso que los algoritmos, como el hardware informático, se consideran tecnología.

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 que lleva realizar el algoritmo ... Otros criterios son la adaptabilidad del algoritmo a las computadoras, su simplicidad y elegancia, etc." [41]
Chaitin: "... un programa es 'elegante', con lo que quiero decir que es el programa más pequeño posible para producir el resultado que produce" [42]

Chaitin comienza su definición con: "Voy a demostrar que no se puede probar que un programa es 'elegante ' "; tal demostración resolvería el problema de la detención (ibid).

Algoritmo versus función calculable por un algoritmo : para una función dada pueden existir múltiples algoritmos. Esto es cierto, incluso sin ampliar 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". [43]

Desafortunadamente, puede haber una compensación entre bondad (velocidad) y 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 Euclid.

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

Minsky describe una variación más agradable del modelo del "ábaco" de Lambek en su "Bases muy simples para la computabilidad ". [50] La máquina de Minsky avanza secuencialmente a través de sus cinco (o seis, dependiendo de cómo se cuenten) instrucciones a menos que un IF-THEN GOTO condicional o un GOTO incondicional cambien 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) [51] : ZERO (por ejemplo, el contenido de la ubicación reemplazado por 0: L ← 0), SUCCESSOR (por ejemplo, L ← L + 1) y DECREMENT (por ejemplo, L ← L - 1). [52] 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 esTuring completo con solo cuatro tipos generales de 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, DECREMENT, INCREMENT y ZERO / CLEAR / EMPTY para una máquina Minsky) para la completitud de Turing; su especificación exacta depende un poco 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 (computor) : 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". [53] Pero ¿qué pasa con una simulación o ejecución de algo real? El programador debe traducir el algoritmo a un lenguaje que el simulador / computadora / computor pueda ejecutar de manera efectiva . Stone da un ejemplo de esto: al calcular las raíces de una ecuación cuadrática, el compilador debe saber cómo sacar una raíz cuadrada. Si no es así, entonces el algoritmo, para ser efectivo, debe proporcionar un conjunto de reglas para extraer una raíz cuadrada. [54]

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

Pero, ¿qué modelo debería utilizarse para la simulación? Van Emde Boas observa "incluso si basamos la teoría de la complejidad en máquinas abstractas en lugar de concretas, la arbitrariedad de la elección de un modelo permanece. Es en este punto que entra la noción de simulación ". [55] Cuando se mide la velocidad, el conjunto de instrucciones es importante. 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 resta (o peor: solo "decremento" de Minsky).

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

Símbolos canónicos de diagrama de flujo [60] : el asistente gráfico llamado diagrama de flujo , ofrece una manera de describir y documentar un algoritmo (y un programa de computadora de uno). Como el flujo de 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 (SEQUENCE, GOTO), el rombo (IF-THEN-ELSE) y el punto (OR-tie). 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 única salida de la superestructura. Los símbolos y su uso para construir las estructuras canónicas se muestran en el diagrama.

Ejemplos [ editar ]

Ejemplo de algoritmo [ editar ]

Uno de los algoritmos más simples es encontrar el número más grande en una lista de números de orden aleatorio. Encontrar la solución requiere mirar todos los números de la lista. 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:

  1. Si no hay números en el conjunto, entonces no hay el número más alto.
  2. Suponga que el primer número del conjunto es el número más grande del conjunto.
  3. Para cada número restante en el conjunto: si este número es mayor que el número más grande actual, considere que este número es el número más grande del conjunto.
  4. Cuando no quedan 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 :

Número más grande del algoritmo Entrada: Una lista de números L . Salida: El número más grande de la lista L .
 si  L.size = 0 devuelve nulo más grandeL [0] para cada  artículo  en  L , hazlo  si  artículo > más grande , entonces  más grandeartículo  devuelve  más grande
  • "←" denota asignación . Por ejemplo, " más grandeartículo significa" que el valor de los mayores cambios en el valor del elemento .
  • " return " termina el algoritmo y genera el siguiente valor.

Algoritmo de Euclides [ editar ]

El diagrama de ejemplo del algoritmo de Euclides de TL Heath (1908), con más detalles agregados. Euclides no va más allá de una tercera medición y no da ejemplos numéricos. Nicomachus da el ejemplo de 49 y 21: "Resto el menor del mayor; queda 28; luego de nuevo resto de esto el mismo 21 (porque esto es posible); queda 7; resto esto de 21, 14 es a la izquierda; de lo que de nuevo resto 7 (porque esto es posible); queda 7, pero 7 no se puede restar de 7. " Heath comenta que "La última frase es curiosa, pero su significado es bastante obvio, como también el significado de la frase sobre la terminación 'en el mismo número'" (Heath 1908: 300).

El algoritmo de Euclides para calcular el máximo común divisor (MCD) en dos números aparece como la Proposición II en el Libro VII ("Teoría de los números elementales") de sus Elementos . [61] Euclides plantea el problema así: "Dados dos números que no son primos entre sí, para encontrar su máxima medida común". Él define "Un número [es] una multitud compuesta de unidades": un número de conteo, un 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 una longitud l más larga hasta que la porción restante r sea ​​menor que la longitud s más corta . [62] En palabras modernas,recordatorior = l - q × s , siendo q el cociente, o el resto r es el "módulo", la parte entera-fraccionaria que queda después de la división. [63]

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 dé cero).

La prueba original de Euclides agrega un tercer requisito: las dos longitudes no deben ser primos 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 . [64] Si bien el algoritmo de Nicomachus es el mismo que el de Euclides, cuando los números son primos entre sí, se obtiene el número "1" para su medida común. Entonces, para ser precisos, el siguiente es realmente el algoritmo de Nicomachus.

Una expresión gráfica del algoritmo de Euclides para encontrar el máximo común divisor de 1599 y 650.
1599 = 650 × 2 + 299650 = 299 × 2 + 52 299 = 52 × 5 + 39 52 = 39 × 1 + 13 39 = 13 × 3 + 0

Lenguaje informático para el algoritmo de Euclides [ editar ]

Solo se requieren unos pocos tipos de instrucción 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 minúsculas y (generalmente) se asocia con el nombre de la ubicación. Por ejemplo, la ubicación L al principio puede contener el número l = 3009.

Un programa poco elegante para el algoritmo de Euclid [ editar ]

"Inelegante" es una traducción de la versión de Knuth del algoritmo con un ciclo de resto basado en restas que reemplaza su uso de la división (o una instrucción de "módulo"). Derivado de Knuth 1973: 2-4. Dependiendo de los dos números, "Inelegant" puede calcular el mcd en menos pasos que "Elegant".

El siguiente algoritmo se enmarca como la versión de Knuth de cuatro pasos de Euclides y Nicomachus, pero, en lugar de usar la división para encontrar el resto, usa sustracciones sucesivas de la longitud más corta s de la longitud restante r hasta que r sea ​​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 ubicaciones L y S poner los números l y s que representan las dos longitudes]: ENTRADA L, S2 [Inicializar R: hacer que la longitud restante r sea igual a la longitud inicial / inicial / de entrada l ]: R ← L

E0: [Asegúrese de rs .]

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 : GOTO paso 7 DEMÁS intercambiar el contenido de R y S.4 L ← R (este primer paso es redundante, pero es útil para una discusión posterior).5 R ← S6 S ← L

E1: [Encontrar 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 Terminé de medir así GOTO 10 DEMÁS medir de nuevo,8 R ← R - S9 [Remainder-loop]: GOTO 7 .

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

10 SI R = 0 ENTONCES hecho GOTO paso 15 DEMÁS CONTINÚE CON el paso 11 ,

E3: [Intercambio s y r ] : La tuerca de algoritmo de Euclides. Utilice el resto r para medir lo que antes era un número menor s ; L sirve como ubicación temporal.

11 L ← R12 R ← S13 S ← L14 [Repetir el proceso de medición]: GOTO 7

SALIDA :

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

HECHO :

16 DETENER, FINALIZAR, DETENER.

Un programa elegante para el algoritmo de Euclides [ editar ]

La siguiente versión del algoritmo de Euclid requiere sólo seis instrucciones básicas para hacer lo que trece deben hacer por "Inelegant"; peor aún, "Inelegant" requiere más tipos de instrucciones. [ aclarar ] 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 Euclid's algoritmo 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  DEJAR  A = A - B  70  GOTO  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-bucles", 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 al 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 = abs ( B );  while  ( B ! = 0 ) {  si  ( A > B )  A = A - B ;  si no  B = B - A ;  }  return  A ; }

Probando los algoritmos de Euclid [ editar ]

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

Pero los "casos excepcionales" [66] deben identificarse y probarse. ¿"Inelegant" funcionará correctamente cuando R> S, S> R, R = S? Lo mismo ocurre con "Elegante": B> A, A> B, A = B? (Sí a todo). ¿Qué sucede cuando un número es cero, ambos números son cero? ("Inelegant" calcula para siempre en todos los casos; "Elegant" 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 enteros positivos, incluido el 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. Un fallo notable debido a excepciones es el fallo del cohete Ariane 5 Flight 501 (4 de junio de 1996).

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". [67] Tausworthe propone que una medida de la complejidad de un programa sea la longitud de su prueba de corrección. [68]

Medición y mejora de los algoritmos de Euclid [ editar ]

Elegancia (compacidad) versus bondad (velocidad) : Con solo seis instrucciones básicas, "Elegante" es el claro ganador, en comparación con "Inelegante" en trece instrucciones. Sin embargo, "Inelegant" es más rápido (llega a HALT en menos pasos). El análisis de algoritmos [69] indica por qué es así: "Elegante" hace dos pruebas condicionales en cada ciclo de resta, mientras que "Inelegante" solo hace una. Como el algoritmo (normalmente) requiere muchos bucles, en promedio se pierde mucho tiempo haciendo un "B = 0?" prueba que se necesita solo después de que se calcule el resto.

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

La compacidad de "Inelegant" se puede mejorar eliminando cinco pasos. Pero Chaitin demostró que la compactación de un algoritmo no puede automatizarse mediante un algoritmo generalizado; [70] más bien, solo se puede hacer de forma heurística ; es decir, mediante búsqueda exhaustiva (se pueden encontrar ejemplos en Busy beaver ), ensayo y error, inteligencia, 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" da 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 "Elegante" 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 requeriría un análisis detallado.

Análisis algorítmico [ editar ]

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 para el análisis de algoritmos para obtener tales respuestas cuantitativas (estimaciones); por ejemplo, el algoritmo de clasificación anterior tiene un requisito de tiempo de O ( n ), utilizando la notación O grande con n como la longitud de la lista. En todo momento, el algoritmo solo necesita recordar dos valores: el número más grande encontrado hasta ahora 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 de tablas en listas o matrices ordenadas.

Formal versus empírico [ editar ]

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 el sentido de que se centra 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ítmicafinalmente 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, comercial o de larga duración, puede ser crítico. El escalado de una n pequeña a una n grande expone con frecuencia 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 se pueden utilizar para comparar antes / después de las posibles mejoras 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 para realizarlas de manera justa. [71]

Eficiencia de ejecución [ editar ]

Para ilustrar las posibles mejoras posibles incluso en algoritmos bien establecidos, una innovación significativa reciente, relacionada con los algoritmos FFT (muy utilizados en el campo del procesamiento de imágenes), puede reducir el tiempo de procesamiento hasta 1000 veces para aplicaciones como la imagen médica. [72] En general, las mejoras de velocidad dependen de propiedades especiales del problema, que son muy comunes en aplicaciones prácticas. [73] 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 [ editar ]

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

Por implementación [ editar ]

Una forma de clasificar los algoritmos es mediante la implementación.

Recursividad
Un algoritmo recursivo es aquel que se invoca (hace referencia a) 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 a la programación funcional . Los algoritmos iterativos utilizan 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 comprenden 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ógico
Un algoritmo puede verse como una deducción lógica controlada . Esta noción se puede expresar como: Algoritmo = lógica + control . [74] El componente lógico expresa los axiomas que pueden usarse 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 suministrando 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 distribuido
Los algoritmos generalmente se discuten con el supuesto de que las computadoras ejecutan una instrucción de un algoritmo a la vez. Esas computadoras a veces se denominan 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 tales algoritmos no es solo los ciclos del 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 determinista
Los algoritmos deterministas resuelven el problema con una decisión exacta en cada paso del algoritmo, mientras que los algoritmos no deterministas resuelven problemas mediante conjeturas, aunque las conjeturas típicas se hacen más precisas mediante el uso de heurísticas .
Exacto o aproximado
Si bien muchos algoritmos alcanzan una solución exacta, los algoritmos de aproximación buscan una aproximación más cercana a la verdadera solución. La aproximación se puede alcanzar utilizando una estrategia determinista o aleatoria. Estos 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 artículo tiene cierto peso y cierto 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 el peso de los artículos así como su valor. [75]
Algoritmo cuántico
Se ejecutan en un modelo realista de computación cuántica . El término se usa generalmente 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 [ editar ]

Otra forma de clasificar los algoritmos es por su metodología de diseño o paradigma . Existe 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 exhaustiva o por fuerza bruta
Este es el método ingenuo de probar todas las soluciones posibles para ver cuál es la mejor. [76]
Divide y conquistaras
Un algoritmo de 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 de forma recursiva ) 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 combinación . La clasificación se puede hacer en cada segmento de datos después de dividir los datos en segmentos y la clasificación de los datos completos se puede obtener en la fase de conquista mediante la fusión de los segmentos. Una variante más simple de dividir y conquistar se llama algoritmo de disminución y conquista., que resuelve un subproblema idéntico y usa la solución de este subproblema para resolver el problema mayor. Dividir y conquistar 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ón
Muchos problemas (como jugar al ajedrez ) se pueden modelar 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 estos problemas. Esta categoría también incluye algoritmos de búsqueda , enumeración de ramas y límites y retroceso .
Algoritmo aleatorizado
Dichos algoritmos toman algunas decisiones de forma aleatoria (o pseudoaleatoria). Pueden ser muy útiles para encontrar soluciones aproximadas para problemas en los que encontrar soluciones exactas puede resultar 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 . [77] Si los algoritmos aleatorios con complejidad de tiempo polinómico pueden ser los algoritmos más rápidos para algunos problemas es una cuestión abierta conocida como el problema P versus NP . Hay dos grandes clases de tales algoritmos:
  1. 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 .
  2. Los algoritmos de Las Vegas siempre devuelven la respuesta correcta, pero su tiempo de ejecución solo está limitado de forma probabilística, por ejemplo, ZPP .
Reducción de complejidad
Esta técnica implica resolver un problema difícil transformándolo en un problema más conocido para el que tenemos (con suerte) algoritmos óptimos asintóticamente . 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 no ordenada implica primero ordenar la lista (la parte cara) y luego sacar el elemento del medio en la lista ordenada (la parte barata). Esta técnica también se conoce como transformar y conquistar .
Seguimiento posterior
En este enfoque, se crean múltiples soluciones de forma incremental y se abandonan cuando se determina que no pueden conducir a una solución completa válida.

Problemas de optimización [ editar ]

Para problemas de optimización hay una clasificación de algoritmos más específica; 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 lineal
Cuando se buscan soluciones óptimas para una función lineal vinculada a restricciones de igualdad y desigualdad lineales, las restricciones del problema se pueden utilizar directamente para producir las soluciones óptimas. Hay algoritmos que pueden resolver cualquier problema en esta categoría, como el popular algoritmo simplex . [78] Los problemas que se pueden resolver con la programación lineal incluyen el problema de flujo máximo para gráficos dirigidos. Si un problema además requiere que una o más de las incógnitas sean un número entero, entonces se clasifica en la programación de números enteros.. Un algoritmo de programación lineal puede resolver este problema si se puede demostrar 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 encuentre soluciones aproximadas, dependiendo de la dificultad del problema.
Programación dinámica
Cuando 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 utilizan para resolver muchas instancias de problemas diferentes, un enfoque más rápido llamado programación dinámica evita volver a calcular soluciones que ya se han calculado. Por ejemplo, en el algoritmo de Floyd-Warshall , el camino más corto a un objetivo desde un vértice en un gráfico ponderado se puede encontrar utilizando el camino más corto al objetivo desde todos los vértices adyacentes. Programación dinámica y memorizaciónir juntos. 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 sencilla está en el almacenamiento en caché o la memorización de llamadas recursivas. Cuando los subproblemas son independientes y no hay repetición, la memorización no ayuda; por tanto, la programación dinámica no es una solución para todos los problemas complejos. Mediante la memorización o el mantenimiento de una tabla de subproblemas ya resueltos, la programación dinámica reduce la naturaleza exponencial de muchos problemas a la complejidad polinomial.
El método codicioso
Un algoritmo codicioso 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 parten de alguna solución, que se puede dar o se ha construido 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 algoritmos codiciosos es encontrar el árbol de expansión mínimo donde es posible encontrar la solución óptima con este método. Árbol Huffman , Kruskal , Prim , Sollin son algoritmos codiciosos que pueden resolver este problema de optimización.
El método heurístico
En problemas de optimización , se pueden utilizar algoritmos heurísticos para encontrar una solución cercana a la solución óptima en los casos en que encontrar la solución óptima no sea 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 período de 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 [ editar ]

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 los algoritmos de búsqueda , algoritmos de ordenación , algoritmos de fusión , algoritmos numéricos , algoritmos de grafos , algoritmos de cuerda , algoritmos geométricos computacionales , algoritmos combinatorios , algoritmos médicos , aprendizaje automático , criptografía , compresión de datos algoritmos y técnicas de análisis sintáctico .

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

Por complejidad [ editar ]

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, el recorrido 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 por 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 en función de la complejidad de los mejores algoritmos posibles para ellos.

Algoritmos continuos [ editar ]

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

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

Problemas legales [ editar ]

Los algoritmos, por sí mismos, no suelen ser patentables. En los Estados Unidos, una afirmació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 , la aplicación de un algoritmo de retroalimentación simple para ayudar en el curado del caucho sintético se consideró patentable. El patentamiento de software es muy controvertido y existen patentes muy criticadas que involucran algoritmos, especialmente algoritmos de compresión de datos , como Unisys.' Patente LZW .

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

Historia: desarrollo de la noción de "algoritmo" [ editar ]

Antiguo Cercano Oriente [ editar ]

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

Los algoritmos para la aritmética también se encuentran en las matemáticas del antiguo Egipto , que se remontan al papiro matemático de Rhind alrededor del 1550 a. C. [10] Los algoritmos se utilizaron más tarde en las matemáticas helenísticas antiguas . Dos ejemplos son el Tamiz de Eratóstenes , que fue descrito en la Introducción a la Aritmética por Nicomachus , [82] [12] : Cap. 9.2 y el algoritmo Euclidiano , que fue descrito por primera vez en Elementos de Euclides (c. 300 AC). [12] : Capítulo 9.1

Símbolos discretos y distinguibles [ editar ]

Marcas de conteo: para llevar un registro de sus rebaños, sus sacos de grano y su dinero, los antiguos usaban el conteo: acumulando piedras o marcas raspadas en palos o haciendo símbolos discretos en arcilla. A través del uso babilónico y egipcio de marcas y símbolos, finalmente 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 unario que se usa en los cálculos de la máquina de Turing y la máquina de Post-Turing .

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

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

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

Algoritmos criptográficos [ editar ]

El primer algoritmo criptográfico para descifrar 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 . [13]

Aparatos mecánicos con estados discretos [ editar ]

El reloj : Bolter acredita la invención del reloj impulsado por peso como "La invención clave [de Europa en la Edad Media]", en particular, el escape de borde [85] que nos proporciona el tic-tac de un reloj mecánico. "La máquina automática precisa" [86] 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. [87]A Lovelace se le atribuye la primera creación de un algoritmo destinado a ser procesado en una computadora (el motor analítico de Babbage, el primer dispositivo considerado una computadora real de Turing completa en lugar de una simple 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 "listones de madera provistos de alfileres, ideados de modo que cualquier parte o clase de las combinaciones [lógicas] pueda seleccionarse mecánicamente ... Más recientemente, sin embargo, he reducido el sistema a una forma completamente mecánica, y así han incorporado la totalidad del proceso indirecto de inferencia en lo que podría llamarse una máquina lógica"Su máquina venía equipada con" ciertas varillas de madera móviles "y" en el pie hay 21 teclas como las de un piano [etc] ... ". Con esta máquina podía analizar un" silogismo o cualquier otro simple argumento lógico ". [88]

Esta máquina la exhibió en 1870 ante los miembros de la Royal Society. [89] Sin embargo, otro lógico, John Venn , en su Lógica simbólica de 1881 , miró con amargura este esfuerzo: "Yo mismo no tengo una gran estimación del interés o la importancia de lo que a veces se llama máquinas lógicas ... para mí, que cualquier invento actualmente conocido o que pueda descubrirse 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, según tengo entendido, al ábaco del profesor Jevon... [Y] [una] ganancia, correspondiente a la máquina lógica del Prof. Jevons, se puede describir la siguiente invención. Prefiero llamarlo simplemente una máquina de diagrama lógico ... pero supongo que podría hacer muy completamente todo lo que se puede esperar racionalmente de cualquier máquina lógica ". [90]

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. [91] A mediados del siglo XIX, el telégrafo , el precursor del teléfono, estaba en uso en todo el mundo, y su codificación discreta y distinguible de letras como "puntos y rayas" era un sonido común. A finales del siglo XIX, la cinta de teletipo (ca 1870) estaba en uso, al igual que el uso de tarjetas Hollerith en el censo estadounidense de 1890. Luego vino el teleimpresor(ca. 1910) con su uso en 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 adición digital. Mientras trabajaba en Bell Laboratories, observó el "oneroso" uso 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 binario" . [92]

Davis (2000) observa la importancia particular del relé electromecánico (con sus dos "estados binarios" abiertos y cerrados ):

Sólo con el desarrollo, a partir de la década de 1930, de las calculadoras electromecánicas que utilizaban relés eléctricos, se construyeron máquinas con el alcance que Babbage había previsto " [93].

Matemáticas durante el siglo XIX hasta mediados del siglo XX [ editar ]

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 ". [94]

Pero Heijenoort le da a Frege (1879) este elogio: Frege es "quizás la obra individual más importante jamás escrita en lógica ... en la que vemos un" 'lenguaje de fórmulas', 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 ". [95] El trabajo de Frege fue simplificado y ampliado aún más por Alfred North Whitehead y Bertrand Russell en sus Principia Mathematica (1910-1913).

Las paradojas : Al mismo tiempo, aparecieron varias paradojas inquietantes en la literatura, en particular, la paradoja de Burali-Forti (1897), la paradoja de Russell (1902-03) y la paradoja de Richard . [96] 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.

Cálculo efectivo : en un esfuerzo por resolver el problema de Entscheidung definido precisamente por Hilbert en 1928, los matemáticos se propusieron por primera vez definir lo que 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 apareció lo siguiente: Alonzo Church , Stephen Kleene y JB Rosser 's λ-calculus [97] una definición finamente perfeccionada de "recursividad general" de la obra de Gödel actuando sobre sugerencias de Jacques Herbrand (cf. 1934) y simplificaciones posteriores de Kleene. [98] Iglesia 's prueba [99]que el Entscheidungsproblem era irresoluble, 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 está allí marcar o borrar un papel u observar el papel y hacer un sí -no decisión sobre la siguiente instrucción. [100] La prueba de Alan Turing de que el problema de la Entscheidung era irresoluble mediante el uso de su "una- [automática-] máquina" [101] —en efecto, casi idéntica a la "formulación" de Post, la definición de J. Barkley Rosser de "método efectivo "en términos de" una máquina ". [102] Propuesta de Kleene de un precursor de la " tesis de la Iglesia "que llamó "Tesis I", [103]y unos años más tarde, Kleene cambió el nombre de su Tesis a "Tesis de Church" [104] y propuso "Tesis de Turing". [105]

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

Emil Post (1936) describió las acciones de una "computadora" (ser humano) de la siguiente manera:

"... se trata de dos conceptos: el de un espacio simbólico en el que se va a realizar el trabajo que lleva del problema a la respuesta, y un conjunto fijo e inalterable de direcciones .

Su espacio simbólico sería

"una secuencia infinita bidireccional de espacios o cajas ... El solucionador de problemas o el trabajador es moverse y trabajar en este espacio simbólico, siendo capaz de estar y operar en una sola caja a la vez ... una caja es admitir dos condiciones posibles, es decir, estar vacío o sin marcar, y tener una sola marca, digamos un trazo vertical.
"Una casilla debe ser señalada y llamada punto de partida. ... un problema específico debe ser dado en forma simbólica por un número finito de casillas [es decir, INPUT] marcadas con un trazo. Asimismo, la respuesta [es decir, , SALIDA] se dará en forma simbólica mediante dicha 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 sólo cuando se trata de la dirección de tipo (C) [es decir, DETENER]". [106] Ver más en Post-Turing machine
Estatua de Alan Turing en Bletchley Park

Alan Turing trabajo 's [107] precedió a la 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 parecido 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 señora 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' ". [108] Dada la prevalencia del código Morse y la telegrafía, las máquinas de teletipo y los teletipos, nosotros [ ¿quién? ] podría 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 simple conjunto de movimientos básicos y "estados mentales". Pero continúa un paso más allá y crea una máquina como modelo de cálculo de números. [109]

"La computación se realiza normalmente escribiendo ciertos símbolos en papel. Podemos suponer que este papel está dividido en cuadrados como un libro de aritmética infantil ... Supongo entonces que el cálculo se lleva a cabo en un papel unidimensional, es decir, en una cinta dividida en cuadrados. Supondré también que el número de símbolos que pueden imprimirse 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 hay 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 mentales que deben tenerse 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 divididas aún más". [110]

La reducción de Turing produce lo siguiente:

Por tanto, las operaciones sencillas deben 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 anteriormente.

"Puede ser que algunos de estos cambios necesariamente invoquen 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 los cuadrados observados, junto con un posible cambio de estado de ánimo"
"Ahora podemos construir una máquina para hacer el trabajo de esta computadora". [110]

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 alguna definición matemática expresable más definida. ... [analiza 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 afirmación literalmente, entendiendo por un proceso puramente mecánico que podría ser realizado por una máquina. Es posible dar una descripción matemática, en una 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". [111]

JB Rosser (1939) y SC Kleene (1943) [ editar ]

J. Barkley Rosser definió un 'método [matemático] efectivo' de la siguiente manera (cursiva agregada):

"'Método efectivo' se utiliza aquí en el sentido bastante especial de un método en el que cada paso está determinado con precisión y que seguramente 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 al pie de página # 5; ver la discusión inmediatamente a continuación]. El más simple de estos de afirmar (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 (más tarde) 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 fuerte a favor de la exactitud de cualquiera "(Rosser 1939: 225-226).

La nota al pie No. 5 de Rosser hace referencia al trabajo de (1) Church y Kleene y su definición de definibilidad de λ, en particular el uso de Church 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 las proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados I (1931); y (3) Post (1936) y Turing (1936-1937) en sus modelos de mecanismo 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, ejecutable para cada conjunto de valores de las variables independientes, cuyo procedimiento necesariamente termina y de tal manera que a partir del resultado podemos leer una respuesta definitiva, "sí" o "no", a la pregunta, "¿es verdadero el valor del predicado?" "(Kleene 1943: 273)

Historia después de 1950 [ editar ]

Se han dirigido varios esfuerzos hacia un mayor refinamiento de la definición de "algoritmo", y la actividad está en curso debido a cuestiones que rodean, en particular, 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 .

Ver también [ editar ]

  • Máquina abstracta
  • Ingeniería de algoritmos
  • Caracterizaciones de algoritmos
  • Composición algorítmica
  • Entidades algorítmicas
  • Síntesis algorítmica
  • Técnica algorítmica
  • Topología algorítmica
  • Basura dentro basura fuera
  • Introducción a los algoritmos (libro de texto)
  • Lista de algoritmos
  • Lista de temas generales de algoritmos
  • Lista de publicaciones importantes en informática teórica - Algoritmos
  • Regulación de algoritmos
  • Teoría de la computación
    • Teoría de la computabilidad
    • Teoría de la complejidad computacional

Notas [ editar ]

  1. ^ "El glosario definitivo de jerga matemática superior - algoritmo" . Bóveda de matemáticas . 1 de agosto de 2019. Archivado desde el original el 28 de febrero de 2020 . Consultado el 14 de noviembre de 2019 .
  2. ^ "Definición de ALGORITMO" . Diccionario en línea Merriam-Webster . Archivado desde el original el 14 de febrero de 2020 . Consultado el 14 de noviembre de 2019 .
  3. ^ "Cualquier algoritmo matemático clásico, por ejemplo, puede describirse en un número finito de palabras en inglés" (Rogers 1987: 2).
  4. ^ Bien definido con respecto al agente que ejecuta el algoritmo: "Existe un agente informático, generalmente humano, que puede reaccionar a las instrucciones y realizar los cálculos" (Rogers 1987: 2).
  5. ^ "un algoritmo es un procedimiento para calcular una función (con respecto a alguna notación elegida para números enteros) ... esta limitación (a las funciones numéricas) no da como resultado una pérdida de generalidad", (Rogers 1987: 1).
  6. ^ "Un algoritmo tiene cero o más entradas, es decir, cantidades que se le dan inicialmente antes de que comience el algoritmo" (Knuth 1973: 5).
  7. ^ "Un procedimiento que tiene todas las características de un algoritmo excepto que posiblemente carece de finitud puede llamarse un 'método computacional ' " (Knuth 1973: 5).
  8. ^ "Un algoritmo tiene una o más salidas, es decir, cantidades que tienen una relación específica con las entradas" (Knuth 1973: 5).
  9. ^ Es discutible si un proceso con procesos interiores aleatorios (sin incluir la entrada) es un algoritmo. Rogers opina que: "un cálculo se lleva a cabo de manera discreta por pasos, sin el uso de métodos continuos o dispositivos analógicos ... llevado adelante de manera determinista, sin recurrir a métodos o dispositivos aleatorios, por ejemplo, dados" (Rogers 1987: 2) .
  10. ↑ a b c Chabert, Jean-Luc (2012). Una historia de algoritmos: del guijarro al microchip . Springer Science & Business Media. págs. 7-8. ISBN 9783642181924.
  11. ^ a b "Matemáticas helenísticas" . La historia de las matemáticas. Archivado desde el original el 11 de septiembre de 2019 . Consultado el 14 de noviembre de 2019 .
  12. ↑ a b c Cooke, Roger L. (2005). La historia de las matemáticas: un curso breve . John Wiley e hijos. ISBN 978-1-118-46029-0.
  13. ↑ a b Dooley, John F. (2013). Una breve historia de la criptología y los algoritmos criptográficos . Springer Science & Business Media. págs. 12–3. ISBN 9783319016283.
  14. ^ "Al-Khwarizmi - Matemáticas islámicas" . La historia de las matemáticas. Archivado desde el original el 25 de julio de 2019 . Consultado el 14 de noviembre de 2019 .
  15. ^ Kleene 1943 en Davis 1965: 274
  16. ^ Rosser 1939 en Davis 1965: 225
  17. ^ "Biografía de Al-Khwarizmi" . www-history.mcs.st-andrews.ac.uk . Archivado desde el original el 2 de agosto de 2019 . Consultado el 3 de mayo de 2017 .
  18. ^ "Etimología del algoritmo" . Diccionario de Cámaras . Archivado desde el original el 31 de marzo de 2019 . Consultado el 13 de diciembre de 2016 .
  19. Hogendijk, Jan P. (1998). "al-Khwarzimi" . Pitágoras . 38 (2): 4–5. Archivado desde el original el 12 de abril de 2009.
  20. ^ Oaks, Jeffrey A. "¿Fue al-Khwarizmi un algebrista aplicado?" . Universidad de Indianápolis . Archivado desde el original el 18 de julio de 2011 . Consultado el 30 de mayo de 2008 .
  21. ^ Brezina, Corona (2006). Al-Khwarizmi: el inventor del álgebra . El Grupo Editorial Rosen. ISBN 978-1-4042-0513-0.
  22. ^ Los textos matemáticos más importantes de la historia Archivado el 9 de junio de 2011 en la Wayback Machine , según Carl B. Boyer .
  23. ^ "algorismic" , The Free Dictionary , archivado desde el original el 21 de diciembre de 2019 , obtenido el 14 de noviembre de 2019
  24. ^ Diccionario de inglés de Oxford , tercera edición, 2012 sv
  25. ^ Mehri, Bahman (2017). "De Al-Khwarizmi al algoritmo". Olimpíadas de Informática . 11 (2): 71–74. doi : 10.15388 / ioi.2017.special.11 .
  26. ^ "Abu Jafar Muhammad ibn Musa al-Khwarizmi" . miembros.peak.org . Archivado desde el original el 21 de agosto de 2019 . Consultado el 14 de noviembre de 2019 .
  27. ^ Piedra 1973: 4
  28. ^ Simanowski, Roberto (2018). El algoritmo de la muerte y otros dilemas digitales . Meditaciones intempestivas. 14 . Traducido por Chase, Jefferson. Cambridge, Massachusetts: MIT Press. pag. 147. ISBN 9780262536370. Archivado desde el original el 22 de diciembre de 2019 . Consultado el 27 de mayo de 2019 . [...] el siguiente nivel de abstracción de la burocracia central: algoritmos que operan globalmente.
  29. ^ Dietrich, Eric (1999). "Algoritmo". En Wilson, Robert Andrew; Keil, Frank C. (eds.). La Enciclopedia de Ciencias Cognitivas del MIT . Biblioteca MIT Cognet. Cambridge, Massachusetts: MIT Press (publicado en 2001). pag. 11. ISBN 9780262731447. Consultado el 22 de julio de 2020 . Un algoritmo es una receta, método o técnica para hacer algo.
  30. Stone simplemente requiere que "debe terminar en un número finito de pasos" (Stone 1973: 7-8).
  31. ^ Boolos y Jeffrey 1974, 1999: 19
  32. cf Stone 1972: 5
  33. ^ Knuth 1973: 7 afirma: "En la práctica, no solo queremos algoritmos, queremos buenos algoritmos ... un criterio de bondad es el tiempo que lleva realizar el algoritmo ... otros criterios son la adaptabilidad del algoritmo a las computadoras , su sencillez y elegancia, etc. "
  34. cf Stone 1973: 6
  35. Stone 1973: 7-8 establece que debe haber, "... un procedimiento que un robot [es decir, una computadora] pueda seguir para determinar con precisión cómo obedecer la instrucción". Stone agrega finitud del proceso y precisión (sin ambigüedad en las instrucciones) a esta definición.
  36. ^ Knuth, loc. cit
  37. ^ Minsky 1967 , p. 105
  38. Gurevich 2000: 1, 3
  39. ^ Sipser 2006: 157
  40. ^ Goodrich, Michael T .; Tamassia, Roberto (2002), Diseño de algoritmos: fundamentos, análisis y ejemplos de Internet , John Wiley & Sons, Inc., ISBN 978-0-471-38365-9, archivado desde el original el 28 de abril de 2015 , consultado el 14 de junio de 2018
  41. ^ Knuth 1973: 7
  42. ^ Chaitin 2005: 32
  43. ^ Rogers 1987: 1–2
  44. En su ensayo "Calculations by Man and Machine: Conceptual Analysis" Seig 2002: 390 atribuye esta distinción a Robin Gandy, cf. Wilfred Seig, et al., 2002 Reflexiones sobre los fundamentos de las matemáticas: Ensayos en honor de Solomon Feferman , Association for Lógica simbólica, AK Peters Ltd, Natick, MA.
  45. ^ cf Gandy 1980: 126, Tesis y principios para los mecanismos de Robin Gandy Church que aparecen en las págs. 123-148 en J. Barwise et al. 1980 El Simposio de Kleene , North-Holland Publishing Company.
  46. ^ Un "robot": "Una computadora es un robot que realiza cualquier tarea que pueda describirse como una secuencia de instrucciones". cf Stone 1972: 3
  47. ^ El "ábaco" de Lambek es un "número infinito contable de ubicaciones (agujeros, alambres, etc.) junto con un suministro ilimitado de contadores (guijarros, cuentas, etc.). Las ubicaciones son distinguibles, los contadores no". Los agujeros tienen una capacidad ilimitada, y hay un agente que comprende y es capaz de llevar a cabo la lista de instrucciones "(Lambek 1961: 295). Lambek hace referencia a Melzak, quien define su máquina Q como" un número indefinidamente grande de ubicaciones. .. un suministro indefinidamente grande de contadores distribuidos entre estas ubicaciones, un programa y un operador cuyo único propósito es ejecutar el programa "(Melzak 1961: 283). BBJ (loc. cit.) agrega la estipulación de que los agujeros son "capaz de contener cualquier número de piedras" (p. 46).Tanto Melzak como Lambek aparecen en The Canadian Mathematical Bulletin, vol. 4, no. 3, septiembre de 1961.
  48. ^ Si no se produce confusión, se puede eliminar la palabra "contadores" y se puede decir que una ubicación contiene un solo "número".
  49. ^ "Decimos que una instrucción es efectiva si existe un procedimiento que el robot puede seguir para determinar con precisión cómo obedecer la instrucción". (Piedra 1972: 6)
  50. ^ cf Minsky 1967: Capítulo 11 "Modelos de computadora" y Capítulo 14 "Bases muy simples para la computabilidad" pp. 255-281, en particular,
  51. ^ cf Knuth 1973: 3.
  52. ^ Pero siempre precedido de SI-ENTONCES para evitar una resta incorrecta.
  53. ^ Knuth 1973: 4
  54. ^ Piedra 1972: 5. Los métodos para extraer raíces no son triviales: consulte Métodos para calcular raíces cuadradas .
  55. ^ Leeuwen, enero (1990). Manual de Informática Teórica: Algoritmos y complejidad. Un volumen . Elsevier. pag. 85. ISBN 978-0-444-88071-0.
  56. ^ John G. Kemeny y Thomas E. Kurtz 1985 De vuelta a lo básico: la historia, la corrupción y el futuro del idioma , Addison-Wesley Publishing Company, Inc. Reading, MA, ISBN 0-201-13433-0 . 
  57. ^ Tausworthe 1977: 101
  58. ^ Tausworthe 1977: 142
  59. ^ Knuth 1973 sección 1.2.1, ampliado por Tausworthe 1977 en las páginas 100ff y Capítulo 9.1
  60. ^ cf Tausworthe 1977
  61. Heath 1908: 300; La edición de Hawking's Dover 2005 se deriva de Heath.
  62. ^ "'Deje CD, midiendo BF, deje FA menos que él mismo'. Ésta es una abreviatura clara para decir, medir a lo largo de BA longitudes sucesivas iguales a CD hasta que se alcance un punto F tal que la longitud FA restante sea menor que CD; en otras palabras, sea BF el mayor múltiplo exacto de CD contenido en BA " (Heath 1908: 297)
  63. Para tratamientos modernos que utilizan la división en el algoritmo, consulte Hardy y Wright 1979: 180, Knuth 1973: 2 (Volumen 1), además de más discusión sobre el algoritmo de Euclides en Knuth 1969: 293-297 (Volumen 2).
  64. ^ Euclides cubre esta cuestión en su Proposición 1.
  65. ^ "Elementos de Euclides, libro VII, propuesta 2" . Aleph0.clarku.edu. Archivado desde el original el 24 de mayo de 2012 . Consultado el 20 de mayo de 2012 .
  66. ^ Si bien esta noción es de uso generalizado, no se puede definir con precisión.
  67. ^ Knuth 1973: 13-18. Él acredita "la formulación de la demostración de algoritmos en términos de afirmaciones e inducción" a R W. Floyd, Peter Naur, CAR Hoare, HH Goldstine y J. von Neumann. Tausworth 1977 toma prestado el ejemplo de Euclides de Knuth y amplía el método de Knuth en la sección 9.1 Pruebas formales (págs. 288-298).
  68. ^ Tausworthe 1997: 294
  69. cf Knuth 1973: 7 (Vol. I), y sus análisis más detallados en pp. 1969: 294-313 (Vol II).
  70. ^ La avería se produce cuando un algoritmo intenta compactarse. El éxito resolvería el problema de la detención .
  71. ^ Kriegel, Hans-Peter ; Schubert, Erich; Zimek, Arthur (2016). "El arte (negro) de la evaluación en tiempo de ejecución: ¿estamos comparando algoritmos o implementaciones?". Sistemas de conocimiento e información . 52 (2): 341–378. doi : 10.1007 / s10115-016-1004-2 . ISSN 0219-1377 . S2CID 40772241 .  
  72. ^ Gillian Conahan (enero de 2013). "Mejor matemática hace redes de datos más rápidas" . discovermagazine.com. Archivado desde el original el 13 de mayo de 2014 . Consultado el 13 de mayo de 2014 .
  73. ^ Haitham Hassanieh, Piotr Indyk , Dina Katabi y Eric Price, " Simposio ACM-SIAM sobre algoritmos discretos (SODA) Archivado el 4 de julio de 2013 en Wayback Machine , Kyoto, enero de 2012. Véase también la página web sFFT Archivada el 21 de febrero , 2012, en la Wayback Machine .
  74. ^ Kowalski 1979
  75. ^ Problemas con la mochila | Hans Kellerer | Springer . Saltador. 2004. ISBN 978-3-540-40286-2. Archivado desde el original el 18 de octubre de 2017 . Consultado el 19 de septiembre de 2017 .
  76. ^ Carroll, Sue; Daughtrey, Taz (4 de julio de 2007). Conceptos fundamentales para el ingeniero de calidad de software . Sociedad Estadounidense para la Calidad. págs. 282 y siguientes. ISBN 978-0-87389-720-4.
  77. ^ Por ejemplo, el volumen de un politopo convexo (descrito usando un oráculo de membresía) puede aproximarse con alta precisión mediante un algoritmo de tiempo polinomial aleatorio, pero no mediante uno determinista: ver Dyer, Martin; Frieze, Alan; Kannan, Ravi (enero de 1991), "A Random Polinomial-time Algorithm for Approximating the Volume of Convex Bodies", J. ACM , 38 (1): 1-17, CiteSeerX 10.1.1.145.4600 , doi : 10.1145 / 102782.102783 , S2CID 13268711  .
  78. ^ George B. Dantzig y Mukund N. Thapa. 2003. Programación Lineal 2: Teoría y Extensiones . Springer-Verlag.
  79. ^ Tsypkin (1971). Adaptación y aprendizaje en sistemas automáticos . Prensa académica. pag. 54. ISBN 978-0-08-095582-7.
  80. ^ Knuth, Donald E. (1972). "Algoritmos babilónicos antiguos" (PDF) . Comun. ACM . 15 (7): 671–677. doi : 10.1145 / 361454.361514 . ISSN 0001-0782 . S2CID 7829945 . Archivado desde el original (PDF) el 24 de diciembre de 2012.   
  81. ^ Aaboe, Asger (2001), Episodios de la historia temprana de la astronomía , Nueva York: Springer, págs. 40-62, ISBN 978-0-387-95136-2
  82. ^ Ast, Courtney. "Eratóstenes" . Universidad Estatal de Wichita: Departamento de Matemáticas y Estadística. Archivado desde el original el 27 de febrero de 2015 . Consultado el 27 de febrero de 2015 .
  83. ^ Chabert, Jean-Luc (2012). Una historia de algoritmos: del guijarro al microchip . Springer Science & Business Media. pag. 2. ISBN 9783642181924.
  84. Davis 2000: 18
  85. Bolter 1984: 24
  86. Bolter 1984: 26
  87. Bolter 1984: 33–34, 204–206.
  88. ^ Todas las citas de W. Stanley Jevons 1880 Lecciones elementales de lógica: deductiva e inductiva , Macmillan and Co., Londres y Nueva York. Republicado como un googlebook; cf Jevons 1880: 199-201. Louis Couturat 1914 el Álgebra de la lógica , The Open Court Publishing Company, Chicago y Londres. Republicado como un googlebook; cf Couturat 1914: 75–76 da algunos detalles más; lo compara con una máquina de escribir y con un piano. Jevons afirma que el relato se encuentra en The Proceedings of the Royal Society del 20 de enero de 1870.
  89. ^ Jevons 1880: 199-200
  90. ^ Todas las citas de John Venn 1881 Symbolic Logic , Macmillan and Co., Londres. Republicado como un googlebook. cf Venn 1881: 120-125. El lector interesado puede encontrar una explicación más profunda en esas páginas.
  91. ^ Diagrama de Bell y Newell 1971: 39, cf. Davis 2000
  92. ^ * Melina Hill, corresponsal de Valley News, A Tinkerer consigue un lugar en la historia , Valley News West Lebanon NH, jueves 31 de marzo de 1983, p. 13.
  93. Davis 2000: 14
  94. van Heijenoort 1967: 81ff
  95. El comentario de van Heijenoort sobre la Begriffsschrift de Frege , un lenguaje de fórmulas, modelado sobre el de la aritmética, para el pensamiento puro en van Heijenoort 1967: 1
  96. Dixon 1906, cf. Kleene 1952: 36–40
  97. ^ cf. nota a pie de página en Alonzo Church 1936a en Davis 1965: 90 y 1936b en Davis 1965: 110
  98. ^ Kleene 1935-6 en Davis 1965: 237ff, Kleene 1943 en Davis 1965: 255ff
  99. ^ Iglesia 1936 en Davis 1965: 88ff
  100. ^ cf. "Procesos combinatorios finitos - formulación 1", posterior a 1936 en Davis 1965: 289-290
  101. ^ Turing 1936–37 en Davis 1965: 116ff
  102. ^ Rosser 1939 en Davis 1965: 226
  103. ^ Kleene 1943 en Davis 1965: 273–274
  104. Kleene 1952: 300, 317
  105. ^ Kleene 1952: 376
  106. ^ Turing 1936–37 en Davis 1965: 289–290
  107. ^ Turing 1936 en Davis 1965, Turing 1939 en Davis 1965: 160
  108. ^ Hodges, pág. 96
  109. ^ Turing, 1936–37: 116
  110. ^ a b Turing 1936–37 en Davis 1965: 136
  111. ^ Turing 1939 en Davis 1965: 160

Bibliografía [ editar ]

  • Axt, P (1959). "En una jerarquía subrecursiva y grados recursivos primitivos" . Transacciones de la American Mathematical Society . 92 (1): 85-105. doi : 10.2307 / 1993169 . JSTOR  1993169 .
  • Bell, C. Gordon y Newell, Allen (1971), Estructuras informáticas: lecturas y ejemplos , McGraw – Hill Book Company, Nueva York. ISBN 0-07-004357-4 . 
  • Blass, Andreas ; Gurevich, Yuri (2003). "Algoritmos: una búsqueda de definiciones absolutas" (PDF) . Boletín de la Asociación Europea de Ciencias de la Computación Teórica . 81 . Incluye una excelente bibliografía de 56 referencias.
  • Bolter, David J. (1984). El hombre de Turing: cultura occidental en la era de la informática (ed. 1984). Chapel Hill, NC: Prensa de la Universidad de Carolina del Norte. ISBN 978-0-8078-1564-9., ISBN 0-8078-4108-0 
  • Boolos, George ; Jeffrey, Richard (1999) [1974]. Computabilidad y lógica (4ª ed.). Cambridge University Press, Londres. ISBN 978-0-521-20402-6.: cf. Capítulo 3 Máquinas de Turing donde discuten "ciertos conjuntos enumerables no efectivamente (mecánicamente) enumerables".
  • Burgin, Mark (2004). Algoritmos superrecursivos . Saltador. ISBN 978-0-387-95569-8.
  • Campagnolo, ML, Moore, C. y Costa, JF (2000) Una caracterización analógica de las funciones subrecursivas. En Proc. de la 4ª Conferencia sobre Números y Computadoras Reales , Universidad de Odense, págs. 91–109
  • Iglesia, Alonzo (1936a). "Un problema irresoluble de la teoría de números elemental". The American Journal of Mathematics . 58 (2): 345–363. doi : 10.2307 / 2371045 . JSTOR  2371045 .Reimpreso en The Undecidable , p. 89ff. La primera expresión de la "Tesis de la Iglesia". Ver en particular la página 100 ( Lo indecidible ) donde define la noción de "calculabilidad efectiva" en términos de "un algoritmo", y usa la palabra "termina", etc.
  • Iglesia, Alonzo (1936b). "Una nota sobre el Entscheidungsproblem". El diario de la lógica simbólica . 1 (1): 40–41. doi : 10.2307 / 2269326 . JSTOR  2269326 . Iglesia, Alonzo (1936). "Corrección de una nota sobre el Entscheidungsproblem". El diario de la lógica simbólica . 1 (3): 101-102. doi : 10.2307 / 2269030 . JSTOR  2269030 .Reimpreso en The Undecidable , p. 110ff. Church muestra que el problema de la Entscheidung es irresoluble en aproximadamente 3 páginas de texto y 3 páginas de notas al pie.
  • Daffa ', Ali Abdullah al- (1977). La contribución musulmana a las matemáticas . Londres: Croom Helm. ISBN 978-0-85664-464-1.
  • Davis, Martin (1965). Lo indecidible: artículos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables . Nueva York: Raven Press. ISBN 978-0-486-43228-1.Davis da comentarios antes de cada artículo. Se incluyen artículos de Gödel , Alonzo Church , Turing , Rosser , Kleene y Emil Post ; los citados en el artículo se enumeran aquí por nombre de autor.
  • Davis, Martín (2000). Motores de la lógica: matemáticos y el origen de la computadora . Nueva York: WW Nortion. ISBN 978-0-393-32229-3.Davis ofrece biografías concisas de Leibniz , Boole , Frege , Cantor , Hilbert , Gödel y Turing con von Neumann como el villano que roba el espectáculo. Biografías muy breves de Joseph-Marie Jacquard , Babbage , Ada Lovelace , Claude Shannon , Howard Aiken , etc.
  •  Este artículo incorpora material de dominio público  del  documento NIST :  Black, Paul E. "algoritmo" . Diccionario de algoritmos y estructuras de datos .
  • Dean, Tim (2012). "Evolución y diversidad moral" . Anuario internacional báltico de cognición, lógica y comunicación . 7 . doi : 10.4148 / biyclc.v7i0.1775 .
  • Dennett, Daniel (1995). La peligrosa idea de Darwin . Complejidad . 2 . Nueva York: Touchstone / Simon & Schuster. págs.  32 –36. Bibcode : 1996Cmplx ... 2a..32M . doi : 10.1002 / (SICI) 1099-0526 (199609/10) 2: 1 <32 :: AID-CPLX8> 3.0.CO; 2-H . ISBN 978-0-684-80290-9.
  • Dilson, Jesse (2007). El ábaco ((1968, 1994) ed.). St. Martin's Press, Nueva York. ISBN 978-0-312-10409-2., ISBN 0-312-10409-X 
  • Yuri Gurevich , Sequential Abstract State Machines Capture Sequential Algorithms , ACM Transactions on Computational Logic, Vol 1, no 1 (julio de 2000), págs. 77-111. Incluye bibliografía de 33 fuentes.
  • van Heijenoort, Jean (2001). De Frege a Gödel, A Source Book in Mathematical Logic, 1879-1931 ((1967) ed.). Prensa de la Universidad de Harvard, Cambridge. ISBN 978-0-674-32449-7., 3ª edición 1976 [?], ISBN 0-674-32449-8 (pbk.) 
  • Hodges, Andrew (1983). Alan Turing: El enigma . Física hoy . 37 . Nueva York: Simon y Schuster . págs. 107–108. Código bibliográfico : 1984PhT .... 37k.107H . doi : 10.1063 / 1.2915935 . ISBN 978-0-671-49207-6., ISBN 0-671-49207-1 . Cf. Capítulo "El espíritu de la verdad" para una historia que conduzca y una discusión de su prueba. 
  • Kleene, Stephen C. (1936). "Funciones recursivas generales de números naturales" . Mathematische Annalen . 112 (5): 727–742. doi : 10.1007 / BF01565439 . S2CID  120517999 . Archivado desde el original el 3 de septiembre de 2014 . Consultado el 30 de septiembre de 2013 .Presentado a la American Mathematical Society, septiembre de 1935. Reimpreso en The Undecidable , p. 237ff. La definición de Kleene de "recursividad general" (conocida ahora como recursión mu) fue utilizada por Church en su artículo de 1935 An Unsolvable Problem of Elementary Number Theory que probó que el "problema de decisión" era "indecidible" (es decir, un resultado negativo).
  • Kleene, Stephen C. (1943). "Predicados y cuantificadores recursivos" . Transacciones de la Sociedad Americana de Matemáticas . 54 (1): 41–73. doi : 10.2307 / 1990131 . JSTOR  1990131 .Reimpreso en The Undecidable , p. 255ff. Kleene refinó su definición de "recursividad general" y procedió en su capítulo "12. Teorías algorítmicas" a postular "Tesis I" (p. 274); más tarde repetiría esta tesis (en Kleene 1952: 300) y la denominaría "Tesis de la Iglesia" (Kleene 1952: 317) (es decir, la tesis de la Iglesia ).
  • Kleene, Stephen C. (1991) [1952]. Introducción a la Metamatemática (Décima ed.). Compañía editorial de Holanda Septentrional. ISBN 978-0-7204-2103-3.
  • Knuth, Donald (1997). Algoritmos fundamentales, tercera edición . Reading, Massachusetts: Addison – Wesley. ISBN 978-0-201-89683-1.
  • Knuth, Donald (1969). Volumen 2 / Algoritmos seminuméricos, El arte de la programación informática Primera edición . Reading, Massachusetts: Addison – Wesley.
  • Kosovsky, NK Elements of Mathematical Logic y su aplicación a la teoría de algoritmos subrecursivos , LSU Publ., Leningrado, 1981
  • Kowalski, Robert (1979). "Algoritmo = Lógica + Control". Comunicaciones de la ACM . 22 (7): 424–436. doi : 10.1145 / 359131.359136 . S2CID  2509896 .
  • AA Markov (1954) Teoría de algoritmos . [Traducido por Jacques J. Schorr-Kon y personal del PST] Pie de imprenta Moscú, Academia de Ciencias de la URSS, 1954 [es decir, Programa de Traducciones Científicas de Jerusalén, Israel, 1961; disponible en la Oficina de Servicios Técnicos, Departamento de Comercio de EE. UU., Washington] Descripción 444 p. 28 cm. Añadido tp en Traducción rusa de obras del Instituto de Matemáticas, Academia de Ciencias de la URSS, v. 42. Título original: Teoriya algerifmov. [QA248.M2943 Biblioteca de Dartmouth College. Departamento de Comercio de EE. UU., Oficina de Servicios Técnicos, número OTS 60-51085.]
  • Minsky, Marvin (1967). Computación: máquinas finitas e infinitas (Primera ed.). Prentice-Hall, Englewood Cliffs, Nueva Jersey. ISBN 978-0-13-165449-5.Minsky amplía su "... idea de un algoritmo - un procedimiento eficaz ..." en el capítulo 5.1 Computabilidad, procedimientos eficaces y algoritmos. Máquinas infinitas.
  • Publicar, Emil (1936). "Procesos combinatorios finitos, Formulación I". El diario de la lógica simbólica . 1 (3): 103-105. doi : 10.2307 / 2269031 . JSTOR  2269031 .Reimpreso en The Undecidable , págs. 289 y siguientes. Post define un proceso simple de tipo algorítmico en el que un hombre escribe o borra marcas y va de una caja a otra y finalmente se detiene, mientras sigue una lista de instrucciones simples. Esto es citado por Kleene como una de las fuentes de su "Tesis I", la llamada tesis de Church-Turing .
  • Rogers, Jr., Hartley (1987). Teoría de funciones recursivas y computabilidad efectiva . La prensa del MIT. ISBN 978-0-262-68052-3.
  • Rosser, JB (1939). "Una exposición informal de las pruebas del teorema de Gödel y el teorema de la Iglesia". Revista de lógica simbólica . 4 (2): 53–60. doi : 10.2307 / 2269059 . JSTOR  2269059 .Reimpreso en The Undecidable , p. 223ff. Aquí está la famosa definición de Rosser de "método efectivo": "... un método cada paso del cual está predeterminado con precisión y que seguramente producirá la respuesta en un número finito de pasos ... una máquina que luego resolverá cualquier problema de el conjunto sin intervención humana más allá de insertar la pregunta y (más tarde) leer la respuesta "(p. 225-226, The Undecidable )
  • Santos-Lang, Christopher (2014). "Enfoques de la ecología moral a la ética de las máquinas" (PDF) . En van Rysewyk, Simon; Pontier, Matthijs (eds.). Ética Médica de la Máquina . Sistemas Inteligentes, Control y Automatización: Ciencia e Ingeniería. 74 . Suiza: Springer. págs. 111-127. doi : 10.1007 / 978-3-319-08108-3_8 . ISBN 978-3-319-08107-6.
  • Scott, Michael L. (2009). Pragmática del lenguaje de programación (3ª ed.). Editorial Morgan Kaufmann / Elsevier. ISBN 978-0-12-374514-9.
  • Sipser, Michael (2006). Introducción a la Teoría de la Computación . Compañía Editorial PWS. ISBN 978-0-534-94728-6.
  • Sobrio, Elliott; Wilson, David Sloan (1998). Hacia los demás: la evolución y psicología del comportamiento desinteresado . Cambridge: Prensa de la Universidad de Harvard.
  • Stone, Harold S. (1972). Introducción a la organización informática y las estructuras de datos (ed. 1972). McGraw-Hill, Nueva York. ISBN 978-0-07-061726-1.Cf. en particular, el primer capítulo titulado: Algoritmos, máquinas de Turing y programas . Su sucinta definición informal: "... cualquier secuencia de instrucciones que pueda ser obedecida por un robot, se llama algoritmo " (p. 4).
  • Tausworthe, Robert C (1977). Desarrollo estandarizado de métodos de software de computadora Parte 1 . Englewood Cliffs Nueva Jersey: Prentice – Hall, Inc. ISBN 978-0-13-842195-3.
  • Turing, Alan M. (1936-1937). "Sobre números computables, con una aplicación al problema Entscheidungs". Actas de la London Mathematical Society . Serie 2. 42 : 230-265. doi : 10.1112 / plms / s2-42.1.230 .. Correcciones, ibid, vol. 43 (1937) págs. 544–546. Reimpreso en The Undecidable , p. 116ff. El famoso trabajo de Turing se completó como disertación de maestría mientras estaba en King's College Cambridge UK.
  • Turing, Alan M. (1939). "Sistemas de lógica basados ​​en ordinales". Actas de la London Mathematical Society . 45 : 161-228. doi : 10.1112 / plms / s2-45.1.161 . hdl : 21.11116 / 0000-0001-91CE-3 .Reimpreso en The Undecidable , págs. 155ff. El trabajo de Turing que definió "el oráculo" fue su tesis doctoral mientras estuvo en Princeton.
  • Oficina de Patentes y Marcas de los Estados Unidos (2006), 2106.02 **> Algoritmos matemáticos: patentabilidad 2100 , Manual de procedimiento de examen de patentes (MPEP). Última revisión agosto de 2006

Lectura adicional [ editar ]

  • Bellah, Robert Neelly (1985). Hábitos del corazón: individualismo y compromiso en la vida estadounidense . Berkeley: Prensa de la Universidad de California. ISBN 978-0-520-25419-0.
  • Berlinski, David (2001). El advenimiento del algoritmo: el viaje de 300 años desde una idea a la computadora . Libros de cosecha. ISBN 978-0-15-601391-8.
  • Chabert, Jean-Luc (1999). Una historia de algoritmos: del guijarro al microchip . Springer Verlag. ISBN 978-3-540-63369-3.
  • Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introducción a los algoritmos (3ª ed.). MIT Press. ISBN 978-0-262-03384-8.
  • Harel, David; Feldman, Yishai (2004). Algoritmos: el espíritu de la informática . Addison-Wesley. ISBN 978-0-321-11784-7.
  • Hertzke, Allen D .; McRorie, Chris (1998). "El concepto de ecología moral". En Lawler, Peter Augustine; McConkey, Dale (eds.). Comunidad y pensamiento político hoy . Westport, CT: Praeger .
  • Knuth, Donald E. (2000). Artículos seleccionados sobre análisis de algoritmos . Stanford, California: Centro para el estudio del lenguaje y la información.
  • Knuth, Donald E. (2010). Artículos seleccionados sobre diseño de algoritmos . Stanford, California: Centro para el estudio del lenguaje y la información.
  • Wallach, Wendell; Allen, Colin (noviembre de 2008). Máquinas morales: enseñar a los robots lo correcto de lo incorrecto . Estados Unidos: Oxford University Press. ISBN 978-0-19-537404-9.

Enlaces externos [ editar ]

  • "Algoritmo" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
  • Algoritmos en Curlie
  • Weisstein, Eric W. "Algoritmo" . MathWorld .
  • Diccionario de algoritmos y estructuras de datos - Instituto Nacional de Estándares y Tecnología
Repositorios de algoritmos
  • El repositorio de algoritmos de Stony Brook - Universidad Estatal de Nueva York en Stony Brook
  • Algoritmos recopilados de la ACM - Association for Computing Machinery
  • The Stanford GraphBase - Universidad de Stanford