Avec APB, au moins on rigole

Dans un article récent, Binaire s’est associé à la demande de l’association Droits des Lycéens pour l’ouverture du code de APB. Nous avons exploré le problème du Mariage stable et présenté un algorithme (pas celui utilisé par APB, alors inconnu) pour résoudre ce problème qui est finalement assez simple algorithmiquement. Nous avons expliqué pourquoi, selon nous, le code devrait être ouvert à tous.

Rappelons l’histoire :

  • Pendant longtemps la distribution des élèves entre les filières a été réalisée de façon opaque et parfois arbitraire.
  • Un programme informatique opaque a remplacé la méthode « manuelle ».
  • Nous étions nombreux à ne pas comprendre cette opacité. Droits des Lycéens a demandé officiellement à avoir accès au programme.
  • Réponses embarrassées.
  • Le Ministre Thierry Mandon décide de « dévoiler l’un des secrets défense les mieux gardés ».
  • Un texte explicatif de la plateforme est dévoilé… mais pas le code
  • La Commission d’accès aux documents administratifs rend un avis qui demande que le code soit ouvert.
  • Un code est fourni par l’Éducation Nationale. Mais il n’est que partiel… et il a été envoyé par La Poste en papier !

Des mois ont passé depuis la déclaration du ministre. Pourquoi est-ce que cela a pris tant de temps ? Cela ne peut être de la mauvaise volonté. Nous pouvons imaginer la traque à l’intérieur du ministère de ce petit morceau de poésie, le code informatique de quelques pages d’APB. Le responsable, M. André-Pierre Beugue, un vague programmeur dont personne ne se souvient trop, a disparu depuis des lunes. Le code source avec lui. Finalement, c’est un officier de la NSA qui a retrouvé le programmeur le plus recherché de la planète, dans un casino de Las Vegas.  M. Beugue y travaillait comme croupier. Il a fort aimablement fourni un code dont il n’est pas possible d’affirmer que ce n’est pas le bon.

Pour nos lecteurs trop jeunes pour comprendre ce que c’est qu’envoyer un texte par la poste, quelques explications. On imprime le texte électronique sur une imprimante (attention pas la 3D). On met la feuille de papier imprimée dans une enveloppe et on colle un timbre. Ne pas oublier d’inscrire l’adresse sur l’enveloppe, pas l’adresse mail, mais « nom/prénom du destinataire, rue et numéro, code postal, ville ». On met l’enveloppe dans la boite jaune au coin de la rue dont vous vous demandiez à quoi elle sert. Si vous ne savez pas ce que c’est qu’une enveloppe ou un timbre, demandez à vos grands parents. C’est dingue après que certains trouvent encore que c’est compliqué d’envoyer un courriel !

Gageons que cette procédure a été proposée par le secrétaire d’État à la Réforme de l’État et à la Simplification.

Le code partiel traite de la « génération automatique de classements aléatoires en production, pour les formations non sélectives. ». Droits des Lycéens demande l’aide des informaticiens pour comprendre le programme.

Serge Abiteboul

Pour aller plus loin :

Fichier 04-10-2016 01 00 55

Comment Alma va décoder le code grâce à David.

David_Wilgenbus_et_123-codezElle c’est Alma, elle a entre 8 ans et 14 ans, disons 8 ans et demi, et elle va commencer à apprendre l’informatique à l’école dans quelques jours. C’est un personnage imaginaire, mais il y a aussi des jeunes comme Eva* ou Mélissa*, précurseurs, et qui existent réellement. Lui c’est David, il est bien réel, et il va nous expliquer, comment et pourquoi on va réussir à apprendre à décoder le code à l’école. Thierry Viéville.

David, Claire et Mathieu.

Alma : Bonjour David, qui es-tu ?

David : Quelqu’un de passionné, qui s’enflamme facilement ! D’abord pour l’astronomie, puis pour l’enseignement des sciences… le développement durable, et plus dernièrement l’enseignement de l’informatique ! J’ai été formé par la recherche, en étudiant le milieu interstellaire (plus particulièrement, la formation des étoiles). Pour simuler l’effondrement d’un nuage interstellaire, qui va donner naissance à des étoiles, il fallait faire beaucoup de programmation, et au siècle dernier, on utilisait un langage informatique un peu archaïque (le Fortran, un peu modernisé dans les années 90). Etant marié à une institutrice (on doit dire « professeur des écoles », officiellement), je me suis intéressé à l’enseignement des sciences et, en 2001, j’ai sauté le pas en rejoignant l’aventure de La main à la pâte. Une bande de passionnés qui se sont retrouvés autour d’une même envie : partager une vraie culture scientifique avec chacune et chacun, et en particulier les plus jeunes. C’est tellement important. Au début, mon travail a surtout consisté à animer un site Internet qui propose des ressources pour les enseignants.

Alma : Mais, tu t’occupais du site en tant qu’informaticien, ou bien des contenus en tant qu’éditeur ?

David : Les deux justement. À la fois les parties techniques et les contenus scientifiques et pédagogiques. C’est très utile de pouvoir intimement lier les deux, pour produire des ressources numériques vraiment bien. Le site « lamap » propose beaucoup de choses pour faire des sciences en classe, et certains projets pédagogiques ont rencontré un grand succès, allant jusqu’à 10 000, voire 30 000 classes pour les plus populaires. Surtout des classes de primaire mais aussi, de plus en plus, de collège.

Alma : Ouaouh, tu sembles une vraie exception !

David : Et bien, bonne nouvelle : non. Mes collègues de La main à la pâte ont tous un parcours un peu atypique, allant de la science à la pédagogie, ou l’inverse, Sur le projet « 1, 2, 3… codez ! », j’ai travaillé avec 2 personnes en particulier : Claire Calmet est généticienne et bio-informaticienne, tandis que Mathieu Hirtzig est un astrophysicien, qui a fait aussi beaucoup de modélisation numérique, et qui est désormais le WebMestre de La main à la pâte. Aucun de nous n’est informaticien de métier, mais chacun de nous est un peu tombé dans la marmite de l’informatique. On fait aussi beaucoup de formation d’enseignants. De manière symétrique, des collègues chercheurs ou enseignante-chercheures, comme Gilles Dowek, Florent Masseglia ou Marie Dulflot-Kremer, sont des scientifiques de renommée internationale, mais qui font aussi beaucoup de médiation scientifique : c’est une facette de leur métier. Ils nous ont beaucoup aidés dans notre projet.

1 … 2 … 3 … codons !

Alma : Dis moi, c’est quoi le livre «1,2,3-codez!» que tu tiens à la main sur la photo ?

David : C’est un outil qui va te permettre de réussir à apprendre à décoder le code à l’école. Ta ou ton professeur des écoles, dispose là de tout ce qu’il faut pour initier à l’informatique.

Alma : Tu veux dire : apprendre à programmer avec Scratch, comprendre comment sont codés les objets numériques (comme les pixels d’une image), ou jouer avec des robots pour maîtriser tout ça ?

David : Oui oui, et grâce à ces activités, comprendre les notions, les fondements de ce qu’on appelle le numérique.

Alma : Je vois. Mais, toi : comment es tu sûr que ça va bien se passer avec ton livre, ce nouvel enseignement ?

David : Parce qu’on a tout fait pour ! Ce projet est le fruit d’un important travail, avec une cinquantaine de personnes mobilisées pendant 2 ans et demi ! En plus des 3 auteurs (Claire, Mathieu et moi), c’est un groupe d’une douzaine de référents scientifiques d’Inria et France-IoI qui ont travaillé avec nous et une trentaine d’enseignants qui ont testé le projet dans leurs classes, ainsi que des formateurs qui les ont accompagnés. On a testé avec des enseignants débutants et confirmés, en milieu rural et urbain, avec ou sans équipement informatique, pour des classes multi-niveau ou mono-niveau, et ceci de la moyenne section de maternelle, à la classe de 6ème incluse.

Alma : C’est énorme ! En fait vous avez développé ce livre d’initiation à la science informatique de manière … scientifique ! Et qu’avez-vous appris de tous ces tests ?

David : Beaucoup de choses, je voudrais en partager trois. D’abord la grande importance des activités débranchées : ce sont des activités ludiques sans ordinateur ni tablette (comme jouer au jeu du robot, ou à passer des pixels à travers un paravent) qui permettent de manipuler concrètement et en situation des notions comme le codage et le décodage ou la notion de langage (pas humain, mais formel). Ce qu’on observe, c’est que si les enfants apprennent juste la programmation ou la robotique, ils vont avoir du mal à conceptualiser ce qu’ils font, et transformer leur savoir-faire en apprentissage structuré. Mais si ils font aussi des activités débranchées, alors l’expérience montre que c’est optimal. Il vont savoir et savoir-faire. L’idéal est de faire des aller-retour entre le débranché et des activités sur machine.

Alma : Ah oui, je vois on joue d’abord au robot sous forme de jeu de rôle, avant d’en programmer un.

Apprendre au fil d’un scénario.

David : Tu as bien compris. L’autre point extrêmement important, surtout en primaire, est de travailler sur un scénario, pas juste un ensemble d’activités. Ainsi, avec les enseignants qui ont pioché ça et là des activités, sans avoir un vrai fil conducteur, les activités prennent moins de sens et cela marche moins bien. On trouve de très bonnes idées, par exemple dans l’excellent livre de Tim Bell sur les activités débranchées, mais cela demande un important travail de scénarisation avant d’en faire un vrai projet de classe. Dans « 1, 2, 3… codez ! », on a testé les activités, mais aussi, et surtout, les scénarios…

Alma : Oui oui j’ai vu ça dans le livre. Pour les CE1 ou avant, ils ont une héroïne qui est plongée dans un monde inconnu, et il faut l’aider à rentrer chez elle avec des problèmes à résoudre au fil des aventures. Ensuite les plus jeunes programment le récit avec Scratch Junior pour raconter l’aventure. Pour les grands de CE2 comme moi, on explore une planète inconnue avec un rover imaginaire, et on fait des tas de choses passionnantes : on fait des algorithmes,  on s’assure de l’intégrité des données, comment les cacher en les chiffrant, ce qui se passe quand on les numérise, …

David : Attends, Alma, je sais bien que ton prénom veut dire « savante´´, mais à … 8 ans, comment peux-tu avoir appris tant de mots si compliqués, ce n’est pas plausible !!!

Alma :  Mais si, justement, nous les enfants, on a à apprendre tellement de choses inconnues, alors ce n’est pas un tout petit peu de jargon qui nous fait peur. Bien entendu, nous ne comprenons les choses qu’à notre niveau, mais en découvrant dès maintenant les fondements du numérique, plus tard, cela nous paraîtra bien plus facile. Et puis c’est tout nouveau, et nous sommes très curieux à nos âges tu sais. Apprendre en jouant, de manière active, c’est vraiment cool. Je suis certaine que cela nous aide aussi pour apprendre le reste : la lecture, l’écriture, le calcul.

David : Bien entendu. Mais là tu triches Alma, une petite fille ne saurait pas dire tout ça 🙂

Alma :  Qui sait 🙂 ? En revanche, David, je n’ai rien compris aux histoires de scénario conceptuel versus scénario pédagogique que le livre propose. Tu peux m’expliquer ?

David : C’est un peu abstrait pour un élève… mais ça parle aux enseignants. Le scénario conceptuel décrit quelles notions doivent être comprises par les enfants et comment passer d’une notion à l’autre par un enchainement logique. Les programmes scolaires donnent un cadre général, mais ils ne sont pas assez précis, ce n’est qu’un squelette et il faut mettre la chair autour : décrire les notions, les liens entre-elles. Nous avons fait cela avec les scientifiques qui ont contribué au manuel.

scenario-conceptuel-123codez-cycle3-vue-partielleAlma : Donne moi un exemple plutôt.

David : Pas de problème. Clique sur cette image, à gauche, tu vas voir une grande figure avec les notions qui doivent être partagées et comment passer d’une notion à l’autre.

Alma : C’est comme une carte avec toutes les idées à découvrir sur le sujet : donc si on maîtrise tout ça, on maîtrise les fondements du numérique ?

David : Voilà, c’est le scénario conceptuel. Le scénario pédagogique, lui, incarne ces notions dans des activités, avec une histoire, comme piloter un rover imaginaire, pour utiliser aussi l’imaginaire des enfants afin de mieux les motiver. Le scénario fait en sorte qu il y a une progression pédagogique de difficulté croissante. Ainsi, ce qu’on a appris nous pose de nouvelles questions, qui vont être traitées dans les séances suivantes. Les enseignants vont sûrement inventer leur propre scénario à partir de ce qui est proposé, mais ils ont une vraie base, clé en main, pour commencer.

Alma : 

Comment la France va réussir le numérique.

David : Tu ne m’écoutes plus ?

Alma :  Euh, si ! mais je me souviens que tu disais que les tests vous ont appris trois choses. Il en reste une, donc.

David : Tout à fait ! On a réalisé que cette ressource peut aussi servir au collège, car pour l’instant les jeunes sont tous débutants. Dès lors qu’ils n’ont jamais fait d’informatique avant, ils ont donc les mêmes premières compétences à acquérir, la forme étant évidemment un peu différente. Donc, même si « 1, 2, 3… codez ! » s’arrête en théorie à la classe de 6ème, l’expérience a montré qu’il pouvait être utilisé jusqu’en 3ème, avec assez peu de modifications.

Alma : Ah oui, mais non ! Ça ne va tenir que pendant quelques années, ce que tu dis. Moi quand je serai au collège, pas question de recommencer la même chose, je veux comprendre de nouvelles choses : comment marche Internet, apprendre à faire des sites Webs, des jeux vidéos, …

David : Oui oui Alma, mais tu sais nous sommes à une étape d’une longue histoire. Au moment où tu naissais, en 2007, Gérard berry expliquait pourquoi et comment le monde était devenu numérique et combien c’était essentiel d’en maîtriser les fondements. Il a fallu du temps pour que les gens comprennent, et en 2013 l’Académie des Sciences lançait une alerte en publiant un rapport « L’enseignement de l’informatique en France – Il est urgent de ne plus attendre ». Nous avons alors lancé cette action « militante » : créer un manuel pour inciter à introduire l’informatique dans les programmes, montrer que c’est possible et que ça marche, parce que le besoin sociétal est là. En cours de route, le ministère fait le choix d’introduire l’enseignement de l’informatique et le projet « 1, 2, 3…codez ! » est devenu une ressource à la fois d’autoformation et de mise en application des programmes.

Alma : Tu veux dire que les enseignants se forment seuls ?

David : Ils peuvent, au pire, s’autoformer à l’aide de ce manuel. Mais, dans l’idéal, il vaut mieux se former avec d’autres, pour partager. On apprend mieux à plusieurs. Le projet Class’Code leur offre une vraie formation en ligne avec des temps de rencontre où ils s’entraident et partagent leurs bonnes pratiques. Class’Code et « 1, 2, 3… codez ! » sont des projets très proches, et qui partagent la même philosophie. L’un insiste sur la formation, l’autre sur les outils… et les deux aspects sont indissociables.

Alma :  C’est formidable, on va toutes et tous piger le numérique, pour réussir …

T’as pas 100 000€ là sous ta semelle de basketteur ?

Alma : … alors il faut donner un manuel à chaque professeur !

David : Idéalement oui.  Mais beaucoup d’enseignants trouvent plus pratique de travailler avec un vrai livre. Donc, nous travaillons avec un éditeur qui nous fait un prix d’ami, ce qui nous a permis d’en acheter plus de 5000 pour les donner aux enseignants qui se lancent. Mais plus de 10 000 autres enseignants en auraient besoin dès maintenant. Pour cela, La main à la pâte recherche des partenaires pour nous aider à financer cette diffusion gratuite. Une dizaine d’euros par classe permet de faire travailler une trentaine d’élèves pendant plusieurs semaines. On a vu des projets moins efficaces ! On peut difficilement demander aux enseignants, qui font déjà l’effort de se former à une nouvelle discipline (en plus de tout le reste qui pèse sur leurs épaules), d’avoir en plus à payer pour se procurer de quoi mettre les nouveaux programmes en application !

Alma : Ah moi je sais calculer avec des « 0´´, tu sais. Et bien 100000€ c’est ce que gagne Tony Parker en deux jours. Donc si dix de ces personnes qui gagnent des millions, offraient un millième de leur salaire, ça marcherait.

David : Quel dommage que tu ne sois qu’un personnage imaginaire Alma, car je suis sûr que tu les convaincrais 🙂

David Wilgenbus et Alma

(*) Des exemples d’enfants précurseurs qui savent décoder le code, et le partage.

– Mélissa, en 6ème, anime des ateliers, grâce à Bibliothèque sans Frontière,  pour initier les filles et les les garçons à coder afin de maîtriser le numérique, source Voyageur du code.

– Eva, 10 ans, utilise le robot Thymio comme robot-artiste, et repartage sur son blog ce qu’elle a appris en robotique et informatique, source Les Echos, Marion Degeorges, 03 juillet 2016.

Vous connaissez d’autres beaux exemples ? Dites le nous, on repartagera !

A.P.B. : La vie après le bac

D’un côté, quelques mois avant l’examen du bac, les lycéens postent sur le site d’Admission Post-Bac la liste de leurs choix d’enseignement supérieur, dans l’ordre de préférence, et limitée à une quarantaine de possibilités; ce qui représente plusieurs centaines de milliers de listes. De l’autre, les différentes formations indiquent le nombre de places disponibles, ainsi que les conditions d’admission; plus de dix mille d’entre elles transmettent ces informations au site. Le jour J arrivé, la moulinette (un algorithme) tâchera d’affecter les élèves aux formations, en satisfaisant « au mieux » les attentes de chaque partie.

Nous avons donc délégué cette tâche des plus importantes, qui ne décide de rien de moins que de l’avenir de nos propres enfants, à un simple algorithme. Mais pas de panique !

Fichier 04-10-2016 01 00 55
© Laure Cornu

Avant tout, évitons le : « C’était mieux avant ».

  • Avant, sans outil de centralisation, il était indispensable de fouiller les recoins des sites des diverses possibilités post-bac, afin d’en extraire les modalités d’une candidature, qui étaient évidemment loin d’être similaires d’une formation à l’autre.
  • Avant, les élèves étaient encore plus mal informés.
  • Avant, les « on-dit » précipitaient déjà des bataillons d’élèves vers quelques formations prestige ou à la mode.

L’appréhension que ressentait un élève d’hier, vis-à-vis des retours de ses multiples candidatures, vaut bien celle de celui qui, aujourd’hui, attend la réponse d’un algorithme. Les dilemmes d’aujourd’hui, pour spécifier l’ordre de la liste des préférences, ne sont pas plus cornéliens que ceux d’hier, qui précédaient un choix entre plusieurs offres.

Traité par des administrations débordées, ou par un programme informatique, le problème est délicat, et on peut évidemment comprendre l’énorme frustration de l’élève qui a candidaté pour la formation de ses rêves, et qui s’en trouve exclu par un simple tirage au sort. Mais la faute ne doit pas être imputée à l’algorithme lui-même. Elle vient d’un choix sociétal de privilégier des filières pour le supérieur non sélectives, où le nombre de candidats dépasse parfois largement celui des places disponibles. A défaut de réelle sélection, on laisse le hasard décider, que ce soit via un algorithme, ou une personne qui joue à pile ou face.

Les avantages de l’algorithme.  De plus, si la procédure est émaillée de maladresses qui pourraient être évitées, l’utilisation d’un algorithme présente des avantages. Avec l’aide de l’informatique, la méthode d’affectation est bien plus efficace, en temps, et en ressources techniques et humaines. Nous verrons d’ailleurs que, d’un point de vue purement algorithmique, le problème est relativement simple. Il est même possible de garantir que l’affectation soit « optimale », c’est-à-dire qu’elle satisfasse un maximum de contraintes parmi celles données par à la fois les élèves et les formations, ce qu’une méthode « à la main » ne permettait pas au bon vieux temps. Surtout, il est possible d’aussi garantir l’équité des affectations, de ne pas favoriser ou défavoriser un élève en se basant sur son origine ethnique, son genre, etc. Nous n’avons plus besoin de devoir nous fier à la conscience morale des jurys : l’algorithme ne se réfère qu’au code qui l’implémente, au programme explicitement écrit, aux règles et non à des interprétations plus ou moins osées.

La difficulté n’est pas tant de trouver un algorithme efficace, que de définir les règles propres à la sélection de candidats. Leur choix est avant tout sociétal.

@Maev59
@Maev59

Est-ce que nous voulons, par exemple, que les candidates soient exclues des filières scientifiques ? Est-ce que nous considérons que les sciences fondamentales ou expérimentales ne leur sont pas destinées ? Ou voulons-nous, au contraire, appuyer la candidature des jeunes filles, plutôt que celles de leurs camarades masculins avec des dossiers sensiblement proches, dans les formations scientifiques de prestige, pour essayer de rattraper le déséquilibre actuel ? Ou encore, souhaitons-nous que l’algorithme ne prenne pas en compte le genre ? Toutes ces règles peuvent être incluses dans l’algorithme (mais pas en même temps). La difficulté est de choisir !

 

Le principal problème d’A.P. B. est son opacité !

La confiance, dans les règles régissant ce processus d’affectation, est essentielle. Les règles adoptées doivent pouvoir être discutées, contestées, approuvées. Mais comment les approuver, comment les contester, comment les discuter, si elles restent confidentielles ?

On connaît les arguments : le code est trop complexe pour être montré ; s’il est connu, les élèves tenteront de contourner le système. Mais aucun n’est vraiment solide. D’ailleurs, le gouvernement a annoncé que les textes qui spécifient l’algorithme en question seraient publiés : « Nous allons donc dévoiler l’un des secrets défense les mieux gardés : l’algorithme d’A.P.B. ! », a affirmé Thierry Mandon, avec un certain humour. Pour nous, il ne suffit pas d’en dévoiler les grandes lignes, que les spécialistes connaissent déjà plus ou moins. Il faut mettre le programme informatique sur la place publique, pour qu’il puisse être débattu, peut-être corrigé, afin que la société l’accepte.

Le gouvernement ouvert

De manière générale, les gouvernements, les administrations, s’appuient de plus en plus sur des algorithmes, qui prennent ainsi une place de plus en plus grande dans notre vie quotidienne. Leur but est d’améliorer le fonctionnement des institutions. Néanmoins, les algorithmes ne décideront jamais à notre place : c’est bien nous qui choisiront les rêgles qui les déterminent.  Il faut bien garder à l’esprit que les choix effectués par un algorithme sont à l’origine implémentés, programmés, écrits, par des humains. Dans une approche « ouverte » du gouvernement (ou de la démocratie), le fonctionnement précis des logiciels qui nous gouvernent n’a pas à être secret. Et effectivement, le Projet de Loi sur la République Numérique inclut un article créant «  un droit d’accès aux règles définissant les traitements algorithmiques utilisés par les administrations publiques et aux principales caractéristiques de leur mise en œuvre, lorsque ces traitements débouchent sur des décisions individuelles ».

Il faut encore aller plus loin ! Nous devrions aussi pouvoir consulter les entrailles des logiciels, au niveau de l’algorithme même, pour pouvoir vérifier les règles sur lesquelles ils prétendent se fonder, et aussi pour pouvoir discuter d’éventuelles modifications. Ceci est nécessaire si nous voulons qu’une réelle confiance règne entre toutes les parties concernées, entre les institutions et les individus.

Il y a toujours un aspect un peu magique dans l’utilisation d’un algorithme dont on n’a pas le début d’une idée quant à son fonctionnement. Pour conclure cet article, nous voudrions vous convaincre qu’un tel  algorithme n’a pas besoin d’être super compliqué. Laissez-nous vous expliquer la démarche générale pour résoudre un « problème d’affectation ».  Ce problème est également connu sous le nom de « problème des mariages stables », c’est bien d’A.P.B. dont il s’agit.

L’algorithme de Gale-Shapley* (1962)

La question des mariages stables en informatique, loin d’être une affaire de mœurs plus ou moins libres, intervient assez régulièrement dans des domaines divers de notre vie quotidienne, d’Admission Post Bac aux sites de rencontres amoureuses par exemple. Le point commun est de former de façon optimale, c’est-à-dire en essayant de satisfaire au mieux les participants, des couples d’éléments de deux groupes distincts d’individus ou d’entités. En l’occurrence, pour Admission Post Bac, nous chercherons à apparier futurs bacheliers et établissements de l’enseignement supérieur. Avec l’optimalité dans un mariage s’agit, il s’agit, par tradition, d’éviter que l’un des partenaires n’ailler chercher son bonheur ailleurs ; il faudra donc s’assurer notamment qu’il n’existe pas deux lycéens associés à deux formations distinctes qui auraient pu échanger leurs affectations pour aboutir à plus de satisfaction pour tous.

Imaginez-vous quelques instants être devenu l’incarnation humaine d’A.P.B. (oui, oui). Vous êtes chargé d’affecter un petit groupe de lycéens, Alice, Bob et Charlie, à un ensemble de formations post-bac, intitulées sobrement A, B et C. On supposera ici que A, B et C n’acceptent qu’un seul étudiant dans leur établissement. Vous connaissez les préférences des participants pour pouvoir réaliser l’affectation.

Pensons d’abord à une méthode naïve : vous affectez les lycéens à des formations au hasard. Supposons que vous ayez affecté Alice en A, Bob en B, et Charlie en C. Il se peut très bien que Charlie ait un dossier qui convient mieux à la formation A, et que Charlie lui-même ne rêve que d’aller dans cet établissement. Autrement dit, il existe deux couples lycéens/formations tels que la formation dans le premier couple préférait le lycéen du deuxième couple, et que réciproquement, ce dernier avait placé plus haut dans ses choix l’établissement du premier couple, par rapport à celui où il se trouve actuellement. C’est un mariage instable, et donc non optimal. Vous avez fait un travail de cochon et il y a de grandes chances pour qu’on se passe de vos services l’année prochaine.

La lourde tâche vous revient donc de « marier » de façon optimale, donc sans cas d’instabilité comme vu précédemment, formations et lycéens.

Commençons par Alice : sa liste indique qu’elle voudrait entrer d’abord en A, sinon en C, sinon en B. Pour l’instant, nous n’avons pas plus d’informations. Puisque tel est le souhait d’Alice, pour le moment nous allons l’associer à la formation A – c’est-à-dire que nous l’affecterons à la formation A si nous ne trouvons pas de meilleure configuration.

Passons à la liste de Bob, qui, lui, voudrait aller d’abord en C, sinon en B, sinon en A. La formation C n’étant affectée à personne pour le moment, nous faisons comme pour Alice : nous associons Bob à C, faute de mieux.

Enfin, Charlie indique sur sa liste qu’il préfèrerait aller d’abord en C, sinon en A, sinon en B. Vous pourriez affecter Charlie à la dernière formation restante, c’est-à-dire B. Mais, si la formation C avait placé Charlie avant Bob dans son classement ? (Il fallait bien que les classements des formations interviennent quelque part. Quand même.) Vous retomberiez alors sur la situation décrite dans le paragraphe précédent, que vous voulez à tout prix éviter.

Ainsi, dans le cas où la formation C a classé Charlie avant Bob, la meilleure configuration rompt le couple Bob/C, et préfère associer Charlie à C. Finalement, comme il n’y a pas d’autre meilleure configuration et que tous les lycéens ont été affectés à une formation, les couples associés sont alors définitifs. Vous obtenez un mariage stable. Victoire !

Le lecteur intéressé pourra trouver une formalisation de l’intuition précédente sur cette page du blog Binaire.

Serge Abiteboul, Inria, Clémence Réda, étudiante ENS Cachan

Cet article est écrit en collaboration avec theconversation.fr.

Pour aller plus loin
•    http://www.pourlascience.fr/ewb_pages/a/article-admission-post-bac-une-informatisation-opaque-37149.php, Gilles Dowek, Pour la Science
•    https://fr.wikipedia.org/wiki/Admission_Post-Bac
•    http://rue89.nouvelobs.com/2016/04/06/admission-post-bac-lyceens-veulent-connaitre-lalgorithme-mystere-263667

(*) Lloyd Shappley a obtenu le Prix Nobel d’Économie en 2012 pour ses recherches sur la théorie des jeux collaboratifs, et ses travaux sur… les mariages stables.

L’algorithme épidémique

sijetaisunalgo

Je serais… épidémique

Nous continuons la rubrique « Si j’étais un algorithme » avec Anne-Marie Kermarrec qui est Directrice de Recherche Inria à Rennes, et récemment CEO and co-fondatrice de la startup « Mediego ». C’est une spécialiste, entre autres, des systèmes distribués en pair-à-pair, et des algorithmes épidémiques. Anne-Marie, une longue contributrice et amie de Binaire, a choisi de nous parler justement d’algorithmes épidémiques. Serge Abiteboul.
Cet article est publié en collaboration avec The Conversation
.

Anne-Marie Kermarrec ©Inria/Lebedinsky
Anne-Marie Kermarrec ©Inria/Lebedinsky

Aujourd’hui, difficile de faire un faux pas quand on est une célébrité sans que le monde entier ne soit au courant… Échapper au buzz quand il se manifeste à l’échelle planétaire  relève de l’impossible : qu’on le veuille ou non, chacun d’entre nous a fini par vaguement se dandiner sur le rythme de Gangnam Style, cet improbable coréen, devenu brutalement une star du Web. Et les exemples foisonnent. On parle d’ailleurs de diffusion virale, on met en garde nos adolescents « soyez vigilants au sujet des contenus que vous postez sur Facebook, ils se diffusent comme une trainée de poudre ». Comment cette information se propage exactement ? Pourquoi est-ce un modèle de communication si efficace ? Et bien, tout cela est orchestré par des algorithmes de diffusion épidémique.

Épidémique ?

Une épidémie est une maladie, comme la grippe, la peste, le choléra, qui se propage très rapidement au sein d’une population et le plus souvent par contagion de personne à personne. Tiens, c’est aussi comme ça qu’une rumeur se propage, très vite, entre des personnes qui se croisent et qui, de manière extrêmement efficace et décentralisée, diffusent cette rumeur. Épidémies et rumeurs se caractérisent par une contamination très rapide et très efficace et il s’avère que les mathématiques sous-jacentes, les mathématiques épidémiques, ont été très étudiées dans de nombreux domaines.

Le rapport avec l’informatique ?

Si nous remplaçons les gens par des ordinateurs et les commérages par des messages électroniques, nous obtenons un nouveau modèle de communication fiable, rapide, capable de passer à l’échelle. C’est le Graal pour diffuser une information rapidement sur Internet !

Justement, les algorithmes épidémiques ont été utilisés dans de nombreux contextes sur Internet : pour diffuser des messages à un très grand nombre de gens, pour améliorer la qualité et la latence du streaming vidéo, pour surveiller de grands systèmes informatiques comme par exemple s’assurer qu’aucun ordinateur n’est défaillant dans un centre de données ou encore tout simplement pour diffuser des données sur les réseaux sociaux.

Pourquoi ces algorithmes épidémiques sont-ils si séduisants pour la diffusion. Dans tous ces contextes, l’objectif est d’envoyer une information (la vidéo, un tweet, une alerte, etc.) à un grand nombre de destinataires. Quels sont les critères qui importent ? Que l’information arrive (1) vite et (2) à tout le monde. Les algorithmes candidats pour ce faire sont nombreux.

@Maev59
@Maev59

Les algorithmes centralisés

C’est la solution qui vient en premier à l’esprit : on confie la responsabilité de l’envoi de l’information à l’ensemble des destinataires à un serveur central. En théorie, le message arrive vite et bien (c’est à dire à tout le monde). Oui, mais deux problèmes se posent quand on l’applique à un système informatique de très grande taille.

  1. Le serveur central doit faire tout le travail et le « tuyau de communication » qui sort de cette entité pour aller sur Internet a bel et bien un diamètre limité (on parle de bande passante). Donc le serveur ne peut pas envoyer simultanément les messages à des millions de destinataires, il faut qu’il les envoie l’un après l’autre… Et ça prend du temps.
  2. Le deuxième problème, c’est que ce serveur central doit rester au top pendant tout le processus. Si pour une raison ou une autre il est défaillant (panne de courant, bug, attaque), les destinataires qui n’avaient pas encore reçu le message ne le recevront pas toute de suite, peut-être jamais. Et il n’est pas nécessaire de vous dire que les ordinateurs ne fonctionnent pas toujours comme ils le devraient. Vous avez sûrement déjà remarqué.

Les algorithmes hiérarchiques

Une alternative est d’organiser tous les destinataires en une hiérarchie, un arbre par exemple, pour se partager le boulot. L’envoyeur original envoie le message à n destinataires, qui chacun le renverront à n autres, etc. Cette solution nous force tout d’abord à organiser tous les destinataires en arbre mais elle présente l’avantage d’éviter qu’un seul serveur fasse tout le travail. Tous les nœuds intermédiaires de l’arbre participent. Le message arrive assez rapidement à chacun. En revanche, si un des ces intermédiaires tombe en panne, tous les destinataires qui en dépendent ne le recevront peut-être jamais. Avec cette technique, on a résolu le passage à l’échelle mais les défaillances posent toujours problème.

@Maev59
@Maev59

Les algorithmes épidémiques, c’est mieux !

Remarquez que les épidémies continuent à se propager si quelques personnes sont clouées au lit avant d’avoir pu transmettre le virus à quiconque et les rumeurs ne sont clairement pas étouffées parce que quelques personnes bien intentionnées résistent à la tentation de les colporter.

Diffuser de l’information avec un algorithme épidémique dans un très grand système consiste donc d’abord à demander à tous les destinataires de participer pour être certain que cela fonctionnera même avec un grand nombre de destinataires. Il faut ensuite accepter qu’un nœud reçoive plusieurs fois le même message : c’est le prix pour résister aux pannes. Enfin, il faut utiliser l’aléatoire pour éviter que le nombre de messages ne devienne abusif et avoir de bonnes propriétés de propagation.

Considérons donc une entité qui doit envoyer une information à un très grand nombre N de destinataires.

  • L’entité choisit au hasard n destinataires et leur envoie l’information.
  • À la réception de ce message, chaque destinataire
    • S’il a déjà reçu l’information, ne fait rien (il est déjà infecté).
    • Sinon, il devient infecté et il contribue alors à la dissémination : il choisit à son tour n destinataires au hasard et leur envoie l’information.
  • Et ainsi de suite, jusqu’à ce que l’information cesse d’être diffusée car l’ensemble des N destinataires a été déjà infecté.

Cet algorithme est rapide, capable de passer à l’échelle et supporte admirablement bien les défaillances des uns et des autres. Il est rapide car le nombre de personnes recevant le message se multiplie à chaque étape lors de la première phase (ensuite bien entendu, il est de moins en moins probable de toucher quelqu’un« non-infecté´´). Mais il est fiable car la probabilité que tous les destinataires reçoivent l’information est très très élevée, y compris si certains destinataires ne transmettent pas l’information, parce qu’ils sont en panne par exemple. Il passe à l’échelle car si chaque participant doit envoyer son information à un nombre n de destinataires environ égal au logarithme de N, alors toutes ses propriétés sont garanties. Logarithme ? Par exemple si chaque entité transmet son information à 6 destinataires dans un système de 1 million de participants, cela convient. De plus sa charge de travail passe à 9, donc augmente très peu quand on passe à un système de 1 milliard de participants. C’est dans tous les cas beaucoup plus faible que le nombre d’amis que chacun d’entre nous a sur Facebook !

Vous avez dit « logarithme´´ ? La définition informatique est très facile !
C’est tout simplement «combien de fois je peux diviser un grand nombre par un autre nombre, disons dix». On essaye ? Prenons N = 1000 destinataires, divisé par dix, cela fait 100, divisé encore par dix, cela fait 10, et encore divisé par dix, voilà 1, divisé par dix, ah … non, ce n’est pas possible, on a fini. Je peux donc diviser N = 1000, n = 3 fois de suite par dix avant de trouver 1. Le logarithme décimal de 1000 est donc 3. Celui de un million ? Ce sera 6, essayez.
En tout, c’est plus facile à expliquer que la définition mathématique 🙂

En fait il existe beaucoup d’autres algorithmes épidémiques qui se distinguent par exemple, par le choix des destinataires, comme les « influenceurs » qui ont de nombreux followers sur Twitter. Pour certains autres de ces algorithmes, c’est le destinataire qui demande, quand il le souhaite, le message, etc.

Des algorithmes, qui fonctionnent un peu comme les épidémies ou les rumeurs, permettent des mécanismes de diffusion puissants, efficaces et robustes aux défaillances, bien adaptés aux très grands systèmes informatiques dont la taille ne cesse d’augmenter. Et puis ces algorithmes peuvent très facilement être mis en œuvre sans aucune autorité centrale, ce qui est pratique dans le cas de nombreux systèmes, par exemple, les systèmes de l’internet des objets, très tendances !

Anne-Marie Kermarrec

Tu quoque, France Inter !?

Cela devient hélas une habitude, on va encore s’intéresser à l’image de l’informatique dans les média, plus précisément au billet de ce matin (6 octobre 2016) de Frédéric Beigbeder sur France Inter. Vu la notoriété de l’auteur, et la station qui l’a diffusé, difficile de laisser passer un tel tissu d’âneries. Décortiquons.

@Maev59
@Maev59

Beigbeder commence par donner une définition un peu obscure, trouvée en ligne, du mot algorithme, en concluant : « c’est scientifique, c’est obscur, je comprends pas, donc les algorithmes c’est n’importe quoi ». Hum ! Puisqu’on en est à railler, remarquons tout de même que Beigbeder commence par aller se renseigner sur… Wikipedia. Wikipedia, une encyclopédie en ligne fabriquée par qui ? Par des geeks. Ces vilains qui mangent des algorithmes, oui, eux-mêmes.

Justement, Beigbeder s’affole ensuite du pouvoir des geeks et de leur emprise sur nos vies et nos données, car, c’est bien connu, tout Zuckerberg est un geek et tout geek est un Zuckerberg. Alors là, on est d’accord : il y a de quoi s’inquiéter, nous vous en parlons assez souvent ici. Sauf que, Zuckerberg est peut-être un geek, peut-être pas (je ne le connais pas, je ne saurais dire), c’est surtout un chef d’entreprise assez malin, et c’est en ça que lui et ses acolytes de Google, Amazon, etc, sont inquiétants. En revanche, la majorité des geeks ne sont pas Zuckerberg. La majorité des geeks sont à l’exact opposé, défendant des outils libres qu’ils se cassent la nénette à produire, souvent gracieusement, pour vous éviter justement Zuckerberg et consorts. Un bel exemple : Wikipedia, un effort collectif sensationnel pour fabriquer un outil encyclopédique en ligne, utile à tous, même aux Beigbeder.

Il faut le dire et le redire, la culture geek n’a rien à voir avec Zuckerberg et s’y oppose même souvent. Qui décortique les incompréhensibles politiques de confidentialité des outils numériques de la vie de tous les jours ? Le Monde, Voici, Le Point, France Inter ? Pas tellement. Si vous voulez protéger vos données, ou simplement comprendre les enjeux qui se cachent derrière les conditions d’utilisation de Google et Facebook, ou la guerre des adblocks, ou les implications de la récente Loi Renseignement, ou encore les discussions numériques en cours au parlement européen, lisez plutôt la presse « geek » (Numérama, Le Journal du net, Slate…), ou suivez les sur Twitter (@manhack, @AdrienneCharmet…).

@Maev59
@Maev59

Quand Beigbeder s’affole des grandes puissances industrielles qui utilisent nos données pour truquer nos goûts et notre vision du monde, c’est à juste titre. Il n’y a pas si longtemps, on parlait d’ailleurs ici des GAFA, des geeks, etc. On a plus de mal à le croire vraiment concerné par la victoire d’une Intelligence Artificielle en Go, qu’il met dans le même panier : artificielle ou non, l’intelligence ne semble pas vraiment son créneau. Mais soit : l’humain est battu au go. La belle affaire.

On passera sur la confusion entre informaticien (qui produit, souvent, des gros méchants algorithmes) et geek (qui est plutôt une sorte de groupe culturel, informaticien ou non). On n’en est plus là. Attardons-nous un instant sur le plus gros reproche fait par Beigbeder aux geeks, le truc qui semble absolument impardonnable à ses yeux : ils ne baisent pas, ils ne savent pas faire du skate, ils ne moonwalkent pas. Alors là, c’est vrai, il m’a eue. J’avais pas réalisé. Je suis informaticienne et malgré une vie sexuelle que je trouve tout-à-fait satisfaisante, je n’ai jamais participé à une partouze, pas plus que je ne sais skater ni moonwalker. Pour quelqu’un dont le boulot est de produire des algorithmes (en optimisation combinatoire, voyez, je vous dis tout), c’est la honte. Avec une telle incompétence, je devrais peut-être arrêter de travailler (note perso : vérifier s’il y a à la fac des formations moonwalk, ou « comment gagner son premier milliard »)… L’argument est excellent, d’ailleurs : puisqu’on est en période d’élections, voilà la question à poser aux candidats : avez-vous couché « avant votre premier milliard d’euros » (sic) ? Non mais c’est important, on veut savoir, on ne va pas élire n’importe qui non plus.

Et finalement, on ne peut que se demander : que cherche-t-il, Beigbeder ? C’est quoi, l’alternative à la dictature annoncée du monstre geek sur le pauvre monde ? On a presque l’impression qu’il part en croisade contre l’existence même d’internet. On était bien, au Moyen-Age, n’est-ce pas, Monseigneur ? Ma foi, peut-être. Peut-être qu’on était mieux sans internet, c’est bien possible. Mais ce n’est pas vraiment la question, car on ne reviendra pas en arrière. Internet est là, il ne s’en ira pas. L’homme est battu au Go, il ne sera pas dé-battu. La vraie question, la voilà : dans ce nouveau monde, on continue à laisser les grosses boîtes du net faire ce qu’elles veulent, et des parlementaires incompétents voter des lois mal fichues, ou on essaie, justement, de se renseigner, de comprendre, et d’aller dans une meilleure direction ?

En conclusion : oubliez les vieux éditorialistes rancis sur des radios trop complaisantes à leur égard (malgré leur bonne qualité générale). Lisez la presse en ligne, écoutez les youtubeurs scientifiques. Vous rigolerez plus, en prime. Par exemple, cette BD bien fichue qui explique qu’un algorithme, ce n’est jamais qu’un truc écrit par un humain.

Charlotte Truchet @chtruchet

Et toi , citoyen-ne-s, coderas tu ?

Tiens ? Voici revenir la semaine du code : Comme les choses ont changé depuis sa première édition de 2013 ! Nos enfants commencent à apprendre un peu d’informatique à l’école, nous comprenons bien mieux ce mouvement populaire et participatif qui célèbre la créativité par le code, montre qu’il est possible de concrétiser ses idées grâce au code informatique, et de démystifier les compétences informatiques, afin de rassembler le plus de gens autour du plaisir d’apprendre ensemble.

Cette année ce sera du 15 au 23 octobre 2016 à de nombreux endroits, avec des robots parfois, en jouant aussi de manière débranchée, mais surtout en codant, programmant … créant quoi !
Plus de 45 pays et une demi-million de participantes et participants en 2015 : jusqu’où irons nous cette année avec tous les autres citoyens du monde ?

C’est aussi au cours de cette semaine que les premières formations Class´Code vont permettre aux profesionnel-le-s de l’éducation de bien initier nos filles et nos garçons à la pensée informatique pour maîtriser le numérique.

Rendez-vous sur http://www.codeweekfrance.org pour participer, proposer, partager, et s’amuser.

Thierry Viéville.

Publié en commun avec Pixees.fr.