Séance de cours

Propagation de la croyance pour la coloration graphique

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

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 concept de propagation de la croyance pour la coloration des graphiques, en mettant l'accent sur la distribution des probabilités et la température inverse. Il explique le processus de recherche de points fixes et les implications pour la coloration des graphiques. La séance de cours se penche sur les défis des interactions anti-ferromagnétiques et les propriétés de convergence de l'algorithme.

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

Proximité ontologique

Mathématiques

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

Concepts associés (32)

Théorie des graphes

vignette|Un tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non symétriques (les graphes sont alors dits orientés) et sont alors appelées des flèches ou des arcs.

Lexique de la théorie des graphes

NOTOC Acyclique graphe ne contenant pas de cycle. Adjacence une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.

Température de Curie

La température de Curie (ou point de Curie) d'un matériau ferromagnétique ou ferrimagnétique est la température T à laquelle le matériau perd son aimantation permanente. Le matériau devient alors paramagnétique. Ce phénomène a été découvert par le physicien français Pierre Curie en 1895. L’aimantation permanente est causée par l’alignement des moments magnétiques. La susceptibilité magnétique au-dessus de la température de Curie peut alors être calculée à partir de la loi de Curie-Weiss, qui dérive de la loi de Curie.

Chaîne (théorie des graphes)

Dans un graphe non orienté, une chaîne reliant à , notée , est définie par une suite finie d'arêtes consécutives, reliant à . La notion correspondante dans les graphes orientés est celle de chemin. Une chaîne élémentaire est une chaîne ne passant pas deux fois par un même sommet, c'est-à-dire dont tous les sommets sont distincts. Une chaîne simple est une chaîne ne passant pas deux fois par une même arête, c'est-à-dire dont toutes les arêtes sont distinctes. Un cycle est une chaîne simple dont les deux extrémités sont identiques.

Afficher plus

Séances de cours associées (64)

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.

Points fixes dans la théorie des graphiques

Se concentre sur les points fixes dans la théorie des graphiques et leurs implications dans les algorithmes et l'analyse.

Modèle de bloc stochastique

Couvre le modèle de bloc stochastique et son application dans la détection communautaire, explorant sa formulation mathématique et ses défis.

Chaînes de Markov: Applications et analyse

Explore les chaînes de Markov, en se concentrant sur le problème de coloration et l'analyse de l'algorithme.

Les inégalités de Cheeger

Explore les inégalités de Cheeger pour les promenades aléatoires sur les graphiques et leurs implications.

Afficher plus

Concepts associés (32)

Théorie des graphes

Lexique de la théorie des graphes

Connectivity (graph theory)

Température de Curie

Chaîne (théorie des graphes)

Afficher plus