| Algorithme déterministe. Algorithme probabiliste( LasVegas et MonteCarlo ). |
On s’en tient aux définitions et à des exemples choisis par le professeur. On mentionne l’intérêt d’une méthode Las Vegas pour construire un objet difficile à produire par une méthode déterministe (par exemple, construction d’un nombre premier de taille cryptographique). Quelques exemples possibles :𝑘-ième minimum d’un tableau non trié, problème des huit reines, etc. |
| Problème de décision. Problème d’optimisation. Instance d’un problème, fonction de coût. Notion d’algorithme d’approximation. |
Seule la notion d’algorithme d’approximation est au programme. L’étude de techniques générales d’approximation est hors programme. On indique, par exemple sur le problème MAX2SAT, que la méthode probabiliste peut fournir de bons algorithmes d’approximation. |