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 existe 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 se caracterizan ampliamente 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 se puede expresar 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 , avanza a través de un número finito [8] de estados sucesivos bien definidos, y eventualmente produce una "salida" [ 9] y terminando en un estado final final. La transición de un estado al siguiente no es necesariamente determinista ; Algunos algoritmos, conocidos como algoritmos aleatorios , incorporan entradas aleatorias. [10]
Etimología
Alrededor del año 825 d.C., el científico y erudito 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ī ("Adición y resta en la 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 y aritmética hindú-árabe , 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 la presente, 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, la palabra inglesa algorismo está atestiguada y luego, por Chaucer en 1391, los ingleses adoptaron el término francés. [4] [5] [ se necesita aclaración ] En el siglo XV, bajo la influencia de la palabra griega ἀριθμός ( arithmos , "número"; cf. "aritmética"), la palabra latina fue alterada a algoritmus . [ cita necesaria ]
Definición
Una definición informal es "un conjunto de reglas que define con precisión una secuencia de operaciones", [11] [ necesita cita para verificar ] que incluiría todos los programas de computadora (incluidos los programas que no realizan cálculos numéricos) y (por ejemplo) cualquier procedimiento burocrático prescrito [12]
o receta de libro de cocina . [13] En general, un programa es un algoritmo sólo si finalmente se detiene [14] , aunque a veces los bucles infinitos pueden resultar deseables. Boolos, Jeffrey & 1974, 1999 definen un algoritmo como un conjunto de instrucciones para determinar una salida, dadas explícitamente, en una forma que puede ser seguida por una máquina informática o por un ser humano que sólo puede realizar operaciones elementales específicas sobre símbolos. . [15]
El concepto de algoritmo también se utiliza para definir la noción de decidibilidad , noción central para explicar cómo surgen los sistemas formales a partir de un pequeño conjunto de axiomas y reglas. En lógica , el tiempo que requiere un algoritmo para completarse no se puede medir, ya que aparentemente no está relacionado con la dimensión física habitual. De estas incertidumbres, que caracterizan el trabajo en curso, se deriva 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.
Desde la antigüedad se atestiguan procedimientos paso a paso para la resolución de problemas matemáticos. Esto incluye las matemáticas babilónicas (alrededor del 2500 a. C.), [16] las matemáticas egipcias (alrededor del 1550 a. C.), [16] las matemáticas indias (alrededor del 800 a. C. y posteriores), [17] [18] El Oráculo de Ifá (alrededor del 500 a. C.), Matemáticas griegas (alrededor del 240 a. C.), [19] y matemáticas árabes (alrededor del 800 d. C.). [20]
La evidencia más antigua de algoritmos se encuentra en las matemáticas babilónicas de la antigua Mesopotamia (el actual Irak). Una tablilla de arcilla sumeria encontrada en Shuruppak, cerca de Bagdad , que data de c. 2500 aC describió el primer algoritmo de división . [16] Durante la dinastía Hammurabi c. 1800 – c. 1600 a. C. , las tablillas de arcilla babilónicas describían algoritmos para calcular fórmulas. [21] Los algoritmos también se utilizaron en la astronomía babilónica . Las tablillas de arcilla babilónicas describen y emplean procedimientos algorítmicos para calcular la hora y el lugar de eventos astronómicos importantes. [22]
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 mediante análisis de frecuencia , el primer algoritmo de descifrado de códigos. [20]
Ordenadores
Relojes impulsados por peso
Bolter atribuye la invención del reloj impulsado por pesas como "el invento clave [de Europa en la Edad Media]". En particular, atribuye el mérito al mecanismo de escape [24] que nos proporciona el tic y tac de un reloj mecánico. "La máquina automática precisa" [25] condujo inmediatamente a los " autómatas mecánicos " a partir del siglo XIII y finalmente a las "máquinas computacionales": la máquina diferenciadora y las máquinas analíticas de Charles Babbage y la condesa Ada Lovelace , a mediados del siglo XIX. [26] A Lovelace se le atribuye la primera creación de un algoritmo destinado al procesamiento en una computadora (el motor analítico de Babbage, el primer dispositivo considerado una verdadera computadora Turing completa en lugar de solo una calculadora ) y a veces se le llama "el primer programador de la historia" como un resultado, aunque la 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) indican que el telar Jacquard (1801), precursor de las tarjetas Hollerith (tarjetas perforadas, 1887), y las "tecnologías de conmutación telefónica" fueron las raíces de un árbol que condujo al desarrollo de las primeras computadoras. [27] A mediados del siglo XIX, el telégrafo , el precursor del teléfono, se utilizaba en todo el mundo; su codificación discreta y distinguible de letras como "puntos y rayas" era un sonido común. A finales del siglo XIX, el teletipo ( c. 1870 ) estaba en uso, al igual que el uso de tarjetas Hollerith en el censo estadounidense de 1890. Luego vino la teleimpresora ( c. 1910 ) con su uso en papel perforado del código Baudot en cinta.
Las redes de conmutación telefónica de relés electromecánicos (inventadas en 1835) fueron obra de George Stibitz (1937), el inventor del dispositivo sumador digital. Mientras trabajaba en los Laboratorios Bell, observó el uso "gravoso" de calculadoras mecánicas con engranajes. "Volvió a casa una noche de 1937 con la intención de probar su idea... Cuando terminaron los retoques, Stibitz había construido un dispositivo de suma binaria". [ 28] El matemático Martin Davis apoyó la particular importancia del relé electromecánico [29] .
Los algoritmos se pueden expresar en muchos tipos de notación, incluidos lenguajes naturales , pseudocódigo , diagramas de flujo , diagramas drakon , lenguajes de programación o tablas de control (procesadas por intérpretes ). Las expresiones de algoritmos en lenguaje natural tienden a ser detalladas y ambiguas y rara vez se utilizan para algoritmos complejos o técnicos. El pseudocódigo, los diagramas de flujo, los diagramas 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 obtener más información), como diagramas de flujo y diagramas de drakon (ver estado diagrama para obtener más información), o como una forma de código de máquina rudimentario o código ensamblador llamado "conjuntos de cuádruples" (consulte Máquina de Turing para obtener 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. [32] Una descripción de alto nivel describe las cualidades del algoritmo en sí, ignorando cómo se implementa en la máquina de Turing. [32] Una descripción de la 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. [32] Con el mayor detalle, una descripción formal proporciona la tabla de estados exacta y la lista de transiciones de la máquina de Turing. [32]
Representación de diagrama de flujo
La ayuda gráfica llamada diagrama de flujo ofrece una manera de describir y documentar un algoritmo (y un programa de computadora correspondiente a él). Al igual que el flujo del programa de una máquina Minsky, un diagrama de flujo siempre comienza en la parte superior de una página y continúa hacia abajo. Sus símbolos principales son sólo cuatro: la flecha dirigida que muestra el flujo del programa, el rectángulo (SECUENCIA, GOTO), el diamante (SI-ENTONCES-ELSE) y el punto (OR-empate). Las estructuras canónicas de Böhm-Jacopini están hechas de 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. [33]
Análisis algorítmico
Con frecuencia es importante saber qué cantidad de un recurso particular (como tiempo o almacenamiento) se requiere teóricamente para un algoritmo determinado. Se han desarrollado métodos para el análisis de algoritmos para obtener 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 grande . En todo momento el algoritmo sólo 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 requisito 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 usa para búsquedas de tablas en listas 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 o implementación de programación específica. 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 particular. Normalmente, el pseudocódigo se utiliza para el análisis, ya que es la representación más simple y general. Sin embargo, en última instancia, la mayoría de los algoritmos generalmente se implementan en plataformas de hardware/software particulares y su eficiencia algorítmica eventualmente se pone a prueba utilizando código real. Para la solución de un problema "único", 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, comercial o de larga duración puede ser fundamental. Escalar de n pequeño a n grande frecuentemente expone algoritmos ineficientes que de otro modo serían benignos.
Las pruebas empíricas son útiles porque pueden descubrir interacciones inesperadas que afectan el rendimiento. Se pueden utilizar puntos de referencia para comparar antes/después de posibles mejoras en un algoritmo después de la optimización del programa. Sin embargo, las pruebas empíricas no pueden reemplazar el análisis formal y no es trivial realizarlas de manera justa. [34]
Eficiencia de ejecución
Para ilustrar las posibles mejoras posibles incluso en algoritmos bien establecidos, una importante innovación reciente, relacionada con los algoritmos FFT (muy utilizados en el campo del procesamiento de imágenes), puede reducir el tiempo de procesamiento hasta 1000 veces para aplicaciones como 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 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 forma parte de muchas teorías de solución, como la programación dinámica o divide y vencerás dentro de la investigación operativa . 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 grande 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 calcularse mediante un modelo que se sabe que es Turing completo . De hecho, se ha demostrado que la integridad de Turing requiere sólo cuatro tipos de instrucciones: GOTO condicional, GOTO incondicional, asignación y HALT. Sin embargo, Kemeny y Kurtz observan que, si bien el uso "indisciplinado" de GOTO incondicionales y GOTO condicionales SI-ENTONCES puede dar como resultado un " código espagueti ", un programador puede escribir programas estructurados utilizando sólo 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] SECUENCIA, SI-ENTONCES-ELSE y MIENTRAS-HACER, con dos más: HACER MIENTRAS y CASO. [41] Un beneficio adicional de un programa estructurado es que se presta a pruebas de corrección mediante inducción matemática . [42]
Clasificación
Hay varias formas de clasificar los algoritmos, cada una con sus propias ventajas.
Por implementación
Una forma de clasificar los algoritmos es mediante métodos de implementación.
recursividad
Un algoritmo recursivo es aquel que se invoca (hace referencia) a sí mismo repetidamente hasta que una determinada condición (también conocida como condición de terminación) coincide, lo cual es un método común a la programación funcional . Los algoritmos iterativos utilizan construcciones repetitivas como bucles y, a veces, estructuras de datos adicionales como pilas para resolver los problemas dados. Algunos problemas son naturalmente adecuados para una implementación u otra. Por ejemplo, las torres de Hanoi se entienden bien mediante una implementación recursiva. Cada versión recursiva tiene una versión iterativa equivalente (pero posiblemente más o menos compleja), y viceversa.
Serial, paralelo o distribuido
Los algoritmos generalmente se analizan bajo el supuesto de que las computadoras ejecutan una instrucción de un algoritmo a la vez. A esas computadoras a veces se les llama computadoras en serie. Un algoritmo diseñado para dicho entorno se denomina algoritmo en serie, 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 nuevamente. Por ejemplo, una CPU sería un ejemplo de algoritmo paralelo. El consumo de recursos en tales algoritmos no es solo los ciclos de procesador en cada procesador sino también la sobrecarga de comunicación entre los procesadores. Algunos algoritmos de clasificación se pueden paralelizar de manera eficiente, pero su sobrecarga de comunicación es costosa. Los algoritmos iterativos 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 se acerque más a la solución verdadera. La aproximación se puede alcanzar utilizando una estrategia determinista o aleatoria. Estos algoritmos tienen valor práctico para muchos problemas difíciles. Uno de los ejemplos de algoritmo aproximado es el problema de la mochila , donde hay un conjunto de elementos dados. Su objetivo es empacar la mochila para obtener el máximo valor total. Cada artículo tiene un peso y un valor. El peso total que se puede transportar no es más que un número fijo X. Por lo tanto, la solución debe considerar el peso de los artículos así como su valor. [43]
Otra forma de clasificar los algoritmos es por su metodología o paradigma de diseño . Existe una cierta cantidad 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 llevar mucho tiempo, ya que requiere analizar todas las combinaciones posibles de variables. Sin embargo, a menudo se utiliza cuando otros métodos no están disponibles o son demasiado complejos. La fuerza bruta se puede utilizar para resolver una variedad de problemas, incluido encontrar el camino más corto entre dos puntos y descifrar contraseñas.
Divide y conquistaras
Un algoritmo de divide y vencerás reduce repetidamente una instancia de un problema a una o más instancias más pequeñas del mismo problema (generalmente de forma recursiva ) hasta que las instancias son lo suficientemente pequeñas como para resolverlas fácilmente. Un ejemplo de divide y vencerás es la clasificación por fusión . La clasificación se puede realizar en cada segmento de datos después de dividir los datos en segmentos y la clasificación de datos completos 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 disminuir y vencer , que resuelve un subproblema idéntico y utiliza la solución de este subproblema para resolver el problema mayor. Divide y vencerás divide el problema en múltiples subproblemas, por lo que la etapa de conquista es más compleja que los algoritmos de disminución y conquista. Un ejemplo de algoritmo de disminución y conquista es el algoritmo de búsqueda binaria .
Estos algoritmos toman algunas decisiones de forma aleatoria (o pseudoaleatoria). Pueden resultar muy útiles para encontrar soluciones aproximadas a problemas en los que encontrar soluciones exactas puede resultar poco práctico (consulte el método heurístico a continuación). Para algunos de estos problemas, se sabe que las aproximaciones más rápidas deben implicar cierta aleatoriedad . [44] Si los algoritmos aleatorios con complejidad de tiempo polinomial 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 sólo está limitado probabilísticamente, por ejemplo, ZPP .
Esta técnica implica resolver un problema difícil transformándolo en un problema mejor conocido para el cual tenemos (con suerte) algoritmos asintóticamente óptimos . El objetivo es encontrar un algoritmo reductor cuya complejidad no esté dominada por la del algoritmo reducido resultante. Por ejemplo, un algoritmo de selección para encontrar la mediana en una lista no ordenada implica primero ordenar la lista (la parte cara) y luego extraer el elemento central de 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 problemas de optimización existe una clasificación de algoritmos más específica; un algoritmo para tales problemas puede caer en una o más de las categorías generales descritas anteriormente, así como en una de las siguientes:
Cuando se buscan soluciones óptimas para una función lineal sujeta a restricciones de igualdad y desigualdad lineal, las restricciones del problema se pueden utilizar directamente para producir las soluciones óptimas. Existen algoritmos que pueden resolver cualquier problema de esta categoría, como el popular algoritmo simplex . [45] Los problemas que se pueden resolver con programación lineal incluyen el problema de flujo máximo para gráficos dirigidos. Si un problema requiere además que una o más de las incógnitas sean un número entero, entonces se clasifica en programación entera . Un algoritmo de programación lineal puede resolver tal problema si se puede demostrar que todas las restricciones para valores enteros son superficiales, es decir, las soluciones satisfacen estas restricciones de todos modos. En el caso general se utiliza un algoritmo especializado o un algoritmo que encuentra soluciones aproximadas, dependiendo de la dificultad del problema.
Cuando un problema muestra subestructuras óptimas (lo que significa que la solución óptima a un problema se puede construir a partir de soluciones óptimas a subproblemas) y subproblemas superpuestos , lo que significa que los mismos subproblemas se utilizan para resolver muchas instancias de problemas diferentes, un enfoque más rápido llamado programación dinámica evita volver a calcular soluciones que ya han sido computados. Por ejemplo, en el algoritmo de Floyd-Warshall , el camino más corto hacia una meta desde un vértice en un gráfico ponderado se puede encontrar utilizando el camino más corto hacia la meta desde todos los vértices adyacentes. La programación dinámica y la memorización van de la mano. La principal diferencia entre programación dinámica y divide y conquistarás es que los subproblemas son más o menos independientes en divide y vencerás, mientras que los subproblemas se superponen en la programación dinámica. La diferencia entre la programación dinámica y la recursividad sencilla está en el almacenamiento en caché o la memorización de llamadas recursivas. Cuando los subproblemas son independientes y no hay repetición, la memorización no ayuda; por tanto, la programación dinámica no es una solución para todos los problemas complejos. 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 polinómica.
El método codicioso
Un algoritmo codicioso es similar a un algoritmo de programación dinámica en que funciona examinando subestructuras, en este caso no del problema sino de una solución dada. Dichos algoritmos 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 los óptimos locales , es decir, en soluciones que el algoritmo no puede mejorar pero que no son óptimas. El uso más popular de los algoritmos codiciosos es encontrar el árbol de expansión mínimo donde es posible encontrar la solución óptima con este método. Huffman Tree , Kruskal , Prim y Sollin son algoritmos codiciosos 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 sea práctico. Estos algoritmos funcionan acercándose cada vez más a la solución óptima a medida que avanzan. En principio, si se ejecutan durante un tiempo infinito, encontrarán la solución óptima. Su mérito es que pueden encontrar una solución muy cercana a la solución óptima en un tiempo relativamente corto. Dichos algoritmos incluyen búsqueda local , búsqueda tabú , recocido simulado y algoritmos genéticos . Algunos de ellos, como el recocido simulado, son algoritmos no deterministas, mientras que otros, como la búsqueda tabú, son deterministas. Cuando se conoce un límite en el error de la solución no óptima, el algoritmo se clasifica además como algoritmo de aproximación .
Estatus legal
Los algoritmos, por sí solos, no suelen ser patentables. En los Estados Unidos, una reivindicación que consiste únicamente en simples manipulaciones de conceptos, números o señales abstractos 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 son patentables. Por ejemplo, en Diamond v. Diehr , se consideró patentable la aplicación de un algoritmo de retroalimentación simple para ayudar en el curado del caucho sintético . Las patentes de software son controvertidas [46] y hay 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 (ver exportación de criptografía ).
Ejemplos
Uno de los algoritmos más simples es encontrar el número más grande en una lista de números de orden aleatorio. Encontrar la solución requiere mirar todos los números de la lista. De esto se sigue un algoritmo simple, que puede expresarse 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 existe el número más alto.
Suponga que el primer número del conjunto es el número más grande del conjunto.
Para cada número restante del conjunto: si este número es mayor que el número más grande actual, considere que este número es el número más grande del conjunto.
Cuando no queden 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 el más grande ← L [0] para cada elemento en L , hazlo si el elemento > más grande , entonces el elemento más grande ← devuelve el más grande
"←" indica asignación . Por ejemplo, " mayor ← artículo " significa que el valor del mayor cambia al valor del artículo .
" 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 .
^ ab Blair, Ann, Duguid, Paul, Goeing, Anja-Silvia y Grafton, Anthony. Información: Un compañero histórico, Princeton: Princeton University Press, 2021. p. 247
^ ab David A. Grossman, Ophir Frieder, Recuperación de información: algoritmos y heurística , segunda edición, 2004, ISBN 1402030045
^ ab "Cualquier algoritmo matemático clásico, por ejemplo, se puede describir con un número finito de palabras en inglés" (Rogers 1987:2).
^ ab Bien definido con respecto al agente que ejecuta el algoritmo: "Existe un agente informático, generalmente humano, que puede reaccionar a las instrucciones y realizar los cálculos" (Rogers 1987:2).
^ "un algoritmo es un procedimiento para calcular una función (con respecto a alguna notación elegida para números enteros)... esta limitación (a funciones numéricas) no produce 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 comience el algoritmo" (Knuth 1973:5).
^ "Un procedimiento que tiene todas las características de un algoritmo, excepto que posiblemente carezca de finitud, puede denominarse '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 o no un algoritmo. Rogers opina que: "un cálculo se lleva a cabo de forma discreta y gradual, sin el uso de métodos continuos o dispositivos analógicos... llevado a cabo de forma 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 intempestivas. vol. 14. Traducido por Chase, Jefferson. Cambridge, Massachusetts: MIT Press. pag. 147.ISBN9780262536370. Archivado desde el original el 22 de diciembre de 2019 . Consultado el 27 de mayo de 2019 . [...] 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 de Ciencias Cognitivas del MIT. Biblioteca MIT Cognet. Cambridge, Massachusetts: MIT Press (publicado en 2001). pag. 11.ISBN9780262731447. Consultado el 22 de julio de 2020 . Un algoritmo es una receta, método o técnica para hacer algo.
^ Stone requiere que "debe terminar en un número finito de pasos" (Stone 1973: 7–8).
^ Boolos y Jeffrey 1974,1999:19
^ abc Chabert, Jean-Luc (2012). Una historia de los algoritmos: del guijarro al microchip . Medios de ciencia y negocios de Springer. págs. 7–8. ISBN9783642181924.
^ ab Sriram, MS (2005). "Algoritmos en matemáticas indias". En Emch, Gerard G.; Sridharan, R.; Srinivas, MD (eds.). Contribuciones a la historia de las matemáticas indias . Saltador. pag. 153.ISBN978-93-86279-25-5.
^ Hayashi, T. (2023, 1 de enero). Brahmagupta. Enciclopedia Británica.
^ abc Cooke, Roger L. (2005). La historia de las matemáticas: un curso breve . John Wiley e hijos. ISBN978-1-118-46029-0.
^ ab Dooley, John F. (2013). Una breve historia de la criptología y los algoritmos criptográficos . Medios de ciencia y negocios de Springer. págs. 12-3. ISBN9783319016283.
^ Knuth, Donald E. (1972). "Algoritmos babilónicos antiguos" (PDF) . Comunitario. 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. págs. 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 .
^ Bólter 1984:24
^ Bólter 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 tinkerer consigue un lugar en la historia , Valley News West Lebanon NH, jueves 31 de marzo de 1983, p. 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?". Sistemas de Conocimiento y Información . 52 (2): 341–378. doi :10.1007/s10115-016-1004-2. ISSN 0219-1377. S2CID 40772241.
^ Gillian Conahan (enero de 2013). "Unas mejores matemáticas generan redes de datos más rápidas". descubrirmagazine.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 archivada el 21 de febrero , 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-9. Archivado desde el original el 28 de abril de 2015 . Consultado el 14 de junio de 2018 .
^ "Notación O grande (artículo) | Algoritmos". Academia Khan . Consultado el 3 de junio de 2024 .
^ Knuth 1973 sección 1.2.1, ampliada por Tausworthe 1977 en las páginas 100 y siguientes y capítulo 9.1
^ 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 mediante un oráculo de membresía) se puede aproximar con gran precisión mediante un algoritmo de tiempo polinomial aleatorio, pero no mediante uno determinista: ver Dyer, Martin; Friso, Alan; Kannan, Ravi (enero de 1991). "Un algoritmo aleatorio de tiempo polinómico 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.
^ "Los expertos: ¿El sistema de patentes fomenta la innovación?". El periodico de Wall Street . 16 de mayo de 2013. ISSN 0099-9660 . Consultado el 29 de marzo de 2017 .
Bibliografía
Axt, P (1959). "Sobre una jerarquía subrecursiva y grados recursivos primitivos". Transacciones de la Sociedad Matemática Estadounidense . 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 .
Blas, Andrés ; Gurevich, Yuri (2003). "Algoritmos: una búsqueda de definiciones absolutas" (PDF) . Boletín de la Asociación Europea de Informática Teórica . 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 (1984 ed.). Chapel Hill, Carolina del Norte: Prensa de la Universidad de Carolina del Norte. ISBN 978-0-8078-1564-9., ISBN 0-8078-4108-0
Boolos, George ; Jeffrey, Richard (1999) [1974]. Computabilidad y Lógica (4ª ed.). Cambridge University Press, Londres. ISBN 978-0-521-20402-6.: cf. Capítulo 3 Máquinas de Turing donde se analizan "ciertos conjuntos enumerables que no son efectivamente (mecánicamente) enumerables".
Burgin, Mark (2004). Algoritmos superrecursivos . Saltador. ISBN 978-0-387-95569-8.
Campagnolo, ML, Moore, C. y Costa, JF (2000) Una caracterización analógica de las funciones subrecursivas. En Proc. de la Cuarta Conferencia sobre Números Reales y Computadoras , Universidad de Odense, págs. 91-109
Iglesia, Alonso (1936). "Un problema irresoluble de la teoría de números elemental". La Revista Estadounidense de Matemáticas . 58 (2): 345–363. doi :10.2307/2371045. JSTOR 2371045.Reimpreso en Lo indecidible , p. 89 y sigs. La primera expresión de la "Tesis de la Iglesia". 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 usa la palabra "termina", etc.
Iglesia, Alonso (1936). "Una nota sobre el problema de Entscheidungs". La revista de lógica simbólica . 1 (1): 40–41. doi :10.2307/2269326. JSTOR 2269326. S2CID 42323521. Iglesia, Alonso (1936). "Corrección a una nota sobre el Entscheidungsproblem". La revista de lógica simbólica . 1 (3): 101–102. doi :10.2307/2269030. JSTOR 2269030. S2CID 5557237.Reimpreso en Lo indecidible , p. 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, Martín (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 artículos de Gödel , Alonzo Church , Turing , Rosser , Kleene y Emil Post ; los citados en el artículo se enumeran aquí por nombre del autor.
Decano, Tim (2012). "Evolución y diversidad moral". Anuario internacional báltico de cognición, lógica y comunicación . 7 . doi : 10.4148/biyclc.v7i0.1775 .
Dennett, Daniel (1995). La peligrosa idea de Darwin . Nueva York: Touchstone/Simon & Schuster. págs. 32–36. ISBN 978-0-684-80290-9.
Yuri Gurevich , Máquinas de estados abstractos secuenciales capturan algoritmos secuenciales, Transacciones ACM sobre lógica computacional, Vol 1, no 1 (julio de 2000), págs. Incluye bibliografía de 33 fuentes.
van Heijenoort, Jean (2001). De Frege a Gödel, un libro de consulta sobre lógica matemática, 1879-1931 ((1967) ed.). Prensa de la Universidad de Harvard, Cambridge. ISBN 978-0-674-32449-7., 3.ª edición 1976[?], ISBN 0-674-32449-8 (pbk.)
Kleene, Stephen C. (1936). "Funciones recursivas generales de los números naturales". Annalen Matemáticas . 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. 237 y sigs. 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 Un problema insoluble de la teoría de números elementales que demostró que el "problema de decisión" era "indecidible" (es decir, un resultado negativo).
Kleene, Stephen C. (1943). "Predicados y cuantificadores recursivos". Transacciones de la Sociedad Matemática Estadounidense . 53 (1): 41–73. doi : 10.2307/1990131 . JSTOR 1990131.Reimpreso en Lo indecidible , p. 255 y siguientes. Kleene refinó su definición de "recursión general" y procedió en su capítulo "12. Teorías algorítmicas" a plantear la "Tesis I" (p. 274); Más tarde repetiría esta tesis (en Kleene 1952:300) y la llamaría "Tesis de la Iglesia" (Kleene 1952:317) (es decir, la tesis de la Iglesia ).
Kleene, Stephen C. (1991) [1952]. Introducción a las Metamatemáticas (Décima ed.). Compañía editorial de Holanda Septentrional. ISBN 978-0-7204-2103-3.
Knuth, Donald (1997). Algoritmos fundamentales, tercera edición . Reading, Massachusetts: Addison-Wesley. ISBN 978-0-201-89683-1.
Knuth, Donald (1969). Volumen 2/Algoritmos seminuméricos, El arte de la programación informática, primera edición . Reading, Massachusetts: Addison-Wesley.
Kosovsky, NK 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 los algoritmos . [Traducido por Jacques J. Schorr-Kon y personal del PST] Pie de imprenta Moscú, Academia de Ciencias de la URSS, 1954 [es decir, Programa de Traducciones Científicas de Jerusalén, Israel, 1961; disponible en la Oficina de Servicios Técnicos, Departamento de Comercio de EE. UU., Washington] Descripción 444 p. 28cm. Se añadió tp en la traducción rusa de las obras del Instituto de Matemáticas de la Academia de Ciencias de la URSS, v. 42. Título original: Teoriya algerifmov. [QA248.M2943 Biblioteca de Dartmouth College. Departamento de Comercio de EE. UU., Oficina de Servicios Técnicos, número OTS 60-51085.]
Minsky, Marvin (1967). Computación: máquinas finitas e infinitas (Primera ed.). Prentice-Hall, Englewood Cliffs, Nueva Jersey. ISBN 978-0-13-165449-5.Minsky amplía su "...idea de algoritmo - un procedimiento efectivo..." en el capítulo 5.1 Computabilidad, procedimientos efectivos y algoritmos. Máquinas infinitas.
Correo, Emil (1936). "Procesos Combinatorios Finitos, Formulación I". La revista de lógica simbólica . 1 (3): 103–105. doi :10.2307/2269031. JSTOR 2269031. S2CID 40284503.Reimpreso en Lo indecidible , págs. 289 y siguientes. Post define un proceso algorítmico simple en el que un hombre escribe marcas o borra marcas y va de cuadro en cuadro y finalmente se detiene, mientras sigue una lista de instrucciones simples. Kleene cita esto como una fuente de su "Tesis I", la llamada tesis de Church-Turing .
Rogers, Hartley Jr. (1987). Teoría de funciones recursivas y computabilidad efectiva . La prensa del MIT. ISBN 978-0-262-68052-3.
Rosser, JB (1939). "Una exposición informal de las pruebas del teorema de Gödel y del teorema de Church". Revista de Lógica Simbólica . 4 (2): 53–60. doi :10.2307/2269059. JSTOR 2269059. S2CID 39499392.Reimpreso en Lo indecidible , p. 223 y siguientes. Aquí está la famosa definición de Rosser de "método efectivo": "...un método en el cual cada paso está precisamente predeterminado y que seguramente producirá la respuesta en un número finito de pasos... una máquina que luego resolverá cualquier problema de el conjunto sin intervención humana más allá de insertar la pregunta y (luego) leer la respuesta" (p. 225-226, The Undecidable )
Santos-Lang, Christopher (2015). "Enfoques de ecología moral para la ética de las máquinas" (PDF) . En van Rysewyk, Simon; Pontier, Matthijs (eds.). Ética médica de las máquinas . 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) desde el original el 9 de octubre de 2022.
Scott, Michael L. (2009). Pragmática del lenguaje de programación (3ª ed.). Editores Morgan Kaufmann/Elsevier. ISBN 978-0-12-374514-9.
Sipser, Michael (2006). Introducción a la Teoría de la Computación. Compañía editorial PWS. ISBN 978-0-534-94728-6.
Sobrio, Elliott; Wilson, David Sloan (1998). Hacia los demás: la evolución y la psicología del comportamiento altruista . Cambridge: Prensa de la Universidad de Harvard. ISBN 9780674930469.
Piedra, Harold S. (1972). Introducción a la organización informática y las estructuras de datos (1972 ed.). McGraw-Hill, Nueva York. ISBN 978-0-07-061726-1.Cf. en particular el primer capítulo titulado: Algoritmos, Máquinas de Turing y Programas . Su sucinta definición informal: "...cualquier secuencia de instrucciones que puede ser obedecida por un robot, se llama algoritmo " (p. 4).
Tausworthe, Robert C (1977). Métodos de desarrollo estandarizado de software informático, parte 1 . Englewood Cliffs Nueva Jersey: Prentice – Hall, Inc. ISBN 978-0-13-842195-3.
Turing, Alan M. (1936-1937). "Sobre números computables, con una aplicación al problema de Entscheidungs". Actas de la Sociedad Matemática de Londres . Serie 2. 42 : 230–265. doi :10.1112/plms/s2-42.1.230. S2CID 73712.. Correcciones, ibídem, vol. 43 (1937) págs. 544–546. Reimpreso en Lo indecidible , p. 116 y sigs. El famoso artículo de Turing se completó 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 Sociedad Matemática de Londres . 45 : 161–228. doi :10.1112/plms/s2-45.1.161. hdl : 21.11116/0000-0001-91CE-3 .Reimpreso en Lo indecidible , 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 Estados Unidos (2006), 2106.02 **>Algoritmos matemáticos: 2100 Patentabilidad, Manual de procedimiento 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. Revista universitaria de matemáticas de dos años, 1(2), 76–99. https://doi.org/10.2307/3027363
Otras lecturas
Bellah, Robert Neelly (1985). Hábitos del corazón: individualismo y compromiso en la vida estadounidense. Berkeley: Prensa de la Universidad de California. ISBN 978-0-520-25419-0.
Berlinski, David (2001). El advenimiento del algoritmo: el viaje de 300 años desde una idea hasta la computadora. Libros de cosecha. ISBN 978-0-15-601391-8.
Chabert, Jean-Luc (1999). Una historia de los algoritmos: del guijarro al microchip . Springer Verlag. ISBN 978-3-540-63369-3.
Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introducción a los algoritmos (3ª ed.). Prensa del MIT. ISBN 978-0-262-03384-8.
Harel, David; Feldman, Yishai (2004). Algorítmica: 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 Agustín; McConkey, Dale (eds.). Pensamiento comunitario y político hoy . Westport, Connecticut: Praeger .
Knuth, Donald E. (2000). Artículos 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). Máquinas morales: enseñar a los robots el bien y el mal . Estados Unidos: Oxford University Press. ISBN 978-0-19-537404-9.
Bleakley, Chris (2020). Poemas que resuelven acertijos: la historia y la ciencia de los algoritmos. Prensa de la Universidad de Oxford. ISBN 978-0-19-885373-2.
enlaces externos
Busque algoritmo en Wikcionario, el diccionario gratuito.
Wikilibros tiene un libro sobre el tema de: Algoritmos
En Wikiversity , 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 .
