Le tri anglais des Bermudes

samedi 19 avril 2014
par  Alain BUSSER

Petite expérience

Voici un algorithme si stupide que personne apparemment n'a encore pensé à l'implémenter:

  1. Créer un tableau d'entiers, allant de 0 à 16 (par exemple).
  2. Trier le tableau dans l'ordre croissant, à l'aide de la fonction de comparaison des entiers (c'est ici que l'algorithme est particulièrement stupide puisque le tableau est déjà trié).
  3. Afficher le résultat.

Essayer le script suivant en cliquant sur le bouton:

Si vous utilisez un navigateur autre que Chrome, il y a de fortes chances que l'affichage soit trié de 0 à 16, comme on s'y attend. Mais sous Chrome, l'affichage est plus surprenant...

Découverte du problème

Le point de départ a été une activité faite avec alcoffeethmique sur l’approximation normale d’une loi binomiale. Le cours sur la loi normale ayant déjà été fait, les élèves étaient familiarisés avec la forme de la célèbre courbe en cloche. Il s’agissait donc de leur faire représenter graphiquement des lois binomiales de paramètre N croissant (avec p voisin de 0,5) jusqu’à ce que la forme de cloche leur paraisse évidente [1]. Pour cela, la version d’alcoffeethmique ci-dessous a été utilisée :

Zip - 313.6 ko
alcoffeethmique pour les stats
logiciel de programmation orienté probas-stats-algo

L’algorithme utilisé pour représenter graphiquement une loi binomiale avec alcoffeethmique est celui-ci :

N = 8
p = 0.4
loi = (binomiale N, p, k for k in [0..N])
diagrammeBatonsTrie loi, 1

Rédigé ainsi, il suffit de modifier la première ligne pour avoir d’autres valeurs de N (mais il faut ajuster le dernier paramètre à la quatrième ligne pour que le graphique soit bien dimensionné). On peut décrire l’algorithme ainsi :

  1. On affecte la variable N à 8 (taille de l’échantillon).
  2. On affecte la variable p à 0,4 (probabilité de succès).
  3. On crée un tableau loi contenant les probabilités que le nombre de succès soit k pour toutes valeur de k allant de 0 à N.
  4. On dessine le diagramme en bâtons de la loi binomiale, en triant les valeurs de k au passage (ceci est nécessaire au cas où ces valeurs n’auraient pas été introduites dans l’ordre croissant).

On obtient alors le diagramme en bâtons suivant :

image/svg+xml

Mais pas toujours : Le graphique ci-dessus a été obtenu avec le navigateur Mozilla Firefox. Mais le même alcoffeethmique avec le même script produit sous Google Chrome un graphique visiblement assez différent :

image/svg+xml 50 0 51 2 1 53 5 3 4 55 9 6 7 8 57 14 10 11 12 13 60 20 15 16 17 18 19 64 27 21 22 23 24 25 26 68 35 28 29 30 31 32 33 34 72 44 36 37 38 39 43 42 40 41 77 54 52 49 45 46 48 47 81 62 61 56 58 59 84 67 63 65 66 87 73 69 70 71 89 78 74 76 75 92 83 82 79 80 94 88 86 85 90 91 93 95 96 97 98 99 100

Comme alcoffeethmique est programmé en CoffeeScript, il est relativement aisé de chercher dans son code source comment sont dessinés les diagrammes en bâtons :

diagrammeBatonsTrie = (dico, ech=400) ->
    nombreBatons = (x for x of dico when x<Infinity).length
    dicotrie=(parseFloat x for x of dico when x<Infinity).sort (x,y)-> x>y
    effaceDessin()
    dessineSegment 20, 440, 620, 440, 'black'
    abscisse = 40-600/nombreBatons
    for x in dicotrie
        abscisse += 600/nombreBatons
        hauteur = 400/ech*dico[x]
        dessineRectangle abscisse, 440-hauteur, 5, hauteur, 'blue'
        dessineTexte x.toString().replace(".",","), abscisse, 460, 'black'

C’est donc la troisième ligne qui effectue le tri croissant selon les valeurs du caractère, qui est responsable du mélange des bâtons. Elle crée, à partir de la liste dico des valeurs du caractère, une sous-liste formée par les seuls éléments qui soient à la fois numériques et finis [2]


Question : Comment Google Chrome trie-t-il les nombres ?

D’où vient cette relation d’ordre étrange ? Des Bermudes [3] ?

En effet le phénomène est parfaitement reproductible et le tri obtenu dépend visiblement de la taille du tableau à trier.

Fonction de tri

La variante suivante du script en haut de page, donne un tri correct par Chrome :

N = 16
tableau = [0..N]
tableau.sort()
alert tableau

Ainsi, par défaut, Chrome trie les nombres dans l’ordre croissant. Mais si on lui demande explicitement de le faire, il ne le fait plus... Et un autre problème surgit alors : cette fois-ci, c’est Firefox qui donne un résultat surprenant :

0,1,10,11,12,13,14,15,16,2,3,4,5,6,7,8,9

Au secours, ils sont tous fous !!! Non, en fait il y a une logique dans l’ordre choisi par Firefox : c’est l’ordre lexicographique. Et c’est parce que les informations dans une page html sont essentiellement textuelles, que les développeurs de chez Mozilla ont fait ce choix. Il est donc nécessaire, hors Google Chrome, de préciser que les nombres doivent être rangés dans l’ordre croissant et non dans l’ordre lexicographique, en fournissant à sort (trier) la relation d’ordre choisie :

N = 16
tableau = [0..N]
tableau.sort (x,y) -> x>y
alert tableau

Cet aspect de la fonction sort (tri de JavaScript est, du point de vue mathématique, une porte ouverte vers un univers vaste d’exercices de statistiques : les notions de médiane et de quartiles ne dépendant que du tri, ces notions peuvent très bien s’étendre à d’autres relations d’ordre que l’ordre naturel des nombres. Par exemple, avec l’ordre alphabétique, la notion de mot médian d’un dictionnaire a du sens et même un sens assez concret...

Trier les algorithmes de tri

En fait, il semble que les différents navigateurs internet utilisent différents algorithmes de tri. Ainsi :

  • Safari utiliserait un algorithme de tri par sélection, inefficace sur de grands tableaux puisque le temps de tri d’un tableau de taille n est proportionnel à n² ;
  • Firefox aurait plutôt opté pour le tri fusion, proportionnel à n ln(n) ;
  • Chrome fait plus compliqué : Selon la taille du tableau et la nature de ses éléments, il choisit entre
  • Quant à Internet Explorer, comme ce n’est pas un logiciel libre, on ne peut pas savoir comment il trie les éléments ; on peut cependant supposer que c’est le tri rapide, puisque son auteur Charles Antony Richard Hoare travaille chez Microsoft qui est propriétaire de Internet Explorer.

La correction du bug

En fait, il n’est (heureusement) pas nécessaire de détecter la nature du navigateur et appliquer un algorithme différent selon le navigateur. Il suffit, au lieu d’une fonction booléenne comme relation d’ordre

(x,y) ->
    x>y

d’appliquer une fonction numérique

(x,y) ->
    x-y

Ce qui a pour effet de réconcilier les navigateurs, Firefox continuant à interpréter la relation d’ordre comme booléenne (un nombre positif étant assimilé à true) et Chrome acceptant enfin de ranger les nombres dans l’ordre croissant. La modification [4] sera faite dans la prochaine version d’alcoffeethmique...

Ainsi, on peut tester en haut de cette page la version universelle du tri d’entiers déjà triés :

N = 16
tableau = [0..N]
tableau.sort (x,y) -> x-y
alert tableau

Celle-ci donne l’ordre croissant quel que soit le navigateur, même dans le triangle des Bermudes...

Cependant, même si on sait comment faire pour que Chrome trie les nombres dans l’ordre correct, tout ceci n’explique pas comment il trie les entiers avec la version en haut de cette page. Et comme Chrome n’est pas un logiciel libre, on ne peut pas consulter son code source pour voir comment est effectué ce tri mystérieux venu d’ailleurs...


Pour essayer d’en savoir plus, on peut faire quelques expériences, ce qui permet d’émettre des conjectures :

  • Si la taille du tableau est inférieure à 10, les entiers sont triés dans l’ordre croissant, comme on peut le vérifier cas par cas ; exemple pour N=9 :

image/svg+xml 0 1 2 3 4 5 6 7 8 9

Par contre dès N=10, l’ordre naturel n’est plus respecté :

image/svg+xml 5 0 1 2 3 4 6 7 8 9 10

  • Pour N supérieur à 9, la médiane est déplacée avant le minimum du tableau ; on le voit pour N=10 ci-dessus mais aussi pour les valeurs suivantes : N=11 :

image/svg+xml 6 0 1 2 3 4 5 7 8 9 10 11

Mais aussi N=12 :

image/svg+xml 6 0 7 2 1 3 4 5 8 9 10 11 12

On voit qu’à partir de N=12, la situation devient plus compliquée que le déplacement de la médiane en première position. Mais en continuant on émet d’autres conjectures :

  • Le premier élément reste en seconde position juste après la médiane ; on l’a déjà vu ci-dessus mais effectivement cela semble rester le cas, avec N=13 :

image/svg+xml 7 0 8 2 1 3 4 5 6 9 10 11 12 13

Puis avec N=16 :

image/svg+xml 8 0 9 2 1 11 5 3 4 6 7 10 12 13 14 15 16

  • Il y a toujours deux éléments insérés entre 0 et 1 : l’élément suivant la médiane, et l’élément 2. Regarder les graphiques ci-dessus, mais aussi pour N=20 :

image/svg+xml 10 0 11 2 1 13 5 3 4 15 9 7 8 6 12 14 16 17 18 19 20

ou N=32 :

image/svg+xml 16 0 17 2 1 19 5 3 4 21 9 6 7 8 23 14 13 12 10 11 26 20 18 15 22 24 25 27 28 29 30 31 32

  • Pour N supérieur à 15, le 5 est placé avant le 3 et le 4, et précédé d’un autre élément plus grand que lui. Là encore, on le voit au-dessus, mais aussi par exemple pour N=64 :

image/svg+xml 32 0 33 2 1 35 5 3 4 37 9 6 7 8 39 14 10 11 12 13 42 20 15 16 17 18 19 46 27 21 22 23 26 25 24 50 34 31 28 30 29 53 41 40 36 38 55 45 43 44 57 49 47 48 59 54 52 51 56 58 60 61 62 63 64

Quant à l’élément placé avant le 5, on peut tenter de conjecturer comment il dépend de N avec ce tableau :

N élément avant le 5
16 11
20 13
25 14
32 19
40 23
64 35
100 53

Édifiant, non ?

Il y a sans doute bien d’autres conjectures à émettre. Et on peut même espérer qu’avec beaucoup d’entre elles, on puisse se faire une idée sur l’algorithme de tri utilisé.

Un groupe de MATh.en.JEANS en culottes courtes y arrivera-t-il avant les développeurs de chez Google en bermudas ?


[1En plus, une semaine avant Pâques, ça aide à reconnaître une forme de cloche...

[2Si x n’est pas un nombre, le test x<Infinity échoue et x n’est pas retenu ; il en est évidemment de même si x est, par un hasard malencontreux, infini.

[3Lieu du siège social de Google, qui développe Chrome, et qui est anglais ; d’où le titre de l’article...

[4Solution découverte par Florian Tobé, mais elle avait déjà été faite dans le code source de DGPad qui avait connu un problème similaire.


Commentaires

Logo de Seb
lundi 28 avril 2014 à 04h31 - par  Seb

Intéressant. Du coup quand on a de vrais traitements à faire sur des données, le mieux est encore d’utiliser un vrai langage de programmation (python ;-) ) à la place de javascript et d’un obscur navigateur web :)

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 13 septembre 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 4 octobre 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 11 octobre 2017, 14h-18h, campus du Tampon
- Mercredi 22 novembre 2017, 14h-18h, campus du Tampon
- Mercredi 7 février 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 7 mars 2018, 14h-18h, campus du Tampon
- Mercredi 4 avril 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 2 mai, 14h-18h, campus du Tampon
- Mardi 5 juin 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 6 juin, 14h-18h, campus du Tampon

Fête de la science

Du 13 au 18 novembre 2017.
Thème : « La recherche à l’heure du numérique »

Semaine des mathématiques

Du 26 au 31 mars 2018.
Thème : « Mathématiques et mouvement »


Brèves

Décès de Roger Mohr

mardi 27 juin

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

dimanche 24 septembre 2017

Publication

766 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

38 aujourd'hui
1180 hier
2101282 depuis le début
17 visiteurs actuellement connectés