Algorithmique empirique - Empirical algorithmics

En informatique , l'algorithmique empirique (ou algorithmique expérimentale ) est la pratique consistant à utiliser des méthodes empiriques pour étudier le comportement des algorithmes . La pratique combine le développement d'algorithmes et l'expérimentation: les algorithmes ne sont pas seulement conçus, mais également mis en œuvre et testés dans diverses situations. Dans ce processus, une conception initiale d'un algorithme est analysée afin que l'algorithme puisse être développé par étapes.

Aperçu

Les méthodes de l'algorithmique empirique complètent les méthodes théoriques pour l' analyse des algorithmes . Grâce à l'application de principes de méthodes empiriques, en particulier à partir de statistiques , il est souvent possible d'obtenir des informations sur le comportement d'algorithmes tels que les algorithmes heuristiques de haute performance pour des problèmes combinatoires difficiles qui sont (actuellement) inaccessibles à l'analyse théorique. Des méthodes empiriques peuvent également être utilisées pour obtenir des améliorations substantielles de l' efficacité algorithmique .

L'informaticienne américaine Catherine McGeoch identifie deux branches principales de l'algorithmique empirique: la première (connue sous le nom d' analyse empirique ) traite de l'analyse et de la caractérisation du comportement des algorithmes , et la seconde (connue sous le nom de conception d' algorithmes ou d' ingénierie d'algorithmes ) se concentre sur les méthodes empiriques. pour améliorer les performances des algorithmes . Le premier s'appuie souvent sur des techniques et des outils issus de la statistique , tandis que le second s'appuie sur des approches issues de la statistique , de l'apprentissage automatique et de l' optimisation . Les outils d' analyse dynamique , généralement des profileurs de performances , sont couramment utilisés lors de l'application de méthodes empiriques pour la sélection et le raffinement d'algorithmes de différents types à utiliser dans divers contextes.

La recherche en algorithmique empirique est publiée dans plusieurs revues, dont l' ACM Journal on Experimental Algorithmics (JEA) et le Journal of Artificial Intelligence Research (JAIR). Outre Catherine McGeoch, des chercheurs bien connus en algorithmique empirique comprennent Bernard Moret , Giuseppe F. Italiano , Holger H. Hoos , David S. Johnson et Roberto Battiti .

Profilage des performances dans la conception d'algorithmes complexes

En l'absence d'algorithmique empirique, l'analyse de la complexité d'un algorithme peut impliquer diverses méthodes théoriques applicables à diverses situations dans lesquelles l'algorithme peut être utilisé. Les considérations relatives à la mémoire et au cache sont souvent des facteurs importants à prendre en compte dans le choix théorique d'un algorithme complexe, ou l'approche de son optimisation, dans un but donné. Le profilage des performances est une technique d' analyse de programme dynamique généralement utilisée pour trouver et analyser les goulots d'étranglement dans le code d'une application entière ou pour analyser une application entière afin d'identifier le code peu performant. Un profileur peut révéler le code le plus pertinent pour les problèmes de performances d'une application.

Un profileur peut aider à déterminer quand choisir un algorithme plutôt qu'un autre dans une situation particulière. Lorsqu'un algorithme individuel est profilé, comme pour l'analyse de complexité, les considérations relatives à la mémoire et au cache sont souvent plus importantes que le nombre d'instructions ou les cycles d'horloge; cependant, les résultats du profileur peuvent être considérés à la lumière de la façon dont l'algorithme accède aux données plutôt que du nombre d'instructions qu'il utilise.

Le profilage peut fournir un aperçu intuitif du comportement d'un algorithme en révélant les résultats de performance sous forme de représentation visuelle. Le profilage des performances a été appliqué, par exemple, lors du développement d'algorithmes pour faire correspondre les caractères génériques . Algorithmes précoces pour les caractères génériques correspondant, comme Rich Salz ' wildmat algorithme, généralement invoqué récursion , une technique critiquée pour des raisons de performance. L' algorithme de correspondance des caractères génériques de Krauss a été développé sur la base d'une tentative de formuler une alternative non récursive à l'aide de cas de test suivis par des optimisations suggérées via le profilage des performances, ce qui a abouti à une nouvelle stratégie algorithmique conçue à la lumière du profilage et d'autres considérations. Les profileurs qui collectent des données au niveau des blocs de base ou qui reposent sur une assistance matérielle fournissent des résultats qui peuvent être suffisamment précis pour aider les développeurs de logiciels à optimiser les algorithmes pour un ordinateur ou une situation particulière. Le profilage des performances peut aider les développeurs à comprendre les caractéristiques des algorithmes complexes appliqués dans des situations complexes, telles que les algorithmes coévolutionnaires appliqués à des problèmes arbitraires basés sur des tests, et peut aider à améliorer la conception.

Voir également

Les références