Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Cette thèse explore les perspectives algorithmiques de la marche aléatoire branchante et du modèle continu d'énergie aléatoire (CREM). Nous nous intéressons notamment à la construction d'algorithmes en temps polynomial capables d'échan¬tillonner la mesure de Gibbs du modèle avec une grande probabilité, et à identifier le régime de dureté, qui consiste en toute température inverse bêta telle que de tels algorithmes en temps polynomial n'existent pas. Dans le Chapitre 1, nous fournissons un aperçu historique des modèles et moti¬vons les problèmes algorithmiques étudiés. Nous donnons également un aperçu des verres de spin à champ moyen qui motive la ligne de notre recherche. Dans le Chapitre 2, nous abordons le problème de l'échantillonnage de la mesure de Gibbs dans le contexte de la marche aléatoire branchante. Nous identifions une température inverse critique bêta_c, identique au point critique statique, où une tran¬sition de dureté se produit. Dans le régime sous-critique bêta < bêta_c, nous établissons qu'un algorithme d'échantillonnage récursif est capable d'échantillonner efficace¬ment la mesure de Gibbs. Dans le régime supercritique bêta > bêta_c, nous montrons que nous ne pouvons pas trouver d'algorithme en temps polynomial qui appartienne à une certaine classe d'algorithmes. Dans le Chapitre 3, nous portons notre attention sur le même problème d'échan¬tillonnage pour le modèle continu d'énergie aléatoire (CREM). Dans le cas où la fonction de covariance de ce modèle est concave, nous montrons que pour toute température inverse bêta < à l'infini, l'algorithme d'échantillonnage récursif considéré au Chapitre 2 est capable d'échantillonner efficacement la mesure de Gibbs. Pour le cas non concave, nous identifions un point critique bêta_G où une transition de dureté similaire à celle du Chapitre 2 se produit. Nous fournissons également une borne inférieure de l'énergie libre du CREM qui pourrait être d'un intérêt indépendant. Dans le Chapitre 4, nous étudions le moment négatif de la fonction de ...