Pour un joint…

Serge et Colin nous parlent d’une opération très importante dans notre vie quotidienne, « la jointure », et nous expliquent même un algorithme pour la réaliser. Vous verrez que vous utilisez des jointures souvent sans le savoir et que si une bonne jointure peut toujours servir, une mauvaise peut porter atteinte à votre liberté.

Prenons cette question hypothétique posée à un concours de la fonction publique. Peut-on lier par une jointure les bases de données de l’éducation nationale et de l’immigration ?

  1. Oui. Cela permet de détecter des personnes en situation irrégulière.
  2. Non. Cela pourrait décourager les personnes en situation irrégulière d’envoyer leurs enfants à l’école.

Le choix entre (1) et (2) est un choix de société. Pour nous, c’est une obligation humaniste de décider (2). Aujourd’hui la plupart des élèves qui sortent de l’éducation nationale ne savent pas, peut-être vous ne savez pas, ce que c’est qu’une jointure. Nous pensons qu’il n’est pas possible de comprendre le monde numérique qui nous entoure sans comprendre ce que c’est que la jointure. Nous pensons qu’il n’est pas possible de faire de manière éclairée certains choix de société si on ne comprend pas ce que c’est que la jointure ? C’est pourquoi nous allons vous expliquer cette fameuse jointure…

Vous utilisez quotidiennement des jointures

Imaginez que vous voulez aller au cinéma ce soir. Vous demandez à Allociné « où puis-je voir Mommy ce soir près de chez moi ». L’information est probablement structurée chez Allociné dans une base de donnée de la manière suivante (très simplifiée) :

joinL’information est répartie entre deux tables. La première dit quel cinéma passe quel film à quelle heure. La seconde donne le nom et l’adresse du cinéma. Observez l’utilisation d’identifiant pour chaque cinéma. C’est ce qui permet de faire une « jointure » (comprenez un pont) entre les deux tables et de trouver par exemple que « Imitation game » passe à 17:00 au Gaumont Opéra ».  Pour donner un autre exemple, quand vous cherchez les contacts de votre amie Alice sur Facebook, que faites vous ? Vous allez dans votre liste d’amis (une première table). Vous sélectionnez Alice et allez chercher ses contacts – dans une autre table. Une jointure ! Quand vous regardez les tweets que Twitter vous propose, que l’un d’entre eux, par exemple vient d’Inria et que vous cliquez pour voir les tweets récents d’Inria, une autre jointure ! On pourrait multiplier les exemples. Mais vous avez saisi l’importance de cette opération.

Imaginez maintenant que la première table soit les services de l’immigration et la seconde, une base de données de l’éducation nationale. Oups ! Wikipédia nous raconte : « Le 21 mars 1974, la révélation par le quotidien Le Monde d’un projet gouvernemental tendant à identifier chaque citoyen par un numéro et d’interconnecter, via ce numéro, tous les fichiers de l’administration créa une vive émotion dans l’opinion publique. » C’est cette émotion qui a conduit à la création de la CNIL. Des jointures entre les tables de l’administration risquaient de mettre en cause des libertés fondamentales. Cet identifiant aurait joué le rôle de l’identifiant de salle de cinémas de l’exemple précédant. C’est donc bien une histoire de jointure.

Pour conclure, nous allons vous présenter, en nous appuyant sur l’exemple du cinéma, l’algorithme le plus standard pour réaliser la jointure. Comme cela, nous espérons démystifier un peu pour vous cette opération.

Un algorithme simple pour réaliser des jointures

C’est peut-être ce que vous choisiriez si on vous demandait de réaliser manuellement la jointure.

L’algorithme Tri-fusion 

  1. Tri : Vous commencez par trier la première table par ID-ciné croissant. Vous faites de même de la seconde table. Dans cet algorithme, ce qui prend le plus de temps c’est d’ailleurs typiquement ce tri des deux tables. Pour faire ce tri, vous utilisez votre algorithme de tri préféré. Voir plus loin un exemple d’algorithme de tri.
  2. Fusion : Vous inspectez ensuite les identifiants de ID-ciné par ordre croissant et pour chacun vous construisez (si c’est le cas) des résultats. C’est la partie la plus simple.

Maintenant nous allons vous proposer un algorithme de tri – il en existe des tonnes. Interstices nous en propose une synthèse. Et on peut même le découvrir en dansant:

Nous en donnons un qui est d’une simplicité effrayante :

Algorithme Tri par diviser pour conquérir

  1. Coupez la relation en deux.
  2. Triez chaque morceau
    1. Si le morceau n’a qu’un élément, il est trié.
    2. Sinon réutilisez Tri par diviser pour conquérir
  3. Fusionnez les deux relations triées.

Maintenant, heureusement que ce n’est pas l’algorithme qui est utilisé quand vous demandez un film. Le système utilise un « index » – qui ressemble dans l’idée à l’index à la fin d’un livre. On donne à l’index un identifiant de salle et il trouve directement l’enregistrement correspondant à ce cinéma en quelques millisecondes quand Tri-fusion pourrait prendre quelques secondes voire plus pour de grosses tables.

 

La jointure n’est qu’une des opérations de l’algèbre relationnelle. Pour découvrir les autres, consultez ce Wandida.

Voilà. Maintenant vous savez ce que c’est qu’une jointure. Et vous pouvez comprendre la question : Peut-on lier par une jointure les bases de données de l’éducation nationale et de l’immigration ? Ou pas.

Serge Abiteboul et Colin de la Higuera

 

Des fourmis et des chercheurs

Aux confins de notre monde, une armée pacifique d’hommes et de femmes explorent l’inconnu. Cette exploration est déterminante pour notre société. Elle fournit à chaque instant la matière sur laquelle sera construit le monde de demain, et constitue par l’accumulation de connaissances notre réserve de progrès et d’adaptation.
Le texte que nous propose Christophe Godin, Directeur de Recherche chez Inria, dépasse le cadre de l’informatique, même si les images sur lesquelles il s’appuie sont bien de ce domaine.

Ray-Clid 2014@Rayclid 2014

Note à l’attention des décideurs pour un système de recherche efficace qui tire la croissance puissamment vers le haut.

« Ah vous êtes chercheur ? … mais la société a besoin de trouveurs pas de chercheurs ! »

Dans ma vie extra-professionnelle, j’ai comme beaucoup de collègues chercheurs, souvent été confronté a cette boutade en demi teinte, un soupçon ironique, lancée à l’occasion d’une soirée ou d’une réunion de famille. Un peu dans l’embarras, et touché certainement dans mon amour-propre, j’essaie le plus souvent de répondre en montrant en quoi mon domaine de recherche, mes recherches sont tellement importantes pour la société. En vain… la distance est trop grande, le temps trop court, le vocabulaire trop étriqué, l’expérience trop différente, et finalement le lien trop ténu… Une évidence qui finalement n’en est pas une.

Pourtant, cette boutade, dont la paternité est souvent attribuée à tort semble-t-il au Général De Gaulle (voir l’article de Pierre-Carl Langlais du 18/10/2014), pose trois questions essentielles sur la fonction du chercheur dans la société. Premièrement, la recherche est-elle utile à notre société ? Après tout la grande masse des individus de la société ne sont pas chercheurs. Ne pourrait-on pas tout simplement se passer de cette activité dont on n’a pas toujours l’impression qu’elle est essentielle, ici et maintenant ? Deuxièmement, en admettant tout de même que la société ait besoin de chercheurs, a-t-elle besoin d’une telle masse de chercheurs (dont une grande partie sont en France des fonctionnaires) pour progresser dans la connaissance et faire des découvertes ? Les chercheurs qui cherchent et ne trouvent pas ne sont ils pas inutiles ? Ne pourrait-on pas faire beaucoup d’économies en appointant uniquement des chercheurs qui trouvent ? Ne pourrait-on plus efficacement utiliser l’argent du contribuable en formant des trouveurs plutôt que des chercheurs, des sortes de super-chercheurs qui, en plus de chercher, trouveraient ?

Et finalement, la recherche est-elle un bien ou un mal ? C’est la recherche qui permet de trouver de nouveaux vaccins, de construire des avions plus rapides, de rester en contact malgré les distances. Mais c’est également la recherche qui engendre des applications dont le risque mal évalué conduit à des accidents comme ceux de Tchernobyl ou de Fukushima, à l’accumulation de pollutions (gaz à effet de serre, déchets dangereux ou massifs) dont l’impact est maintenant mondial. En arrêtant de financer la recherche, ne supprimerions nous pas bien des maux dont souffre aujourd’hui notre société ? Ces questions sont tout à fait légitimes, et il faut y répondre. Cependant, je me suis progressivement rendu compte qu’elles ne posent pas le problème correctement (d’où mon embarras à y répondre), et que l’apparent bon sens derrière ces questions est en réalité lié à un malentendu commun mais, à terme, dangereux sur la fonction de chercheur dans la société.

Formica_rufa_a1
Source Wikimedia Adam Opiola

Pour le comprendre, observons le comportement des fourmis. Vous vous êtes sans doute comme moi étonné au printemps de la terrible efficacité des fourmis pour repérer toute trace de nourriture : le moindre insecte mort, de morceau de sucre ou de pain tombé sur le sol est après quelques minutes seulement envahi de fourmis et acheminé vers la fourmilière dans un convoi ininterrompu. Cette efficacité n’est bien sur pas un hasard. C’est le fruit d’un processus comportemental sélectionné par la nature pour son efficacité redoutable. Pour explorer le territoire autour de la fourmilière, des fourmis spécialisées dans l’exploration se déplacent selon une trajectoire un peu aléatoire. L’ensemble des trajectoires de ces exploratrices réalise en permanence un maillage assez fin de la surface entière du territoire, de sorte qu’une source de nourriture sera vite repérée où qu’elle soit. En revenant à la fourmilière, une fourmi ayant fait une telle découverte, indique par l’odeur qu’elle dépose sur le chemin aux autres fourmis le lieu de sa découverte, attirant ainsi vers la source de nourriture très rapidement ses congénères qui intensifient alors l’exploitation du filon.

Il est intéressant de s’arrêter un instant sur ce sur quoi repose une stratégie aussi efficace :

  1. les acteurs (les fourmis) sont nombreux et autonomes ;
  2. ils se déplacent en partie aléatoirement ;
  3. tous travaillent simultanément ;
  4. une fois une source de nourriture trouvée, un mécanisme collaboratif se met en œuvre afin de permettre aux fourmis d’exploiter cette source rapidement.

En réalité, cette stratégie affinée par la nature pour explorer et exploiter une espace donné avec efficacité a une nature universelle. Elle peut être mise en œuvre par bien d’autres systèmes que celui des fourmis dès qu’il s’agit d’explorer un espace vaste et de découvrir en un temps raisonnable des éléments d’intérêt dans celui-ci. C’est en particulier en partie comme cela que la recherche procède chez les hommes.

Pour les hommes, l’espace à explorer est le monde physique et biologique ainsi que le monde conceptuel que l’on peut construire par abstraction et déduction (monde économique, sociologique, mathématique, numérique). Cet espace est gigantesque, bien plus vaste que ce que nous pouvons imaginer. Pourtant, à travers l’histoire des sciences et des technologies, nous savons qu’il recèle une quantité formidable de sources de nouvelles connaissances et de propriétés à découvrir. Pour explorer cet espace, nous avons petit à petit mis en place une stratégie implacable, comparable à celle des fourmis : des individus spécialisés (les chercheurs) explorent cet espace et développent des trajectoires (travaux de recherche) qui ensemble couvrent à tout moment une grande partie de l’espace à explorer. Lorsqu’ils font une découverte, ils laissent une trace pour leurs collègues (publication) qui permet à toute la communauté de repérer et d’exploiter la nouvelle mine de savoir ainsi dévoilée. Il existe bien sûr une disparité dans la capacité de recherche, les compétences, l’intuition et l’efficacité de chacun des acteurs (comme chez les fourmis sans doute). Mais c’est bien l’ensemble de ces trajectoires et leur nombre qui garantit la terrible efficacité de notre système de recherche dans son ensemble. Et c’est là le point essentiel !

fourmiliere
Source : ElPadawan

Comme toutes les métaphores, celle de l’organisation distribuée des fourmis explorant leur espace dans un mouvement essentiellement aléatoire a des limites lorsqu’on la compare à l’activité de recherche humaine. La plus importante est sans doute que les fourmis sont des acteurs doués de facultés de raisonnement limitées. Pour autant, elle nous fournit une grille de lecture très utile pour penser l’efficacité de notre système de recherche actuel et sa gouvernance. C’est ce point que j’aimerais maintenant discuter. Cette grille fait apparaitre 4 principes fondamentaux sous-tendant un système de recherche efficace :

  • Principe des moyens exploratoires
    Le premier principe est qu’il faut laisser les chercheurs faire ce pour quoi ils sont formés et payés : explorer systématiquement l’espace inconnu autour de nous tous. La condition principale d’une telle recherche est le temps : il faut laisser aux chercheurs l’essentiel de leur temps pour chercher. C’est un point d’une importance capitale, mais dont la fragilité tient en ce que, s’il n’est pas assuré, il est très difficile pour le système de détecter immédiatement qu’il y a un problème ; les effets se feront ressentir des années plus tard. Si on ne laisse pas suffisamment de temps d’exploration aux chercheurs, l’espace inconnu parcouru par l’ensemble de la communauté sera de faible étendue et le risque de passer à côté des découvertes clés largement accru. Ainsi, si on estime que l’efficacité d’un chercheur pour la communauté croit en proportion du temps qu’il met dans son exploration du monde, alors on voit bien que l’accumulation de tâches secondaires, non directement liées à ses capacités de chercheur (tâches administratives, tâches d’évaluation, rapports, rédaction de projets, tronçonnage excessif des publications pour faire « du chiffre », etc.) va nécessairement se faire au détriment de son travail d’exploration. Voir à ce sujet le témoignage de Marco Zito, physicien au Commissariat à l’Énergie Atomique : « Pris dans l’engrenage« . Il est essentiel pour bien prendre la mesure de l’ampleur du problème de rappeler les deux processus majeurs qui amputent aujourd’hui régulièrement des pans entiers au temps que les chercheurs peuvent consacrer à leur exploration.

    1. La surenchère de création de structures qui a sévi dans la dernière quinzaine d’années a eu des conséquences dévastatrices sur notre capacité de recherche. On a vu foisonner dans les dernières années un nombre incalculable de structures liées à l’organisation de la recherche UMR, UPR, IFR, FDR, USR, COMUE, PRES, Pôles d’excellence, Instituts Carnot, Alliances, LABEX, IDEX, EQUIPEX, Fondations, pôles de compétitivité, projets d’avenir, etc. La liste est longue.  Toutes ces structures s’empilent en un écheveau émergent d’une grande complexité où se multiplient à l’infini les tâches administratives des chercheurs qui appartiennent souvent à nombre d’entre elles. Le système s’étouffe de lui même, au point que l’académie des science a adressé à la sphère politique  des recommandations d’urgence pour simplifier du système et qui sont pour le moment pour l’essentiel restées lettre morte. (Voir son rapport.)
    2. Depuis une vingtaine d’années, les chercheurs consacrent de plus en plus de leur temps dans des processus compétitifs à l’échelle nationale et européenne pour obtenir des moyens de recherche. Cette stratégie peut inciter les collaborations entre équipes de recherche et fournir des compléments de moyens pour réaliser des projets innovants. Pourtant, poussée trop loin, elle est simplement naïve et dangereuse pour l’ensemble du système car elle détourne de façon significative les chercheurs de leur travail d’exploration (voir par exemple l’article de John Ionnadis dans la revue Nature).
  • Principe de complétude exploratoire
    Il est essentiel d’encourager les chercheurs à explorer tous les compartiments de l’espace inconnu qui nous entoure (et non seulement une partie de celui-ci). C’est cette complétude du balayage de l’espace de recherche qui peut garantir la meilleure efficience des découvertes (comme pour les fourmis). Ce mouvement d’exploration systématique prend sa source à l’échelle des équipes de recherche : il est l’équivalent du déplacement aléatoire des fourmis. Il n’est pas dirigé par une instance supérieure qui prétendrait savoir où chercher. C’est lui qui garantit la performance de découverte de l’ensemble du système. L’alternative est de laisser un individu ou un groupe décider pour la nation de ce qui est le plus prometteur en matière de retombées sociétales. Or, il est extrêmement difficile à quiconque de prédire dans quel domaine vont être faites les prochaines découvertes les plus significatives pour la société. Un exemple célèbre est celui de la vaccin contre la rage, ou celui de la découverte de pénicilline en médecine, d’autres sont ceux des découvertes de la radioactivité en physique, de l’invention des transistors en électronique, ou plus récemment celle du Web par exemple dans les sciences du numérique.
  • Principe de compétence des acteurs
    La nature de l’espace à explorer même exige que les chercheurs aient reçu une formation très spécifique. Il s’agit d’être capable de se déplacer dans ce monde des idées et de l’expérimentation. Ce type de « déplacement » exige une formation pointue, qui permette de reconnaitre les endroits où d’autres sont déjà passés, de trouver de nouvelles pistes (idées ou expériences) et de les mettre en œuvre. L’étape ultime de cet apprentissage est celle du doctorat. L’idée est qu’un jeune chercheur travaille pendant plusieurs années sur un sujet de recherche, et mette pour la première fois à l’épreuve du réel les compétences acquises au cours de sa formation théorique. Aujourd’hui, le temps de cet apprentissage a été réduit uniformément quelques soient les universités et les matières à 3 ans. Tous les financements sont obtenus pour cette durée. Les écoles doctorales au sein des universités sont évaluées sur leur capacité à faire respecter ces délais. Ceci est absurde.  Il est intéressant de noter qu’il en va tout autrement outre-Atlantique et que la durée d’une thèse peut être largement variable en fonction des cas. En revanche, il est essentiel de considérer ces jeunes chercheurs pendant toute leur période d’apprentissage comme des chercheurs à part entière et de les rémunérer en conséquence.
  • Principe de masse critique
    Le nombre de chercheurs doit être suffisant pour explorer l’espace accessible à la découverte. Ce point est également une pierre angulaire de tout le dispositif. Il se heurte aujourd’hui à deux difficultés. Il s’agit tout d’abord d’une crise des vocations et d’attractivité. Devant la grisaille des horizons qu’offre notre société, les jeunes sont de moins en moins attirés par un métier dont on ne sait plus bien ce qu’il constitue comme repère. Pour vouloir devenir un explorateur, il faut avoir envie de rêver le monde, d’inventer de nouveaux chemins, d’être convaincu que l’inconnu recèle un passage, une beauté cachés. Ce rêve est aujourd’hui comme un drapeau en berne. Il faut le raviver, susciter l’intérêt des plus jeunes pour le métier de chercheur, les faire rêver de leurs rêves. La recherche doit venir à leur contact, leur parler, les émerveiller, leur montrer la valeur intrinsèque de la connaissance et le plaisir de chercher. Il faut, au-delà encore, que notre espace de recherche national attire les esprits scientifiques étrangers, ou favorise le retour de chercheurs français un temps expatriés, et que tous aient l’ambition de faire ou de poursuivre leur parcours exploratoire sur un territoire fertile et stimulant. A l’attractivité scientifique, il faut adjoindre une attractivité financière. Si en général les chercheurs ne travaillent pas pour devenir riches, ils sont en revanche très sensibles à la reconnaissance que leurs collègues ou que la société pour laquelle ils travaillent leur témoignent. Le salaire est l’une des formes importante de cette reconnaissance. Enfin, pour atteindre une masse critique à la fertilité des découvertes, jouer sur les leviers des vocations ou de l’attractivité ne suffit pas. Il faut également qu’en fonction de sa taille la société se dote d’une densité d’explorateurs suffisamment importante pour répondre à ses attendus en matière de progrès, d’innovation, de compétition et d’adaptation.

La recherche n’est bien sûr ni un bien ni un mal. Elle est la condition même de l’évolution de notre société. Il est essentiel que la société civile et les hommes et femmes politiques perçoivent cette réalité au delà des formes. Ainsi, l’exemple de l’organisation de l’exploration d’un territoire par les fourmis nous permet de prendre du recul sur la nature même et la fonction de l’activité de recherche dans nos sociétés. La comparaison de chercheurs à des fourmis, si elle est flatteuse pour les fourmis, n’en est pas moins utile pour analyser les enjeux derrière cette activité humaine très particulière, et finalement vitale à l’échelle de notre civilisation. C’est en reconnaissant la composante collective du travail de recherche que nous pourrons prendre les décisions adaptées à la manipulation de cet instrument complexe, mais tellement puissant si l’on s’en sert avec intelligence. Certains chercheurs, talentueux, audacieux et parfois chanceux (ou tout à la fois), vont être sous le feu des projecteurs. Et c’est très bien, car la société peut à travers eux prendre connaissance des fruits de l’immense effort consenti par tous : les contribuables, les entreprises qui investissent dans la recherche et les chercheurs eux-mêmes. Ils sont portés derrière eux par l’ensemble de la fourmilière des éclaireurs. Si la société a retenu le mot « chercheur » plutôt que celui de « trouveur », c’est bien qu’elle reconnait profondément la valeur essentielle de l’acte de chercher en soi ! Il ne nous reste qu’à accompagner dignement cette sagesse collective.

… Vous rêviez de trouver ? J’en suis fort aise :
Et bien ! Cherchez maintenant.

Christophe Godin, Inria

Pour aller plus loin

  • Quelques chiffres utiles sur la recherche française: « La dépense intérieure de recherche et développement s’élève à 45 milliards d’euros en 2011. Au total, 543 000 personnes participent à une activité de recherche en France dont 249 100 chercheurs (en équivalent temps plein). On compte 148 300 chercheurs dans les entreprises et 100 800 dans le publicEn 2012, la dépense intérieure de recherche et développement (DIRD) s’établit à 46,5 milliards d’euros, en hausse de 1,9 % en volume par rapport à 2011. »  rapport du Ministère de l’enseignement et de la recherche.
    Si l’on passait au même chiffre que l’Allemagne par exemple cela correspondrait à 60 milliards d’euros au lieu de 46.5 milliards d’euros en France, et 73 milliards d’euros si nous avions une politique similaire à la Finlande (soit 26 milliards d’euros en plus des 46.5 milliards d’euros du budget français R&D 2012).
    Comment déterminer alors la masse critique de chercheurs efficace pour une nation ? Il y aurait une étude complète à développer sur ce thème. Une solution pragmatique consiste à se reposer sur l’expérience comparée des différents pays. Par exemple, les chiffres donnant le pourcentage du PIB national utilisé pour la recherche et le développement par différents pays nous permet de faire une première estimation de cette densité. Par exemple, l’Espagne consacre 1.30% de son PIB à la recherche et au développement, l’Irlande 1.72, Royaume Uni 1.72, Pays-Bas 2.16, France: 2.26,  Etats Unis: 2.79, Allemagne: 2.92  Danemark: 2.98, Japon 3.39, Suède 3.41, Finlande: 3.55,  Israël: 3.93, Corée 4.05, Moyenne mondiale: 2.21 (ref  Banque Mondiale – dépenses en recherche et développement en % du PIB données 2012– ). Pour un pays comme la France, ce chiffre correspond actuellement à environ 100 000 chercheurs dans le secteur public. Un point supplémentaire (ce qui nous positionnerait à peu près au niveau du Japon) correspondrait à un investissement supplémentaire d’environ 20 milliards d’euros dans la recherche et le développement et 43 000 chercheurs supplémentaires (en supposant par exemple simplement que le nombre de chercheurs du public croit proportionnellement au PIB investi dans la recherche).

La nuit de l’info 2014

Et voilà, la 7ème édition de la nuit de l’info s’est terminée le vendredi 5 décembre 2014 à 8h04 sur un nouveau record de participation avec plus de 2900 étudiants.

Cette année, en lien avec l’actualité, les étudiants avaient à leur disposition toute une nuit pour inventer un système d’information a vocation humanitaire. C’était pour eux l’occasion de mettre leurs compétences au service des autres, dans un monde en crise où l’informatique pourrait être utilisée pour aider des populations en péril. Les scénarios sur lesquels ils ont travaillé permettraient d’aider les zones victimes d’épidémies ou de crise sanitaire, des réfugiés de guerre à la recherche de leurs proches, ou encore les ONG en charge des campagnes de prévention dans les zones à risques.

Et cette année encore, les organisateurs de la nuit ont su répondre présent avec probablement l’un des plus beaux thèmes depuis le début de l’évènement : « UNE NUIT POUR INVENTER LES SYSTÈMES D’INFORMATION HUMANITAIRES DE DEMAIN »

Les équipes, au nombre de 337, se sont affrontées dans ce challenge festif autour de l’informatique. Pendant toute la nuit, ils pouvaient répondre aux défis lancés par les nombreux partenaires industriels, pour tenter de décrocher les cadeaux associés. Défi du projet le plus surprenant, défi de la meilleure modélisation, il y en avait pour tous les gouts ! Chaque partenaire industriel, porteur de défi, amène dans la Nuit son cœur de métier, et défie les participants sur des problématiques qui lui sont chères, comme l’ergonomie ou encore la prise en compte du handicap.

Mais la Nuit c’est plus que ça.  C’est avant tout un lieu de rencontres, d’échanges, de discussions où les entreprises partenaires viennent conseiller et soutenir les étudiants tout au long de la nuit. C’est l’occasion pour chacun de se faire remarquer, dans une ambiance festive : difficile d’imaginer dans un autre contexte de pouvoir discuter de développement logiciel avec un directeur d’agence alors que l’on est déguisé en panda ! La Nuit est aussi une formidable opportunité pour décrocher un stage ou un emploi auprès des entreprises soucieuses de faire connaitre leur nom mais aussi de repérer les petits génies de demain.  C’est une occasion unique où les étudiants de tous niveaux (DUT, Licence Pro, Master ou Ingénieur) éprouvent leurs compétences et sont confrontés à des exigences professionnelles sur une période inhabituelle.

N’hésitez pas à consulter le site de la Nuit de l’info pour plus d’information. Qui sait, peut-être participerez-vous à l’édition 2015 ?

Gaëtan Rey et Sébastien Mosser

Osons les cours d’informatique à l’école

Tout le monde s’accorde (ou presque) pour dire que l’informatique est indispensable. En revanche, il y a un point qui fait frémir : quels cours supprimeriez-vous pour l’enseigner ? Retrouvez la tribune sur Slate.fr datée du 8 décembre 2014 de Colin de la Higuera, président de la Société Informatique de France (SIF) et Gilles Dowek, président du conseil du scientifique de cet espace de réflexion, de concertation sur les enjeux de l’informatique qu’est la SIF.

 

Barbie est moins conne qu’on le dit

Barbie est moins conne* qu’on le dit.
Barbie is ultimately not that a dummy**.

Lorsque Casey Fiesler, Doctorante en Sciences Informatiques, a vu les fils de ces média sociaux déborder d’indignation à propos de l’incommensurable maladresse de la bande dessinée « Barbie: I Can Be a Computer Engineer » elle a fait une chose tout à fait constructive et utile pour toutes et tous nos enfants. Elle a réécrit ce qu’aurait du être une telle histoire. Et met en partage « Barbie, remixed : je peux (vraiment !) être ingénieure en informatique ». Un auteur du blog voisin bigbrowser.blog.lemonde.fr nous explique sa démarche.

À notre tour*** d’aider parents et enfants à ne pas être victimes de tels poncifs. À réaliser que nous avons besoin des deux moitiés de l’humanité à égalité pour avancer au mieux sur tous les sujets. Voici la version française, à lire, offrir et partager sans modération ! Même la Mère ou le Père Noël pourrait glisser ces huit feuillets au pied du sapin.

Barbie revisitée : « Je peux être ... ingénieure en informatique »

Colin, Marie-Agnès, Pierre, Serge, Sylvie et Thierry.


(*) Ici dans le sens de femme sotte, manquant d’intelligence et éventuellement prétentieuse.

(**) [english traduction of this text] When Casey Fiesler, PhD student in Computer Science, discovered that her social media feeds have been full of outrage over the unboudned awkwardness of the comic « Barbie I Can Be a Computer Engineer » she simply did the constructive and useful think to do. For all small girls and boys: She rewrote what should have been such a story, i.e., « Barbie, remixed: I (really!) can be computer engineer« , as explained on bigbrowser.blog.lemonde.fr.
It is our turn to contribute, helping parents and children not to be victims of such cliches. To help realizing that we need the two halves of humanity equaly treated to get the best on all subjects. Here is the French version of Casey’s work, to read, offer and share without moderation! Even Mother or Father Christmas can put some of them under the Christmas tree !

(***) La traduction du travail de Casey Fiesler a été faite par Provence Traduction avec le soutien d’Inria .

Un algorithme : PageRank de Google

Que se passe-t-il si on cherche Michael Jackson  sur Google ? On voit apparaître des liens vers des pages concernant le chanteur : sa vie, ses photos, ses clips, sa famille, ses fan clubs, sa mort, etc. Tout cela nous paraît bien logique a priori. Mais si l’on creuse un peu, cela devrait nous intriguer. Après tout, il y a des millions de pages avec la chaîne de caractères « Michael Jackson » sur le Web. Pourquoi Google ne nous propose rien sur Michael Jackson menuisier à Dallas ? Ou Michael Jackson professeur de chant à San Francisco ? Si vous étiez ce menuisier, vous pourriez même être outré de ne voir aucun lien vers une page qui parle de vous, alors que vous en avez publié des dizaines, en y incluant à chaque fois votre nom. Pourquoi de telles injustices ?

En fait, Google propose des liens sur les pages du chanteur, car il suppose que c’est le chanteur qu’un internaute va chercher. Et il y a une forte probabilité que ce soit le cas… le plus souvent. Mais comment Google peut-il savoir qu’il y a une forte probabilité qu’un internaute recherche en général le chanteur plutôt que le menuisier ?

Google ne le sait pas. Ce que Google sait, par contre, c’est que parmi toutes les pages qu’il gère et qui parlent de Michael Jackson (d’un certain Michael Jackson), celles concernant le chanteur sont les plus « importantes » (comprenez les plus « populaires »). La notion d’importance est mesurée par un algorithme, un de plus, parmi ceux qui régissent notre vie quotidienne.

L’algorithme PageRank, inventé par Sergeï Brin et Larry Page, les deux fondateurs de Google, s’inspire des travaux de Jon Kleinberg d’IBM. PageRank était à l’origine du classement des résultats du moteur de recherche Google. Aujourd’hui, plus de deux cents autres critères sont utilisés pour classer ces résultats. La recette est secrète, ce qui ouvre la porte à toutes sortes de spéculations sur ce classement. Est-il vraiment neutre au sens de la neutralité des plateformes du Web ?

Nous allons parler ici de l’algorithme PageRank original, dans une version très simplifiée, pour le rendre accessible à des non-informaticiens. Avant de se lancer dans sa description, il est important de savoir que PageRank travaille sur des pages indexées par des mots-clés, comme les mots « Michael » et « Jackson », des pages qui sont donc susceptibles d’être proposées à des utilisateurs comme réponses à une requête « Michael Jackson ». À l’heure actuelle, Google indexe près de 1012  pages. Il en indexait 109 en 2000. On est encore loin du 10100 : le fameux nombre « googol » qui a inspiré son nom à la société.

En gros, PageRank calcule périodiquement l’importance relative des pages indexées sous forme d’un score. Lorsqu’on soumet une requête à Google, il nous affiche celles qui ont le score le plus élevé (id est celles du chanteur) parmi celles qui correspondent à cette requête (par exemple parmi toutes les pages connues du moteur de recherche contenant les mots  « Michael » et « Jackson »).

Pour calculer le score des pages, PageRank se base sur les liens entre ces pages. En effet, chaque page cite un certain nombre d’autres pages : elle a des liens vers ces pages. Quelqu’un qui se trouve pendant sa navigation sur une page p peut y trouver un lien vers une page q et y aller directement. C’est ce qui se passe quand, dans une page Wikipedia sur PageRank, on rencontre un lien vers la page de Larry Page.

L’idée de PageRank est de représenter le score d’une page p par la probabilité qu’un utilisateur qui se baladerait « au hasard » dans une bibliothèque constituée de toutes les pages du Web se retrouve sur la page p.  Cette probabilité est d’autant plus grande que :

  1. Il y a de nombreuses pages q qui ont des liens vers p ;
  2. Ces pages q ont elles-mêmes un score important (on a une forte probabilité de tomber sur elles) ;
  3. Ces pages q ont peu de liens vers d’autres pages qui pourraient distraire notre attention.

Une manière de synthétiser (1), (2) et (3) est de faire la somme des scores des pages q ayant un lien vers p en divisant chacun par le nombre de liens sortant de q. Ainsi, en première approximation, si l’on représente par liens (q) le nombre de liens sortant d’une page q :
Score(p) = Somme(Score(q)/liens(q))
– pour toutes les pages q ayant un lien vers p

Intuitivement, c’est comme si chaque page avait un certain nombre de votes, représenté par son score, et qu’elle pouvait partager ses votes entre toutes les pages qu’elle référence. Considérons le petit dessin ci-dessous représentant quatre pages : q ayant un lien vers p et p’ et q’ ayant un lien vers p’. Supposons par ailleurs que les scores de q et q’ sont 1.  On aura : Score(p) = 0.5 et Score(p’) = 1.5.

En fait, l’algorithme PageRank prend aussi en compte le fait qu’un utilisateur qui se balade dans la bibliothèque peut aller directement d’une page à une autre sans passer par des liens, un peu comme s’il se téléportait par-dessus les murs de la bibliothèque. Plus précisément, PageRank relativise le score ci-dessus en le multipliant par un facteur d’atténuation d entre 0 et 1, auquel il rajoute (1-d) pour avoir une probabilité. Le facteur d’atténuation est pris par exemple 0.85.  Ainsi :

PageRank(p) = 0.15 + 0.85 * Somme(PageRank(q)/liens(q))
– pour toutes les pages q ayant un lien vers p

Comme on calcule le score d’une page en fonction de scores d’autres pages, il est légitime de se poser la question : comment ont été calculés les scores des pages initiales q et q’ ci-dessus ? PageRank prend la même valeur pour toutes les pages du Web. Ensuite il applique les équations ci-dessus pour toutes pages. Il s’arrête quand les valeurs ne changent plus.

On vous a caché des tas de détails. On pourrait dire pour vous effrayer qu’on calcule le « point-fixe d’une équation matricielle avec une matrice avec des milliards de lignes et de colonnes ». Plus prosaïquement, imaginez qu’il faut calculer plusieurs fois la fonction ci-dessus pour les milliards de pages indexées. C’est un gros calcul ? Non ! C’est vraiment un très, très… très gros calcul. Et il faut des tas d’ordinateurs pour le réaliser. Et ce n’est qu’une des fonctions d’un moteur de recherche…

Rachid Guerraoui, professeur à l’Ecole polytechnique fédérale de Lausanne

(*) Pour en savoir plus en vidéo: http://wandida.com/en/archives/571