Por el contrario, una heurística es un enfoque para resolver problemas que no tienen resultados correctos u óptimos bien definidos. [2] Por ejemplo, aunque los sistemas de recomendación de redes sociales se denominan comúnmente "algoritmos", en realidad se basan en heurísticas, ya que no existe una recomendación verdaderamente "correcta".
Como método eficaz , un algoritmo puede expresarse dentro de una cantidad finita de espacio y tiempo [3] y en un lenguaje formal bien definido [4] para calcular una función . [5] A partir de un estado inicial y una entrada inicial (quizás vacía ), [6] las instrucciones describen un cálculo que, cuando se ejecuta , procede a través de un número finito [7] de estados sucesivos bien definidos, produciendo eventualmente una "salida" [8] 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. [9]
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 . [10] 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". [2] Alrededor de 1230, se atestigua la palabra inglesa algoritmo y luego, por Chaucer en 1391, los ingleses adoptaron el término francés. [3] [4] [ 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 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 explícito de instrucciones para determinar un resultado, que puede ser seguido por una máquina de computación o un humano que solo podría realizar operaciones elementales específicas en símbolos . [15]
La evidencia más temprana de algoritmos se encuentra en las matemáticas de la antigua Mesopotamia . 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 verticilos [25] que produce el tic-tac de un reloj mecánico. "La máquina automática precisa" [26] condujo inmediatamente a los " autómatas mecánicos " en el siglo XIII y a las "máquinas computacionales" (los motores diferenciales y analíticos de Charles Babbage y Ada Lovelace a mediados del siglo XIX). [27] Lovelace diseñó el primer algoritmo destinado a ser procesado en una computadora, el motor analítico de Babbage, que es el primer dispositivo considerado una verdadera computadora Turing-completa en lugar de solo una calculadora . Aunque una implementación completa del segundo dispositivo de Babbage no se realizó hasta décadas después de su muerte, a Lovelace se la ha llamado "la primera programadora de la historia".
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 expresiones estructuradas de algoritmos que evitan las ambigüedades comunes del lenguaje natural. Los lenguajes de programación se utilizan principalmente para expresar algoritmos en una forma ejecutable por computadora, pero también se utilizan para definir o documentar algoritmos.
Máquinas de Turing
Existen muchas representaciones posibles y los programas de máquina de Turing pueden expresarse como una secuencia de tablas de máquina (consulte máquina de estados finitos , tabla de transición de estados y tabla de control para obtener más información), como diagramas de flujo y diagramas de drakon (consulte diagrama de estados para obtener más información), como una forma de código de máquina rudimentario o código ensamblador llamado "conjuntos de cuádruples", y más. Las representaciones de algoritmos también pueden clasificarse 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 las 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 proporciona estados exactos. [33] Con más detalle, una descripción formal proporciona 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). Tiene cuatro símbolos principales: flechas que muestran el flujo del programa, rectángulos (SECUENCIA, IR A), rombos (SI-ENTONCES-SINO) y puntos (OR-empate). Las subestructuras pueden "anidarse" en rectángulos, pero sólo si hay una única salida desde la superestructura.
Análisis algorítmico
A menudo es importante saber cuánto tiempo, almacenamiento u otro costo puede requerir un algoritmo. 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 requisito de tiempo de , utilizando la notación O mayúscula . 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. Si no se cuenta el espacio requerido para almacenar los números de entrada, tiene un requisito de espacio de , de lo contrario se requiere .
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 . Los algoritmos suelen estudiarse de forma abstracta, sin hacer referencia a ningún lenguaje de programación o implementación específicos. El análisis de algoritmos se parece a otras disciplinas matemáticas, ya que se centra en las propiedades del algoritmo, no en la implementación. El pseudocódigo es típico para el análisis, ya que es una representación simple y general. La mayoría de los algoritmos se implementan en plataformas de hardware/software particulares y su eficiencia algorítmica se prueba utilizando código real. La eficiencia de un algoritmo particular puede ser insignificante para muchos problemas "puntuales", pero puede ser crítica para algoritmos diseñados para un uso científico interactivo rápido, comercial o de larga duración. Escalar de n pequeño a n grande con frecuencia expone algoritmos ineficientes que de otro modo serían benignos.
Las pruebas empíricas son útiles para descubrir interacciones inesperadas que afectan el rendimiento. Se pueden utilizar puntos de referencia para comparar 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 es trivial que tengan un rendimiento justo. [34]
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. [35] En general, las mejoras de velocidad dependen de propiedades especiales del problema, que son muy comunes en aplicaciones prácticas. [36] 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 es un método o proceso matemático para la resolución de problemas y la ingeniería de algoritmos. El diseño de algoritmos forma 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, [37] 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. [38]
Programación estructurada
Según la tesis de Church-Turing , cualquier algoritmo puede ser calculado por cualquier modelo completo de Turing . La completitud de Turing solo requiere 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". [39] Tausworthe aumenta las tres estructuras canónicas de Böhm-Jacopini : [40] SEQUENCE, IF-THEN-ELSE y WHILE-DO, con dos más: DO-WHILE y CASE. [41] Un beneficio adicional de un programa estructurado es que se presta a pruebas de corrección mediante inducción matemática . [42]
Estatus legal
Por sí mismos, los algoritmos 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, [43] 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
Por implementación
Recursión
Un algoritmo recursivo se invoca a sí mismo repetidamente hasta que cumple una condición de terminación y es un método común de programación funcional . Los algoritmos iterativos utilizan repeticiones como bucles o estructuras de datos como pilas para resolver problemas. Los problemas pueden ser adecuados para una implementación u otra. Las Torres de Hanoi es un rompecabezas que se resuelve comúnmente mediante una 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 asumiendo que las computadoras ejecutan una instrucción de un algoritmo a la vez en computadoras seriales. Los algoritmos seriales están diseñados para estos entornos, a diferencia de los algoritmos paralelos o distribuidos . Los algoritmos paralelos aprovechan las arquitecturas informáticas en las que varios procesadores pueden trabajar en un problema al mismo tiempo. Los algoritmos distribuidos utilizan varias máquinas conectadas a través de una red informática. Los algoritmos paralelos y distribuidos dividen el problema en subproblemas y recopilan los resultados. El consumo de recursos en estos algoritmos no solo son los 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.
Mientras que muchos algoritmos llegan a una solución exacta, los algoritmos de aproximación buscan una aproximación que esté cerca de la solución verdadera. Dichos algoritmos tienen valor práctico para muchos problemas difíciles. Por ejemplo, el problema de la mochila , donde hay un conjunto de elementos y el 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. [44]
La fuerza bruta es un método de resolución de problemas que consiste en probar sistemáticamente todas las opciones posibles hasta encontrar la solución óptima. Este enfoque puede requerir mucho tiempo, ya que se prueban todas las combinaciones posibles de variables. Se suele utilizar cuando no hay otros métodos disponibles o son demasiado complejos. La fuerza bruta puede 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 un problema a una o más instancias más pequeñas de sí mismo (generalmente de forma recursiva ) hasta que las instancias son lo suficientemente pequeñas como para resolverse fácilmente. La ordenación por fusión es un ejemplo de divide y vencerás, donde una lista desordenada se puede dividir en segmentos que contienen un elemento y la ordenación de la lista completa se puede obtener fusionando los segmentos. Una variante más simple de divide y vencerás se llama algoritmo de disminución y vencerás , que resuelve una instancia más pequeña de sí mismo y usa la solución 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 conquista. [ cita requerida ] Un ejemplo de un algoritmo de disminución y conquista es el algoritmo de búsqueda binaria .
Estos algoritmos toman algunas decisiones de forma aleatoria (o pseudoaleatoria). Encuentran soluciones aproximadas cuando encontrar soluciones exactas puede resultar poco práctico (véase el método heurístico a continuación). Para algunos problemas, las aproximaciones más rápidas deben implicar cierta aleatoriedad . [45] 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 . Existen 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 transforma problemas difíciles en problemas más conocidos que se pueden resolver con 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 encuentra la mediana de una lista desordenada ordenando primero la lista (la parte costosa) y luego extrayendo 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 limitada por restricciones de igualdad y desigualdad lineales, las restricciones se pueden usar directamente para producir soluciones óptimas. Hay algoritmos que pueden resolver cualquier problema en esta categoría, como el popular algoritmo simplex . [46] Los problemas que se pueden resolver con programación lineal incluyen el problema de flujo máximo para grafos dirigidos. Si un problema también requiere que cualquiera de las incógnitas sean números enteros , 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 se puede construir a partir de soluciones óptimas a 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 tener que volver a calcular las soluciones. Por ejemplo, el algoritmo Floyd-Warshall , la ruta más corta entre un vértice de inicio y un vértice de destino en un gráfico ponderado se puede encontrar utilizando la ruta más corta al destino desde todos los vértices adyacentes. La programación dinámica y la memorización van de la mano. A diferencia de dividir y vencer, los subproblemas de programación dinámica a menudo se superponen. La diferencia entre la programación dinámica y la recursión simple es el almacenamiento en caché o la memorización de las llamadas recursivas. Cuando los subproblemas son independientes y no se repiten, la memorización no ayuda; por lo tanto, la programación dinámica no es aplicable a todos los problemas complejos. El uso de la memorización en la programación dinámica reduce la complejidad de muchos problemas, desde exponenciales hasta polinómicos.
El método codicioso
Los algoritmos voraces , de manera similar a la programación dinámica, funcionan examinando subestructuras, en este caso no del problema sino de una solución dada. Dichos algoritmos comienzan con alguna solución y la mejoran haciendo pequeñas modificaciones. Para algunos problemas siempre encuentran la solución óptima, pero para otros pueden detenerse en óptimos locales . El uso más popular de los algoritmos voraces es encontrar árboles de expansión mínimos de grafos sin ciclos negativos. Huffman Tree , Kruskal , Prim y Sollin son algoritmos voraces que pueden resolver este problema de optimización.
El método heurístico
En los problemas de optimización , los algoritmos heurísticos encuentran soluciones cercanas a la solución óptima cuando encontrar la solución óptima es impráctico. Estos algoritmos se acercan 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. Idealmente, pueden encontrar una solución muy cercana a la solución óptima en un tiempo relativamente corto. Estos algoritmos incluyen búsqueda local , búsqueda tabú , recocido simulado y algoritmos genéticos . Algunos, 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 busca el número más grande en una lista de números ordenados aleatoriamente. Para encontrar la solución es necesario observar cada número de la lista. De esto se desprende un algoritmo simple, que puede describirse en términos sencillos como:
Descripción de alto nivel:
Si un conjunto de números está vacío, entonces no existe un número más alto.
Supongamos que el primer número del conjunto es el más grande.
Para cada número restante en el conjunto: si este número es mayor que el más grande actual, se convierte en el nuevo más grande.
Cuando no quedan números sin marcar en el conjunto, considere que el número más grande actual es el 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 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 en cuanto al 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).
^ Blair, Ann, Duguid, Paul, Goeing, Anja-Silvia y Grafton, Anthony. Información: A Historical Companion, Princeton: Princeton University Press, 2021. pág. 247
^ 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
^ 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 discuten "ciertos conjuntos enumerables no 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.
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.ª 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". Transacciones de la 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 .
Jon Kleinberg, Éva Tardos (2006): Diseño de algoritmos , Pearson/Addison-Wesley, ISBN 978-0-32129535-4
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 .
