Utilisation de l'aléatoire

[jcourant]

Bonjour,
On trouve dans le code «RANDOM.values(1, 999999)» à plusieurs reprises. Je n'ai pas encore lu l'ensemble du code mais il semble que ça serve à départager les candidats. Pour cela, il faut éviter de tomber deux fois sur la même valeur (ce qu'on appelle une collision).

Or le paradoxe des anniversaires (le fait que dans une assemblée de 24 personnes, il y a au moins une chance sur deux que 2 personnes aient la même date d'anniversaire) dit essentiellement que la probabilité d'avoir une collision lors de k tirages indépendants parmi n valeurs équiprobables est importante lorsque k est de l'ordre de racine de n. Si on tire au sort entre 1000 candidats, on y est... (Peut-être que ça n'a pas d'impact par la suite, mais ça n'est pas très bon signe quand même.)

De manière plus générale, l'utilisation d'un tirage au sort ici me semble poser pas mal de questions :

1. Quel est le générateur utilisé ? Est-il vraiment solide ? La graine choisie est-elle de taille suffisamment grande pour qu'on puisse considérer qu'il y a effectivement un choix au hasard parmi à peu près toutes les situations possibles plutôt qu'un choix tordu mais arbitraire entre certaines d'entre elles ?
2. Comment garantit-on que celui qui lance l'algo ne le relance pas si le résultat ne lui convient pas ? Dans les tirages au sort un peu sérieux, on fait appel à un huissier. Ne conviendrait-il pas ici qu'un huissier tire une graine au hasard (avec un procédé physique) et l'introduise dans le système de façon à ce qu'on puisse par la suite faire un audit en cas de contestation.

Ce n'est pas comme si ces questions étaient totalement nouvelles : il existe des protocoles cryptographiques conçus pour pouvoir tirer des valeurs au hasard de façon à garantir que la fraude ne soit pas possible (dans certaines limites). Vu la sensibilité des données manipulées, APB ne devrait-il pas les utiliser ?

Judicaël Courant
(Enseignant d'informatique, c'est cependant en tant que citoyen que je m'exprime ici).

[Sboulahia]

Bonjour,
Le tirage au sort sert à départager les candidats qui postulent à la même licence, avec le même ordre relatif et le même ordre absolu et de même type (AEFE ou non), on est encore loins d'avoir 1000 candidats dans un même tirage

[Sboulahia]

Et la probabilité qu'à une licence, entre deux candidats de même type, de même ordres absolu et relatif et de même nombre aléatoire, seul l'un des deux est admis est négligeable.

[jferard]

Ces points ont déjà été soulevés, bien que de manière nettement moins complète :

• ici, point 3 à la fin du document pour les collisions, sans entrer autant dans le détail (le document est en cours de révision) ;
• concernant la graine, on trouve une mention dans une citation du README.md et cela a été également soulevé dans une issue où, en suivant les liens, ici, toujours avec moins de détails.

Sur le fond, on a vraiment quelque chose qui ressemble à un problème de conception (il y a effectivement les procédés utilisés en cryptographie, mais on pourrait aussi imaginer une solution déterministe, type un hash sur une partie des données (les collisions sont alors réputées rares), etc.).

Mais cela reste très marginal par rapport à d'autres questions, par exemple celle-ci : le numéro d'ordre du voeu d'un candidat pour une formation est stocké dans plusieurs champs de la table a_voe, notamment a_ve_ord_vg_rel, a_ve_ord_aff et a_vg_ord (qui servent à ordonner les candidats de manière plus systématique, le nombre aléatoire restant le dernier recours) et rien ne nous indique la manière dont ces champs sont initialisés : on les imagine séquentiels et commençant à 1, mais que se passe-t-il s'ils sont initialisés à 1 et jamais modifiés pour un candidat ?

[jcourant]

Le mer. 26 oct. 2016, Julien Férard [email protected] a écrit :

Sur le fond, on a vraiment quelque chose qui ressemble à un problème
de conception (il y a effectivement les procédés utilisés en
cryptographie, mais on pourrait aussi imaginer une solution
déterministe, type un hash sur une partie des données (les collisions
sont alors réputées rares), etc.).

Le déterminisme (total) n'est pas une bonne idée a priori. D'une part
parce qu'on peut lui objecter des raisons morales (ça ressemble plus à
de l'arbitraire qu'à du hasard) et d'autre part et surtout parce que ça
permet à quelqu'un qui connaît les données et peut les modifier en
partie d'améliorer son sort (il n'obtiendra pas nécessairement ce qu'il
veut mais il peut «rejouer» tant que le résultat ne lui plaît pas).

Mais cela reste très marginal par rapport à d'autres questions

Je suis d'accord.

TEL : (+33) (0)4 72 50 48 13
GPG public key: 783D F28F DBEA 5600 C0CB A7C4 828A B452 479A 5941

[jferard]

@jcourant difficile de modifier son nom ou son prénom, mais on peut toujours déménager ! C'est donc vrai. La seule vraie bonne méthode, à ma connaissance, c'est celle de la bataille : effectue des tirages aléatoires jusqu'à ce qu'on obtienne une différence. La probabilité de collision sur n tirages tend vers 0 avec n croissant, donc on a l'espoir de parvenir à départager les candidats en un temps raisonnable. Mais pour implanter ça en PL/SQL, c'est une autre histoire : ce genre de problématique ne correspond pas tout à fait à l'idée qu'on se fait d'un traitement batch.

[jcourant]

La seule vraie bonne méthode, à ma connaissance, c'est celle de la
bataille : effectue des tirages aléatoires jusqu'à ce qu'on obtienne
une différence.

Il y en a une autre, meilleur AMHA : la méthode de Fisher-Yates (appelée
aussi mélange de Knuth). Elle est linéaire en le nombre d'éléments sur
un tableau et elle est très similaire à un tri par sélection. Le tri par
sélection consiste à chercher l'indice du max du tableau et à échanger
la valeur à cet indice avec la dernière, puis l'indice du max des n-1
premières valeurs et à échanger la valeur à cet indice avec
l'avant-dernière, etc. La méthode de Fisher Yates fait la même chose
mais au lieu de calculer l'indice d'un maximum, tire l'indice au hasard
( https://fr.wikipedia.org/wiki/M%C3%A9lange_de_Fisher-Yates ).

Mais pour implanter ça en PL/SQL, c'est une autre histoire : ce genre
de problématique ne correspond pas tout à fait à l'idée qu'on se fait
d'un traitement batch.

APB n'a aucune obligation de travailler exclusivement en PL/SQL...

Cela dit, je ne connais de PL/SQL que ce que je viens de regarder
rapidement sur Wikipedia, mais j'aurais tendance à dire que pour
implanter la méthode de Fisher-Yates, on doit pouvoir sans problème
créer un tableau t contenant les clés primaires des candidats à
départager, le mélanger, et en itérant sur le tableau t, attribuer au
candidat de clé primaire t(i) la priorité i. Itérer explicitement sur un
ensemble de candidat n'est pas tellement dans l'esprit SQL mais c'est de
toute façon déjà ce qui est fait dans le code.

[jferard]

@jcourant très intéressant. Je suis resté collé au problème : en supposant la collision inévitable, comment s'en sortir ? Ce cas de figure existe également (dans un réseau par ex. : https://fr.wikipedia.org/wiki/Carrier_Sense_Multiple_Access_with_Collision_Detection, avec la solution mentionnée ci-dessus), mais ici, il s'agit simplement d'ordonner de manière aléatoire des éléments.

Je ne connaissais par la méthode de Fisher-Yates, mais elle me conforte dans une idée simple : il est plus facile et plus rapide de créer du désordre (O(n)) que de l'ordre (O(n²) pour le tri par sélection) !

Concernant le PL/SQL, c'est un langage de batch, donc on peut faire beaucoup de choses, mais ce n'est pas pour autant le bon outil pour tout. Pour mettre en oeuvre un algorithme assez simple comme celui-là, on entrerait déjà dans le dur...