Algorithmes randomisés et d'approximation
Les algorithmes randomisés et d'approximation sacrifient l'exactitude ou le déterminisme au profit de l'efficacité : les algorithmes randomisés utilisent des choix aléatoires pour gagner en vitesse ou en simplicité, tandis que les algorithmes d'approximation trouvent des solutions dont la quasi-optimalité est prouvée pour des problèmes trop difficiles à résoudre exactement.
Definition
Les algorithmes randomisés effectuent des choix aléatoires pendant l'exécution et sont analysés en fonction de leur temps d'exécution espéré ou de leur probabilité de correction ; les algorithmes d'approximation s'exécutent efficacement et renvoient des solutions garanties comme étant à l'intérieur d'un facteur prouvé de l'optimal pour les problèmes d'optimisation difficiles.
Scope
Ce domaine couvre les algorithmes qui assouplissent l'objectif d'une réponse exacte et déterministe. Il inclut les algorithmes randomisés (Las Vegas et Monte Carlo), avec leurs garanties probabilistes ; les algorithmes d'approximation pour l'optimisation NP-difficile avec des ratios d'approximation prouvés ; et les algorithmes en ligne qui doivent prendre des décisions sans connaître l'avenir, analysés par leur ratio de compétitivité. Ce sont les réponses standard à l'intractabilité et aux situations d'incertitude, s'appuyant sur l'analyse de la complexité et les paradigmes de conception.
Sub-topics
Core questions
- Comment la randomisation améliore-t-elle le temps d'exécution, la simplicité ou la robustesse ?
- Quelle est la différence entre les garanties de Las Vegas et de Monte Carlo ?
- Comment la qualité d'un algorithme d'approximation est-elle quantifiée par un ratio d'approximation ?
- Quels problèmes NP-difficiles admettent de bonnes approximations, et lesquels y résistent ?
- Comment les décisions en ligne, prises sans information future, sont-elles évaluées de manière compétitive ?
Key concepts
- algorithmes randomisés
- Las Vegas et Monte Carlo
- temps d'exécution espéré
- inégalités de concentration
- ratio d'approximation
- schéma d'approximation en temps polynomial
- algorithmes en ligne
- ratio de compétitivité
Key theories
- Randomisation pour l'efficacité
- Les choix aléatoires peuvent produire des algorithmes plus rapides ou plus simples que les meilleurs algorithmes déterministes, avec des garanties sur le temps espéré (Las Vegas) ou sur la probabilité d'erreur (Monte Carlo), utilisant souvent des inégalités de concentration pour l'analyse.
- Ratios d'approximation pour les problèmes NP-difficiles
- Lorsque les solutions exactes sont intraitables, un algorithme d'approximation fournit une solution dont il est prouvé qu'elle se situe à l'intérieur d'un certain facteur (le ratio d'approximation) de l'optimum ; le ratio réalisable caractérise la qualité de l'approximation d'un problème.
Clinical relevance
Ces méthodes constituent la boîte à outils pratique pour les problèmes difficiles et incertains : les algorithmes randomisés sont à la base des tests de primalité en cryptographie, du hachage et de l'équilibrage de charge ; les algorithmes d'approximation produisent des solutions utilisables pour les problèmes NP-difficiles d'ordonnancement, de routage, de regroupement (clustering) et de localisation d'installations ; et les algorithmes en ligne modélisent la mise en cache, la pagination et l'allocation de ressources où les décisions doivent être prises en temps réel.
History
Les algorithmes randomisés ont gagné en importance avec les tests de primalité de Solovay-Strassen et Rabin dans les années 1970 et la promotion plus large des méthodes probabilistes par Rabin. Les algorithmes d'approximation se sont développés parallèlement à la théorie de la NP-complétude à partir des années 1970, et l'analyse compétitive des algorithmes en ligne a été formalisée par Sleator et Tarjan dans les années 1980, formant ensemble l'étude moderne des algorithmes inexacts et probabilistes.
Key figures
- Rajeev Motwani
- Prabhakar Raghavan
- Vijay Vazirani
- Michael Rabin
- Robert Solovay
- Volker Strassen
Related topics
Seminal works
- motwani1995
- vazirani2001
- cormen2009
Frequently asked questions
- Les algorithmes randomisés sont-ils peu fiables parce qu'ils utilisent le hasard ?
- Non. Les algorithmes de Las Vegas renvoient toujours une réponse correcte et seul leur temps d'exécution varie. Les algorithmes de Monte Carlo peuvent commettre des erreurs, mais la probabilité d'erreur peut être rendue arbitrairement faible par répétition. Leurs garanties sont des énoncés probabilistes précis, et non de l'imprévisibilité.
- Pourquoi utiliser un algorithme d'approximation au lieu de simplement trouver la solution optimale ?
- Pour les problèmes d'optimisation NP-difficiles, trouver l'optimum exact peut être infaisable pour de grandes entrées. Un algorithme d'approximation s'exécute en temps polynomial et garantit une solution à l'intérieur d'un facteur connu de l'optimum, ce qui est souvent suffisant et bien plus pratique que d'attendre une réponse exacte.