Algorithmique 4

Ce module explore quelques sujets avancés en conception et analyse d’algorithmes.

En conception d’algorithmes, des techniques permettant de s’attaquer à des problèmes difficiles seront présentées. D’une part, nous aborderons les algorithmes de recherche exhaustive et de retour sur trace (backtrack) qui fournissent des solutions exactes, de manière relativement efficace en pratique. D’autre part, nous étudierons les algorithmes d’approximation qui n’apportent que des solutions approchées, mais avec une complexité bien plus faible. En analyse d’algorithmes, nous dépasserons l’analyse en pire cas pour aborder l’analyse en moyenne (lorsque les données en entrées sont aléatoires) et l’analyse amortie (lorsqu’une même opération est effectuée plusieurs fois à la suite). Enfin, nous verrons de manière

transverse l’utilisation de l’aléa en algorithmique, via l’introduction de la notion d’algorithme probabiliste et l’étude des tables de hachages qui sont une structure de donnée intrinsèquement probabiliste.