Semaine du lundi 27 janvier 2025
Tout ce qui précède, auquel on ajoute le début de la partie sur les algorithmes probabilistes. Il faut :
- savoir ce qu'est un algorithme de Monte-Carlo : la définition générale, et le cas particulier des algorithmes de Monte-Carlo sur des problèmes de décision, qui peuvent être biaisés ou non. Dans ce cas, savoir appliquer une méthode d'amplification.
- savoir ce qu'est un algorithme de Las Vegas.
- savoir faire l'analyse d'un algorithme probabiliste, avec plus ou moins de guidage. Dans cas d'un algorithme de Monte-Carlo, on cherche généralement la probabilité d'erreur, et la complexité en pire cas. Dans le cas d'un algorithme de Las Vegas, on cherche la complexité moyenne.
Les algorithmes d'approximations n'ont pas encore été vus.
