Informatique

L’objectif du cours est de permettre aux étudiants de maîtriser une boîte à outils de méthodes variées pour faire face aux problèmes difficiles. Il s’agit également de bien comprendre le type de compromis que font ses méthodes afin de pouvoir évaluer dans quelles circonstances il est possible de les utiliser. Enfin l’évocation de la théorie de la complexité permettra aux étudiants de comprendre les limites de ces approches.

Lorsque l’on cherche à résoudre un problème difficile (au sens de la complexité), il peut être intéressant de faire des compromis entre la qualité de la solution trouvée et les ressources de calcul utilisées pour la trouver. On parle alors d’algorithme d’approximation. Il est également possible de cherche à avoir une bonne solution avec une forte probabilité ou une utilisation d’un faible nombre de ressources de calcul avec une forte probabilité. L’utilisation du hasard permet également de trouver des solutions ayant de bonne propriété.

Ce cours se propose de présenter les principales façons de construire des algorithmes d’approximation comme: les algorithmes gloutons, la recherche locale, la relaxation convexe, les méthodes primal-dual, ou encore l’échantillonnage aléatoire. Le cours abordera de nombreux problèmes d’approximation comme la couverture de graphes par sommets, le problèmes de Knapsack,…

Concernant les algorithmes probabilistes, le cours présentera les principaux types d’algorithmes comme Las Vegas et Monte Carlo. Une analyse de l’exemple historique du test de primalité de Miller-Rabin sera présentée ainsi que quelques exemples de chaque types d’algorithme probabiliste pour des problèmes de graphes classiques.

Une attention particulière sera portée à la démonstration des qualités des solutions trouvée pas les algorithmes. Il s’agit de pouvoir offrir des garanties sur le fonctionnement des algorithmes d’approximation ou sur les résultats des algorithmes probabilistes.

Enfin, les lien avec la théorie de la complexité, en particulier des classes PTAS, APX pour les problèmes d’approximation, ZPP et BPP pour les algorithmes probabilistes, seront évoqués au fil du cours pour que les étudiants soient en mesure de comprendre des limites de ces méthodes.

• de trouver des compromis sur les qualités des solutions d’un problème en fonction du contexte pour mettre en oeuvre des algorithmes pratiques
• de connaître les principales méthodes d’approximation,
• d’utiliser le hasard dans des algorithmes pour qu’ils soient plus performants.