algoritmo - Algorithm


De Wikipedia, la enciclopedia libre

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 denominados A y B. El algoritmo procede por sustracciones sucesivas en dos bucles: Si la prueba B ≥ A produce "sí" (o verdadero) (con más precisión el número b en la ubicación B es mayor que o igual que el número de una en la ubicación a), entonces, el algoritmo especifica B ← B - a (es decir, el número b - una sustituye a la antigua b). Del mismo modo, si a> b, entonces a ← A - B. El proceso termina cuando (el contenido de) B es 0, produciendo el gcd en A. (algoritmo derivado de Scott 2009: 13; símbolos y estilo de dibujo de Tausworthe 1977) .

En matemáticas y ciencias de la computación , un algoritmo ( / æ l del ɡ del ə r ɪ ð əm /  ( escuchar )Acerca de este sonido ) es una especificación inequívoca de cómo resolver una clase de problemas. Los algoritmos pueden realizar el cálculo , procesamiento de datos y razonamiento automatizado tareas.

Como un método eficaz , un algoritmo puede expresarse dentro de una cantidad finita de espacio y tiempo y en un lenguaje formal bien definido para el cálculo de una función . A partir de una entrada inicial estado e inicial (tal vez vacío ), las instrucciones describen un cálculo que, cuando se ejecuta , procede a través de un número finito de estados sucesivos bien definidos, con el tiempo la producción de "salida" y que 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.

El concepto de algoritmo ha existido durante siglos. Matemáticos griegos utilizan algoritmos en, por ejemplo, la criba de Eratóstenes para encontrar números primos y el algoritmo de Euclides para encontrar el máximo común divisor de dos números.

La palabra algoritmo en sí se deriva del matemático del siglo noveno Muhammad ibn Musa al-Khwarizmi , latinizado Algoritmi . Una formalización parcial de lo que sería el concepto moderno de algoritmo se inició con los intentos de resolver el Entscheidungsproblem (problema de decisión) formulada por David Hilbert en 1928. formalizaciones más tarde fueron enmarcados como los intentos de definir " calculabilidad efectiva " o "método eficaz". Esos formalizaciones incluyen la 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

La palabra 'algoritmo' tiene sus raíces en latinizar el nombre de Muhammad ibn Musa al-Khwarizmi en un primer paso para Algorismus . Al-Khwarizmi ( persa : خوارزمی ., C 780-850) fue un persa matemático, astrónomo , geógrafo y experto en la Casa de la Sabiduría en Bagdad , cuyo nombre significa 'el nativo de Khwarezm ', una región que formaba parte de mayor Irán y se encuentra ahora en Uzbekistán .

Aproximadamente 825, al-Khwarizmi escribió un idioma árabe tratado sobre el sistema de numeración Hindú-Árabe , que fue traducido al latín en el siglo 12 bajo el título Algoritmi de numero Indorum . Este título significa "Algoritmi sobre el número de los indios", donde "Algoritmi" era del traductor latinización del nombre de Al-Khwarizmi. Al-Khwarizmi fue el matemático más leído en Europa en la Edad Media tardía, principalmente a través de otro de sus libros, el álgebra . A finales de latín medieval, Algorismus , Inglés ' algoritmo ', la corrupción de su nombre, simplemente significaba el "sistema de numeración decimal". En el siglo 15, bajo la influencia de la palabra griega ἀριθμός 'número' ( cf. 'aritmética'), la palabra latina fue alterado para algorithmus , y el correspondiente término Inglés 'algoritmo' primero se atestigua en el siglo 17; el sentido moderno fue introducido en el siglo 19.

En Inglés, que fue utilizado por primera vez en 1230 y luego por Chaucer en 1391. Inglés adoptó el término francés, pero no fue hasta finales del siglo 19 que "algoritmo" adquirió el significado que tiene en Inglés moderno.

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

Haec Algorismus ars praesens dicitur, en qua / Talibus Indorum fruimur bis quinque figuris.

lo que se traduce como:

Algoritmo es el arte por el cual en la actualidad utilizamos esas figuras indio, que número dos veces cinco.

El poema es unos pocos cientos de líneas de largo y resume el arte de cálculo con el nuevo estilo de los dados de la India, o Talibus Indorum o numerales hindúes.

definición informal

Una definición informal podría ser "un conjunto de reglas que define con precisión una secuencia de operaciones." que incluiría todos los programas de ordenador, incluidos los programas que no realizan cálculos numéricos. En general, un programa sólo es un algoritmo si se detiene el tiempo.

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

Boolos, Jeffrey y 1974, 1999 oferta un significado informal de la palabra en la siguiente cita:

Ningún ser humano puede escribir lo suficientemente rápido, o lo suficientemente largo, o lo suficientemente pequeño † († "cada vez más pequeños y sin límite ... que estaría tratando de escribir sobre las moléculas, en los átomos, los electrones en") para listar todos los miembros de una enumerably infinita establecido por escribir sus nombres, uno tras otro, en alguna notación. Sin embargo, los seres humanos pueden hacer algo igualmente útil, en el caso de ciertos conjuntos infinitos enumerably: Pueden dar instrucciones explícitas para determinar el n º miembro del conjunto , por arbitraria finita n . Tales instrucciones son para ser dada de manera bastante explícita, en una forma en la que podían ser seguidos por una máquina de computación , o por un humano que es capaz de llevar a cabo operaciones sólo es muy elementales sobre los símbolos.

Un "conjunto enumerably infinita" es uno cuyos elementos se pueden poner en correspondencia uno-a-uno con los números enteros. Por lo tanto, Boolos y Jeffrey están diciendo que un algoritmo implica instrucciones para un proceso que "crea" enteros salida de un arbitrario número entero "entrada" o enteros que, en teoría, puede ser arbitrariamente grande. Así, un algoritmo puede ser una ecuación algebraica tal como = y m + n - dos "variables de entrada" arbitrarias m y n que producen una salida y . Pero los intentos de varios autores para definir la noción indican que la palabra implica mucho más que esto, algo del orden de (por ejemplo, la adición):

Instrucciones precisas (en idioma comprensible "la computadora") para un proceso rápido, eficiente, "bueno" que especifica los "movimientos" de "la computadora" (máquina o humano, equipado con el necesario contenido internamente la información y capacidades) para encontrar , decodificar, y después del proceso de entrada arbitraria enteros / símbolos m y n , símbolos + y = ... y "eficacia" producir, en un tiempo "razonable", la salida de enteros y en un lugar determinado y en un formato especificado.

El concepto de algoritmo también se utiliza para definir la noción de decidibilidad . Esta idea es central para explicar cómo los sistemas oficiales llegaron a existir a partir de un pequeño conjunto de axiomas y reglas. En lógica , el tiempo que requiere un algoritmo para completar no se puede medir, ya que no está aparentemente relacionada con nuestra dimensión física habitual. A partir de estas incertidumbres, que caracterizan el trabajo en curso, tallos la falta de una definición de algoritmo que se adapte tanto concretos (en algún sentido) y el uso del término abstracto.

Formalización

Los algoritmos son esenciales para el proceso de datos de ordenadores manera. Muchos programas de computadora contienen algoritmos que detallan las instrucciones específicas de un equipo debe realizar (en un orden específico) para llevar a cabo una tarea específica, como el cálculo cheques de pago o de impresión de los estudiantes empleados libretas de calificaciones. Por lo tanto, un algoritmo puede ser considerado ser cualquier secuencia de operaciones que se pueden simular por un Turing completo sistema. Los autores que afirman esta tesis incluyen Minsky (1967), Savage (1987) y Gurevich (2000):

Minsky: "Pero también vamos a mantener, con Turing que cualquier procedimiento que podría... 'Naturalmente' se llama efectiva, puede, de hecho, ser realizado por una máquina (simple) Aunque esto puede parecer extremo, los argumentos... . a su favor son difíciles de refutar".

Gurevich: "... argumento informal de Turing en favor de su tesis justifica una tesis más fuerte: cada algoritmo puede ser simulado por una máquina de Turing ... según salvaje [1987], un algoritmo es un proceso de cálculo definido por una máquina de Turing" .

Típicamente, cuando un algoritmo se asocia con el proceso de información, los datos pueden ser leídos desde una fuente de entrada, escrita a un dispositivo de salida y se almacenan para su posterior procesamiento. Los datos almacenados son considerados como 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 tal proceso computacional, el algoritmo debe ser rigurosamente definido: se especifica en la forma en que se aplica en todas las circunstancias posibles que puedan surgir. Es decir, cualquier paso condicional habrá de tratarse sistemáticamente, caso por caso; los criterios para cada caso deben ser claras (y computables).

Debido a que un algoritmo es una lista precisa de pasos precisos, el orden de cálculo es siempre crucial para el funcionamiento del algoritmo. Las instrucciones se supone generalmente que se enumeran de forma explícita, y se describen como productos de partida "de la parte superior" y va "hacia abajo a la parte inferior", una idea que se describe más formalmente por flujo de control .

Hasta ahora, esta discusión de la formalización de un algoritmo ha asumido las instalaciones de la programación imperativa . Esta es la concepción más común, y se intenta describir una tarea en medios discretos, "mecánicos". Única de esta concepción de algoritmos formalizadas es la operación de asignación , estableciendo el valor de una variable. Se deriva de la intuición de la " memoria " como un bloc de notas. Hay un ejemplo a continuación de tal asignación.

Para algunas concepciones alternativas de lo que constituye un algoritmo ver la programación funcional y programación lógica .

expresando algoritmos

Los algoritmos pueden ser expresados en muchos tipos de notación, incluyendo los lenguajes naturales , pseudocódigo , diagramas de flujo , drakon-gráficos , lenguajes de programación o tablas de control (procesados por los intérpretes ). Expresiones del lenguaje natural de los algoritmos tienden a ser prolijo y ambigua, y rara vez se utilizan para algoritmos complejos o técnicos. Pseudocódigo, diagramas de flujo, drakon-gráficos y tablas de control son formas estructuradas para expresar algoritmos que evitan muchas de las ambigüedades comunes en los estados de lenguaje natural. Los lenguajes de programación están destinados principalmente para expresar algoritmos en una forma que puede ser ejecutado por un ordenador, pero se utiliza a menudo como una forma de definir o algoritmos de documentos.

Hay una amplia variedad de representaciones posible y uno puede expresar una determinada máquina de Turing programa como una secuencia de cuadros de la máquina (ver más a la máquina de estado finito , tabla de transición de estado y tabla de control ), como diagramas de flujo y drakon-gráficos (ver más en diagrama de estado ), o como una forma de rudimentario código máquina o código de montaje llamado "conjuntos de cuádruples" (ver más a máquina de Turing ).

Las representaciones de los algoritmos se pueden clasificar en tres niveles aceptados de Turing descripción de la máquina:

Descripción 1 de alto nivel
"... la prosa para describir un algoritmo, haciendo caso omiso de los detalles de implementación. En este nivel, no necesitamos hablar de cómo la máquina gestiona su cinta o la cabeza."
Descripción 2 Aplicación
"... la prosa utiliza para definir la forma en que la máquina de Turing utiliza su cabeza y la forma en que almacena los datos en su cinta. En este nivel, no damos detalles de estados o función de transición."
3 Descripción Formal
Más detallada, "nivel más bajo", da "tabla de estado" de la máquina de Turing.

Para un ejemplo de la algoritmo simple "Añadir m + n" se describe en los tres niveles, véase algoritmo # Ejemplos .

Diseño

Diseño de algoritmos se refiere a un método o proceso matemático para la resolución de problemas y de ingeniería algoritmos. El diseño de algoritmos es parte de muchas teorías de soluciones de investigación de operaciones , tales como la programación dinámica y de divide y vencerás . Las técnicas para el diseño e implementación de algoritmos diseños también son llamados patrones de diseño de algoritmos, como el patrón método de la plantilla y el patrón decorador.

Uno de los aspectos más importantes del diseño del algoritmo es la creación de un algoritmo que tiene un tiempo de ejecución eficiente, también conocido como Big O .

Pasos a seguir para el desarrollo de algoritmos:

  1. Definición del problema
  2. Desarrollo de un modelo
  3. Especificación del algoritmo
  4. El diseño de un algoritmo
  5. Comprobar la corrección del algoritmo
  6. Análisis de algoritmos
  7. Implementación de algoritmo
  8. prueba de programas
  9. preparación de la documentación

Implementación

NAND lógica algoritmo implementado electrónicamente en 7400 de chip

La mayoría de los algoritmos están destinados a ser implementado como programas de ordenador . Sin embargo, los algoritmos también son implementadas por otros medios, tales como en una red neural biológica (por ejemplo, el cerebro humano la aplicación de la aritmética o un insecto en busca de comida), en un circuito eléctrico , o en un dispositivo mecánico.

algoritmos informáticos

Ejemplos de diagramas de flujo de las canónicas estructuras Böhm-Jacopini : la secuencia (rectángulos descendente de la página), el while-do y el IF-THEN-ELSE. Las tres estructuras están hechas del GOTO condicional primitiva ( IF prueba = true THEN GOTO paso xxx ) (un diamante), el GOTO incondicional (rectángulo), varios operadores de asignación (rectángulo), y HALT (rectángulo). Nesting de estas estructuras en el interior de asignación de bloques resultan en 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 equipo destinado "objetivo" (s) para producir salida de dado (tal vez null) de entrada . Un algoritmo óptimo, incluso corriendo en hardware antiguo, produciría resultados más rápidos que un no-óptima (mayor tiempo de complejidad algoritmo) para la misma finalidad, se ejecuta en un hardware más eficiente; es por eso que los algoritmos, como el hardware del ordenador, se consideran la tecnología.

Programas "elegantes" (autónomos), a los "buenos" programas (FAST) : La noción de "simplicidad y elegancia" aparece de manera informal en Knuth y precisamente en Chaitin :

Knuth:.." .No quiere buenas ...... Algoritmos en cierto sentido estético vagamente definido un criterio es la cantidad de tiempo necesario para realizar el algoritmo .. Otros criterios son la capacidad de adaptación del algoritmo para computadoras, su simplicidad y elegancia , etc"
Chaitin: ".. Un programa es 'elegante,' por lo cual quiero decir que es el programa más pequeño posible para producir la salida que lo hace"

Chaitin prologa su definición con: "Voy a mostrar que no se puede demostrar que un programa es 'elegante ' " -como una prueba resolvería el problema de la parada (ibid).

Algoritmo contra la función computable por un algoritmo : Para una función dada puede existir múltiples algoritmos. Esto es cierto, incluso sin necesidad de ampliar el conjunto de instrucciones disponible disponible 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 el algoritmo , es decir, el mapeo cedido por procedimiento. La misma función puede tener varios algoritmos diferentes".

Por desgracia, puede haber una compensación entre la bondad (velocidad) y de la elegancia (compacidad) -un programa elegante puede tomar más medidas para completar un cálculo de un menos elegante. Un ejemplo que utiliza el algoritmo de Euclides aparece a continuación.

Ordenadores (y computors), modelos de cálculo : un ordenador (o "computor" humana) es un tipo restringido de máquina, un "dispositivo mecánico determinista discreto" que sigue ciegamente sus instrucciones. Modelos primitivos Lambek de Melzak y de reducidas esta noción a cuatro elementos: (i) discretas, distinguibles localizaciones , (ii) discretas, indistinguibles contadores (iii) un agente, y (iv) una lista de instrucciones que son eficaces con respecto a la capacidad de la agente.

Minsky describe una variación más agradable del modelo de "ábaco" de Lambek en sus "bases muy simple para la computabilidad ". Máquina de Minsky procede secuencialmente a través de sus cinco (o seis, dependiendo de cómo se cuentan las instrucciones), a menos que sea un condicional IF-THEN GOTO o un GOTO incondicional cambia el flujo del programa fuera de secuencia. Además HALT, máquina de Minsky incluye tres asignación (reemplazo, sustitución) las operaciones de: cero (por ejemplo el contenido de ubicación sustituidos por 0: L ← 0), el sucesor (por ejemplo, L ← L + 1), y decremento (por ejemplo, L ← L - 1 ). Rara vez se debe un "código" programador de escritura con un conjunto de instrucciones tan limitado. Pero Minsky muestra (al igual que Melzak y Lambek) que su máquina es Turing completo con sólo cuatro generales tipos de instrucciones: condicional Goto, incondicional GOTO, misiones / reemplazo / sustitución, y HALT.

Simulación de un algoritmo: lenguaje informático (computor) : Knuth aconseja al lector que ".. La mejor manera de aprender un algoritmo es tratar inmediatamente tome lápiz y papel y trabajar a través de un ejemplo". Pero ¿qué pasa con una simulación o ejecución de la cosa real? El programador tiene que traducir el algoritmo en un lenguaje que el simulador / ordenador / computor pueden efectivamente ejecutar. Piedra da un ejemplo de esto: cuando se calculan las raíces de una ecuación de segundo grado del computor debe saber cómo tomar una raíz cuadrada. Si no lo hacen, entonces el algoritmo, para ser eficaz, debe proporcionar un conjunto de reglas para la extracción de una raíz cuadrada.

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

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

La programación estructurada, estructuras canónicas : Por la tesis de Church-Turing , cualquier algoritmo puede ser calculado por un modelo conocido para ser Turing completo , y por las manifestaciones de Minsky, Turing completo requiere sólo cuatro de instrucción tipos condicional IR A, IR A incondicional, misiones, HALT. Kemeny y Kurtz observan que, mientras que el uso "indisciplinado" de GOTOs incondicional y condicional IF-THEN GOTO puede resultar en " código espagueti ", un programador puede escribir programas estructurados utilizando sólo estas instrucciones; por el contrario "también es posible, y no demasiado duro, para escribir programas mal estructurados en un lenguaje estructurado". Tausworthe aumenta las tres estructuras canónicas Böhm-Jacopini : SECUENCIA, IF-THEN-ELSE, y mientras-DO, con dos más: DO-WHILE y CASE. Un beneficio adicional de un programa estructurado es que se presta a las pruebas de corrección utilizando la inducción matemática .

Símbolos de organigrama canónicos : El ayudante gráfica llama un diagrama de flujo , ofrece una manera de describir y documentar un algoritmo (y un programa informático de uno). Al igual que el flujo del programa de una máquina de Minsky, un diagrama de flujo comienza siempre en la parte superior de una página y se baja. Sus símbolos primarios son sólo cuatro: la dirigida flecha de flujo que muestra el programa, el rectángulo (SECUENCIA, GOTO), el diamante (IF-THEN-ELSE), y el punto (O-tie). Las estructuras canónicas Böhm-Jacopini están hechos de estas formas primitivas. Subestructuras puede "nido" en rectángulos, pero sólo si se produce una sola salida de la superestructura. Los símbolos, y su uso para construir las estructuras canónicas se muestran en el diagrama.

Ejemplos

ejemplo algoritmo

Una animación de la algoritmo quicksort clasificar una matriz de valores aleatorios. Las barras rojas marcan el elemento de pivote; en el inicio de la animación, el elemento más a la derecha es elegido como el pivote.

Uno de los algoritmos más simples es encontrar el mayor número en una lista de números de orden aleatorio. Encontrar la solución es necesario analizar todos los números en la lista. De esto se sigue un algoritmo simple, que se pueden exponer en una descripción de alto nivel en prosa Inglés, como:

Descripción de alto nivel:

  1. Si no hay números en el conjunto, entonces no hay número más alto.
  2. Supongamos que el primer número de la serie es el número más grande en el conjunto.
  3. Para cada número restante en el conjunto: si este número es mayor que el número actual más grande, tenga en cuenta que este número es el número más grande en el conjunto.
  4. Cuando no hay números que quedan en el conjunto para repetir, tenga en cuenta el número actual más grande sea el número más grande de la serie.

(Cuasi) descripción formal: Escrito en prosa, pero mucho más cerca del lenguaje de alto nivel de un programa de ordenador, la siguiente es la codificación más formal del algoritmo en pseudocódigo o código pidgin :

Algorithm LargestNumber
  Input: A list of numbers L.
  Output: The largest number in the list L.
  if L.size = 0 return null
  largestL[0]
  for each item in L, do
    if item > largest, then
      largestitem
  return largest
  • "←" denota asignación . Por ejemplo, " más grandeelemento " significa que el valor de los mayores cambios en el valor del elemento .
  • " Retorno " termina el algoritmo y da salida al valor siguiente.

el algoritmo de Euclides

El ejemplo-diagrama del algoritmo de Euclides de TL Heath (1908), con más detalle añadió. Euclides no excede de un tercio de medición y no da ejemplos numéricos. Nicómaco da el ejemplo de 49 y 21: "le resto el menos de la mayor; 28 se deja, a continuación, de nuevo le resto de este mismo 21 (para esto es posible); 7 es izquierda; le resto esto desde 21, 14 es izquierda; de la que de nuevo restar 7 (para esto es posible); 7 se deja, pero 7 no puede ser restada de 7." Heath comenta que "La última frase es curioso, pero el significado de que es bastante obvio, como también el significado de la frase en acabar 'en uno y el mismo número'." (Heath 1908: 300).

Euclides algoritmo 's para calcular el máximo común divisor (MCD) de dos números aparece como Propuesta II en el libro VII ( 'Número Primaria Theory') de sus elementos . Euclides plantea el problema así: "Teniendo en cuenta dos números no primos entre sí, para encontrar su mayor medida común". Se define "Un número [sea] una multitud compuesto de unidades": un número de cuenta, un número entero positivo no incluyendo el cero. Para "medir" es colocar una longitud de medición más corto s sucesivamente ( q veces) a lo largo de mayor longitud l hasta que la porción restante r es menor que la longitud más corta s . En palabras modernos, resto r = l - q × s , q siendo el cociente, o resto r es el "módulo", la parte entera-fraccional queda después de la división.

Para el método de Euclides para tener éxito, las longitudes de partida debe cumplir dos requisitos: (i) las longitudes no deben ser cero, y (ii) la resta deben ser “adecuada”; es decir, una prueba debe garantizar que el menor de los dos números es restada de la más grande (alternativamente, los dos pueden ser igual por lo que sus rendimientos de resta cero).

Prueba original de Euclides añade un tercer requisito: las dos longitudes no deben ser primer entre sí. Euclides estipulado este fin de poder construir una reductio ad absurdum prueba de que la medida común de los dos números es de hecho la mayor . Mientras algoritmo Nicómaco es el mismo que el de Euclides, cuando los números son primos entre sí, se produce el número '1' por su medida común. Por lo tanto, para ser más precisos, lo que sigue es realmente algoritmo Nicómaco.

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

lenguaje de programación para el algoritmo de Euclides

Sólo unas pocas instrucciones tipos son necesarios para ejecutar-algún algoritmo de Euclides pruebas lógicas (Goto condicional), incondicional GOTO, misiones (de reemplazo), y la resta.

  • Una ubicación está simbolizado por letra mayúscula (s), por ejemplo, S, A, etc.
  • La cantidad variable (número) en una ubicación está escrito en letra minúscula (s) y (generalmente) asociado con el nombre de la ubicación. Por ejemplo, la ubicación L en el inicio podría contener el número l = 3,009.

Un programa poco elegante para el algoritmo de Euclides

"Poco elegante" es una traducción de la versión de Knuth del algoritmo con una basada en la resta resto de bucle en sustitución de 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 "poco elegante" puede calcular el máximo común divisor en menos pasos que "elegante".

El siguiente algoritmo se enmarca como la versión de cuatro pasos de Knuth de Euclides y Nicómaco, pero, en lugar de utilizar la división para encontrar el resto, utiliza sustracciones sucesivas de la longitud más corta s de la longitud restante r hasta que r es menor que s . La descripción de alto nivel, que se muestra en negrita, se adapta de Knuth 1973: 2-4:

ENTRADA :

1 [Into two locations L and S put the numbers l and s that represent the two lengths]:
  INPUT L, S
2 [Initialize R: make the remaining length r equal to the starting/initial/input length l]:
  R ← L

E0: [Asegúrese rs .]

3 [Ensure the smaller of the two numbers is in S and the larger in R]:
  IF R > S THEN
    the contents of L is the larger number so skip over the exchange-steps 4, 5 and 6:
    GOTO step 6
  ELSE
    swap the contents of R and S.
4   L ← R (this first step is redundant, but is useful for later discussion).
5   R ← S
6   S ← L

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

7 IF S > R THEN
    done measuring so
    GOTO 10
  ELSE
    measure again,
8   R ← R − S
9   [Remainder-loop]:
    GOTO 7.

E2: [¿Es el cero resto?] : (I) la última medida era exacta, el resto de R es cero, y el programa puede detener, o (ii) el algoritmo debe continuar: la última medida dejó un resto en R menos de medición de número en S.

10 IF R = 0 THEN
     done so
     GOTO step 15
   ELSE
     CONTINUE TO step 11,

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

11  L ← R
12  R ← S
13  S ← L
14  [Repeat the measuring process]:
    GOTO 7

SALIDA :

15 [Done. S contains the greatest common divisor]:
   PRINT S

HECHO :

16 HALT, END, STOP.

Un programa elegante para el algoritmo de Euclides

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

  5 REM Euclid's algorithm for greatest common divisor
  6 PRINT "Type two integers greater than 0"
  10 INPUT A,B
  20 IF B=0 THEN GOTO 80
  30 IF A > B THEN GOTO 60
  40 LET B=B-A
  50 GOTO 20
  60 LET A=A-B
  70 GOTO 20
  80 PRINT A
  90 END

La siguiente versión se puede utilizar con lenguajes orientados a objetos:

// Euclid's algorithm for greatest common divisor
integer euclidAlgorithm (int A, int B){
     A=Math.abs(A);
     B=Math.abs(B);
     while (B!=0){
          if (A>B) A=A-B;
          else B=B-A;
     }
     return A;
}

¿Qué tan "elegante" que funciona : En lugar de un "bucle de Euclides" externa "elegante" cambios de ida y vuelta entre dos "co-loops", una A> B del bucle que calcula Una ← A - B, y B ≤ Un bucle que calcula B ← B - A. Esto funciona porque, cuando al 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 el nuevo r (la longitud a medir); en otras palabras, el "sentido" de la resta se invierte.

Prueba de los algoritmos de Euclides

Qué hace un algoritmo de lo que su autor quiere que haga? Unos pocos casos de prueba por lo general son suficientes para confirmar la funcionalidad del núcleo. Una fuente utiliza 3009 y 884. Knuth sugirió 40902, 24140. Otro caso interesante es el de dos primos entre los números 14157 y 5950.

Pero los casos excepcionales deben ser identificados y probados. Se "poco elegante" realizar de manera adecuada cuando R> S, S> R, R = S? Lo mismo ocurre con "elegante": B> A, A> B, A = B? (Sí a todo). ¿Qué pasa cuando un número es cero, ambos números son cero? ( "Poco elegante" calcula siempre en todos los casos; "elegante" calcula siempre cuando A = 0) ¿Qué pasa si negativos se introducen los números? Números fraccionarios? Si los números de entrada, es decir, el dominio de la función calculada por el algoritmo / programa, es para incluir sólo números enteros positivos, incluyendo cero, entonces los fracasos en cero indican que el algoritmo (y el programa que crea la instancia de ella) es una función parcial en lugar de una función total de . Un notable fracaso debido a las excepciones es el vuelo 501 de Ariane 5 fracaso del cohete (4 de junio, 1996).

La prueba de la corrección del programa mediante el uso de la 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 a probar la validez de cualquier algoritmo". Tausworthe propone que una medida de la complejidad de un programa sea la longitud de su prueba de corrección.

Medir y mejorar los algoritmos de Euclides

Elegance (compacidad) frente a la bondad (velocidad) : Con sólo seis instrucciones básicas, "elegante" es el claro ganador, en comparación con "poco elegante" a los trece instrucciones. Sin embargo, "poco elegante" es más rápido (que llega a detenerse en menos pasos). El análisis algoritmo indica por qué este es el caso: "elegante" hace dos pruebas condicionales en cada bucle de la resta, mientras que "poco elegante" sólo hace una. Como el algoritmo (por lo general) requiere muchos loop-through, en promedio, se pierde mucho tiempo haciendo una "B = 0?" prueba que se necesita sólo después de que el resto se computa.

Se pueden mejorar los algoritmos? Una vez que los jueces programador un programa de "ajuste" y "efectiva", es decir, se calcula la función de la intención de su autor, entonces la pregunta es, puede ser mejorado?

La compacidad del "poco elegante" puede ser mejorada por la eliminación de cinco pasos. Pero Chaitin demostró que la compactación de un algoritmo no puede ser automatizado mediante un algoritmo generalizada; por el contrario, sólo se puede hacer de forma heurística ; es decir, por la búsqueda exhaustiva (los ejemplos que se encuentran en castor ocupado ), ensayo y error, la inteligencia, la penetración, la aplicación de razonamiento inductivo , etc. Observe que los pasos 4, 5 y 6 se repiten en los pasos 11, 12 y 13. La comparación con "elegante" proporciona un indicio de que estos pasos, junto con los pasos 2 y 3, pueden ser eliminados. Esto reduce el número de instrucciones esenciales, desde los trece años a ocho, lo que hace que sea "más elegante" que "elegante", en nueve pasos.

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

análisis algorítmico

Con frecuencia, es importante conocer la cantidad de un recurso en particular (como el tiempo o el 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 el gran notación O con n como la longitud de la lista. En todo momento el algoritmo sólo tiene que 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 el espacio necesario para almacenar los números de entrada no se cuenta, o O ( n ) si se cuenta.

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

Formal frente empírica

El análisis y estudio de algoritmos es una disciplina de la informática , y con frecuencia se practica de manera abstracta sin el uso de un determinado lenguaje de programación o implementación. En este sentido, el análisis algoritmo se asemeja a otras disciplinas matemáticas en que se centra en las propiedades subyacentes del algoritmo y no en los detalles de cualquier aplicación particular. Por lo general pseudocódigo se utiliza para el análisis, ya que es la representación más simple y más general. Sin embargo, en última instancia, la mayoría de los algoritmos normalmente se implementan en las plataformas de hardware / software en particular y su eficiencia algorítmica finalmente se pusieron a prueba utilizando el código real. Para la solución de un problema "excepcional", la eficiencia de un algoritmo particular puede no tener consecuencias significativas (a menos que n es muy grande), pero para los algoritmos diseñados para una rápida interactiva, comercial o de vida larga del uso científico que puede ser crítica. Escalar desde pequeñas a grandes n n con frecuencia expone algoritmos ineficientes que son de otra manera benigna.

Prueba empírica es útil porque puede revelar interacciones inesperadas que afectan al rendimiento. Los puntos de referencia se pueden utilizar para comparar antes / después de potenciales mejoras en un algoritmo después de la optimización del programa. Las pruebas empíricas no pueden sustituir el análisis formal, sin embargo, y no son triviales para llevar a cabo de una manera justa.

eficiencia en la ejecución

Para ilustrar las mejoras potenciales algoritmos posibles incluso bien establecidas en, una reciente innovación significativa, en relación con FFT algoritmos (utilizados en gran medida en el campo de procesamiento de imágenes), puede disminuir el tiempo de procesamiento hasta 1.000 veces para aplicaciones como las imágenes médicas. En general, las mejoras en la velocidad dependen de las propiedades especiales del problema, que son muy comunes en aplicaciones prácticas. Aceleraciones de esta magnitud permiten a los dispositivos informáticos que hacen un amplio uso de procesamiento de imágenes (como cámaras digitales y equipos médicos) para consumir menos energía.

Clasificación

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

por aplicación

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

recursividad
Un algoritmo recursivo es uno que invoca (hace referencia a) sí mismo varias veces hasta que una cierta condición (también conocida como condición de terminación) de los partidos, que es un método común para la programación funcional . Iterativos algoritmos utilizan construcciones repetitivas como bucles y estructuras de datos adicionales a veces como pilas para resolver los problemas dados. Algunos problemas tienen una vocación natural para una aplicación o la otra. Por ejemplo, torres de Hanoi se comprende bien el uso de implementación recursiva. Cada versión recursiva tiene un equivalente (pero posiblemente más o menos compleja) versión iterativo, y viceversa.
Lógico
Un algoritmo puede ser vista como controlada deducción lógica . Esta noción se puede expresar como: Algoritmo = lógica + de control . El componente lógico expresa los axiomas que pueden ser utilizados para 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 para la programación lógica paradigma. En lenguajes de programación lógica pura, el componente de control es fija y algoritmos se especifican mediante el suministro de sólo el componente lógico. El atractivo de este enfoque es el elegante semántica : un cambio en los axiomas produce un cambio bien definido en el algoritmo.
Serie, paralelo o distribuido
Los algoritmos se discuten generalmente con la suposición de que las computadoras ejecutan una instrucción de un algoritmo a la vez. Esos equipos son a veces llamados ordenadores de serie. Un algoritmo diseñado para un entorno de este tipo se denomina un algoritmo de serie, en contraposición a paralelo algoritmos o algoritmos distribuidos . Los algoritmos paralelos aprovechan las arquitecturas de computadora donde varios procesadores pueden trabajar en un problema a la vez, mientras que los algoritmos distribuidos utilizan múltiples máquinas conectadas con una red de ordenadores . Los algoritmos paralelos o distribuidos dividir el problema en subproblemas más simétricos o asimétricos y recogen los resultados de nuevo juntos. El consumo de recursos en tales algoritmos no es sólo ciclos de procesador en cada procesador, sino también a la sobrecarga de la comunicación entre los procesadores. Algunos algoritmos de clasificación pueden ser paralelizados eficiente, pero su sobrecarga de comunicación es caro. Algoritmos iterativos son generalmente paralelizable. Algunos problemas no tienen algoritmos paralelos y se llaman inherentemente problemas de serie.
Determinista o no determinista
Algoritmos deterministas resolver el problema con la decisión exacta en cada paso del algoritmo, mientras que los algoritmos no deterministas resolver problemas a través de adivinanzas aunque conjeturas típicas se hacen más precisa mediante el uso de la heurística .
Exacta o aproximada
Mientras que muchos algoritmos alcanzan una solución exacta, algoritmos de aproximación buscan una aproximación que está más cerca de la verdadera solución. La aproximación se puede alcanzar ya sea usando un determinista o una estrategia aleatoria. Tales algoritmos tienen valor práctico para muchos problemas difíciles. Uno de los ejemplos de un algoritmo aproximado es el problema de la mochila . El problema de la mochila es un problema donde hay un conjunto de objetos disponibles. El objetivo del problema es empacar la mochila para obtener el valor máximo total. Cada artículo tiene algo de peso y un valor. El peso total que podamos llevar no es más que un número fijo X. Por lo tanto, debemos tener en cuenta el peso de los elementos, así como su valor.
algoritmo cuántico
Se ejecutan en un modelo realista de la computación cuántica . El término se utiliza generalmente para los algoritmos que parecen cuántica intrínsecamente, o utilizar alguna característica esencial de computación cuántica como superposición cuántica o entrelazamiento cuántico .

Por paradigma de diseño

Otra forma de clasificar los algoritmos es por su metodología de diseño o paradigma. Hay un cierto número de paradigmas, cada una diferente de la otra. Por otra parte, cada una de estas categorías incluye muchos tipos diferentes de algoritmos. Algunos paradigmas comunes son:

Por fuerza bruta o búsqueda exhaustiva
Este es el método ingenuo de intentar todas las soluciones posibles para ver cuál es el mejor.
Divide y conquistaras
Un algoritmo divide y vencerás reduce repetidamente una instancia de un problema a uno o más pequeños instancias del mismo problema (por lo general de forma recursiva ) hasta que los casos son lo suficientemente pequeños para resolver fácilmente. Uno de estos ejemplos de divide y vencerás es fusionar clasificación . Ordenando se puede hacer en cada segmento de datos después de dividir los datos en segmentos y la clasificación de los datos enteros se pueden obtener en la fase de conquista mediante la fusión de los segmentos. Una variante más simple de dividir y conquistar se llama una disminución y vencerás algoritmo , que resuelve un subproblema idénticos y utiliza la solución de este subproblema para resolver el problema más grande. Divide y conquista divide el problema en varios subproblemas y así la etapa de conquista es más compleja que disminuir y conquistar algoritmos. Un ejemplo de una disminución y vencerás algoritmo es el algoritmo de búsqueda binaria .
Búsqueda y enumeración
Muchos de los problemas (como el juego de ajedrez ) pueden ser modelados como problemas en los gráficos . Un algoritmo de exploración gráfica especifica las reglas para moverse alrededor de un gráfico y es útil para tales problemas. Esta categoría también incluye algoritmos de búsqueda , rama y con destino enumeración y marcha atrás .
algoritmo aleatorio
Tales algoritmos hacen algunas elecciones al azar (o pseudo-aleatoriamente). Pueden ser muy útiles para encontrar soluciones aproximadas de problemas en los que la búsqueda de soluciones exactas pueden ser poco práctico (véase el método heurístico más adelante). Para algunos de estos problemas, se sabe que las aproximaciones más rápidos deben implicar alguna aleatoriedad . Ya sea algoritmos aleatorios con la complejidad polinómica tiempo pueden ser los algoritmos más rápidos para algunos problemas es una cuestión abierta conocido como el problema de P en función de NP . Existen dos grandes clases de este tipo de algoritmos:
  1. Algoritmos de Monte Carlo devuelven una respuesta correcta con alta probabilidad. Por ejemplo, RP es la subclase de éstos que se ejecutan en tiempo polinómico .
  2. Algoritmo de Las Vegas siempre devuelve la respuesta correcta, pero su tiempo de ejecución es única probabilísticamente obligado, por ejemplo, de la ZPP .
Reducción de la complejidad
Esta técnica consiste en la solución de un problema difícil, transformándola en un problema más conocido para los que tenemos (con suerte) asintóticamente óptimos algoritmos. El objetivo es encontrar un algoritmo de reducción cuya complejidad no está dominado por las reducidas del algoritmo resultante. Por ejemplo, un algoritmo de selección para encontrar la mediana en una lista sin ordenar implica en primer lugar la clasificación de la lista (la porción caro) y luego sacando el elemento central en la lista ordenada (la porción barato). Esta técnica también se conoce como transformar y conquistar .
Volver seguimiento
En este enfoque, múltiples soluciones están construidas de forma incremental y abandonados cuando se determina que no pueden conducir a una solución completa válida.

problemas de optimización

Por problemas de optimización no es una clasificación más específica de algoritmos; un algoritmo para este tipo de problemas puede caer en una o más de las categorías generales descritos anteriormente, así como en uno de los siguientes:

Programación lineal
Durante la búsqueda de soluciones óptimas a una función lineal con destino a restricciones de igualdad y desigualdad lineales, las restricciones del problema se pueden utilizar directamente en la producción de las soluciones óptimas. Hay algoritmos que pueden resolver cualquier problema en esta categoría, como el popular algoritmo simplex . 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 que haber un número entero , entonces se clasifica en programación entera . Un algoritmo de programación lineal puede resolver tal 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 encuentra soluciones aproximadas, dependiendo de la dificultad del problema.
Programación dinámica
Cuando un problema muestra subestructuras óptimas - es decir, la solución óptima para un problema puede ser construido a partir de soluciones óptimas para subproblemas - y subproblemas superpuestos , es decir, los mismos subproblemas se usan para resolver muchos casos problema diferente, un enfoque más rápido llamado programación dinámica evita soluciones recalcular que ya han sido calculados. Por ejemplo, Floyd-Warshall algoritmo , el camino más corto a un gol de un vértice en un ponderada gráfico se puede encontrar mediante el uso de la ruta más corta a la meta de todos los vértices adyacentes. La programación dinámica y memoization van de la mano. La principal diferencia entre la programación dinámica y divide y vencerás es que subproblemas son más o menos independientes de divide y vencerás, mientras que los subproblemas se sobreponen en la programación dinámica. La diferencia entre la programación dinámica y la recursividad directa está en caché o memoization de llamadas recursivas. Cuando subproblemas son independientes y no hay repetición, memoization no ayuda; por lo tanto, la programación dinámica no es una solución para todos los problemas complejos. Mediante el uso de memoization o mantener una tabla de subproblemas ya resuelto, programación dinámica reduce la naturaleza exponencial de muchos problemas a la complejidad polinómica.
El método codicioso
Un algoritmo voraz es similar a un algoritmo de programación dinámica en la que funciona por subestructuras que examinan, en este caso no del problema sino de una solución dada. Tales algoritmos comienzan con un poco de solución, que puede ser dada o haber sido construido de alguna manera, y mejorarlo haciendo pequeñas modificaciones. Para algunos problemas que pueden encontrar la solución óptima mientras que para otros se detienen en óptimos locales , es decir, en soluciones que no pueden ser mejoradas por el algoritmo, pero no son óptimas. El uso más popular de algoritmos codiciosos es para encontrar el árbol de expansión mínima, donde la búsqueda de la solución óptima es posible con este método. Huffman árbol , Kruskal , Prim , Sollin son algoritmos voraces que pueden resolver este problema de optimización.
El método heurístico
En problemas de optimización , algoritmos heurísticos se pueden utilizar para encontrar una solución cercana a la solución óptima en los casos en que la búsqueda de la solución óptima es poco práctico. Estos algoritmos funcionan cada vez más cerca y más cerca de la solución óptima a medida que avanzan. En principio, si se ejecuta por una cantidad infinita de tiempo, van a encontrar la solución óptima. Su mérito es que pueden encontrar una solución muy cerca de la solución óptima en un tiempo relativamente corto. Tales algoritmos incluyen la búsqueda local , búsqueda tabú , recocido simulado y algoritmos genéticos . Algunos de ellos, como el recocido simulado, algoritmos son no deterministas, mientras que otros, como la búsqueda tabú, son deterministas. Cuando un salto en el error de la solución no óptima se sabe, el algoritmo se clasifica adicionalmente como un algoritmo de aproximación .

Por campos de estudio

Todos los campos de la ciencia tiene sus propios problemas y necesidades de algoritmos eficientes. Problemas relacionados en un campo a menudo se estudiaron juntos. Algunas clases de ejemplo son los algoritmos de búsqueda , algoritmos de ordenación , fusionar algoritmos , 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 de algoritmos en un campo pueden mejorar las de otros, a veces totalmente sin relación, los campos. Por ejemplo, la programación dinámica fue inventado para la optimización del consumo de recursos en la industria, pero ahora se utiliza en la solución de una amplia gama de problemas en muchos campos.

por la complejidad

Los algoritmos pueden ser clasificados por la cantidad de tiempo que necesitan para completar en comparación con su tamaño de entrada:

  • Constante de tiempo: si el tiempo que necesita el algoritmo es el mismo, independientemente del tamaño de la entrada. Por ejemplo, un acceso a una matriz de elemento.
  • El tiempo lineal: si el tiempo es proporcional al tamaño de entrada. Por ejemplo, la travesía de una lista.
  • Tiempo logarítmica: si el tiempo es una función logarítmica de la magnitud de entrada. Por ejemplo, el algoritmo de búsqueda binaria .
  • Polinomio tiempo: si el tiempo es una potencia del tamaño de entrada. Por ejemplo, el ordenamiento de burbuja algoritmo tiene complejidad cuadrática tiempo.
  • Tiempo exponencial: si el tiempo es una función exponencial del tamaño de entrada. Por ejemplo, la búsqueda de fuerza bruta .

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

algoritmos continuos

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

  • Un algoritmo que opera en los datos que representa cantidades continuas, a pesar de que estos datos se representa mediante aproximaciones-tales discretos algoritmos se estudian en análisis numérico ; o
  • Un algoritmo en forma de una ecuación diferencial que funciona de forma continua en los datos, se ejecuta en un ordenador analógico .

Asuntos legales

Algoritmos, por sí mismos, no son por lo general patentables. En los Estados Unidos, una demanda que consiste únicamente en simples manipulaciones de conceptos abstractos, números o las 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 algoritmos son patentables veces. Por ejemplo, en Diamond v. Diehr , la aplicación de un simple retroalimentación algoritmo para ayudar en el curado de caucho sintético se consideró patentable. La patente de software es muy controvertido, y hay patentes muy criticada implican algoritmos, especialmente la compresión de datos de algoritmos, tales como Unisys ' patente LZW .

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

Historia: El desarrollo de la noción de "algoritmo"

Próximo Oriente Antiguo

Los algoritmos se utilizaron en la antigua Grecia. Dos ejemplos son la criba de Eratóstenes , que fue descrito en Introducción a la aritmética de Nicómaco , y el algoritmo de Euclides , que fue descrito por primera vez en los Elementos de Euclides (c. 300 aC). Tablillas de arcilla babilónicas describen y emplean procedimientos algorítmicos para calcular el tiempo y lugar de los eventos astronómicos significativos.

símbolos discretos y distinguibles

Tally-marcas : hacer un seguimiento de sus rebaños, sus sacos de grano y su dinero los antiguos utilizan recuento: acumulación de piedras o marcas de rayado en los palillos o hacer símbolos discretos en arcilla. A través del uso de Babilonia y Egipto de las marcas y símbolos, finalmente, los números romanos y el ábaco evolucionado (Dilson, p. 16-41). Marcas de conteo aparecen prominentemente en unario sistema de numeración aritmética utilizado en la máquina de Turing y la máquina de Turing Post- cómputos.

La manipulación de símbolos como "marcadores de posición" para los números: el álgebra

El trabajo de los antiguos geómetras griegos ( algoritmo de Euclides ), el matemático indio Brahmagupta , y el matemático persa Al-Khwarizmi (de cuyo nombre los términos " algoritmo " y "algoritmo" se derivan), y los matemáticos de Europa occidental culminó en Leibniz 's noción de la ratiocinator cálculo (ca 1680):

Un buen siglo y medio por delante de su tiempo, Leibniz propuso un álgebra de la lógica, un álgebra que especifique las reglas para la manipulación de conceptos lógicos en la forma que el álgebra ordinaria especifica las reglas para manipular los números.

artificios mecánicos con estados discretos

El reloj : Bolter atribuye la invención de la impulsada por el peso del reloj como "La clave invención [de Europa en la Edad Media]", en particular, la fuga del borde que nos proporciona la garrapata y tac de un reloj mecánico. "La máquina automática precisa" llevado inmediatamente a "mecánicos autómatas " que comienza en el siglo 13 y finalmente a "máquinas computacionales", la máquina diferencial y la máquina analítica de Charles Babbage y la condesa Ada Lovelace , mediados del siglo 19. Lovelace se le atribuye la primera creación de un algoritmo destinado a la transformación en un ordenador - máquina analítica de Babbage, el primer dispositivo considerado un verdadero Turing completo ordenador en lugar de sólo una calculadora - ya veces se llama "la primera programadora de la historia", como resultado, 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- Stanley Jevons 'ábaco lógica' 'y 'máquina lógica' : El problema técnico era reducir ecuaciones booleanas cuando se presenta en una forma similar a lo que ahora se conoce como mapas de Karnaugh . Jevons (1880) describe primero un simple "ábaco" de "tiras de madera provistas con pasadores, ideado de forma que cualquier parte o clase de las combinaciones [lógicos] pueden ser recogidos de forma mecánica... Más recientemente, sin embargo, he reducido el sistema de una forma completamente mecánica, y por lo tanto han incorporado la totalidad del proceso indirecto de la inferencia en lo que puede llamarse una máquina lógica "Su máquina estaba equipada con 'ciertas varillas de madera móviles' y" al pie son 21 teclas como las de un piano [etc.]... ". Con esta máquina se podría analizar un " silogismo o cualquier otro argumento lógico simple".

Esta máquina se visualiza en 1870 antes de que los miembros de la Sociedad Real. Otra lógico John Venn , sin embargo, en su 1881 Symbolic Logic , hizo la vista ictericia a este esfuerzo: "no he alta estimar mismo del interés o importancia de lo que se denominan a veces las máquinas lógicas ... no me parece que cualquier artificios en la actualidad conocidos o que puedan ser descubiertos realmente merecen el nombre de máquinas lógicas "; ver más a caracterizaciones del algoritmo . Pero para no ser menos que él también presentó "un plan algo análogo, me temo, a Jevon del Prof. ábaco ... [Y] ganancia [a], que corresponde a máquina lógica del Prof. Jevons, el siguiente artificio se puede describir. Yo prefiero llamarlo simplemente una máquina lógica diagrama ... pero supongo que podría hacer muy completo de todo lo que se puede esperar racionalmente de cualquier máquina lógica".

Telar de Jacquard, Hollerith tarjetas perforadas, telegrafía y telefonía-relé electromecánico : Bell y Newell (1971) indican que el telar de Jacquard (1801), precursor de tarjetas Hollerith (tarjetas perforadas, 1887), y "tecnologías de conmutación telefónica", fueron las raíces de un árbol que lleva al desarrollo de los primeros ordenadores. Por la mitad del siglo 19 el telégrafo , el precursor del teléfono, estaba en uso en todo el mundo, su codificación discreta y distinguible de letras como "puntos y rayas" un sonido común. A finales del siglo 19 la cinta de teletipo (1870 ca) estaba en uso, al igual que el uso de tarjetas de Hollerith en el censo de Estados Unidos 1890. Luego vino el teletipo (CA 1910), con su uso de papel perforado de código Baudot en la cinta.

Las redes telefónicas de conmutación de electromecánicos relés (inventado 1835) estaba detrás de la obra de George Stibitz (1937), el inventor del dispositivo de adición digital. Mientras trabajaba en los Laboratorios Bell, observó el "uso oneroso' de calculadoras mecánicas con engranajes. 'Se fue a casa una noche en 1937 con la intención de probar su idea ... Cuando el era jugar más, Stibitz había construido un dispositivo de adición binaria' .

Davis (2000) señala la importancia especial del relé electromecánico (con sus dos "estados binarios" abiertos y cerrados ):

Fue sólo con el desarrollo, a partir de la década de 1930, las calculadoras electromecánicas mediante relés eléctricos, que las máquinas fueron construidas con el alcance Babbage había imaginado ".

Las matemáticas en el siglo 19 hasta mediados del siglo 20

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

Pero Heijenoort da Frege (1879) esta felicitaciones: Frege es "quizá la obra más importante que se ha escrito en la lógica ... en la que vemos a." 'Lenguaje de fórmulas', que es un characterica lengua , una lengua escrita con símbolos especiales "para el pensamiento puro", es decir, libre de adornos retóricos ... construido a partir de símbolos específicos que se manipulan de acuerdo con reglas definidas". El trabajo de Frege era aún más simplificada y amplificada por Alfred North Whitehead y Bertrand Russell en su Principia Mathematica (1910 a 1913).

Las paradojas : Al mismo tiempo, una serie de paradojas inquietantes apareció en la literatura, en particular, la paradoja Burali-Forti (1897), la paradoja de Russell (1902-1903), y el Richard paradoja . Las consideraciones resultantes conducido a Kurt Gödel papel 's (1931) -se cita específicamente la paradoja del mentiroso-que reduce completamente reglas de recursión a números.

Calculabilidad efectiva : En un esfuerzo por resolver el Entscheidungsproblem definido con precisión por Hilbert en 1928, los matemáticos primero se dedicó a definir lo que se entiende por un "método eficaz" o "cálculo eficaz" o "calculabilidad efectiva" (es decir, un cálculo que tendría éxito ). En rápida sucesión la siguiente apareció: Alonzo Church , Stephen Kleene y JB Rosser 's λ-cálculo una definición finamente pulida de 'recursividad en general' de la obra de Gödel que actúa sobre sugerencias de Jacques Herbrand (cf. conferencias Princeton de Gödel de 1934) y simplificaciones posteriores por Kleene. La demostración de la iglesia que el Entscheidungsproblem era irresoluble, Emil Mensaje definición de calculabilidad efectiva 's como un trabajador sin pensar siguiendo una lista de instrucciones para mover hacia la izquierda o hacia la derecha a través de una secuencia de habitaciones y, aunque no sea marca o borrar un documento u observar el papel y crea un sí o no la decisión sobre la siguiente instrucción. Prueba de ello Entscheidungsproblem de Alan Turing era imposible de resolver mediante el uso de su "máquina de a- [automático-]" efecto -en casi idéntica a la "formulación" de Post, J. Barkley Rosser definición de 'método eficaz' 's en términos de "una máquina". SC Kleene propuesta 's de un precursor de la ' tesis de Church ' que llamó 'Tesis I', y unos años más tarde Kleene de cambio de nombre de su tesis 'Tesis de Church' y proponer 'Tesis de Turing'.

Emil Post (1936) y Alan Turing (1936-1937, 1939)

Aquí es una notable coincidencia de dos hombres no saber entre sí, sino que describe un proceso de hombres-como-ordenadores que trabajan en cálculos, y con ellos se obtienen las definiciones virtualmente idénticas.

Emil Publica (1936) describe las acciones de un "ordenador" (ser humano) de la siguiente manera:

" ... dos conceptos involucrados son: la de un espacio de símbolo en el que el trabajo que conduce de un problema de responder se va a llevar a cabo, y una inalterable fijo conjunto de direcciones .

Su espacio de símbolo sería

"Una secuencia infinita de dos vías de espacios o cajas ... El solucionador de problemas o trabajador es moverse y trabajar en este espacio símbolo, que es capaz de estar en, y operando en una caja, pero a la vez una caja .... es admitir pero de dos condiciones posibles, es decir, estar vacío o no marcado, y que tiene una sola marca en ella, por ejemplo un trazo vertical.
"Un cuadro debe ser señalado y se llama el punto de partida. ... un problema específico es que debe darse en forma simbólica por un número finito de cajas [es decir, ENTRADA] ser marcado con un accidente cerebrovascular. Del mismo modo, la respuesta [es decir, , SALIDA] debe ser dado en forma simbólica por una configuración de cajas marcadas como ...
"Un conjunto de instrucciones 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, STOP]". Ver más en la máquina Post-Turing
La estatua de Alan Turing en Bletchley Park

Alan Turing trabajo 's precedió a la de Stibitz (1937); se desconoce si Stibitz sabía del trabajo de Turing. El biógrafo de Turing cree que el uso de Turing de un modelo de máquina de escribir deriva de un interés juvenil: "Alan había soñado con la invención de las máquinas de escribir como un niño; la señora Turing tenía una máquina de escribir, y él bien podría haber comenzado por preguntarse qué se entiende por llamar una máquina de escribir 'mecánica'". Dada la prevalencia de código Morse y telegrafía, máquinas de cinta de teletipo, y teletipos podríamos conjeturar que todos eran influencias.

Turing su modelo de computación que ahora se llama una máquina de Turing -Comienza, al igual que Post, con un análisis de un equipo humano que disminuye las reduce a un simple conjunto de movimientos básicos y los "estados de ánimo". Pero él sigue un paso más y crea una máquina como un modelo de cálculo de números.

"La computación se realiza normalmente escribiendo ciertos símbolos en el papel. Podemos suponer este documento se divide en cuadrados como libro de aritmética de un niño ... Asumo entonces que el cálculo se realiza sobre papel unidimensional, es decir, en una cinta dividida en cuadrados. Serán asimismo suponer que el número de símbolos que pueden imprimirse es finito ...
"El comportamiento del equipo en cualquier momento se determina por los símbolos que se está observando, y su 'estado de ánimo' en ese momento. Podemos suponer que existe una cota B al número de símbolos o plazas que el ordenador pueda observar en un momento dado. Si se desea observar más, se debe utilizar observaciones sucesivas. también vamos a suponer que el número de estados de ánimo que es necesario tener en cuenta es finito ...
"Imaginemos que las operaciones realizadas por el ordenador para ser divididos en operaciones simples '', que son tan elemental que no es fácil de imaginar aún más dividido."

reducción de Turing se obtiene la siguiente:

"Las operaciones simples, por lo tanto deben incluir:
"(A) Cambios en el símbolo de una de las plazas observados
"(B) Los cambios de una de las plazas observados a otro cuadrado dentro de los cuadrados l de uno de los cuadrados previamente observados.

"Puede ser que algunos de estos cambios invocan necesariamente un cambio de estado de ánimo La operación individual más general debe, por lo tanto, se toma para ser una de las siguientes.:

"(A) Un posible cambio (a) de símbolo junto con un posible cambio de estado de ánimo.
"(B) un posible cambio (b) de cuadrados observadas, junto con un posible cambio de estado de ánimo"
"Ahora podemos construir una máquina para hacer el trabajo de este equipo."

Unos años más tarde, Turing amplió su análisis (tesis, la definición) con esta expresión contundente de la misma:

"Una función se dice que es 'efectivamente calculable' si sus valores se pueden encontrar mediante algún proceso puramente mecánico. A pesar de que es bastante fácil conseguir una comprensión intuitiva de esta idea, no es menos deseable tener algunos, definición expresable matemática más definida ... [habla sobre la historia de la definición más o menos según lo presentado anteriormente con respecto a Gödel, Herbrand, Kleene, Iglesia, Turing, y post]... Podemos tomar esta declaración, literalmente, la comprensión de un solo proceso puramente mecánico que podría llevarse a cabo por una máquina. es posible dar una descripción matemática, en cierta forma normal, de las estructuras de estas máquinas. el desarrollo de estas ideas conduce a la definición del autor de una función computable, y para la identificación de † computabilidad con calculabilidad efectiva....
"† Vamos a utilizar la expresión 'función computable' en el sentido de una función calculable por una máquina, y dejamos que 'efectivamente calculable' se refieren a la idea intuitiva sin especial identificación con cualquiera de estas definiciones".

JB Rosser (1939) y SC Kleene (1943)

J. Barkley Rosser define un 'método [matemática] eficaz' de la manera siguiente (cursiva añadida):

"Se utiliza aquí 'método eficaz' en el sentido bastante especial de un método de cada paso de la cual es determinada con precisión y que es seguro para 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 # 5; véase la discusión inmediatamente debajo]. La más sencilla de ellas a otro (debido al post y Turing) esencialmente dice que. un método eficaz de resolver ciertos tipos de problemas existe si uno puede construir una máquina que luego resolver cualquier problema del conjunto sin la intervención humana más allá de la inserción de la pregunta y (más tarde) la lectura de la respuesta . las tres definiciones son equivalentes, por lo que no importa cuál se usa. Por otra parte, el hecho de que los tres son equivalentes es una muy fuerte argumento para la corrección de cualquiera ". (Rosser 1939: 225-6)

Nota al pie de Rosser Nº 5 referencias al trabajo de (1) Iglesia y Kleene y su definición de λ-definibilidad, en particular el uso de la iglesia de ella en su un problema sin solución de números elemental Teoría (1936); (2) Herbrand y Gödel y su uso de la recursividad en particular el uso de Gödel en su famoso papel en proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados I (1931); y (3) Post (1936) y Turing (1936-1937) en sus mecanismo de modelos de cálculo.

Stephen C. Kleene define como su ahora famoso "Tesis I", conocido como la tesis de Church-Turing . Pero él hizo esto en el contexto siguiente (en negrita en el original):

"12. teorías algorítmicas ... En la creación de una teoría algorítmica completa, lo que hacemos es describir un procedimiento, realizable para cada conjunto de valores de las variables independientes, que termina necesariamente procedimiento y en la forma que a partir de los resultados que podamos leer una respuesta definitiva, "sí" o "no" a la pregunta "es el valor verdadero predicado?""(Kleene 1943: 273)

Historia después de 1950

Varios esfuerzos se han dirigido hacia un mayor refinamiento de la definición de "algoritmo", y la actividad está en curso debido a los problemas que rodean, en especial, fundamentos de las matemáticas (en especial la tesis de Church-Turing ) y filosofía de la mente (especialmente los argumentos sobre la inteligencia artificial ). Para más información, ver las caracterizaciones del algoritmo .

Ver también

notas

Bibliografía

  • Axt, P (1959). "En una jerarquía de grados y Subrecursive recursivas primitivas". Transacciones de la Sociedad Americana de Matemáticas . 92 : 85-105. doi : 10.2307 / 1993169 . JSTOR  1.993.169 .
  • Bell, C. Gordon y Newell, Allen (1971), Estructuras informáticos: Lecturas y Ejemplos , McGraw-Hill Book Company, Nueva York. ISBN  0-07-004357-4 .
  • Blass, Andreas ; Gurevich, Yuri (2003). "Algoritmos: En busca de una absolutos Definiciones" (PDF) . Boletín de la Asociación Europea para la informática teórica . 81 . Incluye una excelente bibliografía de 56 referencias.
  • Bolter, David J. (1984). Hombre de Turing: cultura occidental en la era del ordenador (1984 ed.). La Universidad de Carolina del Norte Press, Carolina del Norte en Chapel Hill. ISBN  0-8078-1564-0 ., ISBN  0-8078-4108-0 PBK.
  • Boolos, George ; Jeffrey, Richard (1999) [1974]. Computabilidad y Lógica (4ª ed.). Cambridge University Press, Londres. ISBN  0-521-20402-X .: Cf. Capítulo 3 máquinas de Turing donde discuten "ciertos conjuntos enumerables no efectiva (mecánicamente) enumerables".
  • Burgin, Mark (2004). Algoritmos super-recursivas . Saltador. ISBN  978-0-387-95569-8 .
  • Campagnolo, ML, Moore, C. , y Costa, JF (2000) Una caracterización analógica de las funciones subrecursive. En Proc. de la cuarta Conferencia sobre números reales y equipos , Universidad de Odense, pp. 91-109
  • Iglesia, Alonso (1936a). "Un problema sin solución de números elemental teoría". American Journal of Mathematics . 58 (2): 345-363. doi : 10.2307 / 2371045 . JSTOR  2.371.045 .Reimpreso en lo indecidible , p. 89ff. La primera expresión de "Tesis de Church". Véase, en particular página 100 ( El Undecidable ) donde se define la noción de "calculabilidad efectiva" en términos de "un algoritmo", y que usa la palabra "termina", etc.
  • Iglesia, Alonso (1936b). "Una nota sobre Entscheidungsproblem". El Journal of Symbolic Logic . 1 (1): 40-41. doi : 10.2307 / 2269326 . JSTOR  2.269.326 .Iglesia, Alonso (1936). "Corrección de una nota en la Entscheidungsproblem". El Journal of Symbolic Logic . 1 (3): 101-102. doi : 10.2307 / 2269030 . JSTOR  2.269.030 .Reimpreso en lo indecidible , p. 110ff. Iglesia muestra que el Entscheidungsproblem es imposible de resolver en unos 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  0-85664-464-1 .
  • Davis, Martín (1965). El Undecidable: Documentos básicos sobre la Undecidable Proposiciones, problemas sin solución y las funciones computables . Nueva York: Raven Press. ISBN  0-486-43228-9 .Davis da el comentario antes de cada artículo. Papeles de Gödel , Alonzo Church , Turing , Rosser , Kleene , y Emil mensaje se incluyen; los citados en el artículo se enumeran aquí por el nombre del autor.
  • Davis, Martín (2000). Motores de Lógica: Los matemáticos y el origen del ordenador . Nueva York: WW Nortion. ISBN  0-393-32229-7 .Davis ofrece biografías concisas de Leibniz , Boole , Frege , Cantor , Hilbert , Gödel y Turing con von Neumann como el villano presentas el robo. Muy breves biografías de Joseph-Marie Jacquard , Babbage , Ada Lovelace , Claude Shannon , Howard Aiken , etc.
  •  Este artículo incorpora material de dominio público  desde el  NIST documento:  Negro, Paul E. "algoritmo" . Diccionario de Algoritmos y Estructuras de Datos .
  • Dean, Tim (2012). "Evolución y diversidad moral". Báltico Anuario Internacional de la cognición, la lógica y la Comunicación . 7 .
  • Dennett, Daniel (1995). La peligrosa idea de Darwin . Nueva York: Touchstone / Simon & Schuster. ISBN  0-684-80290-2 .
  • Dilson, Jesse (2007). El Abacus ((1968,1994) ed.). St. Martin Press, Nueva York. ISBN  0-312-10409-X ., ISBN  0-312-10409-X (pbk.)
  • Yuri Gurevich , Máquinas de Estado secuenciales Abstract secuencial de captura Algoritmos , ACM Transactions on Lógica Computacional, Vol 1, No 1 (julio de 2000), páginas 77-111. Incluye bibliografía de 33 fuentes.
  • van Heijenoort, Jean (2001). A partir de Frege a Gödel, Un Libro Fuente de la lógica matemática, 1879-1931 ((1967) ed.). Harvard University Press, Cambridge, MA. ISBN  0-674-32449-8 ., 3ª edición de 1976 [?], ISBN  0-674-32449-8 (pbk.)
  • Hodges, Andrew (1983). Alan Turing: The Enigma . Nueva York: Simon and Schuster . ISBN  0-671-49207-1 ., ISBN  0-671-49207-1 . Cf. El capítulo "El Espíritu de la verdad" para una historia que conduce a, y una discusión de, su prueba.
  • Kleene, Stephen C. (1936). "Funciones recursivas general de los números naturales" . Mathematical Annalen . 112 (5): 727-742. doi : 10.1007 / BF01565439 .Presentado a la American Mathematical Society, septiembre de 1935. Reproducido en lo indecidible , p. 237ff. Definición de "recursión general" (conocido ahora como mu-recursión) de kleene fue utilizado por la Iglesia en su documento de 1935 un problema sin solución de números elemental teoría que resultó ser el "problema de decisión" a ser "indecidible" (es decir, un resultado negativo).
  • Kleene, Stephen C. (1943). "Recursiva predicados y cuantificadores". Transacciones American Mathematical Society . 54 (1): 41-73. doi : 10.2307 / 1990131 . JSTOR  1.990.131 .Reimpreso en lo indecidible , p. 255ff. Kleene refinó su definición de "recursión general" y procedió en su capítulo "teorías 12. algorítmicos" postular "Tesis I" (p 274.); que más tarde repetir esta tesis (en Kleene 1952: 300) y el nombre de "Tesis de Church" (Kleene, 1952: 317) (es decir, la tesis de Church ).
  • Kleene, Stephen C. (1991) [1952]. Introducción a Metamathematics (Décimo ed.). North-Holland Publishing Company. ISBN  0-7204-2103-9 . -Excelente accesible, fuente legible-referencia para "fundaciones" matemáticos.
  • Knuth, Donald (1997). Algoritmos fundamentales, Tercera Edición . Reading, Massachusetts: Addison-Wesley. ISBN  0-201-89683-4 .
  • Knuth, Donald (1969). Volumen 2 / Seminumerical Algoritmos, The Art of Computer Programming Primera edición . Reading, Massachusetts: Addison-Wesley.
  • Kosovsky, NK Elementos de lógica matemática y su aplicación a la teoría de la Subrecursive Algoritmos , LSU Publ., Leningrado, 1981
  • Kowalski, Robert (1979). "Algoritmo = Lógica + Control". Comunicaciones de la ACM . 22 (7): 424-436. doi : 10.1145 / 359.131,359136 .
  • AA Markov (1954) Teoría de algoritmos . [Traducido por Jacques J. Schorr-Kon y el personal PST] Pie de imprenta Moscú, Academia de Ciencias de la URSS, 1954 [es decir, Jerusalén, Israel Programa para Científicas Traducciones, 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 ruso de las obras del Instituto de Matemáticas de la Academia de Ciencias de la URSS, v 42. Título original:. Teoriya algerifmov. [Biblioteca QA248.M2943 Dartmouth College. EE.UU. Departamento de Comercio, Oficina de Servicios Técnicos, número 60-51085 OTS.]
  • Minsky, Marvin (1967). Cálculo: Máquinas finito e infinito (Primera ed.). Prentice-Hall, Englewood Cliffs, NJ. ISBN  0-13-165449-7 .Minsky expande su "... idea de un-un algoritmo procedimiento eficaz ..." en el capítulo 5.1 de la computabilidad, procedimientos eficaces y Algoritmos. Máquinas infinito.
  • Post, Emil (1936). "Procesos combinatoria finitos, formulación I". El Journal of Symbolic Logic . 1 (3): 103-105. doi : 10.2307 / 2269031 . JSTOR  2.269.031 .Reimpreso en lo indecidible , p. 289ff. Publica define un simple proceso algorítmico-como de un hombre que escribe marcas o borrar marcas y viniendo de una caja a otra y, finalmente, detener, mientras sigue a una lista de instrucciones simples. Esto es citado por Kleene como una fuente de su "Tesis I", la llamada tesis de Church-Turing .
  • Rogers, Jr, Hartley (1987). Teoría de las funciones recursivas y computabilidad efectiva . The MIT Press. ISBN  0-262-68052-1 .
  • Rosser, JB (1939). "Una exposición informal de pruebas del teorema de Godel y el Teorema de la Iglesia". Journal of Symbolic Logic . 4 (2): 53-60. doi : 10.2307 / 2269059 . JSTOR  2.269.059 .Reimpreso en lo indecidible , p. 223ff. En esto consiste la famosa definición de "método eficaz" de Rosser:" ... un método cada paso de las cuales está predeterminado con precisión y que es seguro para 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 la inserción de la pregunta y (más tarde) la lectura de la respuesta"(p. 225-226, lo indecidible )
  • Santos-Lang, Christopher (2014). "Moral Ecología Enfoques de Ética de la máquina". En van Rysewyk, Simon; Pontier, Matthijs. Máquina de Ética Médica (PDF) . Suiza: Springer. pp. 111-127. doi : 10.1007 / 978-3-319-08108-3_8 .
  • Scott, Michael L. (2009). Lenguaje de Programación Pragmática (3ª ed.). Morgan Kaufmann Publishers / Elsevier. ISBN  978-0-12-374514-9 .
  • Sipser, Michael (2006). Introducción a la Teoría de la computación . PWS Publishing Company. ISBN  0-534-94728-X .
  • Sober, Elliott; Wilson, David Sloan (1998). A los demás: La evolución y la psicología del comportamiento altruista . Cambridge: Harvard University Press.
  • Piedra, Harold S. (1972). Introducción a la Organización de Computadores y Estructuras de Datos (1972 ed.). McGraw-Hill, Nueva York. ISBN  0-07-061726-0 .Cf. en particular, el primer capítulo titulado: Algoritmos, las máquinas de Turing, y Programas . Su sucinta definición informal: "... cualquier secuencia de instrucciones que pueden ser obedecidas por un robot, se llama un algoritmo " (p. 4).
  • Tausworthe, Robert C (1977). Estandarizada Desarrollo de Software Computadoras Parte 1 Métodos . Englewood Cliffs NJ: Prentice-Hall, Inc. ISBN  0-13-842195-1 .
  • Turing, Alan M. (1936-1937). "Sobre los números computables, con una aplicación a la Entscheidungsproblem". Actas de la Sociedad Matemática de Londres . 2. Serie 42 : 230-265. doi : 10.1112 / PLMS / s2-42.1.230 .. Correcciones, ibid, vol. 43 (1937) pp. 544-546. Reimpreso en lo indecidible , p. 116ff. Famoso artículo de Turing completado como tesis de maestría, mientras que en el Kings College de Cambridge Reino Unido.
  • Turing, Alan M. (1939). "Sistemas de lógica basada en Ordinales". Actas de la Sociedad Matemática de Londres . 45 : 161-228. doi : 10.1112 / PLMS / s2-45.1.161 .Reimpreso en lo indecidible , p. 155ff. El artículo de Turing que define "el oráculo", fue su tesis doctoral en Princeton, mientras que EE.UU..
  • Estados Unidos de Patentes y Marcas (2006), 2.106,02 **> Los algoritmos matemáticos: 2100 patentabilidad , Manual de Procedimiento de Examen de Patentes (MPEP). La última revisión de agosto de de 2006

Otras lecturas

enlaces externos

repositorios algoritmo
Notas de lectura