MPO 108 - Le problème de la secrétaire

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

MPO 108 - Le problème de la secrétaire

Message par Schraf »

Le problème de la secrétaire

Vous souhaitez embaucher la meilleure secrétaire parmi N candidates. Pour cela, elles sont interrogées une par une dans un ordre aléatoire mais vous devez prendre une décision juste après l'entretien, à savoir l'embaucher ou passer à la suivante.
Vous pouvez bien entendu classer la candidate par rapport à celles déjà vues mais vous ne connaissez pas les qualités de celles qui ne sont pas encore passées.

Quelle est la stratégie optimale pour maximer votre chance de sélectionner la meilleure candidate ?

Pour ce MPO, vous aurez en valeur d'entrée uniquement le nombre N de secrétaires qui viennent postuler pour le poste. Leurs qualités seront des nombres entre 0 et 1 (exclus) tirés aléatoirement par la machine au moment de l'entretien (donc inutile de les mémoriser quelque part avant de lancer votre programme)

La calculatrice affichera le numéro (entre 1 et N) de la secrétaire retenue ainsi que sa qualité.

Exemples :

Code : Tout sélectionner

MPO108(40)			# 40 secrétaires se présentent
(19, 0.9582957304815056)	# La n°19 a été retenue avec une qualité de 95,83 %

MPO(100)			# 100 secrétaires se présentent
(46, 0.9844756088813564)	# La n°46 a été retenue avec une qualité de 98,44 %
Bien entendu vous ne trouverez pas les mêmes valeurs à chaque fois mais il existe un algorithme très simple (Que nous noterons ALGO_ZERO) que je vous laisser retrouver sur le net et programmer sur vos machines...

Quelques exemples pour vos recrutements

Code : Tout sélectionner

RECRUT1 = [0.05, 0.1, 0.15, 0.2, 0.25, 0.3, 0.35, 0.4, 0.45, 0.5, 0.55, 0.6, 0.65, 0.7, 0.75, 0.8, 0.85, 0.9, 0.95, 0.98]

Les 20 secrétaires arrivent dans cet ordre et sont à chaque fois meilleures que les précédentes.
L'algorithme ALGO_ZERO devrait vous proposer la 8e secrétaire.

RECRUT2 = [0.95, 0.9, 0.85, 0.8, 0.75, 0.7, 0.65, 0.6, 0.55, 0.5, 0.45, 0.4, 0.35, 0.3, 0.25, 0.2, 0.15, 0.1, 0.05, 0.02]

Les 20 secrétaires arrivent dans cet ordre et sont à chaque fois pires que les précédentes.
L'algorithme ALGO_ZERO devrait vous proposer la 20e secrétaire.

RECRUT3 = [0.336, 0.697, 0.116, 0.396, 0.776, 0.693, 0.49, 0.004, 0.065, 0.023, 0.532, 0.515, 0.953, 0.734, 0.649]

L'algorithme ALGO_ZERO devrait vous proposer la 13e secrétaire.
Sommaire des MPO
Modifié en dernier par Schraf le 11 avr. 2022 20:03, modifié 3 fois.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO 108 - Le problème de la secrétaire

Message par C.Ret »

Ah! C'est une méthode qui m'est très familière, c'est avec cet algorithme que je choisi mes fiancées … :D

Bon, évidemment, je ne leur montre pas mes machines…

La difficulté va être de programmer cela sur l'une d'elles sans qu'elles s'en rendent compte !
Modifié en dernier par C.Ret le 10 avr. 2022 20:46, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
badaze
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 8384
Enregistré le : 12 févr. 2007 18:36
Localisation : Pas très loin de Lyon
Contact :

Re: MPO 108 - Le problème de la secrétaire

Message par badaze »

C.Ret a écrit : 10 avr. 2022 20:29 Ah! C'est une méthode qui m'est très familière, c'est avec cet algorithme que je choisi mes fiancées … :D

Bon, évidemment, je ne leur montre pas mes machines…

La difficulté va être de programmer cela sur l'une d'elle sans qu'elles s'en rendent compte !
Moi. J’ai une autre méthode. :mrgreen:
Tout est bon dans le pocket.
Moi j'aime tout.... Casio, HP, Sharp, TI et les autres sauf que les TI semblent ne pas m'aimer :(
http://www.emmella.fr
Mes Casio - HP - Sharp - TI
Homme invisible.
FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: MPO 108 - Le problème de la secrétaire

Message par FLISZT »

J'ai trouvé un (le ?) site qui indique une méthode et précise que ce problème date des années 60.
Jamais je n'aurais trouvé cette méthode tout seul !

Je ne sais pas si je dois indiquer le lien tout de suite…
Dans le doute, je dirai seulement qu'Il se termine par .fr :mrgreen:
et qu'il contient le sigle cnrs… :wink:
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO 108 - Le problème de la secrétaire

Message par C.Ret »

Je vois plusieurs intérêts à ce MPO.

Outre le fait, habituel pour un MPO, de voir apparaitre des implémentations astucieuses tirant profit de subtiles capacités de nos calculettes.

Il y a aussi, pour une fois, le moyen de voir différents algorithmes et leur réalisations pratiques respectives. Car , comme souvent en dans les sciences des Statistiques ou de l'Aide à la Décision, il peut y avoir différentes stratégies ou heuristiques.

Mais, ce qui pourrait être rigolo, c'est qu'une fois que nous avons publié nos codes, Eric nous présente ces fiancées et nous verrons qui de nous repartira avec la meilleure et qui d'entre nous devrons se contenter d'un râteau !

Mais, il faut nous mettre d'accord, est-ce que le score de chaque candidate est restraint à un interval (comme le suggère l'énoncé sur un intervalle [ 0 , 1 ] ) ou, comme pour le jeu bien plus palpitant entre 1 et un Googol(°) ? Parce que cela peut conduire à des stratégies d'arrêt forts différentes !


P.S.: (°)
10,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000.
Modifié en dernier par C.Ret le 11 avr. 2022 18:05, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: MPO 108 - Le problème de la secrétaire

Message par Schraf »

@FLISZT : il y a plusieurs sites qui parlent de cette stratégie, y compris Wikipédia. Le PDF estampillé CNRS donne une formule théorique qui peut être intéressante si on veut précisément savoir combien de secrétaires il faut déjà auditionner "pour rien" (A part pour connaître leurs % de qualité) avant de commencer à chercher celle que l'on va recruter.

On trouve par exemple que pour 20 secrétaires qui se présentent, il faudra en auditionner 7 avant de commencer à pouvoir dire "on vous recrute".
Avec 100 secrétaires, il faudra déjà en auditionner 37 (ou 36 si on utilise l'approximation avec un nombre bien connu que je ne dévoile pas).

Tout cela peut sembler bien mystérieux je vous l'accorde...
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5226
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

Re: MPO 108 - Le problème de la secrétaire

Message par bernouilli92 »

bizarre comme algo, car pour moi si la première secrétaire qui arrive a 1 comme qualité, je l'embauche et je ne passe pas à la seconde.
Quel intérêt à voir d'autres secrétaires qui de toutes façons n'aurons pas une qualité supérieure à 1 (je vois d'autres qualités en tant qu'homme mais ca la calculatrice ne le voit pas :-) ) ?
HP, Casio, Sharp, Psion, quelques TI et divers autres
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: MPO 108 - Le problème de la secrétaire

Message par Schraf »

@bernouilli92 : Normalement les qualités sont aléatoires et non pas classées comme dans l'exemple. Je pense que c'est ça que @C.Ret proposait, qu'il n'y ait pas de limite supérieure, ça veut dire que même si la première a eu 1 million de points, rien ne dit que nous ne mettrons pas 10 millions de points à la seconde... Avec le système par pourcentage, c'est clair que si on met 100% à une personne, rien ne sert d'auditionner les autres.

Restons (pour le moment) avec nombres aléatoires entre 0 et 1 exclus, ce qui permettra de ne jamais avoir la perfection.
FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: MPO 108 - Le problème de la secrétaire

Message par FLISZT »

Voici le site en question : http://images.math.cnrs.fr/Decision.html
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: MPO 108 - Le problème de la secrétaire

Message par Schraf »

@FLISZT : Ce n'est pas la page que j'avais vue mais le principe est là. Cependant, j'ai l'impression qu'il y a un décalage de "1" dans les valeurs.

Pour 40 secrétaires par exemple, je pense que c'est 15 qu'il faut auditionner sans rien décider et commencer la recherche à partir de la 16e (sur le site c'est écrit "ne rien décider avant d’avoir vu les 16 premiers")

Pour ma part, je viens de terminer un programme en 34 pas pour le HP-11C, ça a l'air de fonctionner, j'ai utilisé le Program Editor du site Web 11C emulator, vraiment extra pour tout suivre pas à pas.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: MPO 108 - Le problème de la secrétaire

Message par Schraf »

Démonstration (sur TI-83) en vidéo du choix d'une secrétaire parmi 20 candidates. La machine demande le % de qualité de chacune et s'arrête lorsque le choix est fait. Une version moins fastidieuse que de taper les entrées manuellement est de tirer au hasard des valeurs entre 0 et 1 (ou algorithme équivalent).

Code : Tout sélectionner

RECRUT = [0.336, 0.697, 0.116, 0.396, 0.776, 0.693, 0.49, 0.004, 0.065, 0.023, 0.532, 0.515, 0.953, 0.734, 0.649]
Seconde démonstration (sur HP-11C) avec 20 puis 100 secrétaires et des valeurs choisies au hasard. La machine arrête son choix sur la 58e secrétaire avec un score de 95,7%. Remarquez qu'elle commence rapidement à chercher à partir du n°37, comme si elle n'avait pas testé les 36 premières secrétaires, et pourtant... 🤔
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO 108 - Le problème de la secrétaire

Message par C.Ret »

J'avance.
Mais pas vite.
A priori mon premier code sera pour une HP-15C.
Pas trop le temps d'expliquer, mais voici une vue aérienne du principe de fonctionnement :
MPO108 - Salon du Recrutement (noir de monde).png
MPO108 - Salon du Recrutement (noir de monde).png (21.42 Kio) Vu 4569 fois
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: MPO 108 - Le problème de la secrétaire

Message par Schraf »

@C.Ret : Visiblement tu as appuyé trop fort avec ton doigt sur l'écran ! 😆

Si cela vous intéresse, je viens de mettre en ligne une petite vidéo avec pas mal de simulations pour arriver à se convaincre que c'est bien 36,8% des candidats qu'il faut auditionner "pour rien". A la fin de la vidéo vous pourrez voir comment j'ai fait pour rapidement calculer le max des k premiers candidats (ce que j'ai utilisé dans le programme pour le HP-11C ci-dessous)

Code : Tout sélectionner

g P/R

001	36	ENTER		// On duplique le nb N de secrétaires
002	36	ENTER
003	1	1
004	12	EXP
005	10	/
006	43.44	INTG		// Nb k à auditionner pour rien
007	36	ENTER
008	36	ENTER
009	1	1
010	40	+
011	34	x><y
012	15	1/X
013	42.36	RANDOM		// random^(1/k) (Cf. fin de ma vidéo YT)
014	34	x><y
015	14	POWER		// Calcul de la qualité MAX des k premiers
016	42.21.00 LBL 0		// On cherche une secrétaire meilleure que MAX
017	42.36	RANDOM
018	42.20	X>Y
019	22.01	GTO 1		// Trouvée
020	34	x><y
021	43.33	R up
022	43.33	R up
023	1	1
024	40	+
025	42.40	x=y		// On est arrivé à la fin des N secrétaires ?
026	22.01	GTO 1
027	43.33	R up
028	22.00	GTO 0		// Sinon on continue
029	42.21.01 LBL 1
030	34	x><y		// Affichage du n° de la secrétaire choisie
031	33	R down
032	34	x><y		// et de sa qualité
033	31	R/S

g P/R
GTO .000 (Retour au pas 0)
Pour tester le programme sans rien taper, cliquez sur ce lien puis Load Memory et choisir le programme secretaire.txt que vous trouverez ici.

Faites juste R/S. Une fois le programme arrêté, touche x><y pour voir qualité/n° de la secrétaire choisie. Vous pouvez enchainer avec un nouveau recrutement, par exemple 20 R/S.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO 108 - Le problème de la secrétaire

Message par C.Ret »

Schraf a écrit : 14 avr. 2022 12:51@C.Ret : Visiblement tu as appuyé trop fort avec ton doigt sur l'écran ! 😆
Mais non, c'est juste que je suis au centre de l'écran et toutes les candidates sont folles de moi et se précipitent éperdues pour que je les essayent ! Du coup ça fait un peu désordre dans le salon !

Mais, en réalité, c'est pas du tout, du tout, du désordre ...
.. c'est ça l'astuce.

Sinon, bien la vidéo, mis à part les simulations en Python qui m'énervent, le reste est bien expliqué et bien illustré. Juste dommage que tu ne fasses pas l'inverse; bien expliquer le principe PUIS montrer à nos yeux émerveillés et ouverts tout rond comme des soucoupes comme les résultats numériques collent pile et poils au principe général !

Mais bon, c'est ma formation classique qui me fait préférer cet ordre que je trouve plus académique; l'important est qu'il y ait encore des gens capables d'expliquer tout cela et de profiter de la puissance de calcul pour valider par la pratique. Je dois me faire une raison, ça marche aussi dans le sens de circulation que tu empreintes.

Concernant ce MPO, j'allais poster un code très court pour HP-15C, mais un peu bête car il tombe dans les pièges que tu nous a préparé avec les RECRUT que tu nous as donné ci-dessus.

Alors, come je suis encore une fois le seul à proposer un code, je vais présenter un truc que les lecteurs de ce fils pourrons adapter à leurs machines et surtout optimiser et raccourcir.

Je garde sous le coude les versions plus denses pour la contre-offensive… :twisted:


Mais, je dois trouver le moyen de m'extraire du centre du salon envahi par la foule en harpies de mes fans et trouver le moyen d'atteindre mon HP-15C pour recopier le code …
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

Re: MPO 108 - Le problème de la secrétaire

Message par Schraf »

@C.Ret
Mis à part les simulations en Python qui m'énervent
Je crois que c'est ce que l'on appelle des activités de découverte, les profs font ça en début de chapitre pour mettre les élèves en appétit ! 😝

Ok donc ta capture d'écran c'est plutôt la pub AXEa alors !
Répondre

Retourner vers « Tous les Pockets »