Semaine du lundi 3 février 2025
Tout ce qui précède, auquel on ajoute la partie sur les algorithmes d'approximation. Aucune méthode générale de construction de tels algorithmes n'est exigible (bien qu'on puisse guider les élèves vers la construction d'un tel algorithme sans le fournir directement, quand elle est basée sur une méthode facile, par exemple une approche gloutonne). Il faut cependant :
- savoir ce qu'est une $\alpha$-approximation calculée par un algorithme
- si on connaît la borne $\alpha$ fournie par un algorithme, savoir montrer qu'elle est minimale (en montrant qu'elle est atteinte)
- savoir justifier qu'un algorithme n'est pas une $\alpha$-approximation, pour $\alpha$ fixé (en exhibant une mauvaise instance) et pour tout $\alpha$ (en exhibant une mauvaise instance pour tout $\alpha$)
Les schémas d'approximations (algorithmes d'approximations prenant en paramètre un $\varepsilon$ et garantissant une borne de la forme $\alpha = 1+\varepsilon$, qui permettent donc une précision aussi grande que l'on veut) ne sont pas explicitement au programme, et donc en sont pas à connaître. On peut cependant travailler avec des tels algorithmes en fournissant le guidage nécessaire.
