Algoritmo

Los diagramas de flujo se utilizan a menudo para representar gráficamente algoritmos.

En matemáticas , la informática, la lingüística y disciplinas relacionadas, un algoritmo es un tipo de método eficaz en el que una lista definida de instrucciones bien definidas para completar una tarea, cuando se les da un estado inicial, se procederá a través de una serie bien definida de estados sucesivos, finalmente termina en un estado final. La transición de un estado a otro no es necesariamente determinista; algunos algoritmos, conocidos como algoritmos probabilísticos, incorporan la aleatoriedad.

El concepto de un algoritmo se originó como un medio para registrar los procedimientos para la resolución de problemas matemáticos tales como encontrar el común divisor de dos números o multiplicar dos números; tales algoritmos estaban en uso por los babilonios ya en 1600 antes de Cristo.

Una formalización parcial del concepto comenzó con los intentos de resolver el Entscheidungsproblem (el "problema de decisión") que David Hilbert planteó en 1928. formalizaciones posteriores se enmarca como intentos de definir " calculabilidad efectiva "(Kleene 1943: 274) o" método eficaz "(Rosser 1939: 225); esas formalizaciones incluido el Gödel-Herbrand-Kleene funciones recursivas de 1930, 1934 y 1935, Alonzo Iglesia de lambda cálculo de 1936, Emil Publicar "Formulación I" de 1936, y Alan Turing 's Máquinas de Turing de 1936-7 y 1939.

Etimología

Al-Khwarizmi , persa astrónomo y matemático , escribió un tratado en árabe en el año 825 dC, en el cálculo con números hindúes. (Ver algoritmo). Fue traducido al latín en el siglo 12 como Algoritmi de numero Indorum (al-Daffa 1977), cuyo título es probable que se pretende significar "[Reservación] Algoritmus sobre el número de los indios", donde "Algoritmi" era la interpretación del traductor del nombre del autor en el caso genitivo; pero las personas entienden mal el título tratados Algoritmi como plural latino y esto llevó a la palabra "algoritmo" (Algorismus América) que viene a significar "método de cálculo". El "th" intrusivo es más probable debido a una falso cognado con los griegos αριθμος (arithmos) que significa "número".

¿Por qué algoritmos son necesarios: una definición informal

Sin definición formal generalmente aceptada de "algoritmo" existe todavía. Podemos, sin embargo, obtener pistas sobre los temas en cuestión y un significado informal de la palabra de la siguiente cita de Boolos y Jeffrey (1974, 1999) (en negrita en el original):

Ningún ser humano puede escribir lo suficientemente rápido, o lo suficiente, o lo suficientemente pequeño como para enumerar todos los miembros de un conjunto infinito enumerably escribiendo sus nombres, uno tras otro, en alguna notación. Pero los seres humanos pueden hacer algo igualmente útil, en el caso de determinados conjuntos enumerably infinitas: Pueden dar instrucciones explícitas para determinar el miembro n del conjunto, por arbitraria finito n. Estas instrucciones son para ser dado de forma bastante explícita, en una forma en que podrían ser seguidos por una máquina de computación, o por un humano que es capaz de llevar a cabo operaciones de sólo muy elementales sobre los símbolos (Boolos y Jeffrey 1974, 1999, pág. 19 )

Las palabras "enumerably infinita" significan "contable utilizando números enteros tal vez se extienden hasta el infinito". Así Boolos y Jeffrey están diciendo que un algoritmo implica instrucciones para un proceso que "crea" enteros de salida de una "entrada" entero arbitrario o enteros que, en teoría, se puede elegir entre 0 a infinito. Por lo tanto podríamos esperar un algoritmo para ser una ecuación algebraica como y = m + n - dos "variables de entrada" arbitrarias m y n que producen una salida y. Como vemos en Caracterizaciones del algoritmo - la palabra algoritmo implica mucho más que eso, algo del orden de (para nuestro ejemplo de la suma):

Instrucciones precisas (en idioma comprensible para "la computadora") para un "buen rápido, eficiente," proceso que especifica los "movimientos" de "la computadora" (máquina o humano, equipado con la información contenida internamente y capacidades es necesario) para buscar, decodificar, y luego picar arbitrarias enteros de entrada / símbolos m y n, símbolos + y = ... y (de forma fiable, correctamente, "efectivamente") producir, en un "razonable" de tiempo , la producción entero 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 (lógica). Esa noción es central para explicar cómo sistemas formales vienen a ser 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, los tallos de la falta de disponibilidad de una definición de algoritmo que se adapte tanto hormigón (en algún sentido) y el uso abstracto del término.

Para una presentación detallada de los diversos puntos de vista alrededor de la definición de "algoritmo" ver Caracterizaciones algoritmo. Para ejemplos de algoritmos de adición de simples especificados en la forma detallada se describe en Caracterizaciones algoritmo, vea Ejemplos algoritmo.

Formalización de algoritmos

Los algoritmos son esenciales para la forma en que las computadoras procesan la información, debido a que un programa de ordenador es esencialmente un algoritmo que le dice a la computadora qué pasos específicos para llevar a cabo (en qué orden específico) con el fin de llevar a cabo una tarea específica, como por ejemplo el cálculo de "cheques de pago o la impresión de los estudiantes empleados boletas de calificaciones. Por lo tanto, un algoritmo puede considerarse ser cualquier secuencia de operaciones que se pueden realizar por una Turing-completo del sistema. Los autores que afirman esta tesis incluyen Savage (1987) y Gurevich (2000):

... Argumento informal de Turing en favor de su tesis justifica una tesis fuerte: cada algoritmo puede ser simulado por una máquina de Turing (Gurevich 2000: 1) ... según salvaje [1987], un algoritmo es un proceso computacional definida por una máquina de Turing. (Gurevich 2000: 3)

Normalmente, cuando un algoritmo está asociada con el procesamiento de la información, los datos se leen desde una fuente o dispositivo de entrada, escrito a un fregadero o dispositivo de salida, y / o almacenados para su posterior procesamiento. Los datos almacenados se consideran como parte del estado interno de la entidad que realiza el algoritmo. En la práctica, el estado se almacena en una estructura de datos, pero un algoritmo requiere que los datos internos sólo para conjuntos de operación específicas llamadas tipos de datos abstractos.

Para dicho proceso computacional, el algoritmo debe ser rigurosamente definido: se especifica en la forma en que se aplica en todas las circunstancias posibles que pudieran surgir. Es decir, las medidas condicionales debe 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 casi siempre será fundamental para el funcionamiento del algoritmo. Las instrucciones se asume generalmente que se enumeran explícitamente, y se describen como de partida "de la parte superior" e ir "hasta el fondo", una idea que se describe de manera más formal por flujo de control.

Hasta el momento, esta discusión sobre la formalización de un algoritmo ha asumido las instalaciones de programación imperativa. Esta es la concepción más común, y se trata de describir una tarea en discretas, significa "mecánicas". Único en esta concepción de algoritmos formales es el 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 sede programación funcional y programación lógica.

Terminación

Algunos escritores restringen la definición de algoritmo para los procedimientos que a la larga terminan. En una categoría tan Kleene coloca el "método o algoritmo procedimiento de toma de decisiones o para la pregunta" (Kleene 1952: 136). Otros, incluyendo Kleene, incluyen procedimientos que podrían funcionar para siempre sin parar; tal procedimiento se ha llamado un "método de cálculo" (Knuth 1997: 5) o "procedimiento de cálculo o algoritmo" (Kleene 1952: 137); Sin embargo, Kleene señala que tal método debe presentar eventualmente "un objeto" (Kleene 1952: 137).

Minsky hace la observación pertinente, en lo que respecta a la determinación de si un algoritmo eventualmente terminar (de un estado particular de partida):

Pero si la duración del proceso no se conoce de antemano, a continuación, 'tratando' puede no ser decisivo, ya que si el proceso lo hace durar para siempre - a continuación, en ningún momento, nunca vamos a estar seguros de la respuesta (Minsky, 1967: 105) .

Da la casualidad que ningún otro método puede hacer nada mejor, como se demostró por Alan Turing con su resultado célebre en la indecidibilidad de la llamada problema de la parada. No existe un procedimiento algorítmico para la determinación de algoritmos arbitrarios o no terminan de estados que comienzan dados. El análisis de algoritmos para la probabilidad de que la terminación se llama análisis terminación.

Vea los ejemplos de (im -) resta "adecuada" en función parcial para más información sobre lo que puede suceder cuando un algoritmo falla por algunos de sus números de entrada - por ejemplo, (i) no terminación, (ii) la producción de "basura" (salida en el formato correcto para ser considerado un número) o no número (s) en absoluto (alto termina el cálculo sin salida), (iii) número equivocado (s), o (iv) una combinación de éstos. Kleene propuso que la producción de "basura" o falta de presentación de un número se resuelve haciendo que el algoritmo de detección de estos casos y producir, por ejemplo, un mensaje de error (sugirió "0"), o preferiblemente, forzar el algoritmo en un bucle sin fin ( Kleene 1952: 322). Davis hace esto a su algoritmo de sustracción - fija su algoritmo en un segundo ejemplo de modo que es la resta adecuada (Davis 1958: 12-15). Junto con los resultados lógicos "verdadero" y "falso" Kleene también propone el uso de un tercer símbolo lógico "u" - indecisos (Kleene 1952: 326) - por lo tanto un algoritmo siempre producirá algo cuando se enfrenta a una "propuesta". El problema de las respuestas incorrectas se debe solucionar con una "prueba" independiente del algoritmo por ejemplo, el uso de la inducción:

Normalmente requerimos pruebas auxiliar para esto (que el algoritmo define correctamente un mu función recursiva), por ejemplo, en forma de una prueba inductiva que, para cada valor de argumento, el cálculo termina con un valor único (Minsky 1967: 186).

Expresando algoritmos

Los algoritmos pueden ser expresados en muchos tipos de notación, incluyendo lenguas naturales, pseudocódigo, diagramas de flujo, y lenguajes de programación . Expresiones de lenguaje natural de los algoritmos tienden a ser prolijo y ambigua, y rara vez se utilizan para algoritmos complejos o técnicos. Pseudocódigo y diagramas de flujo son formas estructuradas para expresar algoritmos que evitan muchas de las ambigüedades comunes en declaraciones en lenguaje natural, sin dejar de ser independiente de un lenguaje de implementación particular. Los lenguajes de programación están destinados principalmente para expresar algoritmos en una forma que puede ser ejecutado por un ordenador , pero se utilizan a menudo como una forma de definir o algoritmos de documentos.

Hay una amplia variedad de representaciones posible y uno puede expresar un dado Turing programa de la máquina como una secuencia de mesas de máquinas (ver más en máquina de estados finitos y transición de estados de mesa), como diagramas de flujo (ver más en diagrama de estado), o como una forma rudimentaria de código de máquina o código ensamblador llamado "conjuntos de cuádruples" (vea más en Máquina de Turing).

A veces es útil en la descripción de un algoritmo para complementar pequeños "diagramas de flujo" (diagramas de estado) con lenguaje natural y / o expresiones aritméticas escritas en el interior " diagramas de bloques "para resumir lo que los" diagramas de flujo "están logrando.

Las representaciones de los algoritmos son generalmente clasificados en tres niveles aceptados de Turing descripción de la máquina (Sipser 2006: 157):

• 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 en la cabeza"

• Descripción 2 Implementación:

"... La prosa utiliza para definir la forma en que la máquina de Turing utiliza su cabeza y la forma en que almacena datos sobre su cinta. A este nivel no damos detalles de estados o función de transición"

• 3 Descripción formal:

Lo más detallada, "nivel más bajo", da "tabla de estado" de la máquina de Turing.

Implementación

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 un biológica red neuronal (por ejemplo, el cerebro humano aplicación de la aritmética o un insecto en busca de comida), en una circuito eléctrico, o en un dispositivo mecánico.

Ejemplo

Uno de los algoritmos más simples es encontrar el mayor número en un (sin clasificar) lista de números. La solución necesariamente requiere mirar en cada número de la lista, pero sólo una vez en cada una. De esto se sigue un algoritmo simple, que puede ser indicado en una descripción de alto nivel de Inglés prosa, como:

Descripción de alto nivel:

1. Supongamos que el primer elemento es más grande.
2. Mira cada uno de los productos que queden en la lista y si es mayor que la partida más importante hasta el momento, tome nota de ello.
3. El último elemento señalado es el más grande en la lista cuando se complete el proceso.

(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:

 Algoritmo LargestNumber
   Entrada: Una lista no vacía de números L.
   Salida: El mayor número en la lista L.

   ← grande L 0
   para cada elemento de la lista L ≥1, hacer
     si el artículo> grande, a continuación,
       ← el elemento más grande
   volver más grande

Para un ejemplo más complejo de un algoritmo, ver El algoritmo de Euclides para el máximo común divisor , uno de los primeros algoritmos conocidos.

Análisis Algoritmo

Da la casualidad de que es importante saber qué cantidad de un recurso en particular (como el tiempo o el almacenamiento) se requiere para un algoritmo dado. Se han desarrollado métodos para la análisis de algoritmos para la obtención de tales respuestas cuantitativas; Por ejemplo, el algoritmo 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 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 una necesidad de espacio de O (1), si no se cuenta el espacio necesario para almacenar los números de entrada, u O (log 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 el esfuerzo que otros. Por ejemplo, dados dos recetas diferentes para hacer la ensalada de papa, uno puede tener la cáscara de la papa antes de hervir la papa mientras que el otro se presentan los pasos en el orden inverso, sin embargo, tanto en convocatoria de estos pasos que se repite para todos los papas y final cuando el ensalada de papas está listo para ser comido.

La análisis y estudio de algoritmos es una disciplina de ciencias de la computación , y se practica a menudo en abstracto y sin el uso de un determinado lenguaje de programación o ejecución. En este sentido, el análisis de algoritmo se asemeja a otras disciplinas matemáticas en que se centra en las propiedades subyacentes del algoritmo y no sobre 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 general.

Clases

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

Clasificación por aplicación

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

• La recursión o iteración: A algoritmo recursivo es aquel que invoca (hace referencia a) sí repetidamente hasta un cierto partidos de condición, que es un método común para programación funcional. Algoritmos iterativos utilizan construcciones repetitivas como bucles y estructuras de datos a veces adicionales como apila para resolver los problemas dados. Algunos problemas son adecuados naturalmente para una aplicación o la otra. Por ejemplo, Torres de Hanoi es bien entendido en la implementación recursiva. Cada versión recursiva tiene un equivalente (pero posiblemente más o menos complejo) versión iterativa, y viceversa.

• Lógico: Un algoritmo puede considerarse como controlada deducción lógica. Esta noción se puede expresar como: Algoritmo = + lógica de control (Kowalski 1979). El componente de lógica expresa los axiomas que pueden utilizarse 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 para la paradigma de la programación lógica. En los lenguajes de programación lógica pura del componente de control es fijo y algoritmos se especifican mediante el suministro de sólo el componente de la lógica. El atractivo de este enfoque es el elegante semántica: un cambio en los axiomas tiene un cambio bien definido en el algoritmo.

• Serie o paralelo o distribuido: Algoritmos suelen ser discutidos con la suposición de que las computadoras ejecutar una instrucción de un algoritmo a la vez. Esas computadoras a veces se llaman ordenadores de serie. Un algoritmo diseñado para un entorno de este tipo se denomina un algoritmo de serie, en contraposición a algoritmos paralelos o algoritmos distribuidos. Los algoritmos paralelos aprovechan de arquitecturas de computadora donde varios procesadores pueden trabajar en un problema, al mismo tiempo, mientras que los algoritmos distribuidos utilizan múltiples máquinas conectadas con una red. Los algoritmos paralelos o distribuidos dividen el problema en subproblemas más simétricos o asimétricos y recogen los resultados de nuevo juntos. El consumo de recursos en este tipo de algoritmos no es sólo ciclos de procesador en cada procesador, sino también a la sobrecarga de comunicación entre los procesadores. Algoritmos de ordenación pueden ser paralelizados eficientemente, pero sus gastos generales 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 algoritmo no determinista resolver problemas a través de adivinar aunque conjeturas típicos se hacen más precisa mediante el uso de heurística.

• Exacta o aproximada: Mientras que muchos algoritmos alcancen una solución exacta, algoritmos de aproximación buscan una aproximación que está cerca de la verdadera solución. Aproximación puede utilizar un determinista o una estrategia aleatoria. Estos algoritmos tienen valor práctico para muchos problemas difíciles.

Clasificación por paradigma de diseño

Otra forma de clasificar los algoritmos es por su metodología de diseño o paradigma. Hay un cierto número de paradigmas, cada uno diferente del otro. Además, cada una de estas categorías se incluyen muchos tipos diferentes de algoritmos. Algunos paradigmas se encuentran comúnmente incluyen:

• Divide y vencerás. La dividir y conquistar algoritmo reduce repetidamente una instancia de un problema a uno o más casos más pequeñas del mismo problema (por lo general recursivamente), hasta que los casos son lo suficientemente pequeño como para resolver fácilmente. Un ejemplo 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 clasificación de los datos completos se pueden obtener en la fase conquista mediante la fusión de ellos. Una variante más simple de divide y vencerás se llama 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 vencerás divide el problema en varios subproblemas y así conquistar el escenario será más compleja que la disminución y conquistar algoritmos. Un ejemplo de disminución y vencerás algoritmo es algoritmo de búsqueda binaria.
• La programación dinámica. Cuando un problema muestra subestructura óptima, es decir, la solución óptima a un problema puede ser construido a partir de soluciones óptimas para subproblemas, y subproblemas superpuestos, es decir, las mismas subproblemas se utilizan para resolver muchos casos de problemas diferentes, un enfoque más rápido llamado programación dinámica evita soluciones recomputing que ya han sido calculadas. Por ejemplo, la ruta más corta a un gol de un vértice en un ponderado gráfico se puede encontrar utilizando el camino más corto hacia la meta de todos los vértices adyacentes. La programación dinámica y memoization ir juntos. La principal diferencia entre la programación dinámica y divide y vencerás es que subproblemas son más o menos independiente en el divide y vencerás, mientras subproblemas se sobreponen en la programación dinámica. La diferencia entre la programación dinámica y la recursividad directa es 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. La algoritmo voraz es similar a una algoritmo de programación dinámica, pero la diferencia es que las soluciones a los subproblemas no tienen que ser conocido en cada etapa; en lugar de una elección "codiciosos" se puede hacer de lo que se ve mejor por el momento. El método codicioso extiende la solución con la mejor decisión posible (no todas las decisiones posibles) en una etapa algorítmica basada en la intensidad local óptima y la mejor decisión (no todas las decisiones posibles) realizado en la etapa anterior. No es exhaustiva, y no da respuesta precisa a muchos problemas. Pero cuando se trabaja, será el método más rápido. El algoritmo codicioso más popular es encontrar el árbol de expansión mínima dada por Kruskal.
• Programación lineal. Al resolver un problema utilizando programación lineal, específica desigualdades con las entradas se encuentran a continuación, se hace un intento de maximizar (o minimizar) una función lineal de las entradas. Muchos de los problemas (tales como la flujo máximo para dirigido gráficos) se puede afirmar de una manera programación lineal, y luego ser resuelto mediante un algoritmo de "genérico" como la algoritmo simplex. Una variante más compleja de la programación lineal se llama programación entera, donde el espacio de la solución se limita a los números enteros .
• Reducción. Esta técnica consiste en la resolución de un problema difícil al transformarla en un problema más conocido para los que tenemos (con suerte) asintóticamente algoritmos óptimos. El objetivo es encontrar un algoritmo de reducción de cuya complejidad no está dominado por los resultantes de la reducción de algoritmos. Por ejemplo, una algoritmo de selección para la búsqueda de la mediana en una lista sin ordenar involucra primera clasificación de la lista (la porción caro) y luego extraer el elemento medio en la lista ordenada (la porción barato). Esta técnica también se conoce como transformar y conquistar.
• Búsqueda y enumeración. Muchos de los problemas (como el juego de ajedrez ) pueden ser modelados como problemas en gráficos. La algoritmo de exploración gráfica especifica las reglas para moverse por una gráfica y es útil para este tipo de problemas. Esta categoría también incluye algoritmos de búsqueda, rama bound y enumeración retroceso.
• El paradigma probabilístico y heurístico. Algoritmos que pertenecen a esta clase se ajustan a la definición de un algoritmo más libremente.

1. Algoritmos probabilísticos son los que hacen algunas opciones al azar (o pseudo-azar); para algunos problemas, de hecho puede probarse que las soluciones más rápidas deben implicar algún aleatoriedad.
2. Los algoritmos genéticos intentan encontrar soluciones a los problemas imitando biológicas evolutivas procesos, con un ciclo de mutaciones al azar que producen las sucesivas generaciones de "soluciones". Por lo tanto, emulan la reproducción y la "supervivencia del más apto". En programación genética, este enfoque se extiende a los algoritmos, al considerar el propio algoritmo como una "solución" a un problema.
3. Los algoritmos heurísticos, cuyo propósito general no es encontrar una solución óptima, pero una solución aproximada en que el tiempo y los recursos son limitados. Ellos no son prácticos para encontrar soluciones perfectas. Un ejemplo de esto sería búsqueda local, tabu búsqueda o algoritmos de recocido simulado, una clase de algoritmos probabilísticos heurísticos que varíen la solución de un problema por una cantidad aleatoria. El nombre " recocido simulado "alude al término metalúrgico que significa que el calentamiento y enfriamiento del metal para lograr la libertad de defectos. El propósito de la variación aleatoria es encontrar cerca globalmente soluciones óptimas en lugar de los simplemente localmente óptimas, la idea es que el elemento aleatoria, los disminuir como el algoritmo se establece a una solución.

Clasificación por campo de estudio

Cada campo de la ciencia tiene sus propios problemas y necesidades de algoritmos eficientes. Problemas relacionados en un campo se estudian a menudo juntos. Algunas clases de ejemplo son algoritmos de búsqueda, algoritmos de ordenación, fusionar algoritmos, algoritmos numéricos, algoritmos de grafos, algoritmos de cuerda, algoritmos computacionales geométricas, algoritmos combinatorios , aprendizaje automático, criptografía , algoritmos de compresión de datos y técnicas de análisis.

Los campos tienden a superponerse entre sí, y los avances de algoritmos en un campo pueden mejorar las de otros, a veces sin ninguna relación, campos. Por ejemplo, la programación dinámica fue inventado originalmente 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.

Clasificación por complejidad

Los algoritmos pueden ser clasificados por la cantidad de tiempo que necesitan para completar en comparación con su tamaño de entrada. Hay una amplia variedad: algunos algoritmos completos en tiempo lineal en relación al tamaño de entrada, algunos lo hacen en una cantidad exponencial de tiempo o, peor aún, y algunos nunca detenga. Además, algunos problemas pueden tener múltiples algoritmos de diferente complejidad, 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ó que era más adecuado para clasificar los propios problemas en lugar de los algoritmos en clases de equivalencia basados en la complejidad de los mejores algoritmos posibles para ellos.

Clasificación por potencia de cálculo

Otra forma de clasificar los algoritmos es por el poder de computación. Esto suele hacerse al considerar alguna colección (clase) de los algoritmos. Una clase recursiva de algoritmos es la que incluye algoritmos para todas las funciones computables de Turing. En cuanto a las clases de algoritmos permite la posibilidad de limitar los recursos computacionales disponibles (tiempo y memoria) utilizadas en un cálculo. Una clase de algoritmos subrecursive es uno en el que no todas las funciones computables de Turing se pueden obtener. Por ejemplo, los algoritmos que se ejecute en polinomio tiempo suficiente para muchos tipos importantes de la computación, pero no agotan todas las funciones computables de Turing. Los algoritmos implementados por la clase funciones recursivas primitivas es otra clase subrecursive.

Burgin (2005, p. 24) utiliza una definición generalizada de algoritmos que relaja el requisito común de que la salida del algoritmo que calcula una función debe determinarse después de un número finito de pasos. Él define aa clase super recursiva de algoritmos como "una clase de algoritmos en el que es posible calcular funciones no computables por cualquier máquina de Turing" (Burgin 2005, p. 107). Esto está estrechamente relacionado con el estudio de los métodos de hipercomputación.

Cuestiones jurídicas

Algoritmos, por sí mismos, no suelen ser patentable. En Estados Unidos , una demanda que consiste únicamente en simples manipulaciones de conceptos abstractos, números o señales no constituyen "procesos" (USPTO 2006) y, por 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 sencillo algoritmo de retroalimentación para ayudar en la curación de caucho sintético se considera patentable. La patentes de software es muy controvertido, y hay patentes altamente criticado que implican algoritmos, especialmente algoritmos de compresión de datos, tales como Unisys Patentes LZW.

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

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

Origen de la palabra

El algoritmo de la palabra viene del nombre del siglo noveno Matemático persa Abu Abdullah Muhammad ibn Musa al-Khwarizmi cuyas obras introducidas numeración india y conceptos algebraicos. Trabajó en Bagdad en el momento en que era el centro de estudios científicos y el comercio. La palabra algorismo originalmente se refería únicamente a los estatutos de la realización de la aritmética usando Números arábigos, pero evolucionado a través de la traducción latina de Europa del nombre de al-Khwarizmi en el algoritmo por el siglo 18. La palabra evolucionó para incluir todos los procedimientos definidos para la resolución de problemas o la realización de tareas.

Símbolos discretos y distinguibles

Tally-marcas: Para hacer un seguimiento de sus rebaños, sus sacos de grano y su dinero los antiguos usaban recuento: la acumulación de piedras o marcas de arañazos en los palillos, o hacer símbolos discretos en arcilla. A través del uso babilónico y egipcio de marcas y símbolos, eventualmente números romanos y el ábaco evolucionado (Dilson, p.16-41). Marcas de conteo aparecen prominentemente en unario aritmética sistema de numeración utilizado en Máquina de Turing y Cálculos máquina Post-Turing.

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

El trabajo de los antiguos geómetras griegos, matemático persa Al-Khwarizmi (a menudo considerado como el "padre de la álgebra "), y los matemáticos de Europa Occidental culminaron en Leibniz noción de la 's ratiocinator cálculo (ca 1680):

"Un siglo bueno y medio por delante de su tiempo, Leibniz propuso un álgebra de la lógica, un álgebra que especificar las reglas para la manipulación de conceptos lógicos en la manera que el álgebra ordinaria especifica las reglas para manipular los números" (Davis 2000: 1)

Artificios mecánicos con estados discretos

El reloj: Bolter atribuye la invención de la impulsada por el peso del reloj como "La invención tecla [de Europa en la Edad Media]", en particular la punto de fuga <(Bolter, 1984: 24) que nos proporciona la garrapata y tac de un reloj mecánico. "La máquina automática precisa" (Bolter, 1984: 26) llevó inmediatamente a "mecánica autómatas "que comienza en el siglo XIII y, finalmente, a las" máquinas computacionales "- la motor de diferencias y motores analíticos de Charles Babbage y la condesa Ada Lovelace (páginas 33-34 Bolter, p.204-206).

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

Redes telefónicas de conmutación de electromecánica relés (inventado 1835) fue detrás del trabajo de George Stibitz (1937), el inventor del dispositivo de adición digital. Mientras trabajaba en los Laboratorios Bell, observó el uso "gravosa" de calculadoras mecánicas con engranajes. "Se fue a casa una noche en 1937 con la intención de poner a prueba su idea .... Cuando la era jugar más, Stibitz había construido un dispositivo de adición binaria". (Valley News, p. 13).

Davis (2000) señala la importancia particular del relé electromecánico (con sus dos "estados binarios"abiertosycerrados):

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

Matemáticas durante la década de 1800 hasta mediados de la década de 1900

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 la aritmética a una secuencia de símbolos manipulados por reglas. De Peano Los principios de la aritmética, presentado por un nuevo método (1888) fue "el primer intento de una axiomatización de las matemáticas en un lenguaje simbólico" (van Heijenoort: 81ff).

Pero Heijenoort da Frege (1879) esta felicitaciones: Frege es "quizás la obra más importante que se ha escrito en la lógica ... en la que vemos a." 'Lenguaje de fórmulas', que es uncharacterica lingua, 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 a reglas definidas "(van Heijenoort: 1). El trabajo de Frege era aún más simplificado y amplificada porAlfred North Whitehead yBertrand Russellen suPrincipia Mathematica (1910-1913).

Las paradojas : Al mismo tiempo, una serie de paradojas inquietantes apareció en la literatura, en particular, la paradoja de Burali-Forti (1897), la paradoja de Russell (1902-1903), y el Richard Paradox (Dixon 1906, cf Kleene 1952: 36 -40). Las consideraciones resultantes llevado a papel de Kurt Gödel (1931) - que cita específicamente la paradoja del mentiroso - que reduce por completo las reglas de la recursividad a números.

Calculabilidad efectiva : En un esfuerzo para 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 efectiva" 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 de JB Rosser λ-cálculo, (nota cf en Alonzo Iglesia 1936a: 90, 1936b: 110) una definición finamente afinado de "recursividad generales" de la obra de Gödel que actúe en sugerencias de Jacques Herbrand (Princeton conferencias cf de Gödel de 1934) y simplificaciones posteriores por Kleene (1935-6: 237ff, 1943: 255ff). Prueba de la Iglesia (1936: 88ff) que el Entscheidungsproblem era irresoluble, la definición de Emil Post calculabilidad efectiva como 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 la marca o borrar un papel o observar la papel y hacer un sí o no la decisión sobre la siguiente instrucción (cf "Formulación I", Post 1936: 289-290). Alan Turing prueba 's de que el Entscheidungsproblem era irresoluble por el uso de su "[Automático:] máquina a- "(Turing 1936-7: 116ff) - en efecto casi idéntico al de la publicación" formulación ", J. Definición de Barkley Rosser del "método eficaz" en términos de "una máquina" (Rosser 1939: 226). La propuesta de SC Kleene de un precursor de la " tesis de la Iglesia ", que él llamó" Tesis I "(Kleene 1943: 273-274), y unos años más tarde Kleene de cambiar el nombre de su tesis "Tesis de la Iglesia" (Kleene 1952: 300, 317) y la propuesta de "Tesis de Turing" (Kleene 1952: 376).

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

Aquí hay una notable coincidencia de dos hombres sin saber uno del otro, sino que describe un proceso de hombres-como-ordenadores que trabajan en cálculos - y producir definiciones virtualmente idénticas.

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

"... Dos conceptos están involucrados: la de unespacio de símboloen el que el trabajo que lleva de un problema de responder se debe llevar a cabo, y una inalterable fijoconjunto de direcciones.

Su espacio 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 pero una caja a la vez .... una caja es para admitir sino dos condiciones posibles, es decir, siendo vacía o no marcado, y que tienen una sola marca en él, por ejemplo un trazo vertical.

"Un cuadro es ser señalado y llamado 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, INPUT] está marcado con un golpe. Del mismo modo que la respuesta [es decir, SALIDA] es que debe darse 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 finalizará sólo cuando se trata de la dirección de tipo (C) [es decir, STOP]." (P T. 289-290) Ver más en máquina de Post-Turing

Alan Turing trabajo 's (1936, 1939: 160) precedió a la de Stibitz (1937); se desconoce si Stibitz sabía del trabajo de Turing. El biógrafo de Turing creía que el uso de Turing de un modelo de máquina de escribir como derivado de un interés juvenil: "Alan había soñado con inventar máquinas de escribir como un niño; Sra 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' "(Hodges, p. 96). Dada la prevalencia de código y la telegrafía Morse, 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, como lo hizo 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 (Turing 1936-7: 116).

"La computación se hace normalmente por escrito ciertos símbolos en el papel. Podemos suponer este trabajo se divide en cuadrados como libro de aritmética de un niño .... Supongo entonces que el cálculo se realiza sobre papel unidimensional, es decir, en una cinta dividida en cuadrados. me imagino también que el número de símbolos que pueden ser impresos 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 hay un B ligado al número de símbolos o plazas que el equipo puede observar en un momento. Si desea observar más, debe utilizar las observaciones sucesivas. También vamos a suponer que el número de estados de ánimo que necesita ser tomado en cuenta es finito ...

"Imaginemos que las operaciones realizadas por el equipo que se dividen en« operaciones simples ", que son tan elemental que no es fácil de imaginar aún más dividido" (Turing 1936-7: 136).

Reducción de Turing se obtiene la siguiente:

"Las operaciones simples, por tanto, deben incluir:

"(A) Cambios del símbolo en una de las plazas observados

"(B) Los cambios de una de las plazas observados a otro cuadrado dentro cuadrados L de una de las plazas previamente observados.

"Puede ser que algunos de estos cambios invocar necesariamente un cambio de estado de ánimo, por lo tanto la operación individual más general debe ser llevado a ser uno de los siguientes.:

"(A) Un posible cambio (a) de símbolo junto con un posible cambio de estado de ánimo.

"(B) Un cambio posible (b) de cuadrados observados, junto con un posible cambio de estado de ánimo"

"Ahora podemos construir una máquina para hacer el trabajo de este equipo." (Turing 1936-7: 136)

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

"Una función se dice que es" effectivey calculable "si sus valores se encuentran por algún proceso puramente mecánico. Aunque es bastante fácil conseguir una comprensión intuitiva de esta idea, es neverthessless deseable tener un poco más definido, definición expresable matemática ... [que discute 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 proceso puramente mecánico que pudiera se llevará a cabo por una máquina. Es posible dar una descripción matemática, en cierto 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 la 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 nos dejó" efectivamente calculabile (Turing 1939: 160) "se refieren a la idea intuitiva sin especial identificación con cualquiera de estas definiciones."

JB Rosser (1939) y SC Kleene (1943)

J. Barkley Rosserdefinido audazmente un "método eficaz [matemática] 'de la siguiente manera (en negrita en el original):

"" Método eficaz "se utiliza aquí en el sentido bastante especial de un método cada paso que es precisamente determinada y que es seguro para producir la respuesta en un número finito de pasos. Con este significado especial, se les ha dado tres definiciones precisas diferentes hasta la fecha [su nota al pie # 5; véase la discusión inmediatamente a continuación]. El más simple de estos para el estado (debido a Correos y Turing) dice esencialmente que. existe un método eficaz de resolver ciertos tipos de problemas si se puede construir una máquina que luego resolver cualquier problema del conjunto sin intervención humana más allá de la inserción de la cuestión 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 un muy fuerte argumento a favor de la exactitud de cualquiera ". (Rosser 1939: 225-6)

De Rosser nota # 5 referencias al trabajo de (1) Iglesia y Kleene y su definición de λ-definibilidad, en particular el uso de la Iglesia de la misma en su un problema insoluble de la teoría elemental de números (1936); (2) Herbrand y Gödel y su uso de la recursividad en el uso particular de Gödel en su famoso papel Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados I (1931); y (3) Publicar (1936) y de Turing (1936-7) en sus mecanismo de modelos de computación.

Stephen C. Kleene define como su ahora famoso "Tesis I" conocido como "la Tesis de Church-Turing ". Pero lo hizo en el siguiente contexto (negritas 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 el procedimiento termina necesariamente 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 predicado verdad?" "(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 problemas que rodean, en especial, fundamentos de las matemáticas (especialmente la Tesis de Church-Turing) y filosofía de la mente (especialmente los argumentos alrededor de la inteligencia artificial). Para más información, consulte las caracterizaciones del algoritmo.