Algoritmos empíricos - Empirical algorithmics

En informática , la algorítmica empírica (o algorítmica experimental ) es la práctica de utilizar métodos empíricos para estudiar el comportamiento de los algoritmos . La práctica combina el desarrollo de algoritmos y la experimentación: los algoritmos no solo se diseñan, sino que también se implementan y prueban en una variedad de situaciones. En este proceso, se analiza un diseño inicial de un algoritmo para que el algoritmo se pueda desarrollar de manera escalonada.

Visión general

Los métodos de la algorítmica empírica complementan los métodos teóricos para el análisis de algoritmos . A través de la aplicación de principios de métodos empíricos, particularmente de las estadísticas , a menudo es posible obtener información sobre el comportamiento de algoritmos, como los algoritmos heurísticos de alto rendimiento para problemas combinatorios difíciles que son (actualmente) inaccesibles para el análisis teórico. También se pueden utilizar métodos empíricos para lograr mejoras sustanciales en la eficiencia algorítmica .

La científica informática estadounidense Catherine McGeoch identifica dos ramas principales de la algorítmica empírica: la primera (conocida como análisis empírico ) se ocupa del análisis y caracterización del comportamiento de los algoritmos , y la segunda (conocida como diseño de algoritmos o ingeniería de algoritmos ) se centra en métodos empíricos para mejorar el rendimiento de los algoritmos . El primero a menudo se basa en técnicas y herramientas de estadísticas , mientras que el segundo se basa en enfoques de estadística , aprendizaje automático y optimización . Las herramientas de análisis dinámico , normalmente los perfiladores de rendimiento , se utilizan comúnmente cuando se aplican métodos empíricos para la selección y el refinamiento de algoritmos de varios tipos para su uso en diversos contextos.

La investigación en algoritmos empíricos se publica en varias revistas, incluida la ACM Journal on Experimental Algorithmics (JEA) y la Journal of Artificial Intelligence Research (JAIR). Además de Catherine McGeoch, los investigadores de renombre en algoritmos empíricos incluyen a Bernard Moret , Giuseppe F. Italiano , Holger H. Hoos , David S. Johnson y Roberto Battiti .

Perfiles de rendimiento en el diseño de algoritmos complejos

En ausencia de algoritmos empíricos, analizar la complejidad de un algoritmo puede implicar varios métodos teóricos aplicables a diversas situaciones en las que se puede utilizar el algoritmo. Las consideraciones de memoria y caché son a menudo factores importantes que deben tenerse en cuenta en la elección teórica de un algoritmo complejo, o el enfoque para su optimización, para un propósito determinado. La generación de perfiles de rendimiento es una técnica de análisis de programas dinámicos que se utiliza normalmente para encontrar y analizar cuellos de botella en el código de una aplicación completa o para analizar una aplicación completa para identificar el código de bajo rendimiento. Un generador de perfiles puede revelar el código más relevante para los problemas de rendimiento de una aplicación.

Un generador de perfiles puede ayudar a determinar cuándo elegir un algoritmo sobre otro en una situación particular. Cuando se perfila un algoritmo individual, como ocurre con el análisis de complejidad, las consideraciones de memoria y caché suelen ser más importantes que los recuentos de instrucciones o los ciclos de reloj; sin embargo, los hallazgos del generador de perfiles se pueden considerar a la luz de cómo el algoritmo accede a los datos en lugar del número de instrucciones que utiliza.

La creación de perfiles puede proporcionar una visión intuitiva del comportamiento de un algoritmo al revelar los resultados del rendimiento como una representación visual. La elaboración de perfiles de rendimiento se ha aplicado, por ejemplo, durante el desarrollo de algoritmos para hacer coincidir comodines . Algoritmos temprana para los comodines a juego, tales como Rich Salz ' wildmat algoritmo, por lo general se basó en la recursividad , una técnica criticada por motivos de rendimiento. El algoritmo de comodines de coincidencia de Krauss se desarrolló en base a un intento de formular una alternativa no recursiva utilizando casos de prueba seguidos de optimizaciones sugeridas a través del perfil de rendimiento, lo que resultó en una nueva estrategia algorítmica concebida a la luz del perfil junto con otras consideraciones. Los perfiladores que recopilan datos a nivel de bloques básicos o que dependen de la asistencia de hardware brindan resultados que pueden ser lo suficientemente precisos como para ayudar a los desarrolladores de software a optimizar algoritmos para una computadora o situación en particular. La elaboración de perfiles de rendimiento puede ayudar a los desarrolladores a comprender las características de los algoritmos complejos aplicados en situaciones complejas, como los algoritmos coevolutivos aplicados a problemas arbitrarios basados ​​en pruebas, y puede ayudar a generar mejoras en el diseño.

Ver también

Referencias