Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Propagation de l'enquête: Méthode de la cavité

Dans cours

PHYS-642: Statistical physics for optimization & learning

This course covers the statistical physics approach to computer science problems, with an emphasis on heuristic & rigorous mathematical technics, ranging from graph theory and constraint satisfaction to inference to machine learning, neural networks and st ...

Description

Cette séance de cours couvre l'algorithme de propagation de l'enquête, en mettant l'accent sur la méthode de cavité et son application pour résoudre les problèmes de satisfaction des contraintes. L'instructeur explique le processus itératif de passage des messages et le concept d'excès de degré. La séance de cours se penche également sur la performance de l'algorithme de propagation de l'enquête et sur sa relation avec la propriété Berry Froom.

Enseignant·e·s (2)

Florent Gérard Krzakala

Lenka Zdeborová

Lenka Zdeborová is a Professor of Physics and of Computer Science in École Polytechnique Fédérale de Lausanne where she leads the Statistical Physics of Computation Laboratory. She received a PhD in physics from University Paris-Sud and from Charles University in Prague in 2008. She spent two years in the Los Alamos National Laboratory as the Director's Postdoctoral Fellow. Between 2010 and 2020 she was a researcher at CNRS working in the Institute of Theoretical Physics in CEA Saclay, France. In 2014, she was awarded the CNRS bronze medal, in 2016 Philippe Meyer prize in theoretical physics and an ERC Starting Grant, in 2018 the Irène Joliot-Curie prize, in 2021 the Gibbs lectureship of AMS. She is an editorial board member for Journal of Physics A, Physical Review E, Physical Review X, SIMODS, Machine Learning: Science and Technology, and Information and Inference. Lenka's expertise is in applications of concepts from statistical physics, such as advanced mean field methods, replica method and related message-passing algorithms, to problems in machine learning, signal processing, inference and optimization. She enjoys erasing the boundaries between theoretical physics, mathematics and computer science.

Source officielle

Concepts associés (17)

Problème de satisfaction de contraintes

Les problèmes de satisfaction de contraintes ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques où l'on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Les CSP font l'objet de recherches intenses à la fois en intelligence artificielle et en recherche opérationnelle. De nombreux CSP nécessitent la combinaison d'heuristiques et de méthodes d'optimisation combinatoire pour être résolus en un temps raisonnable.

Constraint satisfaction

In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a set of values for the variables that satisfies all constraints—that is, a point in the feasible region. The techniques used in constraint satisfaction depend on the kind of constraints being considered.

Programmation par contraintes

La programmation par contraintes (PPC, ou CP pour constraint programming en anglais) est un paradigme de programmation apparu dans les années 1970 et 1980 permettant de résoudre des problèmes combinatoires de grande taille tels que les problèmes de planification et d'ordonnancement. En programmation par contraintes, on sépare la partie modélisation à l'aide de problèmes de satisfaction de contraintes (ou CSP pour Constraint Satisfaction Problem), de la partie résolution dont la particularité réside dans l'utilisation active des contraintes du problème pour réduire la taille de l'espace des solutions à parcourir (on parle de propagation de contraintes).

Approximation de π

vignette|upright=2|Graphique montrant l'évolution historique de la précision record des approximations numériques de π, mesurée en décimales (représentée sur une échelle logarithmique). Dans l'histoire des mathématiques, les approximations de la constante π ont atteint une précision de 0,04 % de la valeur réelle avant le début de notre ère (Archimède). Au , des mathématiciens chinois les ont améliorées jusqu'à sept décimales. De grandes avancées supplémentaires n'ont été réalisées qu'à partir du (Al-Kashi).

Hangeul

Le hangeul (prononcé en coréen : ), aussi orthographié hangûl ou hangul en français, appelé josŏn'gŭl en Corée du Nord, est l’alphabet officiel du coréen, à la fois en Corée du Nord et en Corée du Sud. Le hangeul est fréquemment cité pour son histoire particulière : créé au par le roi Sejong le Grand, il est interdit à sa mort, mais perpétué entretemps par les romans féminins avant d'être réintroduit à la fin du sous l'occupation japonaise.

Afficher plus

Séances de cours associées (6)

Sans titre

Mise à l'échelle et renormalisation en mécanique statistique

Explore l'échelle et la renormalisation en mécanique statistique, en mettant l'accent sur les points critiques et les propriétés invariantes.

Algorithme Simplex

Couvre l'algorithme Simplex pour la minimisation des fonctions avec des contraintes linéaires.

Contrôle optimal: Convergence et conditions

Couvre la convergence et les conditions pour un contrôle optimal.

Théorie de l'information : Entropie et capacité

Couvre les concepts d'entropie, de distributions gaussiennes et de capacité de canal avec des contraintes.

Afficher plus