Abstract FR:

Dans le premier chapitre, nous etudions trois problemes classiques d'optimisation combinatoire dans leur version stochastique. Un modele tres populaire en la matiere est le probleme du voyageur de commerce en dimension 2, qui consiste a trouver le chemin le plus court passant par n points choisis au hasard dans un domaine du plan (le plus souvent un carre). Nous considerons egalement le probleme d'appariement minimal euclidien simple et bipartit. Pour ces trois problemes les simulations numeriques montrent qu'il existe une loi d'echelle simple a grand n lorsque les points sont choisis sur un tore (ou plus generalement une surface sans bord): en dimension d, la longueur moyenne d'un lien dans la solution optimale un developpement en puissances de 1/n et tend (dans les unites appropriees) vers une limite finie quand n devient infini. Nous avons exploite ce developpement de taille finie pour obtenir des estimations precises de la valeur limite pour plusieurs valeurs de la dimension dans chacun des trois problemes. Dans le modele euclidien, les distances entre paires de points sont correlees, mais seules sont non nulles les correlations associees a des graphes comprenant une ou plusieurs boucles. Si on neglige ces correlations, on obtient un modele sans geometrie ou les distances sont des variables aleatoires independantes distribuees suivant une meme loi. Pour les trois problemes consideres, ce nouveau modele a liens aleatoires est soluble par une approximation de champ moyen comme la methode des repliques ou la methode de la cavite, comme l'ont montre mezard, parisi, et krauth. Afin de quantifier la qualite de l'approximation du modele a liens aleatoire pour le modele euclidien nous comparons nos estimations de la longueur moyenne d'un lien dans la solution optimale pour le modele euclidien aux predictions analytiques du modele a liens aleatoires, et trouvons que l'approximation est tres bonne meme en petite dimension. Nous obtenons par ailleurs un developpement asymptotique en 1/d pour le modele a liens aleatoires, et cherchons a mettre en evidence un developpement analogue pour le modele euclidien. Dans les trois problemes, nous conjecturons que les effets dus aux correlations euclidiennes sont d'ordre o(1/d#2). Dans le cas du probleme d'appariement minimal, nous etudions egalement l'incorporation au modele a liens aleatoires des correlations euclidiennes a trois liens, d'apres mezard et parisi, et discutons de l'effet des correlations dues a un nombre fini quelconque de liens