Ingénierie des algorithmes - Algorithm engineering
L'ingénierie des algorithmes se concentre sur la conception, l'analyse, la mise en œuvre, l'optimisation, le profilage et l'évaluation expérimentale d' algorithmes informatiques , comblant le fossé entre la théorie des algorithmes et les applications pratiques des algorithmes en génie logiciel . C'est une méthodologie générale pour la recherche algorithmique.
Origines
En 1995, un rapport d'un atelier parrainé par la NSF << dans le but d'évaluer les objectifs et les orientations actuels de la communauté de la théorie de l'informatique (TOC) >> a identifié la lenteur de l'adoption des connaissances théoriques par les praticiens comme un problème important et a suggéré des mesures à
- réduire l'incertitude des praticiens quant à savoir si une certaine percée théorique se traduira par des gains pratiques dans leur domaine de travail, et
- s'attaquer au manque de bibliothèques d'algorithmes prêtes à l'emploi, qui fournissent des implémentations stables, sans bogue et bien testées pour les problèmes algorithmiques et présentent une interface facile à utiliser pour les consommateurs de bibliothèques.
Mais aussi, les approches algorithmiques prometteuses ont été négligées en raison des difficultés d'analyse mathématique.
Le terme «ingénierie des algorithmes» a été utilisé pour la première fois avec spécificité en 1997, avec le premier Workshop on Algorithm Engineering (WAE97), organisé par Giuseppe F. Italiano .
Différence avec la théorie des algorithmes
L'ingénierie des algorithmes n'a pas l'intention de remplacer ou de concurrencer la théorie des algorithmes, mais tente d'enrichir, d'affiner et de renforcer ses approches formelles avec l'algorithmique expérimentale (également appelée algorithmique empirique).
De cette façon, il peut fournir de nouvelles informations sur l'efficacité et les performances des algorithmes dans les cas où
- l'algorithme en question se prête moins à l'analyse théorique de l'algorithme,
- l'analyse formelle suggère de manière pessimiste des limites qui sont peu susceptibles d'apparaître sur des intrants d'intérêt pratique,
- l'algorithme repose sur les subtilités des architectures matérielles modernes telles que la localisation des données, la prédiction de branche, les décrochages d'instructions, les latences d'instructions que le modèle de machine utilisé dans la théorie des algorithmes est incapable de capturer dans les détails requis,
- le croisement entre des algorithmes concurrents avec des coûts constants différents et des comportements asymptotiques doit être déterminé.
Méthodologie
Certains chercheurs décrivent la méthodologie de l'ingénierie des algorithmes comme un cycle comprenant la conception d'algorithmes, l'analyse, la mise en œuvre et l'évaluation expérimentale, auxquels s'ajoutent d'autres aspects tels que des modèles de machine ou des entrées réalistes. Ils soutiennent que l'assimilation de l'ingénierie des algorithmes à l'algorithmique expérimentale est trop limitée, car la visualisation de la conception et de l'analyse, de la mise en œuvre et de l'expérimentation comme des activités distinctes ignore la boucle de rétroaction cruciale entre ces éléments de l'ingénierie des algorithmes.
Modèles réalistes et entrées réelles
Bien que les applications spécifiques ne relèvent pas de la méthodologie de l'ingénierie des algorithmes, elles jouent un rôle important dans la mise en forme de modèles réalistes du problème et de la machine sous-jacente, et fournissent des entrées réelles et d'autres paramètres de conception pour les expériences.
Conception
Par rapport à la théorie des algorithmes, qui se concentre généralement sur le comportement asymptotique des algorithmes, les ingénieurs en algorithmes doivent garder à l'esprit d'autres exigences: simplicité de l'algorithme, implémentabilité dans les langages de programmation sur du matériel réel et permettre la réutilisation du code. De plus, les facteurs constants des algorithmes ont un impact si considérable sur les entrées du monde réel que parfois un algorithme avec un comportement asymptotique pire fonctionne mieux en pratique en raison de facteurs constants inférieurs.
Une analyse
Certains problèmes peuvent être résolus avec des heuristiques et des algorithmes aléatoires d'une manière plus simple et plus efficace qu'avec des algorithmes déterministes. Malheureusement, cela rend même les algorithmes aléatoires simples difficiles à analyser car il y a des dépendances subtiles à prendre en compte .
la mise en oeuvre
D'énormes écarts sémantiques entre les connaissances théoriques, les algorithmes formulés, les langages de programmation et le matériel posent un défi aux implémentations efficaces d'algorithmes, même simples, car de petits détails d'implémentation peuvent avoir des effets d'entraînement sur le comportement d'exécution. Le seul moyen fiable de comparer plusieurs implémentations d'un algorithme est de consacrer beaucoup de temps au réglage et au profilage, à exécuter ces algorithmes sur plusieurs architectures et à examiner le code machine généré.
Expériences
Voir: algorithmique expérimentale
Ingénierie des applications
Les implémentations d'algorithmes utilisés pour les expériences diffèrent de manière significative du code utilisable dans les applications. Alors que le premier donne la priorité au prototypage rapide, aux performances et à l'instrumentation pour les mesures pendant les expériences, le second nécessite des tests approfondis, la maintenabilité, la simplicité et le réglage pour des classes particulières d'entrées .
Bibliothèques d'algorithmes
Les bibliothèques d'algorithmes stables et bien testées comme LEDA jouent un rôle important dans le transfert de technologie en accélérant l'adoption de nouveaux algorithmes dans les applications. Ces bibliothèques réduisent les investissements et les risques requis pour les praticiens, car elles suppriment le fardeau de comprendre et de mettre en œuvre les résultats de la recherche universitaire.
Conférences
Deux grandes conférences sur l'ingénierie des algorithmes sont organisées annuellement, à savoir:
- Symposium sur les algorithmes expérimentaux (SEA), créé en 1997 (anciennement WEA).
- Réunion SIAM sur l'ingénierie et les expériences d'algorithmes (ALENEX), établie en 1999.
L'atelier de 1997 sur l'ingénierie des algorithmes (WAE'97) s'est tenu à Venise (Italie) du 11 au 13 septembre 1997. Le troisième atelier international sur l'ingénierie des algorithmes (WAE'99) s'est tenu à Londres, Royaume-Uni en juillet 1999. Le premier L'atelier sur l'ingénierie et l'expérimentation des algorithmes (ALENEX99) s'est tenu à Baltimore, Maryland du 15 au 16 janvier 1999. Il était parrainé par DIMACS , le Center for Discrete Mathematics and Theoretical Computer Science (à l'Université Rutgers ), avec le soutien supplémentaire du SIGACT , le Groupe d'Intérêt Spécial ACM sur les Algorithmes et la Théorie du Calcul, et la SIAM, la Société de Mathématiques Industrielles et Appliquées .