Modèles de calcul probabiliste et complexité

Description du cours

Le cours se compose de deux parties : 1. une introduction à l’algorithmique probabiliste ; 2. la conception et l’étude d’algorithmes classiques pour l’arithmétique, la cryptographie et l’algorithmique ; Dans la première partie, les familles principales d’algorithmes probabilistes sont présentées (algorithmes de Monte Carlo, Algorithme Las Vegas) ainsi que les méthodes probabilistes conduisant à ces familles d’algorithmes. Dans la deuxième partie, un focus particulier est fait sur les algorithmes utilisés en crytptographie, en arithmétique ou certains problèmes algorithmiques Les TD de la première partie se feront sur machine et viseront à implémenter des algorithmes vus en TD/TP. La seconde partie se fait sous forme de CM/TD où les notions principales du cours sont présentés sous forme d’une succession de problèmes.