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

Coloration graphique III

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 les propriétés des clusters et le seuil de coloration dans la coloration des graphiques, y compris la connectivité moyenne, le cluster, la condensation, la rigidité et le problème COL/UNCOL. L'instructeur discute des propriétés déduites de la contiguïté de la coloration graphique aléatoire et plantée, ainsi que des concepts plus génériques comme les points fixes BP et la complexité des clusters.

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

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

Concepts associés (32)

Coloration de graphe

thumb|Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune.

Coloration des arêtes d'un graphe

thumb|Coloration des arêtes du graphe de Desargues avec trois couleurs. En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs.

Amas stellaire

Un amas stellaire est une concentration locale d'étoiles d'origine commune et liées entre elles par la gravitation, dans un espace dont les dimensions peuvent atteindre 200 pc. Ces objets sont classés en plusieurs familles selon leur aspect ; ce sont, par compacité croissante : les associations stellaires, les amas ouverts et les amas globulaires. Les amas stellaires se maintiennent par l'attraction gravitationnelle mutuelle de leurs membres.

Amas ouvert

En astronomie, un amas ouvert est un amas stellaire groupant environ de 100 à étoiles de même âge liées entre elles par la gravitation, et dont le diamètre varie de 1,5 à 15 pc, avec une moyenne de 4 à 5 pc. Les amas ouverts sont peu lumineux et s’observent essentiellement dans notre Galaxie, où ils se situent dans le plan galactique, et dans les galaxies proches : les deux Nuages de Magellan et la galaxie d’Andromède. On pense qu'ils se forment au sein des nuages moléculaires, les grands nuages de gaz et de poussières qui constituent les nébuleuses diffuses.

Amas globulaire

En astronomie, un amas globulaire est un amas stellaire très dense, contenant typiquement une centaine de milliers d'étoiles distribuées dans une sphère dont la taille varie d'une vingtaine à quelques centaines d'années-lumière. Leur densité est ainsi nettement plus élevée que celle des amas ouverts. Les étoiles de ces amas sont généralement des géantes rouges. On compte globulaires dans notre galaxie, la Voie lactée. Mais il en existe sans doute d'autres, qui restent indétectables parce que masqués par le disque galactique.

Afficher plus

Séances de cours associées (33)

Physique statistique des grappes

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

Coloration graphique II

Explore les concepts avancés de coloration graphique, y compris la coloration plantée, le seuil de rigidité, et les variables gelées en points fixes BP.

Propagation de la croyance

Explore la propagation de la croyance dans les modèles graphiques, les graphiques de facteurs, les exemples de verre de spin, les distributions de Boltzmann et les propriétés de coloration des graphiques.

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.

Théorie de l'information: Bases

Couvre les bases de la théorie de l'information, de l'entropie et des points fixes dans les coloriages graphiques et le modèle Ising.

Afficher plus

Concepts associés (32)

Coloration de graphe

Coloration des arêtes d'un graphe