El algoritmo son las reglas y técnicas de diseño y producción que intervienen en la definición y diseño de algoritmos , es decir, proceso sistemático de resolución de un problema para describir con precisión los pasos para resolver un problema algorítmico .
La palabra "algoritmo" viene del nombre del matemático Al-Khwarizmi (latinizado a las Edad Media en Algoritmi ), que en el IX ° siglo escribió la primera obra sistemática proporcionar soluciones a las ecuaciones lineales y cuadráticas . La h silenciosa, no justificada por la etimología, proviene de una deformación en comparación con el griego ἀριθμός (arithmós). "Algoritmo" dio "algorítmico". El sinónimo "algoritmo", una antigua palabra utilizada, por ejemplo, por Wronski en 1811, todavía se utiliza a veces.
Los primeros algoritmos que se han encontrado descripciones se remontan a los babilonios , el III ° milenio antes de Cristo. AD . Describen métodos de cálculo y soluciones de ecuaciones utilizando ejemplos.
Un algoritmo famoso es el que se encuentra en el Libro 7 de los Elementos de Euclides , y se llama algoritmo de Euclides . Encuentra el máximo común divisor, o MCD , de dos números. Un punto particularmente notable es que contiene explícitamente una iteración y que las proposiciones 1 y 2 demuestran su corrección .
Fue Arquímedes quien propuso por primera vez un algoritmo para el cálculo de π .
El primero en tener algoritmos sistematizados es el matemático persa Al-Khwârizmî , activo entre 813 y 833. En su obra Abrégé du computation by restore and comparation , estudia todas las ecuaciones cuadráticas y da su resolución mediante algoritmos generales. Utiliza métodos similares a los de los babilonios , pero difiere en sus explicaciones sistemáticas donde los babilonios solo dieron ejemplos.
El andaluz erudito Averroès ( 1,126 - 1198 ) evoca un método de razonamiento donde la tesis se refina paso a paso, de manera iterativa, hasta una cierta convergencia y esto de acuerdo con el progreso de un algoritmo. Al mismo tiempo, en el XII ° siglo , el monje Adelardo de Bath introdujo el término América para Algorismus , con el nombre de Al Khwarizmi. Esta palabra da un algoritmo en francés en 1554 .
En el XVII ° siglo , alguna alusión podía vislumbrar el método algorítmico a René Descartes en el enfoque general propuesto por el Discurso del método ( 1637 ), sobre todo cuando, en su segunda parte, el matemático francés propuso a "dividir cada dificultad que se lo examinar, en tantas partes como sea posible, y según sea necesario para resolverlos mejor. " Sin evocar explícitamente el bucle de iteración conceptos o dicotomía , el enfoque de Descartes predispone lógica para acomodar el concepto de programa , palabra nace en Francia en 1677 .
En 1843, la matemática y pionera de la informática Ada Lovelace , hija de Lord Byron y asistente de Charles Babbage llevó a cabo la primera implementación de un algoritmo en forma de programa (cálculo de números de Bernoulli ).
El décimo problema de Hilbert, que forma parte de la lista de 23 problemas planteados por David Hilbert en 1900 en París, es claramente un problema algorítmico. En este caso, la respuesta es que no existe un algoritmo que responda al problema planteado.
La algorítmica XX XX y XXI XX siglos para la base matemática del formalismo, por ejemplo el de las máquinas de Turing , que permiten definir con precisión qué se entiende por "pasos" por "específica" y "ambigua" y que proporcionan un marco científico para el estudio de la propiedades de los algoritmos. Sin embargo, según el formalismo elegido se obtienen diferentes enfoques algorítmicos para resolver el mismo problema. Por ejemplo , los algoritmos recursivos , los algorítmicos paralelos o la computación cuántica dan lugar a presentaciones de algoritmos que son diferentes de los de los algoritmos iterativos.
Algorithmics ha desarrollado principalmente en la segunda mitad del XX ° siglo, como soporte conceptual de la programación informática en el desarrollo de durante este período. Donald Knuth , autor del tratado The Art of Computer Programming, que describe una gran cantidad de algoritmos, ayudó, junto con otros, a sentar las bases matemáticas de su análisis.
El sustantivo algorítmico designa todos los métodos utilizados para crear algoritmos. El término también se usa como adjetivo.
Un algoritmo establece una solución a un problema en forma de una cadena de operaciones a realizar .
Los informáticos utilizan con frecuencia el anglicismo de implementación para referirse a la implementación del algoritmo en un lenguaje de programación . Esta implementación realiza la transcripción de las operaciones constitutivas del algoritmo y especifica la forma en que se invocan estas operaciones. Esta escritura en lenguaje informático también se designa con frecuencia con el término " codificación ". Hablamos de " código fuente " para designar el texto, que constituye el programa, que realiza el algoritmo. El código es más o menos detallado según el nivel de abstracción del lenguaje utilizado, al igual que una receta de cocina debe ser más o menos detallada según la experiencia del cocinero.
Se han desarrollado muchas herramientas formales o teóricas para describir algoritmos, estudiarlos, expresar sus cualidades y poder compararlos:
Los conceptos implementados en algorítmica, por ejemplo según el enfoque de N. Wirth para los lenguajes más extendidos (Pascal, C, etc. ), son pocos en número. Pertenecen a dos clases:
Esta división es a veces difícil de percibir para ciertos lenguajes ( Lisp , Prolog …) más basada en la noción de recursividad donde ciertas estructuras de control están implícitas y, por tanto, parecen desaparecer.
Estas tres nociones "corrección", "completitud", "terminación" están relacionadas y suponen que se escribe un algoritmo para resolver un problema.
La terminación es la garantía de que el algoritmo finaliza en un tiempo finito. Las pruebas de terminación generalmente involucran una función entera positiva estrictamente decreciente en cada "paso" del algoritmo.
Dada la garantía de que un algoritmo terminará, la prueba de corrección debe proporcionar la seguridad de que si el algoritmo termina dando un resultado, entonces este resultado es una solución al problema planteado. Las pruebas de corrección generalmente involucran una especificación lógica que debe verificarse mediante soluciones al problema. Por tanto, la prueba de corrección consiste en demostrar que los resultados del algoritmo satisfacen esta especificación.
La prueba de integridad garantiza que, para un espacio de problemas dado, el algoritmo, si termina, dará el conjunto de soluciones del espacio de problemas. Las pruebas de integridad requieren identificar el espacio del problema y el espacio de la solución para luego mostrar que el algoritmo efectivamente produce el segundo a partir del primero.
Las principales nociones matemáticas en el cálculo del costo de un algoritmo preciso son las nociones de dominación (denotado O (f (n)) , "gran o"), donde f es una función matemática de n , variable que designa la cantidad de información (en bits , número de registros, etc. ) utilizados en el algoritmo. En algorítmica a menudo encontramos complejidades del tipo:
Clasificación | Tipo de complejidad |
---|---|
complejidad constante (independiente del tamaño de los datos) | |
complejidad logarítmica | |
complejidad lineal | |
complejidad cuasi-lineal | |
complejidad cuadrática | |
complejidad cúbica | |
complejidad polinomial | |
complejidad cuasi-polinomial | |
complejidad exponencial | |
complejidad del factor |
Sin entrar en detalles matemáticos, calcular la eficiencia de un algoritmo (su complejidad algorítmica ) consiste en encontrar dos cantidades importantes. La primera cantidad es la evolución del número de instrucciones básicas según la cantidad de datos a procesar (por ejemplo, para un algoritmo de clasificación , este es el número de datos a clasificar), que se preferirá en el tiempo de ejecución medido. en segundos (porque este último depende de la máquina en la que se ejecuta el algoritmo). La segunda cantidad estimada es la cantidad de memoria necesaria para realizar los cálculos. Basar el cálculo de la complejidad de un algoritmo en el tiempo o la cantidad efectiva de memoria que una computadora en particular necesita para realizar dicho algoritmo no tiene en cuenta la estructura interna del algoritmo, ni la peculiaridad del algoritmo. Computadora: según su carga de trabajo, la velocidad de su procesador, la velocidad de acceso a los datos, la ejecución del algoritmo (que puede involucrar al azar) o su organización de la memoria, el tiempo de ejecución y la cantidad de memoria no serán los mismos.
A menudo, el rendimiento se examina "en el peor de los casos", es decir, en configuraciones como el tiempo de ejecución o el espacio de memoria es mayor. También hay otro aspecto de la evaluación de la eficiencia de un algoritmo: el rendimiento "medio". Esto supone tener un modelo de distribución estadística de los datos del algoritmo, mientras que la implementación de las técnicas de análisis implica métodos bastante finos de combinatoria y evaluación asintótica , utilizando en particular las series generadoras y métodos avanzados de análisis complejo . Todos estos métodos se agrupan bajo el nombre de combinatoria analítica .
Otras evaluaciones de la complejidad que generalmente van más allá de los valores propuestos anteriormente y que clasifican los problemas algorítmicos (en lugar de los algoritmos) en clases de complejidad se pueden encontrar en el artículo sobre la teoría de la complejidad de los algoritmos .
Algunas indicaciones sobre la eficiencia de los algoritmos y sus sesgosLa eficiencia algorítmica a menudo solo se conoce asintóticamente, es decir, para valores grandes del parámetro n . Cuando este parámetro es lo suficientemente pequeño, un algoritmo de mayor complejidad asintótica puede ser en la práctica más eficiente. Por lo tanto, para ordenar una matriz de 30 filas (este es un parámetro pequeño), no es necesario utilizar un algoritmo avanzado como la ordenación rápida (uno de los algoritmos de ordenación asintóticamente más eficientes en promedio): l El algoritmo de ordenación más fácil de escribir será ser lo suficientemente eficiente.
Entre dos algoritmos informáticos de idéntica complejidad, utilizaremos el que tenga menos ocupación de memoria. El análisis de la complejidad algorítmica también se puede utilizar para evaluar la ocupación de memoria de un algoritmo. Finalmente, la elección de un algoritmo en lugar de otro debe hacerse de acuerdo con los datos que se espera que proporcionen como entrada. Así, la ordenación rápida , cuando elegimos el primer elemento como pivote, se comporta desastrosamente si la aplicamos a una lista de valores ya ordenada. Por lo tanto, no es prudente usarlo si se espera que el programa reciba como entrada listas que ya están casi ordenadas, o tendrá que elegir el pivote al azar.
Otros parámetros a tener en cuenta incluyen:
El algorítmico ha desarrollado algunas estrategias para resolver los problemas:
Para algunos problemas, los algoritmos son demasiado complejos para obtener un resultado en un tiempo razonable, incluso si se pudiera utilizar una potencia de cálculo fenomenal. Por lo tanto, nos vemos llevados a buscar la solución de manera no sistemática ( algoritmo de Las Vegas ) o a quedarnos satisfechos con una solución lo más cercana posible a una solución óptima mediante pruebas sucesivas ( algoritmo de Monte-Carlo ). Dado que no se pueden probar todas las combinaciones, se deben tomar algunas decisiones estratégicas. Estas elecciones, generalmente muy dependientes del problema tratado, constituyen lo que se llama una heurística . Por tanto, el objetivo de una heurística no es probar todas las combinaciones posibles, sino encontrar una solución en un tiempo razonable y por otro medio, por ejemplo, realizando sorteos aleatorios. La solución puede ser exacta (Las Vegas) o aproximada (Montecarlo). Los algoritmos de Atlantic City , por otro lado, probablemente dan una respuesta probablemente correcta (digamos, con una probabilidad entre cien millones de equivocarse) a la pregunta formulada.
Así es como los programas de ajedrez o go game (por nombrar solo algunos) utilizan con mucha frecuencia heurísticas que modelan la experiencia de un jugador. Algunos programas antivirus también se basan en la heurística para reconocer virus informáticos que no figuran en su base de datos, basándose en similitudes con virus conocidos; este es un ejemplo de un algoritmo de Atlantic City. Asimismo, el problema SAT que es el arquetipo del problema NP-completo y por lo tanto muy difícil se resuelve de manera práctica y eficiente mediante el desarrollo de heurísticas .
Hay una serie de algoritmos clásicos que se utilizan para resolver problemas o más simplemente para ilustrar métodos de programación. Consulte los siguientes artículos para obtener más detalles (consulte también la lista de algoritmos ):