Abstract FR:

Dans la premiere partie de ce travail, nous nous interessons a l'execution rapide de la machine de boltzmann, un algorithme probabiliste capable de resoudre approximativement des problemes d'optimisation np-complets. Nous presentons deux mises en Œuvre de la machine par materiel specialise numerique. La plus puissante des deux realisations execute l'algorithme d'une maniere exacte, a une vitesse de 505 megasynapses (millions d'additions et de multiplications) par seconde; les poids de la machine de boltzmann y sont representes en arithmetique entiere, sur 16 bits. Cette mise en Œuvre est particulierement simple car elle utilise un materiel dedie seulement pour executer la partie la plus simple de la machine de boltzmann, a savoir la multiplication de matrices de nombres par des vecteurs de bits. Les autres operations (compliquees mais n'exigeant pas une puissance de calcul elevee) sont executees par logiciel, sur la machine hote. Nous presentons egalement une methode nouvelle qui devrait aboutir a l'elaboration de mises en Œuvre logicielles et materielles de la machine de boltzmann qui effectueront au moins trois fois moins de calculs que les realisations traditionnelles. Nous demontrons que la minimisation des formes quadratiques binaires (qui est le probleme d'optimisation le plus directement resolu par la machine de boltzmann) est, au sens des l-reductions de papadimitriou et yannakakis, l'un des problemes np-complets les plus difficiles (plus precisement, nous demontrons qu'elle est au moins aussi difficile que la clique). Dans la seconde partie, nous considerons des mots sur 0,1. Nous appelons autodistance d'un tel mot la plus petite des distances de hamming entre lui-meme et ses images par des permutations circulaires non identiques; l'autodistance inverse du mot designe la plus grande de ces distances. Pour tout l2, nous etudions les mots de longueur l dont l'autodistance et l'autodistance inverse sont toutes les deux proches de l/2. Ces mots sont appeles suites synchronisantes. Nous decrivons brievement des familles precedemment connues de suites synchronisantes. Nous presentons une methode pratique, fondee sur le recuit simule, qui permet de generer des suites synchronisantes de toute longueur, et nous analysons des suites ainsi obtenues. Nous prouvons que, pour l suffisamment grand, l'autodistance et l'autodistance inverse sont tres proches de l/2 pour une proportion arbitrairement elevee des mots de longueur l