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

Algorithme de changement cupide : Optimisation et stabilité

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 l'algorithme de changement gourmand pour les pièces de monnaie américaines, prouvant son optimalité en utilisant le moins de pièces possible. Il explore également la stabilité de la correspondance maximale dans le problème du mariage, en introduisant l’algorithme de Gale-Shapley.

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 (23)

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.

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.

Maximum cardinality matching

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph G, and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

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.

Maximum weight matching

In computer science and graph theory, the maximum weight matching problem is the problem of finding, in a weighted graph, a matching in which the sum of weights is maximized. A special case of it is the assignment problem, in which the input is restricted to be a bipartite graph, and the matching constrained to be have cardinality that of the smaller of the two partitions. Another special case is the problem of finding a maximum cardinality matching on an unweighted graph: this corresponds to the case where all edge weights are the same.

Afficher plus

Séances de cours associées (24)

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.

Problème de mariage: Algorithme de Gale Shapley

Couvre le problème du mariage et l'algorithme de Gale Shapley pour trouver des correspondances stables.

Algorithmes et croissance des fonctions

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

Matching bipartite non pondéré

Introduit l'appariement bipartite non pondéré et sa solution en utilisant la programmation linéaire et la méthode simplex.