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

Problème de satisfaction des contraintes

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 le problème de satisfaction des contraintes aléatoires, en discutant de concepts tels que la coloration, le modèle Potts, le premier moment, la complexité et l'entropie de configuration. Il explore diverses méthodes et hypothèses liées à la résolution des problèmes de satisfaction des contraintes.

Enseignant·e·s (2)

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.

Florent Gérard Krzakala

Source officielle

Concepts associés (22)

Classe de complexité

En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Configuration entropy

In statistical mechanics, configuration entropy is the portion of a system's entropy that is related to discrete representative positions of its constituent particles. For example, it may refer to the number of ways that atoms or molecules pack together in a mixture, alloy or glass, the number of conformations of a molecule, or the number of spin configurations in a magnet. The name might suggest that it relates to all possible configurations or particle positions of a system, excluding the entropy of their velocity or momentum, but that usage rarely occurs.

Théorie de la complexité (informatique théorique)

vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.

Hasard

vignette|Les jeux de dés sont des symboles du hasard (jeux de hasard). vignette|Tyché ou Fortuna et sa corne d'abondance (fortune, hasard, en grec ancien, sort en latin) déesse allégorique gréco-romaine de la chance, des coïncidences, de la fortune, de la prospérité, de la destinée...|alt= Le hasard est le principe déclencheur d'événements non liés à une cause connue. Il peut être synonyme de l'« imprévisibilité », de l'« imprédictibilité », de fortune ou de destin.

Afficher plus

Séances de cours associées (33)

Coloration graphique: aléatoire vs symétrique

Comparer la coloration aléatoire et symétrique des graphiques en termes de coloration et d'équilibre des amas.

Physique statistique des grappes

Explore la physique statistique des clusters, en se concentrant sur la complexité et le comportement d'équilibre.

Replique Symmetry Breaking: Solution complète et condensation

Explore Replica Symmetry Breaking in the Random Energy Model, discutant de l'entropie et de la condensation de configuration.

Réplique Symmétrie Breaking: REM

Explore Replica Symmetry Breaking in the Random Energy Model, se concentrant sur l'entropie et les états de probabilité.

Lunettes de spin et holographie

Explore la connexion entre les lunettes de spin et l'holographie, en se concentrant sur le désordre, le modèle SYK, et l'effet quantique papillon.

Afficher plus

Concepts associés (22)

Classe de complexité

Computational complexity

Configuration entropy

Théorie de la complexité (informatique théorique)

Hasard

Afficher plus