Algoritmia empírica

En informática , la algoritmia empírica (o algoritmia experimental ) es la práctica de utilizar métodos empíricos para estudiar el comportamiento de los algoritmos . Esta práctica combina el desarrollo de algoritmos con la experimentación: los algoritmos no solo se diseñan, sino que también se implementan y se prueban en diversas situaciones. En este proceso, se analiza un diseño inicial de un algoritmo para que este pueda desarrollarse de forma gradual. ^{[ 1 ]}

Los métodos de la algoritmia empírica complementan los métodos teóricos para el análisis de algoritmos . ^{[ 2 ]} Mediante la aplicación rigurosa de métodos empíricos, en particular de la estadística , 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 (actualmente) son inaccesibles al análisis teórico. ^{[ 3 ]} Los métodos empíricos también pueden utilizarse para lograr mejoras sustanciales en la eficiencia algorítmica . ^{[ 4 ]}

La científica informática estadounidense Catherine McGeoch identifica dos ramas principales de la algoritmia empírica: la primera (conocida como análisis empírico ) se ocupa del análisis y la 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 . ^{[ 5 ]} La primera suele basarse en técnicas y herramientas de la estadística , mientras que la segunda se basa en enfoques de la estadística , el aprendizaje automático y la optimización . Las herramientas de análisis dinámico , típicamente los analizadores de rendimiento , se utilizan comúnmente al aplicar métodos empíricos para la selección y el refinamiento de algoritmos de diversos tipos para su uso en diversos contextos. ^{[ 6 ] [ 7 ] [ 8 ]}

Las investigaciones en algoritmia empírica se publican en varias revistas, entre ellas el ACM Journal on Experimental Algorithmics (JEA) y el Journal of Artificial Intelligence Research (JAIR). Además de Catherine McGeoch, entre los investigadores más conocidos en algoritmia empírica se encuentran Bernard Moret , Giuseppe F. Italiano , Holger H. Hoos , David S. Johnson y Roberto Battiti . ^{[ 9 ]}

En ausencia de algoritmia empírica, el análisis de la complejidad de un algoritmo puede implicar varios métodos teóricos aplicables a diversas situaciones en las que el algoritmo puede utilizarse. ^{[ 10 ]} Las consideraciones de memoria y caché suelen ser factores importantes a tener en cuenta en la elección teórica de un algoritmo complejo, o el enfoque para su optimización, para un propósito determinado. ^{[ 11 ] [ 12 ]} El perfilado de rendimiento es una técnica de análisis dinámico de programas que se utiliza normalmente para encontrar y analizar cuellos de botella en el código de una aplicación completa ^{[ 13 ] [ 14 ] [ 15 ]} o para analizar una aplicación completa e identificar código con bajo rendimiento. ^{[ 16 ]} Un perfilador puede revelar el código más relevante para los problemas de rendimiento de una aplicación. ^{[ 17 ]}

Un perfilador puede ayudar a determinar cuándo elegir un algoritmo sobre otro en una situación particular. ^{[ 18 ]} Cuando se perfila un algoritmo individual, como en el análisis de complejidad, las consideraciones sobre memoria y caché suelen ser más importantes que el número de instrucciones o los ciclos de reloj; sin embargo, los resultados del perfilador pueden considerarse en función de cómo el algoritmo accede a los datos, en lugar del número de instrucciones que utiliza. ^{[ 19 ]}

El perfilado puede proporcionar una visión intuitiva del comportamiento de un algoritmo ^{[ 20 ]} al revelar los resultados del rendimiento como una representación visual. ^{[ 21 ]} El perfilado de rendimiento se ha aplicado, por ejemplo, durante el desarrollo de algoritmos para la coincidencia de comodines . Los primeros algoritmos para la coincidencia de comodines, como el algoritmo wildmat de Rich Salz , ^{[ 22 ]} normalmente se basaban en la recursión , una técnica criticada por motivos de rendimiento. ^{[ 23 ]} El algoritmo de coincidencia de comodines de Krauss se desarrolló a partir de un intento de formular una alternativa no recursiva utilizando casos de prueba ^{[ 24 ]} seguido de optimizaciones sugeridas a través del perfilado de rendimiento, ^{[ 25 ]} lo que dio como resultado una nueva estrategia algorítmica concebida a la luz del perfilado junto con otras consideraciones. ^{[ 26 ]} Los perfiladores que recopilan datos a nivel de bloques básicos ^{[ 27 ]} o que se basan en la asistencia del hardware ^{[ 28 ]} proporcionan resultados que pueden ser lo suficientemente precisos como para ayudar a los desarrolladores de software a optimizar algoritmos para una computadora o situación particular. ^{[ 29 ]} El análisis del 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 contribuir a mejorar el diseño. ^{[ 30 ]}

• Ingeniería de algoritmos
• Análisis de algoritmos
• Análisis de perfiles (programación informática)
• Ajuste del rendimiento
• Desarrollo de software