Hispanopedia Wiki
Articulo de referencia

Algoritmo

Diagrama de flujo de un algoritmo para encontrar el máximo común divisor de dos números. En matemáticas e informática , un algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm / ⓘ ) es una secuenci...

Hispanopedia WikiContenido en espanolLectura gratuita

En un bucle, resta el número mayor al menor. Detén el bucle cuando la resta dé como resultado un número negativo. Comprueba si uno de dos números es igual a cero. Si lo es, toma el otro como máximo común divisor. Si no, vuelve a incluir los dos números en el bucle de resta.
Diagrama de flujo de un algoritmo para encontrar el máximo común divisor de dos números.

En matemáticas e informática , un algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm /ⓘ ) es unasecuencia finita [ 1 ] deinstruccionesmatemáticamente rigurosasproblemaso para realizar uncálculo. [ 2 ] Los algoritmos se utilizan como especificaciones para realizarcálculosyprocesamiento de datos. Los algoritmos más avanzados pueden utilizarcondicionalespara desviar la ejecución del código a través de varias rutas (lo que se denominatoma de decisiones automatizada) y deducirinferencias(lo que se denominarazonamiento automatizado).

En cambio, una heurística es un método para resolver problemas sin resultados correctos u óptimos bien definidos. [ 3 ] 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 en un espacio y tiempo finitos [ 4 ] y en un lenguaje formal bien definido [ 5 ] para calcular una función [ 6 ] . Partiendo de un estado inicial y una entrada, se realiza un cálculo en cada paso, que finalmente produce una salida [ 7 ] y termina. La transición entre estados puede ser no determinista ; los algoritmos aleatorios incorporan entradas aleatorias [ 8 ] .

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 cálculo indio") y kitab al-jam' wa'l-tafriq al-ḥisāb al-hindī ("Suma y resta en la aritmética india"). A principios del siglo XII, aparecieron traducciones latinas de estos textos que involucraban el sistema de numeración y aritmética indoarábigo , por ejemplo Liber Alghoarismi de practica arismetrice , atribuido a Juan de Sevilla , y Liber Algoritmi de numero Indorum , atribuido a Adelardo de Bath . [ 9 ] Aquí, alghoarismi o algoritmi es la latinización del nombre de Al-Khwarizmi; [ 2 ] El texto comienza con la frase Dixit Algoritmi , o "Así habló Al-Juarismi". [ 3 ]

Muḥammad ibn Mūsā al-Khwārizmī : El matemático del siglo IX cuyo nombre es el origen de la palabra 'algoritmo'.

La palabra algorismo en inglés pasó a significar el uso de la notación posicional en los cálculos; aparece en el Ancrene Wisse de alrededor de 1225. [ 10 ] Para cuando Geoffrey Chaucer escribió Los cuentos de Canterbury a finales del siglo XIV, usó una variante de la misma palabra para describir las piedras augrym , piedras utilizadas para el cálculo posicional. [ 11 ] [ 12 ] En el siglo XV, bajo la influencia de la palabra griega ἀριθμός ( arithmos , "número"; cf. "aritmética"), la palabra latina se modificó a algorithmus . [ 13 ] Hacia 1596, esta forma de la palabra fue utilizada en inglés, como algorithm , por Thomas Hood . [ 14 ]

Definición

Una definición informal es "un conjunto de reglas que define con precisión una secuencia de operaciones" [ 15 ] , lo que incluiría todos los programas informáticos y cualquier procedimiento burocrático [ 16 ] o receta de libro de cocina [ 17 ] . En general, un programa es un algoritmo solo si termina eventualmente [ 18 ] . Formalmente, un algoritmo es un conjunto explícito de instrucciones para producir una salida, que puede ser seguida por una computadora o un humano que realiza operaciones específicas sobre símbolos [ 19 ] .

Historia

Algoritmos antiguos

Se han registrado procedimientos paso a paso para resolver problemas matemáticos desde la antigüedad. Esto incluye las matemáticas babilónicas (alrededor del 2500 a. C.), [ 20 ] las matemáticas egipcias (alrededor del 1550 a. C.), [ 20 ] las matemáticas indias (alrededor del 800 a. C. y posteriores), [ 21 ] [ 22 ] el Oráculo de Ifá (alrededor del 500 a. C.), [ 23 ] las matemáticas griegas (alrededor del 240 a. C.), [ 24 ] las matemáticas chinas (alrededor del 200 a. C. y posteriores) , [ 25 ] y las matemáticas árabes (alrededor del 800 d. C.). [ 26 ]

La evidencia más antigua de algoritmos se encuentra en las matemáticas de la antigua Mesopotamia . Una tablilla de arcilla sumeria hallada en Shuruppak, cerca de Bagdad , y datada alrededor del 2500 a . C., describe el primer algoritmo de división . [ 20 ] Durante la dinastía de Hammurabi , entre el 1800 y el 1600 a. C. , las tablillas de arcilla babilónicas describían algoritmos para calcular fórmulas. [ 27 ] Los algoritmos también se utilizaban 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. [ 28 ] 

También se encuentran algoritmos para la aritmética en las matemáticas del antiguo Egipto , que se remontan al Papiro Matemático de Rhind c. 1550 a. C. [ 20 ] Los algoritmos se utilizaron posteriormente en las matemáticas helenísticas antiguas . Dos ejemplos son la Criba de Eratóstenes , que fue descrita en la Introducción a la Aritmética de Nicómaco , [ 29 ] [ 24 ] : Cap. 9.2 y el algoritmo euclidiano , que fue descrito por primera vez en los Elementos de Euclides ( c. 300 a. C. ). [ 24 ] : Cap. 9.1 Ejemplos de matemáticas de la antigua India incluyen los Shulba Sutras , la Escuela de Kerala y el Brāhmasphuṭasiddhānta . [ 21 ]

En el siglo IX, Muḥammad ibn Mūsā al-Khwārizmī revolucionó el campo al establecer el algoritmo como una secuencia sistemática y finita de pasos lógicos para resolver problemas matemáticos. En su influyente obra, El libro compendioso sobre el cálculo por compleción y equilibrio , fue más allá de las soluciones numéricas específicas para introducir procedimientos generales de reducción y equilibrio algebraicos. Esto transformó las matemáticas en un proceso «mecánico» de reglas bien definidas, un cambio fundamental que sentó las bases de la teoría algorítmica moderna. La traducción latina de su tratado de aritmética, titulado Algoritmi de numero Indorum, dio origen al término algoritmo, derivado de la latinización de su nombre, Algoritmi, específicamente para describir este nuevo enfoque matemático basado en reglas. [ 30 ]

El primer algoritmo criptográfico para descifrar códigos cifrados fue desarrollado por Al-Kindi , un matemático árabe del siglo IX, en su obra Un manuscrito sobre el descifrado de mensajes criptográficos . En ella, ofreció la primera descripción del criptoanálisis mediante análisis de frecuencia , el primer algoritmo de descifrado de códigos. [ 26 ]

Computadoras

Relojes accionados por pesas

Los relojes accionados por pesas fueron una invención europea clave en la Edad Media , específicamente el mecanismo de escape de áncora [ 31 ] que producía el tictac de los relojes mecánicos. Las máquinas automáticas precisas [ 32 ] dieron lugar a los autómatas mecánicos en el siglo XIII y a las máquinas de cálculo: las máquinas diferencial y analítica de Charles Babbage y Ada Lovelace a mediados del siglo XIX. [ 33 ] Lovelace diseñó el primer algoritmo destinado a una computadora, la máquina analítica de Babbage, la primera computadora realmente completa de Turing , más que las calculadoras mecánicas de la época. Aunque la implementación completa del segundo dispositivo de Babbage no se construyó hasta décadas después de su muerte, Lovelace ha sido llamada "la primera programadora de la historia".

Relé electromecánico

El telar Jacquard , precursor de las tarjetas perforadas , y las máquinas de conmutación telefónica propiciaron el desarrollo de las primeras computadoras. [ 34 ] A mediados del siglo XIX, el telégrafo se utilizaba en todo el mundo. A finales del siglo XIX, se desarrollaron la cinta de teletipo ( hacia la década de 1870 ) y las tarjetas perforadas (hacia 1890). Luego llegó el teletipo ( hacia 1910 ) con su uso de papel perforado y código Baudot en cinta.

Las redes de conmutación telefónica mediante relés electromecánicos se inventaron en 1835. Esto propició la invención de la calculadora digital por George Stibitz en 1937. Mientras trabajaba en los Laboratorios Bell, observó el uso engorroso de las calculadoras mecánicas con engranajes, lo que lo impulsó a crear una calculadora digital experimental en su casa. [ 35 ] [ 36 ]

Formalización

Diagrama de Ada Lovelace de " Nota G ", el primer algoritmo informático publicado.

En 1928, se inició una formalización parcial del concepto moderno de algoritmos con intentos de resolver el problema de decisión ( Entscheidungsproblem ) de David Hilbert . Las formalizaciones posteriores se plantearon como intentos de definir la " calculabilidad efectiva " [ 37 ] o el "método efectivo" [ 38 ] . Dichas formalizaciones incluyeron las funciones recursivas de Gödel , Herbrand y Kleene de 1930, 1934 y 1935, el cálculo lambda de Alonzo Church de 1936, la Formulación 1 de Emil Post de 1936 y las máquinas de Turing de Alan Turing de 1936-37 y 1939.

Algoritmos modernos

Durante décadas, se asumió que la evolución de los algoritmos progresaba desde las heurísticas hasta los algoritmos formales. Una integración simbólica ofrece un ejemplo clásico. En 1961, el programa SAINT de James Slagle utilizó heurísticas para resolver 52 de 54 ejercicios de cálculo para estudiantes de primer año de un libro de texto del MIT (aproximadamente el 96%). En 1967, SIN de Larry Moses perfeccionó las heurísticas y logró un éxito del 100%, aunque siguió siendo heurístico. Finalmente, en 1969, Robert Risch presentó el algoritmo de Risch con garantías formales. Esta trayectoria definió el camino tradicional: las heurísticas evolucionaban hasta que surgía un algoritmo definitivo y garantizado.

Sin embargo, el auge de la IA basada en transformadores ha invertido esta secuencia: los algoritmos clásicos están siendo reemplazados una vez más por heurísticas.

Los algoritmos han evolucionado y mejorado considerablemente con el paso del tiempo. Hoy en día, se utilizan comúnmente en aplicaciones de redes sociales como Instagram y YouTube . Los algoritmos se emplean para analizar las preferencias de los usuarios y ofrecerles contenido similar. La computación cuántica utiliza algoritmos cuánticos para resolver problemas con mayor rapidez. Más recientemente, en 2024, el NIST actualizó sus estándares de cifrado postcuántico, que incluyen nuevos algoritmos para reforzar la protección contra ataques mediante computación cuántica.

Representaciones

Los algoritmos pueden expresarse mediante diversas notaciones, como lenguajes naturales , pseudocódigo , diagramas de flujo , diagramas de Drakon , lenguajes de programación o tablas de control . Las expresiones de algoritmos en lenguaje natural suelen ser prolijas 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 un formato ejecutable por ordenador, pero también para definirlos o documentarlos.

Máquinas de Turing

Hay muchas representaciones posibles y los programas de la máquina de Turing pueden expresarse 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), como una forma de código 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. [ 39 ] Una descripción de alto nivel describe las cualidades del algoritmo en sí, ignorando cómo se implementa en la máquina de Turing. [ 39 ] Una descripción de implementación describe la manera general en que la máquina mueve su cabezal y almacena datos para llevar a cabo el algoritmo, pero no da estados exactos. [ 39 ] En el más detallado, una descripción formal da la tabla de estados exacta y la lista de transiciones de la máquina de Turing. [ 39 ]

Representación mediante diagrama de flujo

Un diagrama de flujo es una herramienta gráfica que describe y documenta un algoritmo. Consta de cuatro símbolos principales: flechas que muestran el flujo del programa, rectángulos (SECUENCIA, IR A), rombos que representan decisiones y puntos (OR). Las subestructuras pueden anidarse dentro de los rectángulos, pero solo si existe una única salida desde la superestructura.

Análisis algorítmico

A menudo es importante conocer el tiempo, el almacenamiento u otros costos que puede requerir un algoritmo. Se han desarrollado métodos para analizar algoritmos y estimar estas necesidades. Por ejemplo, un algoritmo que suma los elementos de una lista de n números tendría un requerimiento de tiempo de ⁠O(norte){\displaystyle O(n)}⁠ , utilizando la notación O grande . 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 ⁠O(1){\displaystyle O(1)}, de lo contrarioO(norte){\displaystyle O(n)}es obligatorio .

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 coste ⁠O(registro⁡norte){\displaystyle O(\log n)}⁠ ) ​​supera a una búsqueda secuencial (coste ⁠O(norte){\displaystyle O(n)}) cuando se utiliza para búsquedas en tablas de listas ordenadas.

Formal versus empírico

El análisis y estudio de algoritmos es una disciplina de la informática . Los algoritmos se estudian a menudo de forma abstracta, sin hacer referencia a un lenguaje de programación o implementación específicos. Al igual que otras disciplinas matemáticas, se centra en las propiedades del algoritmo, no en su 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 específicas y su eficiencia algorítmica se prueba con código real. La eficiencia de un algoritmo en particular puede ser insignificante para muchos problemas puntuales, pero puede ser crítica para algoritmos diseñados para un uso rápido, interactivo, comercial o científico a largo plazo. Aumentar el tamaño de la entrada a menudo revela algoritmos ineficientes que, de otro modo, serían inofensivos.

Las pruebas empíricas son útiles para descubrir interacciones inesperadas que afectan el rendimiento. Se pueden usar puntos de referencia para comparar las posibles mejoras de un algoritmo antes y después de la optimización del programa. Las pruebas empíricas no pueden reemplazar por completo el análisis formal y son difíciles de realizar de manera justa. [ 40 ]

Eficiencia de ejecución

Para ilustrar las posibles mejoras incluso en algoritmos bien establecidos, una reciente innovación significativa, relacionada con los algoritmos FFT utilizados para el procesamiento de imágenes, puede reducir el tiempo de procesamiento hasta 1000 veces para imágenes médicas. [ 41 ] En general, las mejoras de velocidad dependen de propiedades especiales del problema, que son muy comunes en aplicaciones prácticas. [ 42 ]

Mejor escenario y peor escenario

El mejor caso de un algoritmo se refiere al escenario o entrada para el cual el algoritmo o estructura de datos requiere el menor tiempo y recursos para completar sus tareas. [ 43 ] El peor caso de un algoritmo es aquel que hace que el algoritmo o estructura de datos consuma el máximo tiempo y recursos computacionales. [ 44 ]

Diseño

El diseño de algoritmos puede aprovechar diversos enfoques, como la estrategia de divide y vencerás o la programación dinámica . Las técnicas para diseñar e implementar algoritmos también se denominan patrones de diseño de algoritmos. [ 45 ] Algunos ejemplos son el patrón de método plantilla y el patrón decorador. Un aspecto importante del diseño de algoritmos es el uso eficiente de recursos como la memoria o el tiempo; la notación O grande se utiliza para describir cómo cambia el uso de recursos a medida que aumenta el tamaño de las entradas. [ 46 ]

Programación estructurada

Cualquier algoritmo puede ser calculado por cualquier modelo Turing completo . La completitud de Turing solo requiere cuatro tipos de instrucciones: GOTO condicional, GOTO incondicional, asignación y HALT. Tausworthe amplía las tres estructuras canónicas de Böhm-Jacopini : [ 47 ] SEQUENCE, IF-THEN-ELSE y WHILE-DO, con dos más: DO-WHILE y CASE. [ 48 ] Un beneficio adicional de un programa estructurado es que se presta a pruebas de corrección mediante inducción matemática . [ 49 ]

Por sí solos, los algoritmos no suelen ser patentables. En Estados Unidos, una reivindicación que consiste únicamente en manipulaciones simples de conceptos abstractos, números o señales no constituye un "proceso", por lo que los algoritmos no son patentables (como en Gottschalk v. Benson ). Sin embargo, las aplicaciones prácticas de los algoritmos sí pueden ser patentables. Por ejemplo, en Diamond v. Diehr , la aplicación de un algoritmo de retroalimentación simple para ayudar en el curado del caucho sintético se consideró patentable. La patentabilidad del software es controvertida, [ 50 ] 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

Mediante la implementación

Recursión
Un algoritmo recursivo se invoca a sí mismo repetidamente hasta que se cumple una condición de terminación y es una técnica común de programación funcional . Los algoritmos iterativos utilizan repeticiones, como bucles , o estructuras de datos, como pilas, para resolver problemas. Algunos problemas se adaptan mejor a una implementación u otra. La Torre de Hanoi es un rompecabezas que se suele resolver mediante una implementación recursiva. Toda versión recursiva tiene una versión iterativa equivalente (aunque posiblemente más o menos compleja), y viceversa.
En serie, en paralelo o distribuido
Los algoritmos suelen analizarse asumiendo que las computadoras ejecutan una instrucción a la vez en sistemas seriales. Estos algoritmos están diseñados para dichos entornos, a diferencia de los algoritmos paralelos o distribuidos . Los algoritmos paralelos aprovechan las arquitecturas informáticas que permiten que múltiples procesadores trabajen en un problema simultáneamente. Los algoritmos distribuidos utilizan múltiples máquinas conectadas a través de una red informática. Tanto los algoritmos paralelos como los distribuidos dividen el problema en subproblemas y recopilan los resultados. El consumo de recursos en estos algoritmos no solo incluye los ciclos de procesamiento de cada procesador, sino también la sobrecarga de comunicación entre ellos. Algunos algoritmos de ordenación pueden paralelizarse de forma eficiente, pero su sobrecarga de comunicación es elevada. Los algoritmos iterativos suelen ser paralelizable, pero algunos problemas no tienen algoritmos paralelos y se denominan inherentemente seriales.
Determinista o no determinista
Los algoritmos deterministas resuelven el problema tomando decisiones exactas en cada paso; mientras que los algoritmos no deterministas lo resuelven mediante conjeturas. Estas conjeturas suelen ser más precisas gracias al uso de heurísticas .
Exacto o aproximado
Si bien muchos algoritmos alcanzan una solución exacta, los algoritmos de aproximación buscan una aproximación cercana a la solución verdadera. Estos algoritmos tienen un valor práctico para muchos problemas difíciles. Por ejemplo, el problema de la mochila , donde hay un conjunto de objetos y el objetivo es llenar la mochila para obtener el máximo valor total. Cada objeto tiene un peso y un valor. El peso total que se puede transportar no supera un número fijo X. Por lo tanto, la solución debe considerar tanto el peso de los objetos como su valor. [ 51 ]
Algoritmo cuántico
Los algoritmos cuánticos se ejecutan sobre un modelo realista de computación cuántica . El término se suele utilizar para aquellos algoritmos que parecen inherentemente cuánticos o que utilizan alguna característica esencial de la computación cuántica, como la superposición cuántica o el entrelazamiento cuántico .

Por paradigma de diseño

Otra forma de clasificar los algoritmos es según su metodología de diseño o paradigma . Algunos paradigmas comunes son:

Búsqueda por fuerza bruta o exhaustiva
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 ser muy laborioso, ya que implica probar todas las combinaciones posibles de variables. Se suele utilizar cuando otros métodos no están disponibles o son demasiado complejos. La fuerza bruta puede resolver diversos problemas, como encontrar la ruta más corta 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 recursivamente ) hasta que las instancias son lo suficientemente pequeñas como para resolverlas fácilmente. La ordenación por fusión es un ejemplo de divide y vencerás, donde una lista no ordenada se divide repetidamente en listas más pequeñas, que se ordenan de la misma manera y luego se fusionan. [ 52 ] En una variante más simple de divide y vencerás llamada poda y búsqueda o algoritmo de disminución y conquista , que resuelve una instancia más pequeña de sí mismo y no requiere un paso de fusión. [ 53 ] Un ejemplo de un algoritmo de poda y búsqueda es el algoritmo de búsqueda binaria .
Búsqueda y enumeración
Muchos problemas (como jugar al ajedrez ) pueden modelarse como problemas en grafos . Un algoritmo de exploración de grafos especifica reglas para moverse por un grafo y resulta útil para este tipo de problemas. Esta categoría también incluye algoritmos de búsqueda , enumeración de ramificación y acotación , y retroceso .
Algoritmo aleatorio
Estos algoritmos toman algunas decisiones de forma aleatoria (o pseudoaleatoria). Encuentran soluciones aproximadas cuando encontrar soluciones exactas puede ser impracticable (véase el método heurístico más adelante). Para algunos problemas, las aproximaciones más rápidas deben implicar cierta aleatoriedad . [ 54 ] Si los algoritmos aleatorios con complejidad temporal polinomial pueden ser el algoritmo más rápido para algunos problemas es una cuestión abierta conocida como el problema P versus NP . Existen dos grandes clases de estos algoritmos:
  1. Los algoritmos de Monte Carlo devuelven una respuesta correcta con alta probabilidad. Por ejemplo, RP es una subclase de estos que se ejecuta en tiempo polinomial .
  2. Los algoritmos de Las Vegas siempre devuelven la respuesta correcta, pero su tiempo de ejecución solo está limitado probabilísticamente, por ejemplo, ZPP .
Reducción de la complejidad
Esta técnica transforma problemas difíciles en problemas más conocidos que se pueden resolver con algoritmos (con suerte) asintóticamente óptimos . 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 central de la lista ordenada (la parte económica). Esta técnica también se conoce como transformar y conquistar .
Retroceder
En este enfoque, se construyen múltiples soluciones de forma incremental y se descartan 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 pertenecer a una o más de las categorías generales descritas anteriormente, así como a una de las siguientes:

Programación lineal
Al buscar soluciones óptimas para una función lineal limitada por restricciones de igualdad y desigualdad lineales, estas restricciones pueden utilizarse directamente para generar dichas soluciones. Existen algoritmos que pueden resolver cualquier problema de esta categoría, como el popular algoritmo simplex . [ 55 ] Entre los problemas que pueden resolverse con programación lineal se incluye el problema del flujo máximo para grafos dirigidos. Si un problema también requiere que alguna de las incógnitas sea un número entero , entonces se clasifica dentro de la programación entera . Un algoritmo de programación lineal puede resolver dicho problema si se puede demostrar que todas las restricciones para los valores enteros son superficiales, es decir, que las soluciones satisfacen estas restricciones de todos modos. En el caso general, se utiliza un algoritmo especializado o un algoritmo que encuentra soluciones aproximadas, dependiendo de la dificultad del problema.
Programación dinámica
Cuando un problema presenta subestructuras óptimas —lo que significa que la solución óptima puede construirse a partir de soluciones óptimas de subproblemas— y subproblemas superpuestos —lo que significa que los mismos subproblemas se utilizan para resolver muchas instancias diferentes del problema—, un enfoque más rápido llamado programación dinámica evita el recálculo de soluciones. Por ejemplo, en el algoritmo de Floyd-Warshall , el camino más corto entre un vértice de inicio y un vértice de destino en un grafo ponderado puede encontrarse utilizando el camino más corto al destino desde todos los vértices adyacentes. La programación dinámica y la memorización van de la mano. A diferencia de la estrategia de divide y vencerás, los subproblemas de la programación dinámica a menudo se superponen. La diferencia entre la programación dinámica y la recursión simple radica en el almacenamiento en caché o memorización de las llamadas recursivas. Cuando los subproblemas son independientes y no se repiten, la memorización no resulta útil; 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 de exponencial a polinómica.
El método codicioso
Los algoritmos voraces , al igual que la programación dinámica, funcionan examinando subestructuras, en este caso no del problema, sino de una solución dada. Estos algoritmos parten de una solución y la mejoran mediante pequeñas modificaciones. Para algunos problemas, siempre encuentran la solución óptima, pero para otros pueden detenerse en óptimos locales . El uso más común de los algoritmos voraces es encontrar árboles de expansión mínima de grafos sin ciclos negativos. El árbol de Huffman , Kruskal , Prim y Sollin son algoritmos voraces que pueden resolver este problema de optimización.
El método heurístico
En problemas de optimización , los algoritmos heurísticos encuentran soluciones cercanas a la óptima cuando hallarla resulta impracticable. Estos algoritmos se aproximan 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. Idealmente, pueden encontrar una solución muy cercana a la óptima en un tiempo relativamente corto. Estos algoritmos incluyen la búsqueda local , la búsqueda tabú , el recocido simulado y los 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 una cota para 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 sencillos encuentra 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. A partir de esto, se deriva un algoritmo sencillo que se puede describir en lenguaje natural como:

Descripción de alto nivel:

  1. Si un conjunto de números está vacío, entonces no existe un número máximo.
  2. Supongamos que el primer número del conjunto es el mayor.
  3. Para cada número restante en el conjunto: si este número es mayor que el mayor actual, se convierte en el nuevo mayor.
  4. Cuando no queden 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 informático, 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 null. largest ← L [0] Para cada elemento en L , haz lo siguiente: si item > largest , entonces largest ← item, devuelve largest.
  • " ← " denota asignación . Por ejemplo, " largest ← item " significa que el valor de largest cambia al valor de item .
  • " return " finaliza el algoritmo y genera el siguiente valor.

Descubrimiento de algoritmos asistido por IA

Los sistemas de inteligencia artificial se han utilizado para descubrir y optimizar algoritmos. En 2023, Google DeepMind presentó AlphaDev , un sistema de aprendizaje por refuerzo basado en AlphaZero que descubrió algoritmos de ordenación y hash mejorados. [ 56 ] En un artículo publicado en Nature , se informó que AlphaDev había descubierto pequeños algoritmos de ordenación que superaban los parámetros de referencia humanos conocidos anteriormente y que se integraron en la biblioteca de ordenación estándar de C++ de LLVM . [ 57 ]

En 2025, Google DeepMind presentó AlphaEvolve , un agente de codificación evolutiva impulsado por grandes modelos de lenguaje para el descubrimiento y la optimización de algoritmos de propósito general. [ 58 ] AlphaEvolve utiliza modelos de lenguaje para proponer cambios en el código, evaluadores automatizados para probar soluciones candidatas y un proceso evolutivo para mejorar algoritmos prometedores a lo largo de múltiples iteraciones. [ 59 ]

Véase también

Notas

  1. ↑ "Un procedimiento que tiene todas las características de un algoritmo excepto que posiblemente carece de finitud puede llamarse 'método computacional ' " (Knuth 1971:5).
  2. 1 2 "Definición de ALGORITMO" . Diccionario en línea Merriam-Webster . Archivado del original el 14 de febrero de 2020. Recuperado el 14 de noviembre de 2019 .
  3. 1 2 David A. Grossman, Ophir Frieder, Recuperación de información: algoritmos y heurísticas , 2.ª edición, 2004, ISBN 1402030045
  4. ↑ "Cualquier algoritmo matemático clásico, por ejemplo, puede describirse en un número finito de palabras en inglés" (Rogers 1987:2).
  5. ↑ Bien definido en cuanto al agente que ejecuta el algoritmo: "Hay un agente computacional, generalmente humano, que puede reaccionar a las instrucciones y llevar a cabo los cálculos" (Rogers 1987:2).
  6. ↑ "un algoritmo es un procedimiento para calcular una función (relacionada con alguna notación elegida para enteros) ... esta limitación (a funciones numéricas) no resulta en pérdida de generalidad", (Rogers 1977:1).
  7. ↑ "Un algoritmo tiene una o más salidas, es decir, cantidades que tienen una relación específica con las entradas" (Knuth 1973:5).
  8. ↑ Es discutible si un proceso con procesos internos aleatorios (sin incluir la entrada) constituye o no un algoritmo. Rogers opina que: "un cálculo se lleva a cabo de forma discreta y gradual, sin utilizar métodos continuos ni dispositivos analógicos... se realiza de forma determinista, sin recurrir a métodos o dispositivos aleatorios, como los dados" (Rogers 1987:2).
  9. ↑ Blair, Ann, Duguid, Paul, Goeing, Anja-Silvia y Grafton, Anthony. Información: Un compañero histórico, Princeton: Princeton University Press, 2021. pág. 247
  10. ↑ "algorismo" . Diccionario Oxford de inglés . Consultado el 18 de mayo de 2025 .
  11. ↑ Chaucer, Geoffrey. "El cuento del molinero" . Línea 3210.
  12. ↑ Skeat, Walter William (1914). «agrim, agrum» . En Mayhew, Anthony Lawson (ed.). Glosario de palabras Tudor y Stuart: especialmente de los dramaturgos . Clarendon Press. págs. 5–6 . 
  13. ↑ Grabiner, Judith V. (diciembre de 2013). «El papel de las matemáticas en la educación en artes liberales». En Matthews, Michael R. (ed.). Manual internacional de investigación en historia, filosofía y enseñanza de las ciencias . Springer. págs. 793–836 . doi : 10.1007/978-94-007-7654-8_25 . ISBN  9789400776548.
  14. ↑ "algoritmo" . Diccionario Oxford de inglés . Consultado el 18 de mayo de 2025 .
  15. ↑ Stone (1971) , pág. 8.
  16. ↑ Simanowski, Roberto (2018). El algoritmo de la muerte y otros dilemas digitales . Meditaciones intempestivas. Vol. 14. Traducido por Chase, Jefferson. Cambridge, Massachusetts: MIT Press. pág. 147. ISBN   9780262536370. Archivado del original el 22 de diciembre de 2019. Recuperado el 27 de mayo de 2019. [ ...] el siguiente nivel de abstracción de la burocracia central: algoritmos que operan globalmente.
  17. ↑ Dietrich, Eric (1999). «Algoritmo». En Wilson, Robert Andrew; Keil, Frank C. (eds.). La enciclopedia del MIT de las ciencias cognitivas . Biblioteca Cognet del MIT. Cambridge, Massachusetts: MIT Press (publicado en 2001). pág. 11. ISBN  9780262731447. Consultado el 22 de julio de 2020. Un algoritmo es una receta, método o técnica para hacer algo.
  18. ↑ Stone exige que "debe terminar en un número finito de pasos" (Stone 1973:7–8).
  19. ↑ Boolos y Jeffrey 1974, 1999:19
  20. 1 2 3 4 Chabert, Jean-Luc (2012). Historia de los algoritmos: del guijarro al microchip . Springer Science & Business Media. págs. 7–8 . ISBN  9783642181924.
  21. 1 2 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. ISBN  978-93-86279-25-5.
  22. ↑ Hayashi, T. (1 de enero de 2023). Brahmagupta . Enciclopedia Británica.
  23. ↑ 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 .  
  24. 1 2 3 Cooke, Roger L. (2005). Historia de las matemáticas: Un breve curso . John Wiley & Sons. ISBN 978-1-118-46029-0.
  25. ↑ Chabert, Jean-Luc, ed. (1999). Una historia de los algoritmos . doi : 10.1007/978-3-642-18192-4 . ISBN 978-3-540-63369-3.
  26. 1 2 Dooley, John F. (2013). Breve historia de la criptología y los algoritmos criptográficos . Springer Science & Business Media. págs. 12–3 . ISBN  9783319016283.
  27. ↑ 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 del original (PDF) el 24 de diciembre de 2012.  
  28. ↑ Aaboe, Asger (2001). Episodios de la historia temprana de la astronomía . Nueva York: Springer. págs. 40–62 . ISBN  978-0-387-95136-2.
  29. ↑ Ast, Courtney. "Eratóstenes" . Universidad Estatal de Wichita: Departamento de Matemáticas y Estadística. Archivado del original el 27 de febrero de 2015. Recuperado el 27 de febrero de 2015 .
  30. ↑ Knuth, Donald E. (1996). Selected Papers on Computer Science . CSLI Publications. pp. 1– 2. El trabajo de Al-Khwarizmi fue el primero en proporcionar un enfoque sistemático y basado en reglas para resolver ecuaciones, razón por la cual la palabra "algoritmo" se acuñó a partir de su nombre para describir este proceso metódico. 
  31. ↑ Bolter 1984:24
  32. ↑ Bolter 1984:26
  33. ^ Bólter 1984: 33–34, 204–206.
  34. ↑ Diagrama de Bell y Newell 1971:39, cf. Davis 2000
  35. ↑ Melina Hill, corresponsal de Valley News, Un inventor hace historia , Valley News West Lebanon NH, jueves 31 de marzo de 1983, pág. 13.
  36. ↑ Davis 2000:14
  37. ↑ Kleene 1943 en Davis 1965:274
  38. ↑ Rosser 1939 en Davis 1965:225
  39. 1 2 3 4 Sipser 2006:157
  40. ↑ Kriegel, Hans-Peter ; Schubert, Erich; Zimek, Arthur (2016). "El (oscuro) arte 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 .  
  41. ↑ Gillian Conahan (enero de 2013). "Mejores matemáticas hacen redes de datos más rápidas" . discovermagazine.com. Archivado del original el 13 de mayo de 2014. Recuperado el 13 de mayo de 2014 .
  42. ↑ 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 sFFT Archivada el 21 de febrero de 2012 en Wayback Machine .
  43. ↑ "Mejor caso" . Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología (NIST). Instituto Nacional de Estándares y Tecnología . Consultado el 29 de mayo de 2025 .
  44. ↑ "peor caso" . Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología (NIST). Instituto Nacional de Estándares y Tecnología (NIST) . Consultado el 29 de mayo de 2025 .
  45. ↑ Goodrich, Michael T .; Tamassia, Roberto (2002). Diseño de algoritmos: Fundamentos, análisis y ejemplos de Internet . John Wiley & Sons, Inc. ISBN 978-0-471-38365-9Archivado del original el 28 de abril de 2015. Consultado el 14 de junio de 2018 .
  46. ↑ "Notación Big-O (artículo) | Algoritmos" . Khan Academy . Consultado el 3 de junio de 2024 .
  47. ↑ Tausworthe 1977:101
  48. ↑ Tausworthe 1977:142
  49. ↑ Knuth 1973 sección 1.2.1, ampliada por Tausworthe 1977 en las páginas 100 y siguientes y en el capítulo 9.1
  50. ↑ «Los expertos: ¿Fomenta el sistema de patentes la innovación?» . The Wall Street Journal . 16 de mayo de 2013. ISSN 0099-9660 . Consultado el 29 de marzo de 2017 . 
  51. ↑ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Problemas con la mochila | Hans Kellerer | Saltador . Saltador. doi : 10.1007/978-3-540-24777-7 . ISBN 978-3-540-40286-2. S2CID 28836720 . Archivado del original el 18 de octubre de 2017 . Recuperado el 19 de septiembre de 2017 . 
  52. ↑ Goodrich, Michael T.; Tamassia, Roberto (2001). "5.2 Divide y vencerás". Diseño de algoritmos: fundamentos, análisis y ejemplos de Internet . John Wiley & Sons. pág. 263. ISBN  9780471383659.
  53. ↑ Goodrich y Tamassia (2001) , pág. 245, 4.7.1 Poda y búsqueda.
  54. ↑ Por ejemplo, el volumen de un politopo convexo (descrito mediante un oráculo de pertenencia) puede aproximarse con alta precisión mediante un algoritmo aleatorio de tiempo polinomial, pero no mediante uno determinista: véase Dyer, Martin; Frieze, Alan; Kannan, Ravi (enero de 1991). "Un algoritmo aleatorio de tiempo polinomial 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 .  
  55. ↑ George B. Dantzig y Mukund N. Thapa. 2003. Programación lineal 2: Teoría y extensiones . Springer-Verlag.
  56. ↑ "AlphaDev descubre algoritmos de ordenación más rápidos" . Google DeepMind . 7 de junio de 2023. Consultado el 29 de abril de 2026 .
  57. ↑ Mankowitz, Daniel J.; Michalski, Andrea; Zhernov, Anton; Gelmi, Marco; Selvi, Marco; et al. (junio de 2023). "Algoritmos de clasificación más rápidos descubiertos mediante aprendizaje profundo por refuerzo". Nature . 618 (7964): 257– 263. doi : 10.1038/s41586-023-06004-9 . PMID 37286649 .  
  58. ↑ "AlphaEvolve: Un agente de codificación impulsado por Gemini para el diseño de algoritmos avanzados" . Google DeepMind . 14 de mayo de 2025. Consultado el 29 de abril de 2026 .
  59. ^ Novikov, Alejandro; Vu, Ngan; Eisenberger, Marvin; Dupont, Emilien; Huang, Po-Sen; et al. (2025). "AlphaEvolve: un agente codificador para descubrimientos científicos y algorítmicos". arXiv : 2506.13131 [ cs.AI ]. 

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 de la Computación Teórica . 81. Archivado (PDF) del 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 discuten "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 Actas de la 4.ª Conferencia sobre Números Reales y Computadoras , Universidad de Odense, pp.  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 ss. La 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 decisión". The Journal of Symbolic Logic . 1 (1): 40– 41. doi : 10.2307/2269326 . JSTOR 2269326. S2CID 42323521 .  Church, Alonzo (1936). " Corrección a una nota sobre el problema de decisión". 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 demuestra que el problema de decisión 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 trabajos de Gödel , Alonzo Church , Turing , Rosser , Kleene y Emil Post ; los citados en el artículo se enumeran aquí por nombre del autor.
  • Davis, Martin (2000). Motores de la lógica: Matemáticos y el origen de la computadora . Nueva York: WW Nortion. ISBN 978-0-393-32229-3.Davis ofrece biografías concisas de Leibniz , Boole , Frege , Cantor , Hilbert , Gödel y Turing, con von Neumann como el villano que acapara toda la atención. También incluye biografías muy breves de Joseph-Marie Jacquard , Babbage , Ada Lovelace , Claude Shannon , Howard Aiken , etc.
  • Dominio público Este artículo incorpora material de dominio público de Paul E. Black. "algoritmo" . Diccionario de algoritmos y estructuras de datos . NIST .
  • 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 .
  • Dennett, Daniel (1995). La peligrosa idea de Darwin . Nueva York: Touchstone/Simon & Schuster. págs. 32-36 . ISBN  978-0-684-80290-9.
  • Dilson, Jesse (2007). El ábaco ((1968, 1994)  ed.). St. Martin's Press, Nueva York. ISBN 978-0-312-10409-2., ISBN 0-312-10409-X
  • Yuri Gurevich , Las máquinas de estados abstractos secuenciales capturan algoritmos secuenciales , ACM Transactions on Computational Logic, vol. 1, n.º 1 (julio de 2000), págs.  77-111. Incluye una bibliografía de 33 fuentes.
  • van Heijenoort, Jean (2001). De Frege a Gödel: Un libro de referencia en lógica matemática, 1879-1931 (  ed. de 1967). Harvard University Press, Cambridge. ISBN 978-0-674-32449-7., 3.ª edición 1976[?], ISBN 0-674-32449-8(pbk.)
  • Hodges, Andrew (1983). Alan Turing: El enigma . Nueva York: Simon and Schuster . ISBN 978-0-671-49207-6., ISBN 0-671-49207-1Véase el capítulo "El espíritu de la verdad" para un análisis histórico de su demostración y una discusión sobre la misma.
  • Kleene, Stephen C. (1936). "Funciones recursivas generales de números naturales" . Mathematische Annalen . 112 (5): 727– 742. doi : 10.1007/BF01565439 . S2CID 120517999. Archivado del original el 3 de septiembre de 2014. Recuperado el 30 de septiembre de 2013 . Presentado a la Sociedad Matemática Americana en septiembre de 1935. Reimpreso en The Undecidable , pág.  237 y siguientes. 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 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 y cuantificadores recursivos" . Transactions of the American Mathematical Society . 53 (1): 41– 73. doi : 10.2307/1990131 . JSTOR 1990131 . Reimpreso en The Undecidable , pág.  255 y ss. 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 la metamatemática (Décima  ed.). 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
  • Kowalski, Robert (1979). "Algoritmo = Lógica + Control" . Communications of the ACM . 22 (7): 424– 436. doi : 10.1145/359131.359136 . S2CID 2509896 . 
  • AA Markov (1954) Teoría de algoritmos . [Traducido por Jacques J. Schorr-Kon y personal de PST] Pie de imprenta Moscú, Academia de Ciencias de la URSS, 1954 [es decir, Jerusalén, Programa de Traducciones Científicas de Israel, 1961; disponible en la Oficina de Servicios Técnicos, Departamento de Comercio de EE. UU., Washington] Descripción 444 p.  28  cm. Portada añadida en ruso Traducción de las Obras del Instituto Matemático, Academia de Ciencias de la URSS, vol.  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  ed.). Prentice-Hall, Englewood Cliffs, NJ. 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.
  • Post, Emil (1936). " Procesos combinatorios finitos, formulación I". The Journal of Symbolic Logic . 1 (3): 103– 105. doi : 10.2307/2269031 . JSTOR 2269031. S2CID 40284503 .  Reimpreso en The Undecidable , págs.  289 y siguientes. Post define un proceso sencillo, similar a un algoritmo, en el que un hombre escribe o borra marcas, va de casilla en casilla y finalmente se detiene, siguiendo una lista de instrucciones simples. Kleene lo cita como una de las fuentes de su "Tesis I", la llamada tesis Church-Turing .
  • Rogers, Hartley Jr. (1987). Teoría de las funciones recursivas y la computabilidad efectiva . The MIT Press. ISBN 978-0-262-68052-3.
  • Rosser, JB (1939). " Una exposición informal de las demostraciones del teorema de Gödel y del teorema de Church". Journal of Symbolic Logic . 4 (2): 53– 60. doi : 10.2307/2269059 . JSTOR 2269059. S2CID 39499392 .  Reimpreso en The Undecidable , págs.  223 y siguientes. Aquí se encuentra la famosa definición de Rosser de "método eficaz": "...un método cuyos pasos están predeterminados con precisión y que garantiza la obtención de la respuesta en un número finito de pasos... una máquina que resolverá cualquier problema del conjunto sin intervención humana más allá de introducir la pregunta y (posteriormente) leer la respuesta" (págs.  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. pp. 111–127 . doi : 10.1007/978-3-319-08108-3_8 . ISBN  978-3-319-08107-6Archivado (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). Unto Others: The Evolution and Psychology of Unselfish Behavior . Cambridge: Harvard University Press. ISBN 9780674930469.
  • Stone, Harold S. (1971). Introducción a la organización de computadoras y estructuras de datos . McGraw-Hill, Nueva York. ISBN 9780070617261.Véase, en particular, el primer capítulo titulado: Algoritmos, máquinas de Turing y programas . Su concisa definición informal: «...cualquier secuencia de instrucciones que pueda ser obedecida por un robot se denomina algoritmo » (p.  4).
  • Tausworthe, Robert C. (1977). Desarrollo estandarizado de software informático. Parte 1: Métodos . Englewood Cliffs, NJ: Prentice-Hall, Inc. ISBN 978-0-13-842195-3.
  • Turing, Alan M. (1936–37). "Sobre los números computables, con una aplicación al problema de decisión". Actas de la Sociedad Matemática de Londres . Serie 2. 42 : 230–265 . doi : 10.1112/plms/s2-42.1.230 . S2CID 73712 . Correcciones, ibid., vol. 43 (1937), págs.  544-546. Reimpreso en The Undecidable , pág.  116 y ss. El famoso artículo de Turing, completado como tesis de maestría durante su estancia 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 The Undecidable , págs.  155 y siguientes. El artículo de Turing que definió "el oráculo" fue su tesis doctoral mientras estuvo 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
  • El NIST publica los tres primeros estándares definitivos de cifrado post-cuántico. https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards

Lecturas adicionales

  • 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). 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). Algoritmia: El espíritu de la computación . 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.). Comunidad y pensamiento político hoy . Westport, CT: Praeger .
  • Jon Kleinberg, Éva Tardos (2006): Diseño de algoritmos , Pearson/Addison-Wesley, ISBN 978-0-32129535-4
  • 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ñando a los robots a distinguir el bien del mal . EE. UU.: Oxford University Press. ISBN 978-0-19-537404-9.
  • Bleakley, Chris (2020). Poemas que resuelven acertijos: Historia y ciencia de los algoritmos . Oxford University Press. ISBN 978-0-19-885373-2.
Repositorios de algoritmos
Obtenido de " https://en.wikipedia.org/w/index.php?title=Algorithm&oldid=1360948503 "
Lecturas relacionadas
6 articulos
Máximo común divisorEn matemáticas , el máximo común divisor ( MCD ), también conocido como máximo común divisor (MCD), de dos o más números enteros , que no sean todo...MatemáticasMatemáticasLas matemáticas son un campo de estudio que descubre y organiza métodos, teorías y teoremas que se desarrollan y prueban para las necesidades de la...Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...SecuenciaUna parte de una sucesión infinita de números reales (en azul), indexada por un número natural n . Esta sucesión no es creciente, decreciente, conv...RigorRigorEl rigor ( inglés británico ) o rigor ( inglés americano ; ver diferencias ortográficas ) describe una condición de rigidez o estrictez. [1] Estas ...Problema computacionalProblema computacionalEn informática teórica , un problema es aquel que pide una solución en términos de un algoritmo . Por ejemplo, el problema de factorizar