Por el contrario, una heurística es un enfoque para la resolución de problemas que puede no estar completamente especificado o no garantizar resultados correctos u óptimos, especialmente en dominios de problemas donde no hay un resultado correcto u óptimo bien definido. [3] Por ejemplo, los sistemas de recomendación de redes sociales se basan en heurísticas de tal manera que, aunque ampliamente caracterizados como "algoritmos" en los medios populares del siglo XXI, no pueden ofrecer resultados correctos debido a la naturaleza del problema.
Como método eficaz , un algoritmo puede expresarse dentro de una cantidad finita de espacio y tiempo [4] y en un lenguaje formal bien definido [5] para calcular una función . [6] A partir de un estado inicial y una entrada inicial (quizás vacía ), [7] las instrucciones describen un cálculo que, cuando se ejecuta , procede a través de un número finito [8] de estados sucesivos bien definidos, produciendo eventualmente una "salida" [9] y terminando en un estado final. La transición de un estado al siguiente no es necesariamente determinista ; algunos algoritmos, conocidos como algoritmos aleatorios , incorporan una entrada aleatoria. [10]
Etimología
Alrededor del año 825 d. C., el científico y polímata persa Muḥammad ibn Mūsā al-Khwārizmī escribió kitāb al-ḥisāb al-hindī ("Libro de computación india") y kitab al-jam' wa'l-tafriq al-ḥisāb al-hindī ("Suma y resta en aritmética india"). [1] A principios del siglo XII, aparecieron traducciones latinas de dichos textos de al-Khwarizmi que involucraban el sistema de numeración hindú-arábigo y la aritmética , por ejemplo , Liber Alghoarismi de practica arismetrice , atribuido a Juan de Sevilla , y Liber Algorismi de numero Indorum , atribuido a Adelardo de Bath . [2] Por lo tanto, alghoarismi o algorismi es la latinización del nombre de Al-Khwarizmi; El texto comienza con la frase Dixit Algorismi , o "Así habló Al-Khwarizmi". [3] Alrededor de 1230, se atestigua la palabra inglesa algoritmo y luego, por Chaucer en 1391, los ingleses adoptaron el término francés. [4] [5] [ aclaración necesaria ] En el siglo XV, bajo la influencia de la palabra griega ἀριθμός ( arithmos , "número"; cf. "aritmética"), la palabra latina fue alterada a algorithmus . [ cita requerida ]
Definición
Una definición informal es "un conjunto de reglas que definen con precisión una secuencia de operaciones", [11] [ necesita citarse para verificar ] que incluiría todos los programas informáticos (incluidos los programas que no realizan cálculos numéricos) y (por ejemplo) cualquier procedimiento burocrático prescrito [12]
o receta de libro de cocina . [13] En general, un programa es un algoritmo solo si se detiene eventualmente [14] —aunque los bucles infinitos a veces pueden resultar deseables. Boolos, Jeffrey y 1974, 1999 definen un algoritmo como un conjunto de instrucciones para determinar un resultado, dado explícitamente, en una forma que puede ser seguida tanto por una máquina de computación como por un humano que solo podría realizar operaciones elementales específicas en símbolos . [15]
El concepto de algoritmo también se utiliza para definir la noción de decidibilidad , una idea que es fundamental para explicar cómo surgen los sistemas formales a partir de un pequeño conjunto de axiomas y reglas. En lógica , el tiempo que requiere un algoritmo para completarse no se puede medir, ya que no está relacionado con la dimensión física habitual. Estas incertidumbres que caracterizan el trabajo en curso se derivan de la falta de disponibilidad de una definición de algoritmo que se adapte tanto al uso concreto (en cierto sentido) como al abstracto del término.
La evidencia más temprana de algoritmos se encuentra en las matemáticas de la antigua Mesopotamia (actual Irak). Una tablilla de arcilla sumeria encontrada en Shuruppak cerca de Bagdad y que data de alrededor del 2500 a. C. describe el algoritmo de división más antiguo . [16] Durante la dinastía Hammurabi , alrededor del 1800 a . C. - alrededor del 1600 a. C. , las tablillas de arcilla babilónicas describían algoritmos para calcular fórmulas. [22] Los algoritmos también se usaban en la astronomía babilónica . Las tablillas de arcilla babilónicas describen y emplean procedimientos algorítmicos para calcular el tiempo y el lugar de eventos astronómicos significativos. [23]
El primer algoritmo criptográfico para descifrar códigos cifrados fue desarrollado por Al-Kindi , un matemático árabe del siglo IX, en Un manuscrito sobre el descifrado de mensajes criptográficos . Dio la primera descripción del criptoanálisis por análisis de frecuencia , el algoritmo de descifrado de códigos más antiguo. [21]
Computadoras
Relojes accionados por peso
Bolter atribuye la invención del reloj impulsado por pesas como "la invención clave [de Europa en la Edad Media]", específicamente el mecanismo de escape de verge [25] que proporciona el tic-tac de un reloj mecánico. "La máquina automática precisa" [26] condujo inmediatamente a los " autómatas mecánicos " a principios del siglo XIII y finalmente a las "máquinas computacionales": las máquinas diferenciales y analíticas de Charles Babbage y Ada Lovelace a mediados del siglo XIX. [27] A Lovelace se le atribuye la primera creación de un algoritmo destinado a procesarse en una computadora, la máquina analítica de Babbage, que es el primer dispositivo considerado una verdadera computadora Turing-completa en lugar de solo una calculadora . A Lovelace a veces se le llama como resultado de esto "la primera programadora de la historia", aunque una implementación completa del segundo dispositivo de Babbage no se realizaría hasta décadas después de su vida.
Relé electromecánico
Bell y Newell (1971) escriben que el telar Jacquard , precursor de las tarjetas Hollerith (tarjetas perforadas), y las "tecnologías de conmutación telefónica" llevaron al desarrollo de las primeras computadoras. [28] A mediados del siglo XIX, el telégrafo , precursor del teléfono, estaba en uso en todo el mundo. A fines del siglo XIX, la cinta de teletipo ( c. 1870 ) estaba en uso, al igual que las tarjetas Hollerith (c. 1890). Luego vino el teleimpresor ( c. 1910 ) con su uso de papel perforado de código Baudot en cinta.
En 1835 se inventaron las redes de conmutación telefónica de relés electromecánicos, que condujeron a la invención del sumador digital por parte de George Stibitz en 1937. Mientras trabajaba en los Laboratorios Bell, observó el uso "engorroso" de las calculadoras mecánicas con engranajes. "Una tarde de 1937 se fue a casa con la intención de probar su idea... Cuando terminó de hacer experimentos, Stibitz había construido un sumador binario". [29] [30]
Los algoritmos se pueden expresar en muchos tipos de notación, incluidos lenguajes naturales , pseudocódigo , diagramas de flujo , diagramas de drakon , lenguajes de programación o tablas de control (procesadas por intérpretes ). Las expresiones de algoritmos en lenguaje natural tienden a ser verbosas y ambiguas y rara vez se utilizan para algoritmos complejos o técnicos. El pseudocódigo, los diagramas de flujo, los diagramas de drakon y las tablas de control son formas estructuradas de expresar algoritmos que evitan muchas de las ambigüedades comunes en las declaraciones basadas en lenguaje natural. Los lenguajes de programación están destinados principalmente a expresar algoritmos en una forma que pueda ser ejecutada por una computadora, pero también se utilizan a menudo como una forma de definir o documentar algoritmos.
Máquinas de Turing
Existe una amplia variedad de representaciones posibles y se puede expresar un programa de máquina de Turing dado como una secuencia de tablas de máquina (ver máquina de estados finitos , tabla de transición de estados y tabla de control para más información), como diagramas de flujo y diagramas de drakon (ver diagrama de estados para más información), o como una forma de código de máquina rudimentario o código ensamblador llamado "conjuntos de cuádruples" (ver máquina de Turing para más información). Las representaciones de algoritmos también se pueden clasificar en tres niveles aceptados de descripción de la máquina de Turing: descripción de alto nivel, descripción de implementación y descripción formal. [33] Una descripción de alto nivel describe cualidades del algoritmo en sí, ignorando cómo se implementa en la máquina de Turing. [33] Una descripción de implementación describe la manera general en que la máquina mueve su cabeza y almacena datos para llevar a cabo el algoritmo, pero no da estados exactos. [33] Con más detalle, una descripción formal da la tabla de estados exacta y la lista de transiciones de la máquina de Turing. [33]
Representación en diagrama de flujo
El diagrama de flujo es una herramienta gráfica que permite describir y documentar un algoritmo (y un programa informático correspondiente). Al igual que el flujo de un programa de una máquina Minsky, un diagrama de flujo siempre comienza en la parte superior de una página y continúa hacia abajo. Sus símbolos primarios son sólo cuatro: la flecha que indica el flujo del programa, el rectángulo (SECUENCIA, IR A), el rombo (SI-ENTONCES-SINO) y el punto (OR-empate). Las estructuras canónicas de Böhm-Jacopini están formadas por estas formas primitivas. Las subestructuras pueden "anidar" en rectángulos, pero sólo si se produce una única salida desde la superestructura. Los símbolos y su uso para construir las estructuras canónicas se muestran en el diagrama. [34]
Análisis algorítmico
Con frecuencia es importante saber cuánto de un recurso particular (como tiempo o almacenamiento) se requiere teóricamente para un algoritmo dado. Se han desarrollado métodos para el análisis de algoritmos para obtener tales respuestas cuantitativas (estimaciones); por ejemplo, un algoritmo que suma los elementos de una lista de n números tendría un requerimiento de tiempo de , usando la notación O mayúscula . En todo momento el algoritmo solo necesita recordar dos valores: la suma de todos los elementos hasta el momento y su posición actual en la lista de entrada. Por lo tanto, se dice que tiene un requerimiento de espacio de , si no se cuenta el espacio requerido para almacenar los números de entrada, o si se cuenta.
Diferentes algoritmos pueden completar la misma tarea con un conjunto diferente de instrucciones en menos o más tiempo, espacio o " esfuerzo " que otros. Por ejemplo, un algoritmo de búsqueda binaria (con costo ) supera a una búsqueda secuencial (costo ) cuando se utiliza para búsquedas en tablas o matrices ordenadas.
Formal versus empírico
El análisis y estudio de algoritmos es una disciplina de la informática y, a menudo, se practica de forma abstracta sin el uso de un lenguaje de programación o implementación específicos. En este sentido, el análisis de algoritmos se parece a otras disciplinas matemáticas en que se centra en las propiedades subyacentes del algoritmo y no en los detalles de una implementación en particular. Por lo general, se utiliza pseudocódigo para el análisis, ya que es la representación más simple y general. Sin embargo, en última instancia, la mayoría de los algoritmos suelen implementarse en plataformas de hardware/software particulares y su eficiencia algorítmica se pone a prueba con el uso de código real. Para la solución de un problema "puntual", la eficiencia de un algoritmo particular puede no tener consecuencias significativas (a menos que n sea extremadamente grande), pero para algoritmos diseñados para un uso científico interactivo rápido, comercial o de larga duración puede ser fundamental. Escalar de n pequeño a n grande con frecuencia expone algoritmos ineficientes que, de lo contrario, serían benignos.
Las pruebas empíricas son útiles porque pueden descubrir interacciones inesperadas que afectan el rendimiento. Los puntos de referencia se pueden utilizar para comparar las posibles mejoras de un algoritmo antes y después de la optimización del programa. Sin embargo, las pruebas empíricas no pueden reemplazar el análisis formal y no son fáciles de realizar de manera justa. [35]
Eficiencia de ejecución
Para ilustrar las posibles mejoras posibles incluso en algoritmos bien establecidos, una innovación significativa reciente, relacionada con los algoritmos FFT (utilizados ampliamente en el campo del procesamiento de imágenes), puede reducir el tiempo de procesamiento hasta 1000 veces para aplicaciones como las imágenes médicas. [36] En general, las mejoras de velocidad dependen de propiedades especiales del problema, que son muy comunes en aplicaciones prácticas. [37] Las aceleraciones de esta magnitud permiten que los dispositivos informáticos que hacen un uso extensivo del procesamiento de imágenes (como cámaras digitales y equipos médicos) consuman menos energía.
Diseño
El diseño de algoritmos se refiere a un método o proceso matemático para la resolución de problemas y la ingeniería de algoritmos. El diseño de algoritmos es parte de muchas teorías de solución, como la de divide y vencerás o la programación dinámica dentro de la investigación de operaciones . Las técnicas para diseñar e implementar diseños de algoritmos también se denominan patrones de diseño de algoritmos, [38] con ejemplos que incluyen el patrón de método de plantilla y el patrón decorador. Uno de los aspectos más importantes del diseño de algoritmos es la eficiencia de los recursos (tiempo de ejecución, uso de memoria); la notación O mayúscula se utiliza para describir, por ejemplo, el crecimiento del tiempo de ejecución de un algoritmo a medida que aumenta el tamaño de su entrada. [39]
Programación estructurada
Según la tesis de Church-Turing , cualquier algoritmo puede ser calculado por un modelo conocido como Turing completo . De hecho, se ha demostrado que la completitud de Turing requiere solo cuatro tipos de instrucciones: GOTO condicional, GOTO incondicional, asignación, HALT. Sin embargo, Kemeny y Kurtz observan que, si bien el uso "indisciplinado" de GOTO incondicionales y GOTO IF-THEN condicionales puede resultar en " código espagueti ", un programador puede escribir programas estructurados utilizando solo estas instrucciones; por otro lado, "también es posible, y no demasiado difícil, escribir programas mal estructurados en un lenguaje estructurado". [40] Tausworthe aumenta las tres estructuras canónicas de Böhm-Jacopini : [41] SEQUENCE, IF-THEN-ELSE y WHILE-DO, con dos más: DO-WHILE y CASE. [42] Un beneficio adicional de un programa estructurado es que se presta a pruebas de corrección mediante inducción matemática . [43]
Estatus legal
Los algoritmos, por sí mismos, no suelen ser patentables. En los Estados Unidos, una reivindicación que consiste únicamente en manipulaciones simples de conceptos abstractos, números o señales no constituye "procesos" (USPTO 2006), por lo que los algoritmos no son patentables (como en Gottschalk v. Benson ). Sin embargo, las aplicaciones prácticas de los algoritmos a veces sí lo son. Por ejemplo, en Diamond v. Diehr , se consideró patentable la aplicación de un algoritmo de retroalimentación simple para ayudar en el curado de caucho sintético . El patentamiento de software es controvertido, [44] y existen patentes criticadas que involucran algoritmos, especialmente algoritmos de compresión de datos , como la patente LZW de Unisys . Además, algunos algoritmos criptográficos tienen restricciones de exportación (véase exportación de criptografía ).
Clasificación
Hay varias formas de clasificar los algoritmos, cada una con sus propios méritos.
Por implementación
Una forma de clasificar los algoritmos es por medios de implementación.
Recursión
Un algoritmo recursivo es aquel que se invoca (hace referencia a) sí mismo repetidamente hasta que se cumple una determinada condición (también conocida como condición de terminación), lo cual es un método común en la programación funcional . Los algoritmos iterativos utilizan construcciones repetitivas como bucles y, a veces, estructuras de datos adicionales como pilas para resolver los problemas dados. Algunos problemas son naturalmente adecuados para una implementación u otra. Por ejemplo, las torres de Hanoi se entienden bien utilizando la implementación recursiva. Cada versión recursiva tiene una versión iterativa equivalente (pero posiblemente más o menos compleja), y viceversa.
Serie, paralelo o distribuido
Los algoritmos se suelen analizar con la suposición de que las computadoras ejecutan una instrucción de un algoritmo a la vez. Esas computadoras a veces se denominan computadoras seriales. Un algoritmo diseñado para un entorno de este tipo se denomina algoritmo serial, a diferencia de los algoritmos paralelos o algoritmos distribuidos . Los algoritmos paralelos son algoritmos que aprovechan las arquitecturas informáticas en las que varios procesadores pueden trabajar en un problema al mismo tiempo. Los algoritmos distribuidos son algoritmos que utilizan varias máquinas conectadas a una red informática. Los algoritmos paralelos y distribuidos dividen el problema en subproblemas más simétricos o asimétricos y recopilan los resultados juntos. Por ejemplo, una CPU sería un ejemplo de un algoritmo paralelo. El consumo de recursos en tales algoritmos no solo son ciclos de procesador en cada procesador, sino también la sobrecarga de comunicación entre los procesadores. Algunos algoritmos de ordenamiento se pueden paralelizar de manera eficiente, pero su sobrecarga de comunicación es costosa. Los algoritmos iterativos generalmente son paralelizables, pero algunos problemas no tienen algoritmos paralelos y se denominan problemas inherentemente seriales.
Si bien muchos algoritmos alcanzan una solución exacta, los algoritmos de aproximación buscan una aproximación que esté más cerca de la solución verdadera. La aproximación se puede alcanzar utilizando una estrategia determinista o aleatoria. Dichos algoritmos tienen valor práctico para muchos problemas difíciles. Uno de los ejemplos de un algoritmo aproximado es el problema de la mochila , donde hay un conjunto de elementos dados. Su objetivo es llenar la mochila para obtener el máximo valor total. Cada elemento tiene cierto peso y cierto valor. El peso total que se puede transportar no es más que un número fijo X. Por lo tanto, la solución debe considerar los pesos de los elementos, así como su valor. [45]
Otra forma de clasificar los algoritmos es por su metodología de diseño o paradigma . Existe un cierto número de paradigmas, cada uno diferente del otro. Además, cada una de estas categorías incluye muchos tipos diferentes de algoritmos. Algunos paradigmas comunes son:
La fuerza bruta es un método de resolución de problemas que implica probar sistemáticamente todas las opciones posibles hasta encontrar la solución óptima. Este enfoque puede requerir mucho tiempo, ya que requiere analizar todas las combinaciones posibles de variables. Sin embargo, se suele utilizar cuando no hay otros métodos disponibles o son demasiado complejos. La fuerza bruta se puede utilizar para resolver una variedad de problemas, como encontrar el camino más corto entre dos puntos y descifrar contraseñas.
Divide y vencerás
Un algoritmo de divide y vencerás reduce repetidamente una instancia de un problema a una o más instancias más pequeñas del mismo problema (generalmente de forma recursiva ) hasta que las instancias son lo suficientemente pequeñas como para resolverlas fácilmente. Un ejemplo de este tipo de divide y vencerás es la ordenación por fusión . La ordenación se puede realizar en cada segmento de datos después de dividir los datos en segmentos y la ordenación de todos los datos se puede obtener en la fase de conquista fusionando los segmentos. Una variante más simple de divide y vencerás se llama algoritmo de disminución y vencerás , que resuelve un subproblema idéntico y usa la solución de este subproblema para resolver el problema más grande. Divide y vencerás divide el problema en múltiples subproblemas y, por lo tanto, la etapa de conquista es más compleja que los algoritmos de disminución y vencerás. Un ejemplo de un algoritmo de disminución y vencerás es el algoritmo de búsqueda binaria .
Estos algoritmos toman algunas decisiones de forma aleatoria (o pseudoaleatoria). Pueden ser muy útiles para encontrar soluciones aproximadas a problemas en los que encontrar soluciones exactas puede resultar poco práctico (véase el método heurístico a continuación). Para algunos de estos problemas, se sabe que las aproximaciones más rápidas deben implicar cierta aleatoriedad . [46] Si los algoritmos aleatorios con complejidad temporal polinómica pueden ser el algoritmo más rápido para algunos problemas es una pregunta abierta conocida como el problema P versus NP . Hay dos grandes clases de tales algoritmos:
Los algoritmos de Las Vegas siempre devuelven la respuesta correcta, pero su tiempo de ejecución solo está limitado probabilísticamente, por ejemplo, ZPP .
Esta técnica implica resolver un problema difícil transformándolo en un problema más conocido para el que tenemos algoritmos asintóticamente óptimos (con suerte) . El objetivo es encontrar un algoritmo reductor cuya complejidad no esté dominada por los algoritmos reducidos resultantes. Por ejemplo, un algoritmo de selección para encontrar la mediana en una lista desordenada implica primero ordenar la lista (la parte costosa) y luego extraer el elemento del medio en la lista ordenada (la parte barata). Esta técnica también se conoce como transformar y conquistar .
En este enfoque, se crean múltiples soluciones de forma incremental y se abandonan cuando se determina que no pueden conducir a una solución completa válida.
Problemas de optimización
Para los problemas de optimización existe una clasificación más específica de algoritmos; un algoritmo para tales problemas puede caer en una o más de las categorías generales descritas anteriormente, así como en una de las siguientes:
Al buscar soluciones óptimas para una función lineal ligada a restricciones de igualdad y desigualdad lineales, las restricciones del problema se pueden usar directamente para producir las soluciones óptimas. Hay algoritmos que pueden resolver cualquier problema en esta categoría, como el popular algoritmo simplex . [47] Los problemas que se pueden resolver con programación lineal incluyen el problema de flujo máximo para grafos dirigidos. Si un problema requiere adicionalmente que una o más de las incógnitas deben ser un número entero , entonces se clasifica en programación entera . Un algoritmo de programación lineal puede resolver dicho 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.
Cuando un problema muestra subestructuras óptimas (es decir, la solución óptima de un problema se puede construir a partir de soluciones óptimas de subproblemas) y subproblemas superpuestos (es decir, los mismos subproblemas se utilizan para resolver muchas instancias de problemas diferentes), un enfoque más rápido llamado programación dinámica evita volver a calcular soluciones que ya se han calculado. Por ejemplo, el algoritmo Floyd-Warshall , el camino más corto a un objetivo desde un vértice en un gráfico ponderado , se puede encontrar utilizando el camino más corto al objetivo desde todos los vértices adyacentes. La programación dinámica y la memorización van de la mano. La principal diferencia entre la programación dinámica y divide y vencerás es que los subproblemas son más o menos independientes en divide y vencerás, mientras que los subproblemas se superponen en la programación dinámica. La diferencia entre la programación dinámica y la recursión directa está en el almacenamiento en caché o la memorización de las llamadas recursivas. Cuando los subproblemas son independientes y no hay repetición, la memorización no ayuda; por lo tanto, la programación dinámica no es una solución para todos los problemas complejos. Al utilizar la memorización o mantener una tabla de subproblemas ya resueltos, la programación dinámica reduce la naturaleza exponencial de muchos problemas a una complejidad polinomial.
El método codicioso
Un algoritmo voraz es similar a un algoritmo de programación dinámica en que funciona examinando subestructuras, en este caso no del problema sino de una solución dada. Tales algoritmos comienzan con alguna solución, que puede estar dada o haber sido construida de alguna manera y la mejoran haciendo pequeñas modificaciones. Para algunos problemas pueden encontrar la solución óptima mientras que para otros se detienen en óptimos locales , es decir, en soluciones que no pueden ser mejoradas por el algoritmo pero que no son óptimas. El uso más popular de los algoritmos voraces es para encontrar el árbol de expansión mínimo donde es posible encontrar la solución óptima con este método. Huffman Tree , Kruskal , Prim , Sollin son algoritmos voraces que pueden resolver este problema de optimización.
El método heurístico
En los problemas de optimización , se pueden utilizar algoritmos heurísticos para encontrar una solución cercana a la solución óptima en los casos en que encontrar la solución óptima no es práctico. Estos algoritmos funcionan acercándose cada vez más a la solución óptima a medida que avanzan. En principio, si se ejecutan durante una cantidad infinita de tiempo, encontrarán la solución óptima. Su mérito es que pueden encontrar una solución muy cercana a la solución óptima en un tiempo relativamente corto. Dichos algoritmos incluyen la búsqueda local , la búsqueda tabú , el recocido simulado y los algoritmos genéticos . Algunos de ellos, como el recocido simulado, son algoritmos no deterministas, mientras que otros, como la búsqueda tabú, son deterministas. Cuando se conoce un límite en el error de la solución no óptima, el algoritmo se clasifica además como un algoritmo de aproximación .
Ejemplos
Uno de los algoritmos más simples consiste en encontrar el número más grande en una lista de números ordenados aleatoriamente. Para encontrar la solución es necesario examinar cada número de la lista. De esto se desprende un algoritmo simple, que puede enunciarse en una descripción de alto nivel en prosa inglesa como:
Descripción de alto nivel:
Si no hay números en el conjunto, entonces no hay número más alto.
Supongamos que el primer número del conjunto es el número más grande del conjunto.
Para cada número restante en el conjunto: si este número es mayor que el número más grande actual, considere este número como el número más grande del conjunto.
Cuando no quedan números en el conjunto para iterar, considere que el número más grande actual es el número más grande del conjunto.
Descripción (cuasi)formal:
Escrita en prosa pero mucho más cercana al lenguaje de alto nivel de un programa de computadora, la siguiente es la codificación más formal del algoritmo en pseudocódigo o código pidgin :
Algoritmo Número más grandeEntrada: Una lista de números L .Salida: El número más grande de la lista L.
si L.size = 0 devuelve nulo más grande ← L [0] para cada elemento en L , hazlo si elemento > más grande , entonces más grande ← elemento devuelve más grande
"←" denota asignación . Por ejemplo, " el elemento más grande ← " significa que el valor del elemento más grande cambia al valor del elemento .
" return " finaliza el algoritmo y genera el siguiente valor.
^ ab «Definición de ALGORITMO». Diccionario en línea Merriam-Webster . Archivado desde el original el 14 de febrero de 2020. Consultado el 14 de noviembre de 2019 .
^ de Blair, Ann, Duguid, Paul, Goeing, Anja-Silvia y Grafton, Anthony. Información: A Historical Companion, Princeton: Princeton University Press, 2021. p. 247
^ de David A. Grossman, Ophir Frieder, Recuperación de información: algoritmos y heurísticas , 2.ª edición, 2004, ISBN 1402030045
^ ab "Cualquier algoritmo matemático clásico, por ejemplo, puede describirse en un número finito de palabras en inglés" (Rogers 1987:2).
^ ab Bien definido respecto del agente que ejecuta el algoritmo: "Hay un agente computacional, generalmente humano, que puede reaccionar a las instrucciones y realizar los cálculos" (Rogers 1987:2).
^ "un algoritmo es un procedimiento para calcular una función (relativa a una notación elegida para números enteros) ... esta limitación (a funciones numéricas) no produce ninguna pérdida de generalidad", (Rogers 1987:1).
^ "Un algoritmo tiene cero o más entradas, es decir, cantidades que se le dan inicialmente antes de que el algoritmo comience" (Knuth 1973:5).
^ "Un procedimiento que tiene todas las características de un algoritmo excepto que posiblemente carece de finitud puede llamarse un 'método computacional ' " (Knuth 1973:5).
^ "Un algoritmo tiene una o más salidas, es decir, cantidades que tienen una relación específica con las entradas" (Knuth 1973:5).
^ Es discutible si un proceso con procesos internos aleatorios (sin incluir la entrada) es un algoritmo. Rogers opina que: "un cálculo se lleva a cabo de manera discreta y por pasos, sin el uso de métodos continuos o dispositivos analógicos... llevado adelante de manera determinista, sin recurrir a métodos o dispositivos aleatorios, por ejemplo, dados" (Rogers 1987:2).
^ Piedra 1973:4
^ Simanowski, Roberto (2018). El algoritmo de la muerte y otros dilemas digitales. Meditaciones inoportunas. Vol. 14. Traducido por Chase, Jefferson. Cambridge, Massachusetts: MIT Press. p. 147. ISBN9780262536370. Archivado del original el 22 de diciembre de 2019 . Consultado el 27 de mayo de 2019 . [...] el siguiente nivel de abstracción de la burocracia central: algoritmos que operan globalmente.
^ Dietrich, Eric (1999). "Algoritmo". En Wilson, Robert Andrew; Keil, Frank C. (eds.). La enciclopedia MIT de las ciencias cognitivas. Biblioteca MIT Cognet. Cambridge, Massachusetts: MIT Press (publicado en 2001). pág. 11. ISBN9780262731447. Recuperado el 22 de julio de 2020. Un algoritmo es una receta, método o técnica para hacer algo.
^ Stone exige que "debe terminar en un número finito de pasos" (Stone 1973:7–8).
^ Boolos y Jeffrey 1974,1999:19
^ abcd Chabert, Jean-Luc (2012). Una historia de los algoritmos: del Pebble al microchip . Springer Science & Business Media. págs. 7-8. ISBN9783642181924.
^ ab Sriram, MS (2005). "Algoritmos en las matemáticas indias". En Emch, Gerard G.; Sridharan, R.; Srinivas, MD (eds.). Contribuciones a la historia de las matemáticas indias . Springer. pág. 153. ISBN978-93-86279-25-5.
^ Hayashi, T. (1 de enero de 2023). Brahmagupta. Enciclopedia Británica.
^ Zaslavsky, Claudia (1970). "Matemáticas del pueblo yoruba y de sus vecinos en el sur de Nigeria". The Two-Year College Mathematics Journal . 1 (2): 76–99. doi :10.2307/3027363. ISSN 0049-4925. JSTOR 3027363.
^ abc Cooke, Roger L. (2005). La historia de las matemáticas: un breve curso . John Wiley & Sons. ISBN978-1-118-46029-0.
^ ab Dooley, John F. (2013). Una breve historia de la criptología y los algoritmos criptográficos . Springer Science & Business Media. págs. 12-3. ISBN9783319016283.
^ Knuth, Donald E. (1972). "Algoritmos babilónicos antiguos" (PDF) . Commun. ACM . 15 (7): 671–677. doi :10.1145/361454.361514. ISSN 0001-0782. S2CID 7829945. Archivado desde el original (PDF) el 24 de diciembre de 2012.
^ Aaboe, Asger (2001). Episodios de la historia temprana de la astronomía . Nueva York: Springer. pp. 40–62. ISBN978-0-387-95136-2.
^ Ast, Courtney. "Eratóstenes". Universidad Estatal de Wichita: Departamento de Matemáticas y Estadística. Archivado desde el original el 27 de febrero de 2015. Consultado el 27 de febrero de 2015 .
^ Bolter 1984:24
^ Bolter 1984:26
^ Bólter 1984: 33–34, 204–206.
^ Diagrama de Bell y Newell 1971:39, cf. Davis 2000
^ Melina Hill, corresponsal de Valley News, Un manitas obtiene un lugar en la historia , Valley News West Lebanon NH, jueves 31 de marzo de 1983, pág. 13.
^ Davis 2000:14
^ Kleene 1943 en Davis 1965:274
^ Rosser 1939 en Davis 1965:225
^ abcd Sipser 2006:157
^ Véase Tausworthe 1977
^ Kriegel, Hans-Peter ; Schubert, Erich; Zimek, Arthur (2016). "El arte (negro) de la evaluación en tiempo de ejecución: ¿estamos comparando algoritmos o implementaciones?". Knowledge and Information Systems . 52 (2): 341–378. doi :10.1007/s10115-016-1004-2. ISSN 0219-1377. S2CID 40772241.
^ Gillian Conahan (enero de 2013). "Better Math Makes Faster Data Networks" (Una mejor matemática permite crear redes de datos más rápidas). discovermagazine.com. Archivado desde el original el 13 de mayo de 2014. Consultado el 13 de mayo de 2014 .
^ Haitham Hassanieh, Piotr Indyk , Dina Katabi y Eric Price, "Simposio ACM-SIAM sobre algoritmos discretos (SODA) Archivado el 4 de julio de 2013 en Wayback Machine , Kioto, enero de 2012. Véase también la página web de sFFT Archivado el 21 de febrero de 2012 en Wayback Machine .
^ Goodrich, Michael T .; Tamassia, Roberto (2002). Diseño de algoritmos: fundamentos, análisis y ejemplos de Internet. John Wiley & Sons, Inc. ISBN978-0-471-38365-9Archivado desde el original el 28 de abril de 2015 . Consultado el 14 de junio de 2018 .
^ "Notación Big-O (artículo) | Algoritmos". Khan Academy . Consultado el 3 de junio de 2024 .
^ John G. Kemeny y Thomas E. Kurtz 1985 De vuelta a lo básico: la historia, la corrupción y el futuro del lenguaje , Addison-Wesley Publishing Company, Inc. Reading, MA, ISBN 0-201-13433-0 .
^ Tausworthe 1977:101
^ Tausworthe 1977:142
^ Knuth 1973 sección 1.2.1, ampliada por Tausworthe 1977 en las páginas 100 y siguientes y el Capítulo 9.1
^ "Los expertos: ¿el sistema de patentes fomenta la innovación?". The Wall Street Journal . 16 de mayo de 2013. ISSN 0099-9660 . Consultado el 29 de marzo de 2017 .
^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Problemas con la mochila | Hans Kellerer | Saltador. Saltador. doi :10.1007/978-3-540-24777-7. ISBN978-3-540-40286-2. S2CID 28836720. Archivado desde el original el 18 de octubre de 2017 . Consultado el 19 de septiembre de 2017 .
^ Por ejemplo, el volumen de un politopo convexo (descrito usando un oráculo de membresía) puede aproximarse con alta precisión mediante un algoritmo de tiempo polinomial aleatorio, pero no mediante uno determinista: véase Dyer, Martin; Frieze, Alan; Kannan, Ravi (enero de 1991). "Un algoritmo de tiempo polinomial aleatorio para aproximar el volumen de cuerpos convexos". J. ACM . 38 (1): 1–17. CiteSeerX 10.1.1.145.4600 . doi :10.1145/102782.102783. S2CID 13268711.
^ George B. Dantzig y Mukund N. Thapa. 2003. Programación lineal 2: teoría y extensiones . Springer-Verlag.
Bibliografía
Axt, P (1959). "Sobre una jerarquía subrecursiva y grados recursivos primitivos". Transactions of the American Mathematical Society . 92 (1): 85–105. doi : 10.2307/1993169 . JSTOR 1993169.
Bell, C. Gordon y Newell, Allen (1971), Estructuras informáticas: lecturas y ejemplos , McGraw–Hill Book Company, Nueva York. ISBN 0-07-004357-4 .
Blass, Andreas ; Gurevich, Yuri (2003). "Algoritmos: una búsqueda de definiciones absolutas" (PDF) . Boletín de la Asociación Europea de Ciencias Informáticas Teóricas . 81 . Archivado (PDF) desde el original el 9 de octubre de 2022.Incluye una bibliografía de 56 referencias.
Bolter, David J. (1984). El hombre de Turing: la cultura occidental en la era de la informática (edición de 1984). Chapel Hill, NC: The University of North Carolina Press. ISBN 978-0-8078-1564-9., ISBN 0-8078-4108-0
Boolos, George ; Jeffrey, Richard (1999) [1974]. Computabilidad y lógica (4ª ed.). Cambridge University Press, Londres. ISBN 978-0-521-20402-6.:cf. Capítulo 3 Máquinas de Turing, donde se analizan "ciertos conjuntos enumerables que no son efectivamente (mecánicamente) enumerables".
Burgin, Mark (2004). Algoritmos superrecursivos . Springer. ISBN 978-0-387-95569-8.
Campagnolo, ML, Moore, C. y Costa, JF (2000) Una caracterización analógica de las funciones subrecursivas. En Proc. de la 4.ª Conferencia sobre números reales y computadoras , Universidad de Odense, págs. 91-109
Church, Alonzo (1936). "Un problema irresoluble de la teoría elemental de números". American Journal of Mathematics . 58 (2): 345–363. doi :10.2307/2371045. JSTOR 2371045.Reimpreso en The Undecidable , pág. 89 y siguientes. Primera expresión de la «Tesis de Church». Véase en particular la página 100 ( The Undecidable ), donde define la noción de «calculabilidad efectiva» en términos de «un algoritmo», y utiliza la palabra «termina», etc.
Church, Alonzo (1936). "Una nota sobre el problema de la entscheidung". Revista de lógica simbólica . 1 (1): 40–41. doi :10.2307/2269326. JSTOR 2269326. S2CID 42323521. Church, Alonzo (1936). "Corrección a una nota sobre el Entscheidungsproblem". The Journal of Symbolic Logic . 1 (3): 101–102. doi :10.2307/2269030. JSTOR 2269030. S2CID 5557237.Reimpreso en The Undecidable , pág. 110 y siguientes. Church muestra que el Entscheidungsproblem es irresoluble en aproximadamente 3 páginas de texto y 3 páginas de notas a pie de página.
Daffa', Ali Abdullah al- (1977). La contribución musulmana a las matemáticas . Londres: Croom Helm. ISBN 978-0-85664-464-1.
Davis, Martin (1965). Lo indecidible: artículos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables . Nueva York: Raven Press. ISBN 978-0-486-43228-1.Davis ofrece comentarios antes de cada artículo. Se incluyen los trabajos de Gödel , Alonzo Church , Turing , Rosser , Kleene y Emil Post ; los autores citados en el artículo aparecen enumerados aquí por nombre de autor.
Dean, Tim (2012). "Evolución y diversidad moral". Anuario internacional báltico de cognición, lógica y comunicación . 7 . doi : 10.4148/biyclc.v7i0.1775 .
Yuri Gurevich , Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, vol. 1, n.º 1 (julio de 2000), págs. 77-111. Incluye bibliografía de 33 fuentes.
van Heijenoort, Jean (2001). From Frege to Gödel, A Source Book in Mathematical Logic, 1879–1931 (edición de 1967). Harvard University Press, Cambridge. ISBN 978-0-674-32449-7., 3.a edición 1976[?], ISBN 0-674-32449-8 (pbk.)
Kleene, Stephen C. (1936). «Funciones recursivas generales de números naturales». Mathematische Annalen . 112 (5): 727–742. doi :10.1007/BF01565439. S2CID 120517999. Archivado desde el original el 3 de septiembre de 2014 . Consultado el 30 de septiembre de 2013 .Presentado a la American Mathematical Society, septiembre de 1935. Reimpreso en The Undecidable , p. 237ff. La definición de Kleene de "recursión general" (conocida ahora como mu-recursión) fue utilizada por Church en su artículo de 1935 An Unsolvable Problem of Elementary Number Theory que demostró que el "problema de decisión" era "indecidible" (es decir, un resultado negativo).
Kleene, Stephen C. (1943). "Predicados recursivos y cuantificadores". Transactions of the American Mathematical Society . 53 (1): 41–73. doi : 10.2307/1990131 . JSTOR 1990131.Reimpreso en The Undecidable , pág. 255ff. Kleene refinó su definición de "recursión general" y procedió en su capítulo "12. Teorías algorítmicas" a postular la "Tesis I" (pág. 274); más tarde repetiría esta tesis (en Kleene 1952:300) y la llamaría "Tesis de Church" (Kleene 1952:317) (es decir, la tesis de Church ).
Kleene, Stephen C. (1991) [1952]. Introducción a las metamatemáticas (décima edición). North-Holland Publishing Company. ISBN 978-0-7204-2103-3.
Knuth, Donald (1997). Algoritmos fundamentales, tercera edición . Reading, Massachusetts: Addison–Wesley. ISBN 978-0-201-89683-1.
Knuth, Donald (1969). Volumen 2/Algoritmos seminuméricos, El arte de la programación informática Primera edición . Reading, Massachusetts: Addison–Wesley.
Kosovsky, NK Elementos de lógica matemática y su aplicación a la teoría de algoritmos subrecursivos , LSU Publ., Leningrado, 1981
AA Markov (1954) Teoría de algoritmos . [Traducido por Jacques J. Schorr-Kon y personal del PST] Pie de imprenta Moscú, Academia de Ciencias de la URSS, 1954 [es decir, Programa de Jerusalén, Israel para Traducciones Científicas, 1961; disponible en la Oficina de Servicios Técnicos, Departamento de Comercio de EE. UU., Washington] Descripción 444 pág. 28 cm. Se agregó tp en Traducción al ruso de Obras del Instituto de Matemáticas, Academia de Ciencias de la URSS, v. 42. Título original: Teoriya algerifmov. [QA248.M2943 Biblioteca del Dartmouth College. Departamento de Comercio de EE. UU., Oficina de Servicios Técnicos, número OTS 60-51085.]
Minsky, Marvin (1967). Computación: máquinas finitas e infinitas (Primera edición). Prentice-Hall, Englewood Cliffs, NJ. ISBN 978-0-13-165449-5.Minsky amplía su "...idea de un algoritmo – un procedimiento efectivo..." en el capítulo 5.1 Computabilidad, procedimientos efectivos y algoritmos. Máquinas infinitas.
Post, Emil (1936). "Procesos combinatorios finitos, formulación I". Revista de lógica simbólica . 1 (3): 103–105. doi :10.2307/2269031. JSTOR 2269031. S2CID 40284503.Reimpreso en The Undecidable , pp. 289 y siguientes. Post define un proceso simple, parecido a un algoritmo, en el que un hombre escribe o borra marcas y pasa de una casilla a otra hasta detenerse, mientras sigue una lista de instrucciones simples. Kleene cita este proceso como una de las fuentes de su "Tesis I", la llamada tesis de Church-Turing .
Rogers, Hartley Jr. (1987). Teoría de funciones recursivas y computabilidad efectiva . The MIT Press. ISBN 978-0-262-68052-3.
Rosser, JB (1939). "Una exposición informal de las pruebas del teorema de Gödel y del teorema de Church". Revista de lógica simbólica . 4 (2): 53–60. doi :10.2307/2269059. JSTOR 2269059. S2CID 39499392.Reimpreso en The Undecidable , pág. 223 y siguientes. Aquí se encuentra la famosa definición de Rosser de "método eficaz": "... un método en el que cada paso está predeterminado con precisión y que es seguro que producirá la respuesta en un número finito de pasos... una máquina que resolverá entonces cualquier problema del conjunto sin intervención humana más allá de insertar la pregunta y (más tarde) leer la respuesta" (págs. 225-226, The Undecidable )
Santos-Lang, Christopher (2015). "Enfoques de la ecología moral para la ética de las máquinas" (PDF) . En van Rysewyk, Simon; Pontier, Matthijs (eds.). Machine Medical Ethics . Sistemas inteligentes, control y automatización: ciencia e ingeniería. Vol. 74. Suiza: Springer. págs. 111–127. doi :10.1007/978-3-319-08108-3_8. ISBN.978-3-319-08107-6. Archivado (PDF) del original el 9 de octubre de 2022.
Scott, Michael L. (2009). Pragmática del lenguaje de programación (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 978-0-534-94728-6.
Sober, Elliott; Wilson, David Sloan (1998). Hacia los demás: la evolución y la psicología del comportamiento altruista . Cambridge: Harvard University Press. ISBN 9780674930469.
Stone, Harold S. (1972). Introducción a la organización de computadoras y estructuras de datos (edición de 1972). McGraw-Hill, Nueva York. ISBN 978-0-07-061726-1.Véase en particular el primer capítulo titulado Algoritmos, máquinas de Turing y programas . Su sucinta definición informal: "...cualquier secuencia de instrucciones que pueda ser obedecida por un robot, se llama algoritmo " (p. 4).
Tausworthe, Robert C (1977). Métodos de desarrollo estandarizado de software de computadora, parte 1. Englewood Cliffs, NJ: Prentice–Hall, Inc. ISBN 978-0-13-842195-3.
Turing, Alan M. (1936–37). "Sobre números computables, con una aplicación al problema de Entscheidung". Actas de la London Mathematical Society . Serie 2. 42 : 230–265. doi :10.1112/plms/s2-42.1.230. S2CID 73712.Correcciones, ibid, vol. 43(1937) pp. 544–546. Reimpreso en The Undecidable , p. 116ff. El famoso artículo de Turing completado como disertación de maestría mientras estaba en el King's College de Cambridge, Reino Unido.
Turing, Alan M. (1939). "Sistemas de lógica basados en ordinales". Actas de la London Mathematical Society . 45 : 161–228. doi :10.1112/plms/s2-45.1.161. hdl : 21.11116/0000-0001-91CE-3 .Reimpreso en The Undecidable , págs. 155 y siguientes. El artículo de Turing que definió "el oráculo" fue su tesis doctoral mientras estaba en Princeton.
Oficina de Patentes y Marcas de los Estados Unidos (2006), 2106.02 **>Algoritmos matemáticos: 2100 Patentabilidad, Manual de procedimientos de examen de patentes (MPEP). Última revisión: agosto de 2006
Zaslavsky, C. (1970). Matemáticas del pueblo yoruba y de sus vecinos en el sur de Nigeria. The Two-Year College Mathematics Journal, 1(2), 76–99. https://doi.org/10.2307/3027363
Lectura adicional
Bellah, Robert Neelly (1985). Hábitos del corazón: individualismo y compromiso en la vida estadounidense. Berkeley: University of California Press. ISBN 978-0-520-25419-0.
Berlinski, David (2001). El advenimiento del algoritmo: el viaje de 300 años desde una idea hasta la computadora. Harvest Books. ISBN 978-0-15-601391-8.
Chabert, Jean-Luc (1999). Una historia de los algoritmos: del Pebble al microchip . Springer Verlag. ISBN 978-3-540-63369-3.
Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introducción a los algoritmos (3ª ed.). Prensa del MIT. ISBN 978-0-262-03384-8.
Harel, David; Feldman, Yishai (2004). Algoritmia: el espíritu de la informática . Addison-Wesley. ISBN 978-0-321-11784-7.
Hertzke, Allen D.; McRorie, Chris (1998). "El concepto de ecología moral". En Lawler, Peter Augustine; McConkey, Dale (eds.). La comunidad y el pensamiento político en la actualidad . Westport, CT: Praeger .
Knuth, Donald E. (2000). Documentos seleccionados sobre análisis de algoritmos Archivado el 1 de julio de 2017 en Wayback Machine . Stanford, California: Centro para el estudio del lenguaje y la información.
Knuth, Donald E. (2010). Artículos seleccionados sobre diseño de algoritmos Archivado el 16 de julio de 2017 en Wayback Machine . Stanford, California: Centro para el estudio del lenguaje y la información.
Wallach, Wendell; Allen, Colin (noviembre de 2008). Moral Machines: Teaching Robots, 1998. Oxford University Press. ISBN : 978-0-822-23-3.978-0-19-537404-9.
Bleakley, Chris (2020). Poemas que resuelven acertijos: la historia y la ciencia de los algoritmos. Oxford University Press. ISBN 978-0-19-885373-2.
Enlaces externos
Busque algoritmo en Wikcionario, el diccionario libre.
Wikilibros tiene un libro sobre el tema: Algoritmos
En Wikiversidad , puedes aprender más y enseñar a otros sobre Algoritmos en el Departamento de Algoritmos.
Wikimedia Commons tiene medios relacionados con Algoritmos .
Este artículo incorpora material de dominio público de Paul E. Black. "algoritmo". Diccionario de algoritmos y estructuras de datos . NIST .
