Ingeniería de algoritmos - Algorithm engineering

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 , reduciendo la brecha entre la teoría de algoritmos y las aplicaciones prácticas de algoritmos en ingeniería de software . Es una metodología general para la investigación algorítmica.

Orígenes

En 1995, un informe de un taller patrocinado por 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 lentitud de la adopción de conocimientos teóricos por parte de los profesionales como un tema importante y sugirió medidas a

  • Reducir la incertidumbre de los profesionales sobre si un cierto avance teórico se traducirá en beneficios prácticos en su campo de trabajo, y
  • abordar la falta de bibliotecas de algoritmos listas para usar, que proporcionan implementaciones estables, sin errores y bien probadas para problemas algorítmicos y exponen una interfaz fácil de usar para los consumidores de bibliotecas.

Pero también, se han descuidado enfoques algorítmicos prometedores debido a las dificultades en el 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 o competir con la teoría de algoritmos, sino que intenta enriquecer, refinar y reforzar sus enfoques formales con algoritmos experimentales (también llamados algoritmos empíricos).

De esta manera, puede proporcionar nuevos conocimientos sobre la eficiencia y el rendimiento de los algoritmos en los casos en que

  • el algoritmo en cuestión es menos susceptible de análisis teórico de algoritmos,
  • El análisis formal sugiere pesimistamente límites que es poco probable que aparezcan en entradas de interés práctico,
  • el algoritmo se basa en las complejidades de las arquitecturas de hardware modernas como la ubicación de los datos, la predicción de rama, las paradas de instrucción, las latencias de instrucción que el modelo de máquina utilizado en la teoría de algoritmos no puede capturar con el detalle requerido,
  • Es necesario determinar el cruce entre algoritmos competidores con diferentes costos constantes y comportamientos asintóticos.

Metodología

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, unidos por otros aspectos como modelos de máquina o entradas realistas. Argumentan que equiparar la ingeniería de algoritmos con algoritmos experimentales es demasiado limitado, porque ver 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.

Modelos realistas e insumos reales

Si bien las aplicaciones específicas están 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 proporcionan entradas reales y otros parámetros de diseño para 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 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ística 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 .

Implementación

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 para las implementaciones eficientes de incluso 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.

Experimentos

Ver: algoritmos experimentales

Ingeniería de aplicaciones

Las implementaciones de algoritmos utilizados para experimentos difieren de manera significativa del código utilizable en aplicaciones. Mientras que el primero prioriza la creación rápida de prototipos, el rendimiento y la instrumentación para las mediciones durante los experimentos, el segundo requiere pruebas exhaustivas, mantenibilidad, simplicidad y ajuste para clases particulares de entradas .

Bibliotecas de algoritmos

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 y el riesgo necesarios para los profesionales, porque eliminan la carga de comprender e implementar los resultados de la investigación académica.

Conferencias

Anualmente se organizan dos conferencias principales sobre Ingeniería de Algoritmos, a saber:

  • Simposio sobre Algoritmos Experimentales (SEA), establecido en 1997 (antes conocido como WEA).
  • Reunión SIAM sobre Ingeniería de Algoritmos y Experimentos (ALENEX), establecida en 1999.

El taller de 1997 sobre ingeniería de algoritmos (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. El primero El Taller sobre Ingeniería y Experimentación de Algoritmos (ALENEX99) se llevó a cabo en Baltimore, Maryland, del 15 al 16 de enero de 1999. Fue patrocinado por DIMACS , el Centro de Matemáticas Discretas e Informática 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 .

Referencias