1 Problème du secrétaire[modifier le wikicode]
Le problème du secrétaire, aussi appelé problème de l'embauche, est un célèbre problème mathématique et algorithmique relevant de la théorie de l'optimisation et des probabilités. Il illustre comment choisir la meilleure option dans une séquence de candidats ou d'éléments présentés un par un, sans possibilité de revenir en arrière.
1.1 Description du problème[modifier le wikicode]
Imaginez que vous êtes un employeur devant choisir le meilleur candidat parmi un ensemble de postulants. Vous rencontrez chaque candidat un par un dans un ordre aléatoire, avec l'obligation de prendre une décision immédiate de sélection ou de refus pour chaque candidat — sans pouvoir revenir en arrière. Le but est de maximiser la probabilité de choisir le meilleur candidat (le plus qualifié).
Le dilemme est évident : faut-il recruter le premier excellent candidat rencontré ? Ou attendre de voir d'autres candidats au risque de perdre les premiers bons éléments ?
1.2 Solution classique[modifier le wikicode]
La stratégie optimale, fondée sur les mathématiques, consiste à rejeter systématiquement la première partie (environ 37 %) des candidats en les utilisant comme références sans les sélectionner, puis à choisir le premier candidat qui est meilleur que tous ceux observés jusque-là.
Plus précisément :
- Soit n le nombre total de candidats.
- Rejeter les premiers r candidats sans les choisir, où r est approximativement égal à n/e (e ≈ 2,71828).
- À partir du candidat r+1, sélectionner le premier candidat qui est meilleur que tous les précédents.
- Si aucun candidat ne dépasse cette qualité, choisir le dernier.
Cette stratégie maximise la probabilité de choisir le meilleur candidat, avec une probabilité asymptotique proche de 1/e ≈ 37 %.
1.3 Applications et variantes[modifier le wikicode]
Applications :
- Embauche d'un salarié (d'où son nom).
- Choix de la meilleure offre dans des enchères ou ventes aux enchères.
- Sélection d'un partenaire dans les décisions personnelles.
- Processus décisionnels en intelligence artificielle et apprentissage automatique.
Variantes :
- Choix avec plusieurs sélections possibles.
- Sélection avec un coût d'observation ou de rejet.
- Ordre non aléatoire des candidats.
- Altérations dans le modèle d'information partielle.
1.4 Humour et anecdotes[modifier le wikicode]
- Un secrétaire désemparé face au « problème du secrétaire » : « Alors je dois rejeter les 37% premiers candidats… Et ceux qui restent ? Je suis censé leur dire 'Vous êtes les meilleurs ?' — réponse directe du candidat : 'Oui, c’est moi, vous m’embauchez ?' »
- Les mathématiciens aiment répéter que leur probabilité d'embauche est ~37%, c’est rassurant, ça leur permet de se concentrer sur la preuve plutôt que sur l'entretien.
1.5 Voir aussi[modifier le wikicode]
1.6 Références[modifier le wikicode]
Erreur de référence : La balise <ref> définie dans <references> n’a pas d’attribut de nom.