Les listes, files et piles constituent une partie importante du programme de terminale en NSI [3]. Dans cet article on va voir le cas emblématique d’un des plus vieux problèmes de mathématiques « récréatives » connues, et l’utilisation de files pour trier des entiers en parallèle. Voici par exemple comment on peut trier 5 entiers avec 3 files, en ne défilant qu’à la fin :
En quoi ces versions sont-elles améliorées ? On remarque que la fonction dup par exemple, s’applique à une pile donnée en argument, ce qui permet de programmer en Forth avec plusieurs piles.
Pour aller plus loin, on peut également programmer en PostScript [1] et même y faire un peu de Sofus :
Et ce jeu de Donald Knuth permet de se familiariser avec la notion de pile. Il s’agit d’utiliser une pile pour trier des nombres.
Une variante du jeu précédent est inspirée par le sujet donné au concours ENS en 2011, lequel montre comment on peut trier des entiers avec plusieurs [2] files :
Un invariant de l’algorithme est « toutes les files sont triées ».
Par exemple pour trier la liste 4,2,1,5,3 (une permutation des 5 premiers entiers), on a besoin de 3 files. Au départ les files sont vides :
L’élément 3 peut donc être placé sur n’importe laquelle de ces files, par exemple celle du haut (la bleue) :
L’invariant impose que l’élément 5 ne soit pas placé sur la même file car sinon, en bout de compte, il serait défilé après le 3 et donc placé avant. On peut le placer sur la file 2 (verte) par exemple :
L’élément 1, a contrario, peut être placé sur n’importe quelle file, car il est plus petit que les éléments y figurant déjà. Par exemple on peut l’ajouter à la file bleue :
2 est plus grand que 1 et ne peut donc plus être placé sur la file bleue. Par contre il est plus petit que 5 et peut être placé sur la file verte :
Jusqu’ici on s’en tirait avec seulement 2 files. Mais 4 est à la fois plus grand que 1 et que 2, et la file du bas (rouge) est donc nécessaire pour accueillir ce 4 :
Au moment où on a placé le 5 sur la file verte, on aurait pu le défiler immédiatement puisqu’il était déjà à sa place. Mais cela ne change rien (le sujet demandait de le prouver) si on préfère attendre que la liste de départ soit vide, pour défiler tout. En commençant bien entendu par le 5 :
En attribuant à chaque nombre de la permutation de départ, la couleur de la file qu’il a traversée au cours du tri, on obtient une coloration d’un graphe :
Il s’agit d’un graphe de permutation. Il représente la relation symétrique « est inversé avec ». Par exemple dans la permutation 4,2,1,5,3 on constate que 4 est placé avant 2 (alors qu’il est plus grand que 2), alors il y a une arête entre 2 et 4 sur le graphe ci-dessus.
Pour dessiner un graphe de permutation, on peut donc utiliser la fonction Python suivante :
Des résultats sont au programme de NSI, sur la complexité de certains algorithmes de tri :
Le tri par insertion est quadratique (programme de 1re)
Le tri par sélection est quadratique (programme de 1re)
Le tri fusion est en n×log(n) (un des exemples possibles en Tle, à propos de la méthode « diviser pour régner »).
Il est alors naturel de se demander quelle est la complexité du tri par files. Si on dispose de k files pour trier une liste de n entiers :
on va n fois effectuer un enfilement (vers une des k files) depuis la liste de départ
on va n fois effectuer un défilement (depuis une des k files) vers la liste d’arrivée.
mais avant chaque enfilement on cherche où enfiler, ce qui nécessite de chercher la première file qui restera triée après l’enfilement : linéaire par rapport à k ; et avant chaque défilement on cherche le plus grand des éléments défilables, qui est celui qu’on défile : là encore complexité linéaire par rapport à k.
En résumé, le tri en utilisant k files est linéaire par rapport à k et par rapport à n.
Mais dans le pire cas (liste triée dans l’ordre décroissant) on a besoin de n files (k=n) et du coup, la complexité de cet algorithme de tri est quadratique.
Il est rare que beaucoup de files soient nécessaires, parce que peu de permutations nécessitent beaucoup (environ n) de files. Pour étudier la répartition statistique des nombres de files, on répète un grand nombre de fois l’opération de mélanger (shuffle) au hasard une liste puis la trier en comptant les files qui ont été nécessaires à ce tri. L’algorithme est basé sur le fait que le nombre de files nécessaires est égal à la longueur de la plus grande sous-suite décroissante. On calcule cette longueur tout simplement en comptant les files, dans une fonction lpgsd (longueur de la plus grande sous-suite décroissante) :
Le problème original est connu sous le nom de problème de Josèphe. Il s’agit d’un problème de permutation lié à des formulettes d’élimination. C’est d’ailleurs cette version plus pacifique que nous allons illustrer ici, comme l’indique le titre de la section.
L’origine historique du problème de Josèphe n’est pas complètement déterminée. On l’attribue à Flavius Josèphe, historiographe judéen du Ier siècle, ayant beaucoup écrit sur les conflits de son temps entre Rome et Jérusalem, mais le travail de Laurent Signac [3] conclut que c’est probablement les Problèmes plaisants et délectables de C.G. Bachet [4] qui ont fait connaître le problème de Josèphe.
Le plouf-plouf (ou pouf-pouf, ou ploum-ploum, ou pia-pia, ou trou-trou etc.) permet de choisir un joueur en éliminant successivement tous les autres. Un des participants joue le rôle de meneur. Tous les enfants se mettent en cercle,
[...]
Le meneur chante une comptine, en pointant du doigt successivement tous les enfants du cercle à chaque temps de la comptine. L’enfant désigné en dernier est éliminé, et le processus recommence avec les participants restants.
But
Nous allons modéliser cette activité enfantine par des objets informatiques au sens de la Programmation Orientée Objets, un des thèmes de chapitre du programme de la spécialité NSI en Terminale [5].
Nous verrons deux modélisations. La première colle au sujet original : il s’agit d’une ronde, avec une entrée (celle désignée par le meneur). La seconde transforme cette ronde en file indienne. Dans les deux cas, un type abstrait de données (TAD) sera à l’honneur.
Dans ce jeu, l’enfant est dans une ronde. Nous avons besoin de l’identifier, par son prénom par exemple. Il a un voisin à sa gauche (bleu pour les petits qui ne maîtrise pas encore le concept de gauche-droite) et un sa droite (rouge).
Voici comment en Python on peut définir un enfant :
Sans nous attarder pour le moment sur les détails syntaxiques (__init__, self) on peut simplement constater que l’objet informatique Enfant est bien constitué d’un prenom et de deux voisins, non définis. L’enfant qui n’est pas dans une ronde n’a, en effet, pas de voisins. Le None représente le rien en Python [6].
La création d’un nouvel Enfant (informatique) se fait par l’appel à la fonction Enfant(), en lui passant un prénom en argument. Quelques exemples :
Elle est définie par une entrée (l’enfant pointé par le meneur) et un nombre d’enfants. On peut aussi, mémoriser le nombre d’enfants de cette ronde. Lorsqu’on décide de créer une ronde, au départ elle est vide.
Il va falloir la remplir des enfants présents. Dans la vraie vie, cette ronde se constitue dans un joyeux désordre, chaque enfant se plaçant comme il veut. En informatique il est plus simple d’organiser un peu les choses. Nous allons intégrer les enfants un par un :
d’abord l’entrée, ie l’enfant pointé par le meneur
puis les autres, en les insérant à la gauche de cette entrée.
Avant de présenter les opérations sur notre ronde d’enfants, et notamment son remplissage ordonné, voici une représentation simplifiée d’une ronde de 5 enfants dont les prénoms ont été réduits à des numéros. Cette ronde a été créée par un appel Ronde() puis initialiser avec 5 enfants, cette opération est décrite dans le bloc suivant.
self ici désigne la ronde elle-même. La ronde tente d’insérer en son sein, un nouveau à gauche d’un enfant déjà en place. inserer_a_gauche procède comme suit :
la ronde demande à l’ancien d’accueillir le nouveau comme voisin de gauche
la ronde incrémente son nombre d’enfants de 1
Et c’est tout. On touche ici un principe fondamental de la POO : les objets se transmettent des ordres, ou plus poliment, des messages. Ainsi la définition de la méthode inserer_a_gauche est extrêmement simple, reportant une partie du travail sur un autre objet (un Enfant) :
Revenons donc à l’enfant qui doit accueillir un nouveau à sa gauche dans la ronde. Pour cela il lui faut effectuer les étapes suivantes (que l’on peut tenter de faire trouver en faisant l’opération dans une vraie ronde) :
Présenter le nouveau comme le voisin de droite de son voisin de gauche
Présenter son voisin de gauche comme étant le voisin de gauche du nouveau
Se présenter comme le voisin de droite du nouveau
Prendre le nouveau comme voisin de gauche
Dans cet algorithme décrit en français, c’est l’enfant qui fait l’accueil qui parle dans la version pythonesque, ce sujet est représenté par le mot-clé self. La méthode accueillir_a_gauche pour un Enfant :
Si vous avez été attentif, vous aurez noté que cela ne fonctionne pas. En effet, lorsqu’on crée l’entrée, ie l’insertion dans la ronde du premier enfant, celui-ci n’a pas de voisins. Dès lors, au moment d’accueillir le second, notre enfant isolé ne peut pas effectuer l’étape 1 : il n’a pas de voisin de gauche. Pour régler le souci, le plus simple est de dire qu’un enfant isolé peut se considérer comme ses propres voisins, dans une ronde où il est seul.
Ce qui nous donne une nouvelle définition de notre Enfant informatique :
Résoudre le problème c’est effectuer la réduction de la ronde jusqu’à n’avoir plus qu’un enfant. Nous devons effectuer les tâches suivantes :
A partir de l’enfant point d’entrée, il nous faut, grâce au pas (qui est le nombre de temps de la comptine) trouver l’enfant qui devra quitter de la ronde
Demander à l’enfant de quitter la ronde
Déplacer l’entrée de la ronde à la droite de l’enfant retiré
Recommencer au 1 jusqu’à ce qu’il n’y ait plus qu’un seul enfant dans le cercle
Ce qui, remis dans un ordre différent donne :
Tant que le cercle comporte plus d’un enfant :
on avance de pas enfants vers la droite à partir de l’entrée de la ronde
on place l’entrée de la ronde à droite de cet enfant
l’enfant sélectionné quitte la ronde
Il ne vous aura pas échappé que pour l’instant il n’a jamais été question de pas dans notre ronde. C’est effectivement une information manquante, qu’il faut mémoriser lors de la création de la Ronde. Nous prendrons ici une valeur par défaut de 2.
Et voici la traduction Python dans une méthode de notre classe Ronde :
A l’instar de la méthode d’insertion, demander à un enfant se quitter la ronde consiste à :
demander à l’enfant de se retirer, sans rompre le cercle
décrémenter de 1 la longueur de la ronde
On pourrait aborder le cas particulier du cercle à 1 élément et qui se retrouve donc vide... mais dans le cadre de ce problème, nous avons vu que le cercle contiendra toujours au moins 1 enfant. Nous pouvons donc ignorer ce cas particulier ce qui simplifie les choses. Voici la méthode de la classe Ronde :
On pourrait réaliser une activité débranchée pour faire découvrir les étapes à suivre pour qu’un enfant se retire du cercle, sans que ce dernier ne soit rompu. Voilà ces étapes :
L’enfant dit à son voisin de droite : « ton nouveau voisin de gauche est mon voisin de gauche »
L’enfant dit à son voisin de gauche : « ton nouveau voisin de droite est mon voisin de droite »
Nous avons maintenant complété notre modèle. On ne peut que constater la facilité d’écriture de la programmation objets qui permet de traduire presque mot à mot les actions à réaliser sur les objets du monde réel. La classe Ronde accompagnée de la classe Enfant implémente ici un type abstrait de données liste chaînée. Il s’agit d’une liste circulaire doublement chaînée. Cette structure est hors programme de NSI. Ne pourrait-on pas modéliser par une autre structure de données ?
Dans cette variante, on imagine la ronde déroulée et transformée en une file d’attente. Ici par exemple Astérix qui est en tête de file, se voit relégué en fin de file par le centurion :
Une fois qu’Astérix est en fin de file, le centurion élimine du jeu, le guerrier goth (en pantalon jaune) qui va donc sortir définitivement du jeu :
En effet le centurion élimine un joueur sur deux et relègue les autres joueurs à la fin de la file. En regardant la file ci-dessus de gauche à droite, on voit que
le second goth (en fourrure) est à son tour relégué en fin de file,
le grec est éliminé,
l’égyptien est relégué en fin de file,
le breton (en flanelle bleue) est éliminé,
le belge (en chemise à carreaux) est relégué en fin de file.
Ainsi, lorsqu’Astérix est à nouveau en tête de file, celle-ci est composée d’Astérix, suivi par le goth en fourrure, suivi par l’égyptien, suivi par le belge. Astérix est éliminé (puisque juste avant lui, le belge était relégué en fin de file), et
le goth en fourrure est relégué en fin de file,
l’égyptien est éliminé,
le belge est relégué en fin de file, laquelle est maintenant constituée du goth en fourrure et du belge.
Mais comme le belge vient à nouveau d’être relégué en fin de file, le goth en fourrure est éliminé, et le belge se retrouve à nouveau en tête de file : il est le gagnant du jeu puisqu’il reste le seul dans la file.
Ce jeu est une métaphore d’un système d’exploitation, les guerriers dans la file symbolisant des processus en attente. Lorsqu’un processus quitte momentanément la file, il est dans l’état en cours, et :
s’il retourne dans la file c’est que le système d’exploitation l’a remis dans l’état en attente ;
s’il est éliminé c’est que le système d’exploitation l’a mis dans l’état terminé.
Type abstrait de données
Imaginons le meneur debout devant la file d’enfants : pendant qu’il égrène les temps de la comptine, il demande à l’enfant en tête de file d’aller se placer derrière. Lorsque la comptine s’achève, l’enfant de tête est éliminé.
Dans une file, l’enfant est toujours identifié par son prénom, mais il n’a plus de voisins à sa gauche et à sa droite. Il a un voisin devant lui dans la file et un voisin derrière lui : un précédent et un suivant. On pourrait modéliser les deux. On retombe sur une structure doublement chaînée, qui est hors programme officiel de NSI [3]. Peut-on choisir une seule liaison entre les personnes de la file ?
Pour faire le bon choix, il nous faut voir les opérations à effectuer sur une file.
Arrivée dans une file
La queue de la file doit dire que son suivant est ce nouveau
De plus, en cas de file vide au départ, la tête c’est aussi ce nouveau
On a une personne de plus dans la file
La file avance
Si la file n’est pas vide : la tête de file devient le suivant de la tête
Si la file ne contenait qu’un seul élément, on doit aussi déplacer la queue de la file.
Si chaque individu de la file mémorise le précédent, on constate que faire avancer la file est moins évident. En effet, comment dire à la tête de pointer la personne derrière elle ? Il faudrait alors partir de la queue de la file et avancer jusqu’à ce que le précédent soit la tête. Le choix de modéliser le suivant s’avère donc le meilleur.
Nos nouveaux objets
On garde donc le suivant comme liaison entre les individus :
Dans une file d’attente, une nouvelle arrivée se met à la queue. Avec le cas particulier que si la file était vide, la tête et la queue sont la même personne. Pour l’avancée de la file, la file ne doit pas être vide.
En utilisant le module graphviz il est possible de générer des graphes orientés (objet Digraph) qu’on peut mettre à jour à chaque étape. Les images ainsi obtenues, permettent la création d’une petite animation. Avec 7 protagonistes (enfants ou chevaliers), et un pas de 2, le survivant porte le numéro 7.
La file de départ : 1 en tête de file, 7 à la queue :
Le pas étant de 2, 1 est invité à passer derrière, 2 se retrouve en tête :
2 est éliminé, 3 se retrouve en tête...
...et passe à l’arrière puisque le meneur compte Un sur lui, 4 se retrouve en tête :
Nous avons vu, grâce à ce petit problème d’élimination la possibilité de manipuler deux structures de données abstraites : une liste circulaire doublement chaînée et une file. La programmation orientée objets autorise une description (relativement) naturelle des propriétés et des actions de nos objets réels.
Ce type de modélisation peut-il faire l’objet d’une séance d’introduction à presque tous les thèmes du chapitre Structures de Données du programme de la spécialité NSI de Terminale [3] ?
En fait, dès lors qu’on n’utilise que ses méthodes pop(0) (retrait en tête de file) et append (rajout en queue de file) une liste de Python se comporte comme une file.
Le mot file étant réservé en Python (c’est un fichier), on appellera queue la file en question (comme dans l’expression « faites la queue » sauf qu’ici le gagnant du jeu est celui qui a réussi à faire la queue le plus longtemps possible). Alors
sortir un joueur de la file (celui qui est en tête), se fait par queue.pop(0)
renvoyer le premier faire la queue, se fait donc par queue.append(queue.pop(0))
mercredi 3 mars 2021, 14h-18h : Saint-Denis, PTU, amphi A177
mercredi 7 avril 2021, 14h-18h : Le Tampon
mercredi 2 juin 2021, 9h-12h et 14h-17h : colloque de fin d’année, Saint-Denis, PTU, amphi A177
Le site Computing : The Human Experience est une source précieuse sur l’histoire de l’informatique, avec de multiples entrées suivant les individus, les artéfacts, les concepts, les institutions, les dates et les lieux.
Sur smartphone Android, Wabbitemu est une calculatrice TI open source - avec ROM open source également disponible [1]. Cette application propose une parfaite réplique des calculatrices utilisées dans nos classes (choisir la ROM open source TI 83+). L’application Wabbitemu est gratuite et se télécharge sur Google Store
Sur iPhone, il y a GraphNCalc83, application propriétaire et payante mais vraiment pas chère comparée au prix d’une réelle calculatrice.
[1] mémoire interne indispensable pour que la calculatrice marche
Une application extraordinaire pour donner le goût de la géométrie à vos élèves : Euclidea propose des challenges géométriques progressifs à réaliser en géométrie dynamique à la règle et au compas.
L’application est disponible en ligne , mais aussi sur tablettes et smartphones.
Du même auteur, on relève deux applications autour du théorème de Pythagore : Pythagorea et Pythagorea 60°, mais surtout XSection (uniquement sur tablettes ou téléphones Apple), qui correspond parfaitement au programme de seconde sur l’espace, avec des sections progressives à faire.
Canopé - CRDP académie de Besançon a le plaisir de vous informer de la mise en ligne de sa nouvelle application Mathador pour iPad et iPhone.
Un outil pour devenir accro du calcul mental !
La maison des mathématiques et de l’informatique de Lyon a été inaugurée le 10 octobre 2012. Elle proposera des expositions, des ateliers mathématiques et des conférences. Ses autres missions sont de fédérer, d’organiser et d’amplifier les diverses actions de diffusion de la culture mathématique qui ont lieu à Lyon et dans sa région.
L’an 2013 sera une année mondiale sur le thème « Mathématiques de la planète Terre » (MPT).
Des activités se tiendront partout autour de la planète : ateliers, groupes de recherche conjoints, écoles d’étés, activités pour le public et les médias, activités dans les écoles et numéros spéciaux de journaux scientifiques.
En France, la semaine des mathématiques 2013 sera rattachée à ce thème.
Le projet Klein vise à construire une communauté d’apprentissage sur les liens entre les mathématiques scolaires et la recherche contemporaine en sciences mathématiques. Dans ce but, une “vignette de Klein”, un texte court sur un sujet particulier de mathématiques, est publiée chaque semaine sur ce blog.
Une série de vidéos réalisées par le CRDP de Créteil sur le thème Les mathématiques : paradigmes ou outils de savoirs d’aujourd’hui ? Premiers conférenciers : Valérie Masson-Delmotte, Dominique Barbolosi, Marc Fort, Jean-Pierre Raoult, François Legendre
Commentaires