La ingeniería de algoritmos se centra en el diseño, análisis, implementación, optimización, elaboración de perfiles y evaluación experimental de algoritmos informáticos , cerrando la brecha entre la teoría algorítmica y las aplicaciones prácticas de los algoritmos en la ingeniería de software . [1] Es una metodología general para la investigación algorítmica. [2]
En 1995, un informe de un taller patrocinado por la NSF "con el propósito de evaluar los objetivos y direcciones actuales de la comunidad de la teoría de la computación (TOC)" identificó la lenta velocidad de adopción de ideas teóricas por parte de los profesionales como un problema importante y sugirió medidas para
Pero también se han descuidado enfoques algorítmicos prometedores debido a dificultades en el análisis matemático. [2]
El término "ingeniería de algoritmos" se utilizó por primera vez con especificidad en 1997, con el primer Taller sobre Ingeniería de Algoritmos (WAE97), organizado por Giuseppe F. Italiano . [4]
La ingeniería de algoritmos no pretende sustituir ni competir con la teoría de algoritmos, sino que intenta enriquecer, refinar y reforzar sus enfoques formales con algoritmia experimental (también llamada algoritmia empírica).
De esta manera, puede proporcionar nuevos conocimientos sobre la eficiencia y el rendimiento de los algoritmos en los casos en que
Algunos investigadores describen la metodología de la ingeniería de algoritmos como un ciclo que consiste en el diseño, análisis, implementación y evaluación experimental de algoritmos, a los que se suman otros aspectos como modelos de máquinas o datos de entrada realistas. Sostienen que equiparar la ingeniería de algoritmos con la algoritmia experimental es demasiado limitado, porque considerar el diseño y el análisis, la implementación y la experimentación como actividades separadas ignora el ciclo de retroalimentación crucial entre esos elementos de la ingeniería de algoritmos. [2]
Si bien las aplicaciones específicas quedan fuera de la metodología de la ingeniería de algoritmos, desempeñan un papel importante en la configuración de modelos realistas del problema y la máquina subyacente, y suministran entradas reales y otros parámetros de diseño para los experimentos. [2]
En comparación con la teoría de algoritmos, que generalmente se centra en el comportamiento asintótico de los algoritmos, los ingenieros de algoritmos deben tener en cuenta otros requisitos: simplicidad del algoritmo, posibilidad de implementación en lenguajes de programación en hardware real y posibilidad de reutilización del código. Además, los factores constantes de los algoritmos tienen un impacto tan considerable en las entradas del mundo real que, a veces, un algoritmo con un peor comportamiento asintótico funciona mejor en la práctica debido a factores constantes más bajos.
Algunos problemas se pueden resolver con heurísticas y algoritmos aleatorios de una manera más simple y eficiente que con algoritmos deterministas. Desafortunadamente, esto hace que incluso los algoritmos aleatorios simples sean difíciles de analizar porque hay dependencias sutiles que deben tenerse en cuenta . [2]
Las enormes brechas semánticas entre los conocimientos teóricos, los algoritmos formulados, los lenguajes de programación y el hardware plantean un desafío a las implementaciones eficientes incluso de algoritmos simples, porque los pequeños detalles de implementación pueden tener efectos en cadena sobre el comportamiento de ejecución. La única forma confiable de comparar varias implementaciones de un algoritmo es dedicar una cantidad considerable de tiempo a ajustar y perfilar, ejecutar esos algoritmos en múltiples arquitecturas y observar el código de máquina generado. [2]
Las implementaciones de algoritmos utilizados para experimentos difieren de manera significativa del código que se puede utilizar en aplicaciones. Mientras que las primeras priorizan la creación rápida de prototipos, el rendimiento y la instrumentación para las mediciones durante los experimentos, las segundas requieren pruebas exhaustivas, capacidad de mantenimiento, simplicidad y ajuste para clases particulares de entradas . [2]
Las bibliotecas de algoritmos estables y bien probadas como LEDA desempeñan un papel importante en la transferencia de tecnología al acelerar la adopción de nuevos algoritmos en las aplicaciones. Estas bibliotecas reducen la inversión necesaria y el riesgo para los profesionales, ya que eliminan la carga de comprender e implementar los resultados de la investigación académica.
Anualmente se organizan dos conferencias principales sobre ingeniería de algoritmos, a saber:
El Taller sobre Ingeniería de Algoritmos de 1997 (WAE'97) se celebró en Venecia (Italia) del 11 al 13 de septiembre de 1997. El Tercer Taller Internacional sobre Ingeniería de Algoritmos (WAE'99) se celebró en Londres, Reino Unido, en julio de 1999. [6] El primer Taller sobre Ingeniería y Experimentación de Algoritmos (ALENEX99) se celebró en Baltimore, Maryland, del 15 al 16 de enero de 1999. [7] Fue patrocinado por DIMACS , el Centro de Matemáticas Discretas y Ciencias de la Computación Teórica (en la Universidad de Rutgers ), con el apoyo adicional de SIGACT , el Grupo de Interés Especial de ACM sobre Algoritmos y Teoría de la Computación, y SIAM, la Sociedad de Matemáticas Industriales y Aplicadas . [7]