Introduction au recuit simulé et à la machine de Boltzmann

Le recuit simulé permet de résoudre approximativement de nombreux problèmes difficiles (par exemple NP-complets) d'optimisation. La méthode est simple d'emploi et peut être appliquée à des problèmes dont on connait mal les propriétés. La machine de Boltzmann est un algorithme d'optimisation particulier conçu selon les principes du recuit simulé. Nous présenterons le recuit simulé en mettant l'accent sur les informations utiles à l'utilisation pratique de la méthode. Notre présentation de la machine de Boltzmann sera accompagnée d'une analyse critique des recherches sur le sujet. Nous parlerons notamment des travaux concernant les applications pratiques de l'algorithme, ainsi que de ses mises en \oe uvre sur matériel spécialisé rapide. L'exposé sera accompagné d'une démonstration du fonctionnement de la machine de Boltzmann, mise en \oe uvre sur matériel de calcul rapide dédié. Nous présenterons et utiliserons en exemple trois probl\`emes d'optimisation~: le partitionnement de graphes (MIN CUT, un problème informatique classique), la recherche de suites synchronisantes binaires (un problème ouvert de la théorie des codes) et la planification des vols d'une compagnie aérienne.