Le cours vise à familiariser les étudiants aux techniques et méthodes avancées pour la conception et l'analyse des algorithmes selon plusieurs modèles et mesures de complexités (algorithmes randomizés, d'approximation, on-line, modèle parallèle, modèle distribué, …).

Le cours commence par une introduction aux algorithmes randomizés. Cette partie présente différentes notions de convergence (Monte-Carlo, Las Vegas, “avec très forte probabilité”, …) pour les algorithmes. Le cours revient ensuite sur divers problèmes algorithmiques pour envisager plusieurs approches possibles comme l'analyse en moyenne, les solutions approchées et les algorithmes d'approximation pour l'optimisation ou encore les mesures de compétitivité pour les algorithmes on-line. Ces notions seront ensuite étendues dans le contexte distribué et parallèle. Le cours se termine par une introduction à la génération aléatoire uniforme de structures discrètes dans l'objectif de pouvoir alimenter à l'envie les entrées (ou des aléas vont intervenir) pour certains algorithmes. Chaque partie de ce cours est enrichie d'exercices liés aux notions que les étudiants devront assimiler.