La ingeniería de algoritmos se centra en el diseño, análisis, implementación, optimización, perfilado y evaluación experimental de algoritmos informáticos, tendiendo un puente entre la teoría algorítmica y las aplicaciones prácticas de los algoritmos en ingeniería de software."Algorithm Engineering", Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, web: http://www.dis.uniroma1.it/~demetres/docs/ae.pdf Es una metodología general para la investigación algorítmica."Algorithm Engineering – An Attempt at a Definition", Peter Sanders, web: http://algo2.iti.kit.edu/documents/definition.pdf
Orígenes
En 1995, un informe de un taller patrocinado por la Fundación Nacional de Ciencias (NSF), "con el propósito de evaluar los objetivos y la dirección actuales de la comunidad especializada en teoría de la computación (TOC)", identificó la lenta adopción de conocimientos teóricos por parte de los profesionales como un problema importante y sugirió medidas para: Reducir la incertidumbre de los profesionales sobre si un determinado avance teórico se traducirá en beneficios prácticos en su campo de trabajo. Abordar la falta de bibliotecas de algoritmos listas para usar, que proporcionen implementaciones estables, sin errores y bien probadas para problemas algorítmicos, y que ofrezcan una interfaz fácil de usar para los usuarios de la biblioteca."Emerging Opportunities for Theoretical Computer Science", Aho, Johnson, Karp, Kosaraju, McGeoch, Papadimitriou, web: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9160
Además, se habían descuidado enfoques algorítmicos prometedores debido a las dificultades de su análisis matemático.
El término ingeniería de algoritmos se utilizó por primera vez con especificidad en 1997, con el primer Taller de Ingeniería de Algoritmos (WAE97), organizado por Giuseppe F. Italiano.
Diferencia con la teoría de algoritmos La ingeniería de algoritmos no pretende reemplazar ni competir con la teoría de algoritmos, sino enriquecer, refinar y reforzar sus enfoques formales con algoritmia experimental (también llamada algoritmia empírica).
De esta forma, puede proporcionar nuevas perspectivas sobre la eficiencia y el rendimiento de los algoritmos en casos donde: El algoritmo en cuestión es menos susceptible al análisis teórico de algoritmos. El análisis formal sugiere de forma pesimista límites que es improbable que aparezcan en entradas de interés práctico. El algoritmo depende de las complejidades de las arquitecturas de hardware modernas, como la localización de datos, la predicción de bifurcaciones, las pausas de instrucciones y las latencias de instrucciones, que el modelo de máquina utilizado en la teoría de algoritmos no puede capturar con el detalle necesario. Se precisa determinar la transición entre algoritmos competidores con diferentes costos constantes y comportamientos asintóticos."Towards a Discipline of Experimental Algorithmics", Bernard M. E. Moret, web: http://infoscience.epfl.ch/record/97865/files/dimacs_algorithmics.pdf
Metodología Algunos investigadores describen la metodología de la ingeniería de algoritmos como un ciclo que consta de diseño, análisis, implementación y evaluación experimental del algoritmo, junto con otros aspectos como modelos de máquina o entradas realistas.
Argumentan que equiparar la ingeniería de algoritmos con la algoritmia experimental es demasiado limitado, ya que considerar el diseño y el análisis, la implementación y la experimentación como actividades separadas ignora el crucial ciclo de retroalimentación entre estos elementos de la ingeniería de algoritmos.
Modelos realistas y entradas reales 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 de la máquina subyacente, y proporcionan entradas reales y otros parámetros de diseño para los experimentos.
Diseño 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, implementabilidad en lenguajes de programación en hardware real y permitir la reutilización de 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.
Análisis Algunos problemas se pueden resolver con heurísticas y algoritmos aleatorios de forma más sencilla y eficiente que con algoritmos deterministas. Desafortunadamente, esto hace que incluso los algoritmos aleatorios simples sean difíciles de analizar, ya que existen dependencias sutiles que deben tenerse en cuenta.
Implementación Las enormes brechas semánticas entre los conocimientos teóricos, los algoritmos formulados, los lenguajes de programación y el hardware representan un desafío para las implementaciones eficientes incluso de algoritmos simples, ya que pequeños detalles de implementación pueden tener efectos en cadena en el comportamiento de ejecución.
La única forma fiable de comparar varias implementaciones de un algoritmo es dedicar una cantidad considerable de tiempo a la optimización y el análisis de rendimiento, ejecutar esos algoritmos en múltiples arquitecturas y observar el lenguaje de máquina generado.
Experimentos Véase: algoritmia experimental
Ingeniería de aplicaciones Las implementaciones de algoritmos utilizados para experimentos difieren significativamente del código utilizable en aplicaciones prácticas.
Mientras que la primera prioriza la creación rápida de prototipos, el rendimiento y la instrumentación para las mediciones durante los experimentos, la segunda requiere pruebas exhaustivas, facilidad de mantenimiento, simplicidad y ajuste para clases específicas de entradas.
Bibliotecas de algoritmos Las bibliotecas de algoritmos estables y bien probadas, como la Library of Efficient Data types and Algorithms (LEDA), desempeñan un papel importante en la transferencia tecnológica al acelerar la adopción de nuevos algoritmos en las aplicaciones. Estas bibliotecas reducen la inversión y el riesgo necesarios para los profesionales, ya que eliminan la carga de comprender e implementar los resultados de la investigación académica.
Conferencias Se organizan anualmente dos conferencias principales sobre Ingeniería de Algoritmos: El Symposium on Experimental Algorithms (SEA), establecida en 1997 (anteriormente conocida como WEA). Reunión SIAM sobre Ingeniería de Algoritmos y Experimentos (ALENEX), establecida en 1999.
El Taller de 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.Algorithm engineering: 3rd International Workshop, Jeffrey Scott Vitter, Christos D. Zaroliagis, 1999, web: BGoogle-sC.
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."Workshop on Algorithm Engineering and Experiments" (overview), JHU.edu, 1999, web: JHU-ALENEX99 . Fue patrocinado por DIMACS, el Centro de Matemáticas Discretas e Informática Teórica de la Universidad Rutgers, con el apoyo adicional del SIGACT, el Grupo de Interés Especial en Algoritmos y Teoría de la Computación de la ACM, y SIAM, la Sociedad de Matemáticas Aplicadas e Industriales.
Véase también AlphaEvolve Anexo:Algoritmos (en inglés) Anexo:Algoritmos de inteligencia artificial (en inglés)
Referencias
Categoría:Algoritmos Categoría:Informática teórica