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 mariage: Algorithme de Gale Shapley

Dans cours

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, disc ...

Description

Cette séance de cours couvre le problème du mariage et l'algorithme de Gale Shapley, qui vise à trouver une correspondance stable entre deux ensembles d'individus en fonction de leurs préférences. L'algorithme couple itérativement les individus jusqu'à ce qu'une correspondance stable soit obtenue.

Enseignant·e

Karl Aberer

Co-Founder of LinkAlong Sarl, 2017.Vice-president EPFL for Information Systems, 2012 –2016.Director of the Swiss National Centre for Mobile Information and Communication Systems NCCR MICS (mics.ch), 2005 -2012.Member of the Swiss Research and Technology Council SWTR, consulting the Swiss Federal government, 2004 - 2011.

Source officielle

Concepts associés (26)

Problème des mariages stables

vignette|Algorithme de Gale Shapley. En mathématiques, informatique et économie, le problème des mariages stables consiste à trouver, étant donné n hommes et n femmes, et leurs listes de préférences, une façon stable de les mettre en couple. Une situation est dite instable s'il y a au moins un homme et une femme qui préféreraient se mettre en couple plutôt que de rester avec leurs partenaires actuels (Dupont préfère à , et préfère Dupont à Durand). Ce problème a des applications en économie, en théorie des jeux et en physique statistique.

Mariage

vignette|Sculpture représentant un couple marié dans la Rome antique.vignette|Les Époux Arnolfini de Jan van Eyck.vignette|Mariage de Willem-Alexander et Máxima, 2002. Le mariage est une union conjugale contractuelle et/ou rituelle, à durée illimitée, déterminée ou indéterminée, reconnue et encadrée par une institution juridique ou religieuse qui en détermine les modalités. Le terme désigne à la fois la cérémonie rituelle, l'union qui en est issue et l'institution en définissant les règles.

Mariage d'enfant

Le mariage d’enfant ou mariage précoce désigne tout mariage officiel ou toute union non officialisée entre un enfant de moins de 18 ans et un adulte ou un autre enfant. Dans leur grande majorité, les mariages d'enfants sont l'union entre une jeune fille et un homme et ils reflètent les inégalités de genre. Bien que l'âge de la majorité civile et l'âge pour contracter un mariage correspondent fréquemment à 18 ans, ils peuvent varier selon les pays et par conséquent, l'âge requis pour se marier peut être inférieur ou supérieur à 18 ans.

Mariage civil

vignette|Mariage en Suisse (Albert Anker, 1887). Le mariage civil est un mariage officialisé par une autorité publique d'un État, à la différence du mariage coutumier et du mariage religieux. Selon les juridictions, il peut être obligatoirement l'union d'un couple d'un homme et d'une femme, s'étendre aux personnes de même sexe ou être polygame. Dans certains pays l'institution du mariage civil répond à une volonté de dégager le mariage de l'influence des institutions religieuses et s'inscrit dans le mouvement de séparation de l'Église et de l'État, qui débute au .

Couplage (théorie des graphes)

En théorie des graphes, un couplage ou appariement (en anglais matching) d'un graphe est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun. Soit un graphe simple non orienté G = (S, A) (où S est l'ensemble des sommets et A l'ensemble des arêtes, qui sont certaines paires de sommets), un couplage M est un ensemble d'arêtes deux à deux non adjacentes. C'est-à-dire que M est une partie de l'ensemble A des arêtes telle que Un couplage maximum est un couplage contenant le plus grand nombre possible d'arêtes.

Afficher plus

Séances de cours associées (27)

Algorithme de changement cupide : Optimisation et stabilité

Explore l'optimalité de l'algorithme de changement gourmand et la stabilité de la correspondance maximale.

Algorithmes et croissance des fonctions

Couvre les algorithmes d'optimisation, l'appariement stable et la notation Big-O pour l'efficacité de l'algorithme.

Algorithmes: Stable Matchings

Couvre le concept d'appariement stable et l'algorithme de Gale-Shapley.

Algorithmes: Stable Matchings

Couvre le concept d'appariement stable et l'algorithme de Gale-Shapley.

Matroids: Intersection matroid

Couvre le concept de matroids, se concentrant sur l'intersection matroid et les propriétés des sous-ensembles d'un ensemble de sol.