Utilisateur:Infisxc

Moi c'est Infisxc. Je me contente essentiellement de faire des retouches cosmétiques (orthographe, corrections de petites erreurs) dans les projets déjà existants.

Dans la vraie vie, je suis Sylvain Chevillard. Je suis chercheur en mathématiques et en informatique à l'Inria à Sophia Antipolis.

Articles dont j'ai noté qu'ils nécessitaient du travail et sur lesquels je m'investirai prioritairement[modifier | modifier le code]

BCG
Athéisme (manque d'impartialité)
Allain Leprest
Romain Didier (inexistant)
Kenneth Arrow (article inexistant : il faut le traduire de l'anglais)
Tchebychev
Algorithme LLL

Point d'entrée pour du boulot de longue haleine[modifier | modifier le code]

http://fr.wikipedia.org/wiki/Portail:Mathématiques

Marque-page[modifier | modifier le code]

Ébauche d'article sur le problème des mariages stables[modifier | modifier le code]

Le problème des mariages stables est un problème de mathématiques qui s'énonce informellement de la façon suivante : on cherche à créer des couples (hétérosexuels) à partir d'un groupe de n hommes et de n femmes. Chaque homme et chaque femme établit un classement de ses préférences. On veut former n couples, de telle sorte que la situation obtenue soit stable. On dit que la situation est instable lorsqu'il est possible de trouver un homme et une femme qui ne sont pas ensembles, mais qui préféreraient tous les deux être l'un avec l'autre plutôt qu'avec leurs partenaires actuels (autrement dit, ils seraient tentés de demander tous deux le divorce, afin de pouvoir se mettre ensemble). A contrario, on dit que la situation est stable lorsqu'elle n'est pas instable.

Considérons un individu, Jean, qui a été fiancé à Jeanne. Jean aurait préféré être avec Marie. Si la situation est stable, Marie préfère rester avec son partenaire actuel que de se mettre en couple avec Jean.

Voici une formulation du problème des mariages stables en des termes plus formels : on se donne deux ensembles finis H et F (l'ensemble des hommes et l'ensemble des femmes). En toute généralité, il n'est pas nécessaire qu'il y ait autant d'hommes que de femmes (nous supposerons, sans perte de généralité qu'il y a au moins autant de femmes que d'hommes). Chaque homme h de H classe les femmes de F par ordre de préférence. Il n'est pas obligé de les classer toutes (celles qui ne sont pas classées sont celles avec lesquelles il ne veut surtout pas être, quitte à rester célibataire). Formellement, on se donne un ordre total >_h sur une partie F_h de F : f₁ >_h f₂ s'interprète comme "h préfère f₁ à f₂". De même, chaque femme f de F classe les hommes suivant un ordre total >_f portant sur une partie H_f de H.

On assigne à chaque homme une femme (sa fiancée), c'est-à-dire qu'on se donne une injection c : H → F qui à un homme associe sa fiancée. On dit que cette injection est instable lorsqu'il existe h dans H et f dans F tels que les trois conditions suivantes soient réunies :

$f>_{h}c(h)\quad$ (h préférerait être avec f qu'avec sa fiancée actuelle) ;
$h\in H_{f}\quad$ (f veut bien être fiancée à h) ;
f n'est pas dans l'image de c (f n'a actuellement pas de partenaire) ou bien $h>_{f}c^{-1}(f)\quad$ (f préférerait être avec h qu'avec son partenaire actuel).

Si l'injection n'est pas instable, on dit qu'elle est stable. On cherche à savoir s'il existe une injection stable. Si oui, est-elle unique ? Sous réserve d'existence, peut-on déterminer algorithmiquement une injection stable ?

En 1962, David Gale et Lloyd Shapley ont prouvé^[1] qu'il existe toujours au moins une situation stable : ils donnent un algorithme qui s'arrête forcément et qui ne peut s'arrêter que sur une situation stable.

Références[modifier | modifier le code]

↑ D. Gale et L. S. Shapley: "College Admissions and the Stability of Marriage", American Mathematical Monthly 69, 9-14, 1962.

[1] D. Gale et L. S. Shapley: "College Admissions and the Stability of Marriage", American Mathematical Monthly 69, 9-14, 1962.

[1]