Algoritmo

Es posible que este artículo requiera una corrección de estilo, gramática, coherencia, tono u ortografía . Puedes ayudar editándolo . ( Abril de 2024 ) ( Aprende cómo y cuándo eliminar este mensaje )

This article is written like a personal reflection, personal essay, or argumentative essay that states a Wikipedia editor's personal feelings or presents an original argument about a topic. Please help improve it by rewriting it in an encyclopedic style. (April 2024) (Learn how and when to remove this message)

En matemáticas e informática , un algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm / ^ⓘ ) es una secuencia finita deinstruccionesmatemáticamente rigurosasproblemaso para realizar uncálculo.^[1]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 conoce comotoma de decisiones automatizada) y deducirinferencias(lo que se conoce comorazonamiento automatizado).

Por el contrario, una heurística es un enfoque para resolver problemas que no tienen resultados correctos u óptimos bien definidos. ^{[2] Por ejemplo, aunque} los sistemas de recomendación de redes sociales se denominan comúnmente "algoritmos", en realidad se basan en heurísticas, ya que no existe una recomendación verdaderamente "correcta".

Como método eficaz , un algoritmo puede expresarse dentro de una cantidad finita de espacio y tiempo ^{[3] y en un} lenguaje formal bien definido ^[4] para calcular una función . ^[5] A partir de un estado inicial y una entrada inicial (quizás vacía ), ^[6] las instrucciones describen un cálculo que, cuando se ejecuta , procede a través de un número finito ^[7] de estados sucesivos bien definidos, produciendo eventualmente una "salida" ^[8] y terminando en un estado final. La transición de un estado al siguiente no es necesariamente determinista ; algunos algoritmos, conocidos como algoritmos aleatorios , incorporan una entrada aleatoria. ^[9]

Alrededor del año 825 d. C., el científico y polímata persa Muḥammad ibn Mūsā al-Khwārizmī escribió kitāb al-ḥisāb al-hindī ("Libro de computación india") y kitab al-jam' wa'l-tafriq al-ḥisāb al-hindī ("Suma y resta en aritmética india"). ^[1] A principios del siglo XII, aparecieron traducciones latinas de dichos textos de al-Khwarizmi que involucraban el sistema de numeración hindú-arábigo y la aritmética , por ejemplo, Liber Alghoarismi de practica arismetrice , atribuido a Juan de Sevilla , y Liber Algorismi de numero Indorum , atribuido a Adelardo de Bath . ^[10] Por lo tanto, alghoarismi o algorismi es la latinización del nombre de Al-Khwarizmi; El texto comienza con la frase Dixit Algorismi , o "Así habló Al-Khwarizmi". ^[2] Alrededor de 1230, se atestigua la palabra inglesa algoritmo y luego, por Chaucer en 1391, los ingleses adoptaron el término francés. ^{[3] [4] [ aclaración necesaria ]} En el siglo XV, bajo la influencia de la palabra griega ἀριθμός ( arithmos , "número"; cf. "aritmética"), la palabra latina fue alterada a algorithmus . ^{[ cita requerida ]}

Una definición informal es "un conjunto de reglas que definen con precisión una secuencia de operaciones", ^{[11] [ necesita citarse para verificar ]} que incluiría todos los programas informáticos (incluidos los programas que no realizan cálculos numéricos), y cualquier procedimiento burocrático prescrito ^[12] o receta de libro de cocina . ^[13] En general, un programa es un algoritmo solo si se detiene eventualmente ^[14] —aunque los bucles infinitos a veces pueden resultar deseables. Boolos, Jeffrey y 1974, 1999 definen un algoritmo como un conjunto explícito de instrucciones para determinar un resultado, que puede ser seguido por una máquina de computación o un humano que solo podría realizar operaciones elementales específicas en símbolos . ^[15]

La mayoría de los algoritmos están pensados ​​para ser implementados como programas informáticos . Sin embargo, los algoritmos también se implementan por otros medios, como en una red neuronal biológica (por ejemplo, el cerebro humano realizando operaciones aritméticas o un insecto buscando comida), en un circuito eléctrico o en un dispositivo mecánico.

This section is missing information about 20th and 21st century development of computer algorithms. Please expand the section to include this information. Further details may exist on the talk page. (October 2023)

Desde la antigüedad se han registrado procedimientos paso a paso para resolver problemas matemáticos, como en 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 Ifa (alrededor del 500 a. C.), ^[19] las matemáticas griegas (alrededor del 240 a. C.), ^[20] y las matemáticas árabes (alrededor del 800 d. C.). ^[21]

La evidencia más temprana de algoritmos se encuentra en las matemáticas de la antigua Mesopotamia . Una tablilla de arcilla sumeria encontrada en Shuruppak cerca de Bagdad y que data de alrededor del 2500 a .  C. describe el algoritmo de división más antiguo . ^[16] Durante la dinastía Hammurabi , alrededor  del 1800 a. C.  - alrededor  del 1600 a. C. , las tablillas de arcilla babilónicas describían algoritmos para calcular fórmulas. ^[22] Los algoritmos también se usaban en la astronomía babilónica . Las tablillas de arcilla babilónicas describen y emplean procedimientos algorítmicos para calcular el tiempo y el lugar de eventos astronómicos significativos. ^[23]

Los algoritmos para la aritmética también se encuentran en las matemáticas del antiguo Egipto , que datan del Papiro matemático Rhind alrededor del año  1550 a . C. ^[16] Los algoritmos se utilizaron más tarde 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 , ^{[24] [20] : Cap. 9.2} y el algoritmo euclidiano , que fue descrito por primera vez en los Elementos de Euclides ( c.  300 a. C. ). ^{[20] : Cap. 9.1} Los ejemplos de matemáticas indias antiguas incluyen los Shulba Sutras , la Escuela de Kerala y el Brāhmasphuṭasiddhānta . ^[17]

El primer algoritmo criptográfico para descifrar códigos cifrados fue desarrollado por Al-Kindi , un matemático árabe del siglo IX, en Un manuscrito sobre el descifrado de mensajes criptográficos . Dio la primera descripción del criptoanálisis por análisis de frecuencia , el algoritmo de descifrado de códigos más antiguo. ^[21]

Bolter atribuye la invención del reloj impulsado por pesas como "la invención clave [de Europa en la Edad Media ]", específicamente el mecanismo de escape de verticilos ^[25] que produce el tic-tac de un reloj mecánico. "La máquina automática precisa" ^[26] condujo inmediatamente a los " autómatas mecánicos " en el siglo XIII y a las "máquinas computacionales" (los motores diferenciales y analíticos de Charles Babbage y Ada Lovelace a mediados del siglo XIX). ^[27] Lovelace diseñó el primer algoritmo destinado a ser procesado en una computadora, el motor analítico de Babbage, que es el primer dispositivo considerado una verdadera computadora Turing-completa en lugar de solo una calculadora . Aunque una implementación completa del segundo dispositivo de Babbage no se realizó hasta décadas después de su muerte, a Lovelace se la ha llamado "la primera programadora de la historia".

Bell y Newell (1971) escriben que el telar Jacquard , precursor de las tarjetas Hollerith (tarjetas perforadas), y las "tecnologías de conmutación telefónica" llevaron al desarrollo de las primeras computadoras. ^[28] A mediados del siglo XIX, el telégrafo , precursor del teléfono, estaba en uso en todo el mundo. A fines del siglo XIX, la cinta de teletipo ( c.  1870 ) estaba en uso, al igual que las tarjetas Hollerith (c. 1890). Luego vino el teleimpresor ( c.  1910 ) con su uso de papel perforado de código Baudot en cinta.

En 1835 se inventaron las redes de conmutación telefónica de relés electromecánicos , que condujeron a la invención del sumador digital por parte de George Stibitz en 1937. Mientras trabajaba en los Laboratorios Bell, observó el uso "engorroso" de las calculadoras mecánicas con engranajes. "Una tarde de 1937 se fue a casa con la intención de probar su idea... Cuando terminó de hacer experimentos, Stibitz había construido un sumador binario". ^{[29] [30]}

En 1928, se inició una formalización parcial del concepto moderno de algoritmos con los intentos de resolver el Entscheidungsproblem (problema de decisión) planteado por David Hilbert . Las formalizaciones posteriores se enmarcaron como intentos de definir la " calculabilidad efectiva " ^[31] o el "método efectivo". ^[32] Esas formalizaciones incluyeron las funciones recursivas de Gödel - Herbrand - 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.

Los algoritmos se pueden expresar en muchos tipos de notación, incluidos lenguajes naturales , pseudocódigo , diagramas de flujo , diagramas de drakon , lenguajes de programación o tablas de control (procesadas por intérpretes ). Las expresiones de algoritmos en lenguaje natural tienden a ser verbosas y ambiguas y rara vez se utilizan para algoritmos complejos o técnicos. El pseudocódigo, los diagramas de flujo, los diagramas de drakon y las tablas de control son expresiones estructuradas de algoritmos que evitan las ambigüedades comunes del lenguaje natural. Los lenguajes de programación se utilizan principalmente para expresar algoritmos en una forma ejecutable por computadora, pero también se utilizan para definir o documentar algoritmos.

Existen muchas representaciones posibles y los programas de máquina de Turing pueden expresarse como una secuencia de tablas de máquina (consulte máquina de estados finitos , tabla de transición de estados y tabla de control para obtener más información), como diagramas de flujo y diagramas de drakon (consulte diagrama de estados para obtener más información), como una forma de código de máquina rudimentario o código ensamblador llamado "conjuntos de cuádruples", y más. Las representaciones de algoritmos también pueden clasificarse en tres niveles aceptados de descripción de la máquina de Turing: descripción de alto nivel, descripción de implementación y descripción formal. ^[33] Una descripción de alto nivel describe las cualidades del algoritmo en sí, ignorando cómo se implementa en la máquina de Turing. ^[33] Una descripción de implementación describe la manera general en que la máquina mueve su cabeza y almacena datos para llevar a cabo el algoritmo, pero no proporciona estados exactos. ^[33] Con más detalle, una descripción formal proporciona la tabla de estados exacta y la lista de transiciones de la máquina de Turing. ^[33]

El diagrama de flujo es una herramienta gráfica que permite describir y documentar un algoritmo (y un programa informático correspondiente). Tiene cuatro símbolos principales: flechas que muestran el flujo del programa, rectángulos (SECUENCIA, IR A), rombos (SI-ENTONCES-SINO) y puntos (OR-empate). Las subestructuras pueden "anidarse" en rectángulos, pero sólo si hay una única salida desde la superestructura.

A menudo es importante saber cuánto tiempo, almacenamiento u otro costo puede requerir un algoritmo. Se han desarrollado métodos para el análisis de algoritmos para obtener tales respuestas cuantitativas (estimaciones); por ejemplo, un algoritmo que suma los elementos de una lista de n números tendría un requisito de tiempo de ⁠ ⁠${\displaystyle O(n)}$ , utilizando la notación O mayúscula . El algoritmo solo necesita recordar dos valores: la suma de todos los elementos hasta el momento y su posición actual en la lista de entrada. Si no se cuenta el espacio requerido para almacenar los números de entrada, tiene un requisito de espacio de ⁠ ⁠${\displaystyle O(1)}$ , de lo contrario se requiere ⁠ ⁠ .${\displaystyle O(n)}$

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 ⁠ ⁠${\displaystyle O(\log n)}$ ) supera a una búsqueda secuencial (costo ⁠ ⁠${\displaystyle O(n)}$ ) cuando se utiliza para búsquedas en tablas o matrices ordenadas.

El análisis y estudio de algoritmos es una disciplina de la informática . Los algoritmos suelen estudiarse de forma abstracta, sin hacer referencia a ningún lenguaje de programación o implementación específicos. El análisis de algoritmos se parece a otras disciplinas matemáticas, ya que se centra en las propiedades del algoritmo, no en la implementación. El pseudocódigo es típico para el análisis, ya que es una representación simple y general. La mayoría de los algoritmos se implementan en plataformas de hardware/software particulares y su eficiencia algorítmica se prueba utilizando código real. La eficiencia de un algoritmo particular puede ser insignificante para muchos problemas "puntuales", pero puede ser crítica para algoritmos diseñados para un uso científico interactivo rápido, comercial o de larga duración. Escalar de n pequeño a n grande con frecuencia expone algoritmos ineficientes que de otro modo serían benignos.

Las pruebas empíricas son útiles para descubrir interacciones inesperadas que afectan el rendimiento. Se pueden utilizar puntos de referencia para comparar posibles mejoras de un algoritmo antes y después de la optimización del programa. Sin embargo, las pruebas empíricas no pueden reemplazar el análisis formal y no es trivial que tengan un rendimiento justo. ^[34]

Para ilustrar las posibles mejoras posibles incluso en algoritmos bien establecidos, una innovación significativa reciente, relacionada con los algoritmos FFT (utilizados ampliamente en el campo del procesamiento de imágenes), puede reducir el tiempo de procesamiento hasta 1000 veces para aplicaciones como las imágenes médicas. ^[35] En general, las mejoras de velocidad dependen de propiedades especiales del problema, que son muy comunes en aplicaciones prácticas. ^[36] Las aceleraciones de esta magnitud permiten que los dispositivos informáticos que hacen un uso extensivo del procesamiento de imágenes (como cámaras digitales y equipos médicos) consuman menos energía.

El diseño de algoritmos es un método o proceso matemático para la resolución de problemas y la ingeniería de algoritmos. El diseño de algoritmos forma parte de muchas teorías de solución, como la de divide y vencerás o la programación dinámica dentro de la investigación de operaciones . Las técnicas para diseñar e implementar diseños de algoritmos también se denominan patrones de diseño de algoritmos, ^[37] con ejemplos que incluyen el patrón de método de plantilla y el patrón decorador. Uno de los aspectos más importantes del diseño de algoritmos es la eficiencia de los recursos (tiempo de ejecución, uso de memoria); la notación O mayúscula se utiliza para describir, por ejemplo, el crecimiento del tiempo de ejecución de un algoritmo a medida que aumenta el tamaño de su entrada. ^[38]

Según la tesis de Church-Turing , cualquier algoritmo puede ser calculado por cualquier modelo completo de Turing . La completitud de Turing solo requiere cuatro tipos de instrucciones: GOTO condicional, GOTO incondicional, asignación, HALT. Sin embargo, Kemeny y Kurtz observan que, si bien el uso "indisciplinado" de GOTO incondicionales y GOTO IF-THEN condicionales puede resultar en " código espagueti ", un programador puede escribir programas estructurados utilizando solo estas instrucciones; por otro lado, "también es posible, y no demasiado difícil, escribir programas mal estructurados en un lenguaje estructurado". ^[39] Tausworthe aumenta las tres estructuras canónicas de Böhm-Jacopini : ^[40] SEQUENCE, IF-THEN-ELSE y WHILE-DO, con dos más: DO-WHILE y CASE. ^[41] Un beneficio adicional de un programa estructurado es que se presta a pruebas de corrección mediante inducción matemática . ^[42]

Por sí mismos, los algoritmos no suelen ser patentables. En los Estados Unidos, una reivindicación que consiste únicamente en manipulaciones simples de conceptos abstractos, números o señales no constituye "procesos" (USPTO 2006), por lo que los algoritmos no son patentables (como en Gottschalk v. Benson ). Sin embargo, las aplicaciones prácticas de los algoritmos a veces sí lo son. Por ejemplo, en Diamond v. Diehr , se consideró patentable la aplicación de un algoritmo de retroalimentación simple para ayudar en el curado de caucho sintético . El patentamiento de software es controvertido, ^[43] y existen patentes criticadas que involucran algoritmos, especialmente algoritmos de compresión de datos , como la patente LZW de Unisys . Además, algunos algoritmos criptográficos tienen restricciones de exportación (véase exportación de criptografía ).

Recursión

Un algoritmo recursivo se invoca a sí mismo repetidamente hasta que cumple una condición de terminación y es un método común de programación funcional . Los algoritmos iterativos utilizan repeticiones como bucles o estructuras de datos como pilas para resolver problemas. Los problemas pueden ser adecuados para una implementación u otra. Las Torres de Hanoi es un rompecabezas que se resuelve comúnmente mediante una implementación recursiva. Cada versión recursiva tiene una versión iterativa equivalente (pero posiblemente más o menos compleja), y viceversa.

Serie, paralelo o distribuido

Los algoritmos se suelen analizar asumiendo que las computadoras ejecutan una instrucción de un algoritmo a la vez en computadoras seriales. Los algoritmos seriales están diseñados para estos entornos, a diferencia de los algoritmos paralelos o distribuidos . Los algoritmos paralelos aprovechan las arquitecturas informáticas en las que varios procesadores pueden trabajar en un problema al mismo tiempo. Los algoritmos distribuidos utilizan varias máquinas conectadas a través de una red informática. Los algoritmos paralelos y distribuidos dividen el problema en subproblemas y recopilan los resultados. El consumo de recursos en estos algoritmos no solo son los ciclos de procesador en cada procesador, sino también la sobrecarga de comunicación entre los procesadores. Algunos algoritmos de ordenamiento se pueden paralelizar de manera eficiente, pero su sobrecarga de comunicación es costosa. Los algoritmos iterativos generalmente son paralelizables, pero algunos problemas no tienen algoritmos paralelos y se denominan problemas inherentemente seriales.

Determinista o no determinista

Los algoritmos deterministas resuelven el problema con una decisión exacta en cada paso, mientras que los algoritmos no deterministas resuelven los problemas mediante conjeturas. Las conjeturas suelen hacerse más precisas mediante el uso de heurísticas .

Exacto o aproximado

Mientras que muchos algoritmos llegan a una solución exacta, los algoritmos de aproximación buscan una aproximación que esté cerca de la solución verdadera. Dichos algoritmos tienen valor práctico para muchos problemas difíciles. Por ejemplo, el problema de la mochila , donde hay un conjunto de elementos y el objetivo es llenar la mochila para obtener el máximo valor total. Cada elemento tiene cierto peso y cierto valor. El peso total que se puede transportar no es más que un número fijo X. Por lo tanto, la solución debe considerar los pesos de los elementos, así como su valor. ^[44]

Algoritmo cuántico

Los algoritmos cuánticos se ejecutan sobre un modelo realista de computación cuántica . El término se utiliza generalmente para aquellos algoritmos que parecen inherentemente cuánticos o utilizan alguna característica esencial de la computación cuántica, como la superposición cuántica o el entrelazamiento cuántico .

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

Búsqueda exhaustiva o por fuerza bruta

La fuerza bruta es un método de resolución de problemas que consiste en probar sistemáticamente todas las opciones posibles hasta encontrar la solución óptima. Este enfoque puede requerir mucho tiempo, ya que se prueban todas las combinaciones posibles de variables. Se suele utilizar cuando no hay otros métodos disponibles o son demasiado complejos. La fuerza bruta puede resolver una variedad de problemas, como encontrar el camino más corto entre dos puntos y descifrar contraseñas.

Divide y vencerás

Un algoritmo de divide y vencerás reduce repetidamente un problema a una o más instancias más pequeñas de sí mismo (generalmente de forma recursiva ) hasta que las instancias son lo suficientemente pequeñas como para resolverse fácilmente. La ordenación por fusión es un ejemplo de divide y vencerás, donde una lista desordenada se puede dividir en segmentos que contienen un elemento y la ordenación de la lista completa se puede obtener fusionando los segmentos. Una variante más simple de divide y vencerás se llama algoritmo de disminución y vencerás , que resuelve una instancia más pequeña de sí mismo y usa la solución para resolver el problema más grande. Divide y vencerás divide el problema en múltiples subproblemas y, por lo tanto, la etapa de conquista es más compleja que los algoritmos de disminución y conquista. ^{[ cita requerida ]} Un ejemplo de un algoritmo de disminución y conquista es el algoritmo de búsqueda binaria .

Búsqueda y enumeración

Muchos problemas (como jugar al ajedrez ) se pueden modelar como problemas en grafos . Un algoritmo de exploración de grafos especifica reglas para moverse por un grafo y es útil para este tipo de problemas. Esta categoría también incluye algoritmos de búsqueda , enumeración de ramificaciones y límites y retroceso .

Algoritmo aleatorio

Estos algoritmos toman algunas decisiones de forma aleatoria (o pseudoaleatoria). Encuentran soluciones aproximadas cuando encontrar soluciones exactas puede resultar poco práctico (véase el método heurístico a continuación). Para algunos problemas, las aproximaciones más rápidas deben implicar cierta aleatoriedad . ^[45] Si los algoritmos aleatorios con complejidad temporal polinómica pueden ser el algoritmo más rápido para algunos problemas es una pregunta abierta conocida como el problema P versus NP . Existen dos grandes clases de tales algoritmos:

1. Los algoritmos de Monte Carlo devuelven una respuesta correcta con alta probabilidad. Por ejemplo, RP es la subclase de estos que se ejecutan 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 asintóticamente óptimos (con suerte) . El objetivo es encontrar un algoritmo reductor cuya complejidad no esté dominada por los algoritmos reducidos resultantes. Por ejemplo, un algoritmo de selección encuentra la mediana de una lista desordenada ordenando primero la lista (la parte costosa) y luego extrayendo el elemento del medio en la lista ordenada (la parte barata). Esta técnica también se conoce como transformar y conquistar .

Seguimiento hacia atrás

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.

Para los problemas de optimización existe una clasificación más específica de algoritmos; un algoritmo para tales problemas puede caer en una o más de las categorías generales descritas anteriormente, así como en una de las siguientes:

Programación lineal

Al buscar soluciones óptimas para una función lineal limitada por restricciones de igualdad y desigualdad lineales, las restricciones se pueden usar directamente para producir soluciones óptimas. Hay algoritmos que pueden resolver cualquier problema en esta categoría, como el popular algoritmo simplex . ^[46] Los problemas que se pueden resolver con programación lineal incluyen el problema de flujo máximo para grafos dirigidos. Si un problema también requiere que cualquiera de las incógnitas sean números enteros , entonces se clasifica en programación entera . Un algoritmo de programación lineal puede resolver dicho problema si se puede demostrar que todas las restricciones para valores enteros son superficiales, es decir, las soluciones satisfacen estas restricciones de todos modos. En el caso general, se utiliza un algoritmo especializado o un algoritmo que encuentra soluciones aproximadas, dependiendo de la dificultad del problema.

Programación dinámica

Cuando un problema muestra subestructuras óptimas (es decir, la solución óptima se puede construir a partir de soluciones óptimas a subproblemas) y subproblemas superpuestos (es decir, los mismos subproblemas se utilizan para resolver muchas instancias de problemas diferentes), un enfoque más rápido llamado programación dinámica evita tener que volver a calcular las soluciones. Por ejemplo, el algoritmo Floyd-Warshall , la ruta más corta entre un vértice de inicio y un vértice de destino en un gráfico ponderado se puede encontrar utilizando la ruta más corta al destino desde todos los vértices adyacentes. La programación dinámica y la memorización van de la mano. A diferencia de dividir y vencer, los subproblemas de programación dinámica a menudo se superponen. La diferencia entre la programación dinámica y la recursión simple es el almacenamiento en caché o la memorización de las llamadas recursivas. Cuando los subproblemas son independientes y no se repiten, la memorización no ayuda; por lo tanto, la programación dinámica no es aplicable a todos los problemas complejos. El uso de la memorización en la programación dinámica reduce la complejidad de muchos problemas, desde exponenciales hasta polinómicos.

El método codicioso

Los algoritmos voraces , de manera similar a la programación dinámica, funcionan examinando subestructuras, en este caso no del problema sino de una solución dada. Dichos algoritmos comienzan con alguna solución y la mejoran haciendo pequeñas modificaciones. Para algunos problemas siempre encuentran la solución óptima, pero para otros pueden detenerse en óptimos locales . El uso más popular de los algoritmos voraces es encontrar árboles de expansión mínimos de grafos sin ciclos negativos. Huffman Tree , Kruskal , Prim y Sollin son algoritmos voraces que pueden resolver este problema de optimización.

El método heurístico

En los problemas de optimización , los algoritmos heurísticos encuentran soluciones cercanas a la solución óptima cuando encontrar la solución óptima es impráctico. Estos algoritmos se acercan cada vez más a la solución óptima a medida que avanzan. En principio, si se ejecutan durante una cantidad infinita de tiempo, encontrarán la solución óptima. Idealmente, pueden encontrar una solución muy cercana a la solución óptima en un tiempo relativamente corto. Estos algoritmos incluyen búsqueda local , búsqueda tabú , recocido simulado y algoritmos genéticos . Algunos, como el recocido simulado, son algoritmos no deterministas, mientras que otros, como la búsqueda tabú, son deterministas. Cuando se conoce un límite en el error de la solución no óptima, el algoritmo se clasifica además como un algoritmo de aproximación .

Uno de los algoritmos más simples busca el número más grande en una lista de números ordenados aleatoriamente. Para encontrar la solución es necesario observar cada número de la lista. De esto se desprende un algoritmo simple, que puede describirse en términos sencillos como:

Descripción de alto nivel:

1. Si un conjunto de números está vacío, entonces no existe un número más alto.
2. Supongamos que el primer número del conjunto es el más grande.
3. Para cada número restante en el conjunto: si este número es mayor que el más grande actual, se convierte en el nuevo más grande.
4. Cuando no quedan números sin marcar en el conjunto, considere que el número más grande actual es el más grande del conjunto.

Descripción (cuasi)formal: Escrita en prosa pero mucho más cercana al lenguaje de alto nivel de un programa de computadora, la siguiente es la codificación más formal del algoritmo en pseudocódigo o código pidgin :

Algoritmo Número más grandeEntrada: Una lista de números L .Salida: El número más grande de la lista L.

si  L.size = 0 devuelve nulo más grande ← L [0] para cada  elemento  en  L , hazlo  si  elemento > más grande , entonces  más grande ← elemento devuelve  más grande

• 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

Busque algoritmo en Wikcionario, el diccionario libre.

Wikilibros tiene un libro sobre el tema: Algoritmos

En Wikiversidad , puedes aprender más y enseñar a otros sobre Algoritmos en el Departamento de Algoritmos.

Wikimedia Commons tiene medios relacionados con Algoritmos .

• "Algoritmo". Enciclopedia de Matemáticas . EMS Press . 2001 [1994].
• Weisstein, Eric W. "Algoritmo". MathWorld .
• Diccionario de algoritmos y estructuras de datos – Instituto Nacional de Estándares y Tecnología

Repositorios de algoritmos

• El repositorio de algoritmos de Stony Brook – Universidad Estatal de Nueva York en Stony Brook
• Algoritmos recopilados de la ACM – Associations for Computing Machinery
• The Stanford GraphBase Archivado el 6 de diciembre de 2015 en Wayback Machine – Universidad de Stanford