Catégorie : Science

Je ne suis pas informaticienne

Il n’est jamais trop tôt pour bien faire. Et l’informatique n’y fait pas exception. Elle est arrivée au lycée, mais cela aura pris le temps. Binaire s’intéresse à des expériences de la découverte de l’informatique à l’école primaire. Isabelle Glas nous parle d’une initiation en Île-de-France sur le temps périscolaire. Sylvie Boldo

Je ne suis pas informaticienne. Mon créneau, c’est la communication, l’événementiel et la gestion administrative. Recrutée en 2013 par le Labex DigiCosme* pour animer le réseau et mettre en œuvre ses activités, je me suis retrouvée parachutée dans l’univers parallèle et insoupçonné des chercheurs en informatique.

Lorsque j’ai abordé ce nouveau secteur (pensez abordage, le sabre au clair et l’âme prête au au combat), il me paraissait évident que tout le monde se préoccupait d’enseigner l’informatique aux générations futures. L’omniprésence des technologies numériques, la virtualisation des échanges, l’introduction de programmes dans tous les produits issus de l’industrie (voitures, montres, télévisions…) semblaient amplement justifier qu’on se préoccupât de munir les jeunes français(e)s d’un bagage minimum en informatique. De fait, je fus stupéfaite de découvrir l’ampleur et la durée du combat mené par les chercheurs de la discipline pour imposer cette conviction et inscrire l’informatique dans les programmes depuis les classes de primaire jusqu’aux cursus des écoles d’ingénieurs (voir http://www.epi.asso.fr).

Par « informatique » , entendez la science et, dans un premier temps, la programmation. Il ne s’agit pas de développer à tout prix le parc numérique des écoles et de remplacer les encyclopédies papier par Wikipédia, mais d’inculquer aux enfants les bases de l’algorithmique. L’objectif est de leur laisser entrevoir la complexité des programmes derrière le lissé des interfaces, mais de façon telle qu’il ne se sentent pas intimidés par cette complexité. Pour ceux qui n’ont jamais programmé, la tâche semble insurmontable, magique, comme si l’apprentissage du code nécessitait un rite initiatique assorti d’un sacrifice à quelque déité païenne. En réalité, la programmation obéit à des bases très simples que tout le monde peut s’approprier, à condition de les apprendre et de les pratiquer. Plus que toute autre discipline, l’art de la programmation est question de rigueur, d’habitude, de réflexe. C’est l’une des raisons pour lesquelles il faut s’y prendre tôt.

Une bonne occasion a été donnée au Labex DigiCosme d’œuvrer pour l’initiation à l’informatique des plus jeunes avec la réforme des rythmes scolaires de 2013 et l’instauration des fameux Temps d’Activités Périscolaires (TAP). Un peu de pragmatisme ne faisant pas toujours de mal, pourquoi ne pas investir ces plages horaires et profiter du « temps de cerveau disponible » pour instiller un peu d’informatique dans les chères têtes blondes et brunes ?

Le plan a très vite fonctionné. Plusieurs chercheurs et ingénieurs volontaires (souvent parents eux-même) se sont manifestés pour participer au projet, proposer des activités et se rendre dans les écoles pour encadrer des séances. Une ébauche de programme a rapidement vu le jour, faisant appel aux outils pédagogiques crées par les chercheurs de France et du monde entier (laby, ressources pixees, concours Castor, scratch). Côté institutionnel, il n’a pas été très difficile de susciter l’intérêt de Mairies et d’établissements, séduits par le concept éducatif (et peut-être le caractère bénévole de l’animation).

Copie d’écran du logiciel Laby

Cela nous mène au centre de loisirs du parc de la grande maison à Bures-sur-Yvette, l’après-midi du mercredi 27 mai 2015. Nous nous étions mis d’accord avec la Mairie pour venir tester certaines activités avec des groupes d’enfants du CE2 au CM2. Nous étions trois, Mathias Hiron (président de France-IOI), Christine Paulin (professeur à l’université Paris-Sud) et moi-même, entourés par l’équipe d’animation du centre. Le programme était divisé en deux ateliers : une partie « Castor » encadrée par Mathias Hiron et une partie « découverte de la programmation » menée par Christine Paulin et moi, centrée sur l’utilisation de Scratch Junior. Nous avions dans notre besace des tablettes flambant neuves, des castors savants et autres animaux virtuels, ainsi qu’une unité centrale et un téléphone hors d’usage prêts à exhiber leurs entrailles électroniques pour satisfaire la curiosité des enfants.

La participation des enfants à l’activité était volontaire, dans la limite du nombre de participants que nous pensions pouvoir gérer sans nous laisser déborder. 18 enfants se présentèrent, ce qui était légèrement plus que prévu mais constituait une belle victoire sur le soleil qui brillait ce jour là avec insolence. Informatique 1 – balle aux prisonnier 0 ! Si l’un des enfant pensait qu’il allait être question de fusées, je suis raisonnablement sûre que la plupart d’entre eux avaient au moins une vague idée de ce dont il allait être question.

Neuf enfants suivirent Mathias Hiron jusqu’aux sièges colorés au fond de la salle pendant que Christine Paulin et moi prenions en main le reste de l’effectif. L’idée était de s’échanger les groupes en cours de route. Je ne ferai pas le compte-rendu de l’atelier Castor – disons simplement que les enfants en sont sortis ravis.

De notre côté, nous commençâmes, comme il se doit, par le début, c’est-à-dire une discussion pour tester les connaissances de notre public et établir une définition de l’ « ordinateur ». Qu’est-ce qu’un ordinateur, après tout ? Qu’est-ce qui le différencie le smartphone et le PC de la machine à laver ? Les enfants se montrèrent très réactifs sur ce thème déjà familier et la conversation permit assez facilement d’identifier les caractéristiques de l’ordinateur (pluralité des tâches, etc.). En récompense, les participants eurent le plaisir de découvrir l’intérieur d’une unité centrale et d’un téléphone portable, démontés à leur intention par l’équipe du LRI. L’étape suivante eut moins de succès et le questionnaire prévu sur les entrées (saisie clavier, clics de souris…) /sorties (affichage, son…) ne suscita qu’un intérêt modéré.

Apparemment, il est déconseillé d’aborder trop de concepts dans une même séance. Les enfants purent se reposer devant un petit film sur les algorithmes présenté par les Sépas, des extraterrestres pas très futés qui ont grand besoin de s’instruire.

Pour la suite, nous avions prévu de jouer au « Robot idiot », grand classique des activités débranchées. Le jeu consiste à demander à un enfant de guider un camarade hors d’un labyrinthe en lui fournissant des instructions précises et exhaustives. Tel un robot exécutant un programme, l’enfant guidé doit suivre exactement les instructions, sans en corriger les insuffisances – la finalité étant de montrer que l’origine des « bugs » se trouve dans les programmes. L’activité était conçue pour que les participants construisent d’abord l’algorithme à l’aide de flèches directionnelles dessinées sur des cartons avant de passer à la mise en situation. Il fut toutefois difficile d’obtenir la dichotomie théorie / test, les enfants apparaissant nettement plus attirés par l’aspect jeu de rôle que par la réflexion sur le processus. Nous assistâmes cependant à de mémorables interprétations de R2D2.

Pour finir en beauté et emporter définitivement l’adhésion de notre public, nous pouvions compter sur « l’effet tablette ». La technologie a cet étrange pouvoir de transformer les enfants fatigués et agités en chérubins sages et motivés (si-si). Nous vîmes même des enfants sacrifier leur pause pour profiter plus longtemps de Scratch junior. Malgré leur empressement, les enfants se montrèrent très civils dans le partage du medium afin que chaque membre du groupe puisse en profiter.

Scratch (et son dérivé utilisable sur tablette, Scratch junior) est l’un des outils les plus connus en matière d’initiation ludique à l’informatique. Conçu par le MIT, il permet d’élaborer des animations en programmant les actions de personnages et objets placés dans un décor au choix de l’utilisateur (plusieurs paysages sont proposés, en ville, à la campagne, sur la lune ou sous l’océan…). Les commandes de programmation sont matérialisées par des briques (avancer, tourner, agrandir …) à associer pour faire bouger chaque élément.

Exemple de création, © MIT et les enfants de Bures-sur-Yvette

L’application connut un grand succès auprès des enfants qui demandèrent même le lien pour la retrouver en ligne. La prise en main étant très intuitive, notre groupe n’eut pas de mal à s’approprier les fonctions de base suite à une simple (et courte) démonstration des principaux outils. Ravis par les horizons ouverts à leur créativité (notamment les outils interactif permettant d’enregistrer sa voix, de colorier les personnages), les enfants s’emparèrent immédiatement du jeu pour proposer les scénarios les plus variés et réaliser des créations, parfois très esthétiques.

L’expérience fut moins concluante sur l’aspect algorithmique. Peu d’élèves s’intéressèrent aux fonctions plus avancées, la majorité préférant se servir des éléments immédiatement utilisables. C’est toutefois ce qui fait l’ingéniosité de Scratch : les outils plus complexes apparaissant lorsque l’utilisateur souhaite créer des animations plus riches, c’est l’imagination qui sert de guide à l’apprentissage. Jamais bloqués dans leur élan, les enfants viennent eux-même s’informer sur les concepts lorsqu’ils deviennent nécessaires à leur création.

Dans notre cas, la grande faiblesse du dispositif résidait dans l’impossibilité de télécharger les projets pour les stocker hors des tablettes (option possible avec Scratch sur PC). Très fiers de leur(s) projet(s), nos informaticiens en herbe auraient aimé pouvoir les retrouver pour les montrer à leurs parents. A défaut, nous eûmes le privilège d’assister à des démonstrations itératives de chauves souris en vol et d’atterrissage de fusées au fond de la mer.

À la fin de l’après-midi, fourbus mais heureux, nous fûmes récompensés par une petite voix qui nous demanda avec espoir « mais alors, vous revenez quand ? ».

Isabelle GLAS, chargée de projets communication et formation, Labex DigiCosme

(*) Le Laboratoire d’Excellence Digicosme est un projet financé par les Investissements d’Avenir qui fédère les laboratoires en informatique de 11 établissements et instituts de recherche de l’Université Paris-Saclay.

30 septembre 2015
Des consensus tout sauf mous

Michel Raynal

Michel Raynal, Professeur à l’Université de Rennes 1 et membre senior de l’Institut Universitaire de France est un passionné. Il aime les voyages, adore la littérature, ne se lasse pas des côtes bretonnes (malgré ses origines du Sud-Ouest), encore moins du rugby (probablement en raison de ces mêmes origines). Michel aurait pu devenir un grand scientifique dans bien des domaines. C’est dans l’informatique qu’il est tombé, et plus particulièrement dans cette même région de l’Ouest où d’autres se sont retrouvés dans une marmite de potion magique. Michel Raynal est le lauréat du SIROCCO Innovation Award 2015 pour ses travaux en informatique distribuée. C’est l’occasion de découvrir ce domaine passionnant.

Un système distribué est un système composé de plusieurs entités (téléphone, capteur, ordinateur par exemple), connectées par un réseau de communication, c’est-à-dire qui peuvent communiquer (en filaire, par wifi, etc.) et qui, ensemble, s’attaquent à un problème comme de réaliser un calcul ou chercher de l’information. Nous vivons aujourd’hui dans un monde où la majorité des systèmes est distribuée. Par exemple, les données relatives aux comptes Facebook d’un ensemble d’amis sont dispersées aux quatre coins du monde ; pourtant lorsqu’un utilisateur met à jour son statut, tous ses amis doivent être notifiés, qu’ils soient connectés depuis le Maroc ou la Chine et que leurs données soient hébergées en Inde ou dans la Silicon Valley. Nos données, comme celles des entreprises, sont distribuées sur des serveurs ; on parle du cloud. La même donnée peut être répliquée sur plusieurs serveurs pour des raisons de fiabilité notamment.

Turing s’est un jour posé la question de ce que sa machine universelle était capable de calculer. Malheureusement, son formalisme ne s’applique pas aux systèmes distribués. Évidemment, les experts se sont posés la question de savoir ce qu’il est possible de calculer dans un système distribué, notamment le problème du consensus qui a été particulièrement étudié. Le problème est le suivant : chaque entité propose une valeur et à la fin du calcul toutes doivent s’être mises d’accord sur l’une de ces valeurs. C’est le type de fonctionnalité dont on a besoin, par exemple, pour assurer la cohérence de données répliquées dans le Cloud. Pour illustrer le besoin de consensus, prenons l’exemple de données bancaires répliquées sur les machines A en France et B aux États-Unis. Ces données sont répliquées pour des raisons de tolérance aux pannes, de sorte que si une machine contenant ces données tombe en panne, l’autre continue de fonctionner. Ceci permet en outre aussi aux utilisateurs des États-Unis d’avoir un accès rapide depuis la machine B et aux utilisateurs européens d’avoir un accès rapide depuis la machine A. Considérons maintenant la situation suivante : Alice effectue un débit de 100$ depuis la France (sur la machine A) de son compte, dont le solde est de 1000$. L’ordre de débit est envoyé à la machine A mais aussi à la machine B pour assurer que les comptes soient cohérents. Le banquier, depuis la machine B, lui décide de verser des intérêts de 10% sur ce compte. Cet ordre de calcul d’intérêt est aussi envoyé aux deux machines. La communication prend du temps pour traverser l’Atlantique, si bien que la machine A reçoit d’abord l’ordre de débit puis celui des intérêts, appliquant donc 10% à un solde de 900$, le solde résultant est alors 990$, alors que la machine B, applique les intérêts, puis le débit, le solde étant alors de 1000$. Pour assurer un bon fonctionnement il est essentiel que les deux machines exécutent les instructions dans le même ordre et pour ce faire doivent atteindre un consensus.

Fisher, Lynch et Patterson [FLP85] ont montré en 1985 que le consensus était impossible dans un système réparti asynchrone* dans lequel les machines peuvent tomber en panne. La preuve est longue et intriquée et il faudrait demander à Michel Raynal de nous l’expliquer. Pour faire court, dans un système asynchrone, si une entité ne répond pas, on ne sait pas différencier si c’est une question de lenteur, ou si c’est une défaillance de l’entité. Et on peut soit attendre éternellement le message alors que l’entité est défaillante ou alors prendre une décision et voir le message arriver trop tard et contredire notre décision. Michel Raynal a reçu le Sirocco Innovation Award en particulier pour ses travaux relatifs à ce problème de consensus, développant de nouveaux résultats à partir du théorème d’impossibilité de Fisher, Lynch et Patterson.

Que peut faire un chercheur en algorithmique distribuée quand un problème est impossible à résoudre ? Il étudie les hypothèses à relâcher pour que le problème devienne résoluble. Par exemple, pour le problème du consensus, on peut décider de prendre l’hypothèse que les messages entre les entités prennent un temps borné. Le consensus devient alors possible. Que peut-il faire quand on sait résoudre le problème ? Il peut chercher un algorithme plus efficace, par exemple plus rapide, demandant moins de messages, moins de calcul. Afin de contourner l’impossibilité du consensus en asynchrone, Michel Raynal avec ses collègues Achour Mostéfaoui et Sergio Rajsbaum ont par exemple proposé une nouvelle méthode à base de conditions [2]. L’idée est de dénombrer les « conditions », c’est à dire les configurations pour lesquelles on sait comment obtenir un consensus. Michel a alors conçu des algorithmes qui permettaient de s’adapter à ces conditions, rendant ainsi l’obtention d’un consensus possible [3].

Le prix de Michel Raynal reconnait ses contributions scientifiques. Pour conclure, on pourrait souligner que Michel assure la relève formant des jeunes chercheurs, et en leur transmettant son enthousiasme et sa passion.

Anne-Marie Kermarrec, Inria Rennes

(*) Dans un système synchrone, les opérations sont coordonnées sous un contrôle centralisé basé sur les signaux d’une horloge. Par opposition, un système asynchrone, en revanche, n’a pas d’horloge globale. Les différentes entités doivent utiliser des communications pour coordonner leurs tâches.

Références

[1] Michael J. Fisher, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the Association for Computing Machinery, 32(2) :374–382, april 1985.

[2] Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal: Conditions on input vectors for consensus solvability in asynchronous distributed systems. J. ACM 50(6): 922-954 (2003)

[3] Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal. Efficient Condition-Based Consensus. SIROCCO 2001.

31 août 2015

L’informatique privée d’ordinateur

« L’informatique sans ordinateur », c’est le titre d’un article de Baptiste Mélès que je vous encourage à lire, dans Images des Mathématiques, une revue du CNRS. Et Baptiste d’enfoncer le clou dès l’incipit : « L’informatique a la fâcheuse réputation d’être la science des ordinateurs. » Il y aurait une informatique sans ordinateur ? Pire, les ordinateurs lui feraient-ils de l’ombre ?

Baptiste raconte l’informatique sans ordinateur à travers trois exemples :

Internet par pigeons voyageurs. Baptiste nous explique comment Internet fonctionne. Surtout, il nous explique que ce fonctionnement est indépendant de l’ordinateur et pourrait être réalisé… avec un dispositif de papier, d’encre et de pigeons.
La recherche d’un mot dans un dictionnaire. Il nous présente un algorithme « diviser pour conquérir », qu’un humain peut réaliser tout autant qu’un ordinateur.
La programmation sur papier. Il nous montre comment écrire des programmes en UML, un langage qui n’exige aucun ordinateur, qui permet à des êtres humains de spécifier des algorithmes, de collaborer entre eux, d’échanger des idées, même s’ils vont utiliser au final des logiciels très différents.

L’article de Baptiste est important parce qu’il s’attaque à la confusion que beaucoup font entre ordinateur et informatique.

Le mot « informatique » est tellement plus juste que computer science – la science des ordinateurs ! Reprenons la définition du texte de la Société Informatique de France :

L’informatique est la science et la technique de la représentation de l’information d’origine artificielle ou naturelle, ainsi que des processus algorithmiques de collecte, stockage, analyse, transformation, communication et exploitation de cette information, exprimés dans des langages formels ou des langues naturelles et effectués par des machines ou des êtres humains, seuls ou collectivement. L’informatique : la science au cœur du numérique

L’informatique n’est pas juste la science des ordinateurs. Depuis Turing, des chercheurs en informatique le montrent dans des résultats éblouissants aux frontières des mathématiques. Les enseignants le découvrent également aussi, notamment en primaire, à travers « l’informatique débranchée » (CS unplugged) Les élèves apprennent loin de tout ordinateur, autour de jeux, les notions au cœur de l’informatique, comme l’information et sa communication, les algorithmes et les ressources qu’ils demandent.

Et pour conclure, j’emprunterai une phrase de Baptiste : « Si l’ordinateur est l’objet informatique par excellence, c’est simplement parce que les concepts et méthodes informatiques y sont mobilisés de façon massive — mais non de façon exclusive. »

Serge Abiteboul, Inria

En savoir plus ? Beaucoup d’activités débranchées sont présentées sur pixees.fr :

Introduire la notion de complexité pour classer les problèmes, et la recherche de solution optimale ou approchée ? Il suffit de trouver le plus court chemin avec une … planche à clou ! En savoir plus.
©Inria et pixees.fr

Faire découvrir la cryptographie sous forme de jeux aux plus petits ? Il suffit de deviner comment passer un message secret avec une clé secrète alors que … tout le monde voit tout ! Essayer de trouver vous aussi. En savoir plus.
©Image des maths. Le vidéo est une coproduction Tralalère, XD Production et Universcience.

27 août 2015

Attaque à l’italienne
Cet article fait suite à la série de billets sur le vote (Qu’est ce qu’un bon système de vote, Le vote papier est il plus sûr que l’électronique, Les bonnes propriétés d’un système de vote électronique). Cette fois, il ne s’agit pas de discuter des différents systèmes propres à assurer la sécurité et la vérifiabilité d’une élection mais de relever des faiblesses propres à tous les systèmes.

Parmi ces faiblesses, une attaque amusante mais peu connue est « l’attaque à l’italienne ». Cette attaque est possible dès que l’espace des votes est important. Qu’est-ce que l’espace des votes ? En France, les élections sont en général « simples »: il s’agit de choisir un candidat (ou une liste) parmi une dizaine tout au plus. La situation est très différente dans d’autres pays. Prenons le cas de l’Allemagne. Lors de l’élection de la chambre d’un Lander (par exemple celui de la Hesse), les électeurs ont la liberté de composer la chambre de leur choix. Chaque parti politique propose une liste composée des candidats, dont le nombre est variable selon les partis. Un électeur peut choisir une liste et sélectionner ainsi tous les candidats de cette liste. Mais il peut également ajouter des voix à certains candidats, rayer certains candidats et ajouter des candidats d’autres listes. Un règlement complexe a été mis en place pour lever les éventuelles ambiguïtés et éviter un trop grand nombre de bulletins invalides. J’invite le lecteur curieux à lire l’article wikipedia (en allemand) pour une explication détaillée et illustrée des différentes règles, ou bien à utiliser l’interface mise en place pour explorer les différentes manières de remplir correctement un bulletin.

En quoi ce type d’élections peut-il être exploité pour mener une attaque ? La clef de l’attaque est la taille de l’espace des votes. Considérons ainsi le cas extrême du bulletin de vote utilisé lors d’une élection au sein de la commune de Francfort en 2011, où plus de 861 candidats étaient proposés pour un total de 93 sièges. Sans même calculer toutes les possibilités, un rapide calcul indique qu’il y a plus 93 choix parmi 861 soit plus de 10^126 façons différentes de remplir un bulletin. Si, de plus, on tient compte de la position des croix (1ère, 2ème ou 3ème colonne), on arrive alors à plus de 10^172 possibilités.
Un attaquant peut utiliser ce large choix pour « signer » un bulletin. Considérons le cas simplifié où les électeurs disposent de seulement 15 voix chacun et supposons que Charlie souhaite forcer Alice à voter pour le parti politique C sur le bulletin affiché ci-dessous. Il exige alors qu’elle remplisse le bulletin de la manière suivante:
- 2 croix devant chaque candidat de la liste C (soit 8 voix au total)
- 7 croix placées selon une combinaison particulière choisie par Charlie.
Bulletin rempli d’après une image de Sven Teschke (Licence : CC-BY-SA-2.0-DE)

Lors du dépouillement, Charlie s’assurera qu’un tel bulletin est bien présent dans l’urne. Comme il est très improbable qu’un autre électeur ait choisi exactement la même combinaison des votes (notamment pour la partie affichée en rouge sur la figure), Alice est obligée d’obéir à Charlie sous peine de représailles après le dépouillement.

En France, ce type de scénarios est improbable car le nombre de choix est très limité. Cependant, c’est exactement pour cette raison qu’il est interdit d’apposer un signe distinctif sur un bulletin, que ce soit un symbole ou un mot particulier, ou bien un pliage original (un bulletin en forme de girafe par exemple). Notons tout de même que malgré cette interdiction, Charlie a encore la possibilité de forcer Alice à s’abstenir, ou plus précisément, de la forcer à voter nul. Il suffit en effet que Charlie demande à Alice de plier son bulletin en forme de girafe (ou tout autre signe distinctif convenu à l’avance). Un tel bulletin sera comptabilisé comme un vote nul et Charlie pourra s’assurer qu’Alice a bien suivi sa consigne en assistant au dépouillement.

Véronique Cortier, CNRS – Nancy

À la suite de la publication de ce billet, Roberto Di Cosmo m’a signalé que les attaques à l’italienne sont encore très vivaces dans la mémoire des Italiens. Ainsi, un film, « Le porteur de Serviette » avec Nanni Moretti, de 1991, fait de ce type d’attaque un élément de son histoire (voir l’extrait en italien). Une pétition (en italien) rappelle l’usage massif fait dans le passé de l’attaque à l’italienne sur les élections à choix multiples, qui ont été remplacées par d’autres schéma de votes. Cette pétition dévoile de nouvelles méthodes utilisées par la Mafia, signale qu’un vote peut se vendre 50 Euros au marché noir, et demande de nouveaux changements des règles électorales.
24 août 2015
L’apprentissage automatique : le diable n’est pas dans l’algorithme

Du 6 au 11 juillet, Lille accueille ICML (International Conference on Machine Learning), le rendez-vous annuel des chercheurs en apprentissage automatique (machine learning). Mais comment expliquer à ma garagiste ou à mon fleuriste ? Et à quoi bon ! Donnons la parole à des chercheurs qui prennent le risque de soulever pour nous le capot du moteur et de nous l’expliquer.

©Mae59

L’apprentissage automatique est là. Pour le meilleur comme pour le pire.

Comme nous le développions il y a quelques jours, l’apprentissage automatique est désormais partout dans notre quotidien. Votre téléphone portable complète vos phrases en fonction de vos habitudes. Lorsque vous cherchez un terme avec votre moteur de recherche favori, vous recevez une liste de pages pertinentes très différente de celle que recevra une personne d’un autre âge ou d’un autre pays. C’est aussi un algorithme qui propose la publicité que vous subissez.

Dans les différents cas ci-dessus, il s’agit bien de calculer automatiquement des préférences, de faire évoluer un logiciel en fonction des données.

L’apprentissage automatique est associé au phénomène Big Data, et quand certains journaux s’inquiètent du pouvoir des algorithmes, il y a fort à parier que les algorithmes en question sont justement ceux qui s’intéressent aux données –aux vôtres en particulier- et essayent d’en extraire une connaissance nouvelle ; par exemple pour offrir un diagnostic médical plus précis. Ou, dans le contexte de la loi sur le renseignement votée récemment, pour récolter et traiter nos données privées.

https://canvas.northwestern.edu/

Alors il y a quelque chose d’inévitable si nous voulons ne pas subir tout cela : il faut comprendre comment ça marche.

Bien alors en deux mots : comment ça marche ?

En deux mots ? apprendre (construire un modèle) et prédire (utiliser le modèle appris). Et pour ce qui est de prédire l’avenir … on en a brulé pour moins que ça !

Apprendre : où l’on récolte des données pour mieux les mettre en boîte.

La première problématique consiste à construire, automatiquement, un modèle : il s’agit donc de comprendre quelque chose dans les données. Par exemple dans tous ces résultats médicaux quelle est la loi statistique ? Ou bien dans ces nombreuses données financières, quelle est la fonction cachée ? Ou encore dans ces énormes corpus de textes, quels sont les motifs, les règles ? Et ailleurs, dans le parcours du robot, les résultats transmis par ses capteurs font-ils émerger un plan de la pièce ?

Cette modélisation peut être vue comme une simple tâche de compression : remplacer des très grands volumes de données par une description pertinente de celles-ci. Mais il s’agit aussi d’abstraire, de généraliser, c’est à dire de rechercher des règles ou des motifs expliquant les données. Autrement dit, on essaye d’oublier intelligemment les données brutes en les remplaçant par une information structurée plus compacte.

Cette construction est de nature algorithmique et la diversité des algorithmes est gigantesque. Mais essayons de nous y retrouver.

Apprentissage supervisé ou non.

Si les données sont étiquetées, donc qu’on connait la valeur que l’on voudrait prédire, alors il s’agit d’un apprentissage supervisé : les données peuvent être utilisées pour prédire ce qui est correct et ce qui ne l’est pas.

La valeur peut être un nombre (par exemple le cours d’une action dans trois mois) ou une classe (par exemple, dans le cas d’une image médicale, la présence ou l’absence d’un motif qui serait associé à une maladie). Dans le premier cas, on parle de régression, dans le second, de classification.

Si les données ne sont pas étiquetées, le but sera de trouver une organisation dans ces données (par exemple comment répartir en groupes homogènes les votants d’un parti politique, ou organiser les données en fonction de la proximité de leurs valeurs). Cette fois, l’apprentissage est non supervisé, puisque personne ne nous a dit à l’avance quelle est la bonne façon de mesurer, de ranger, de calculer.

Apprentissage passif ou actif

Les données, elles, ont été le plus souvent collectées à l’avance, mais il peut également s’agir de données que le même programme va chercher à obtenir par interaction avec l’environnement : on parle alors d’apprentissage actif.

On peut formaliser le fait qu’il reçoit à chaque étape une récompense (ou une punition) et ajuste son comportement au mieux en fonction de ce retour. Ce type d’apprentissage a aussi été formalisé, on parle d’apprentissage par renforcement.

Les trois grands types de modèles.

Le modèle peut être de nature géométrique : typiquement, les données sont des points dans un espace de très grande dimension, et le modèle donne l’équation pour séparer le mieux possible les différentes étiquettes. Le modèle peut-être logique : il sera alors un ensemble de règles qui permettront dans le futur de dire si un nouvel objet est d’une catégorie ou d’une autre. Le modèle peut être probabiliste : il nous permettra de définir, pour un nouvel objet, la probabilité d’être dans telle ou telle catégorie.

Inférer : où l’informatique fait concurrence aux devins.

Reste à savoir utiliser le modèle appris, ou choisir parmi un ensemble de modèles possibles. L’inférence est souvent un problème d’optimisation : trouver la meilleure prédiction étant donné le(s) modèle(s) et les données. Les arbres de décision (étudiés aujourd’hui au lycée) permettent, pour les valeurs d’un modèle et des données, de calculer la probabilité de rencontrer ces données si on considère le modèle et ses valeurs. La question de l’inférence est en quelque sorte l’inverse, celle de choisir le modèle étant donné un certain ensemble de données.

Ici on raisonne souvent en terme de probabilité, il faut donc évaluer le risque, au delà du coût lié à chaque choix.

Ouaouh ! Alors il y a des maths en dessous ?

Oui oui ! Et de très jolies mathématiques, par exemple on peut se poser la question suivante :

De quel nombre m de données ai-je besoin
pour faire une prédiction avec une erreur ε en prenant un risque δ ?

Croyez-nous ou non, pour certains modèles la formule existe, et elle peut prendre cette forme :

et nous la trouvons même assez jolie. C’est Leslie Valiant qui l’a proposée dans un cadre un peu idéal. Son formalisme permet de convertir ce qui était fondamentalement un problème mal posé, en un problème tout à fait mathématique. Leslie Valiant a d’ailleurs reçu le Turing Award (l’équivalent du prix Nobel pour l’informatique) en 2011 pour cela. D’autres chercheurs, comme Vladimir Vapnik, ont proposé d’autres formules pour quantifier dans quelle mesure ces algorithmes sont capable de généraliser ce qui a été appris à n’importe quel autre donnée qui peut arriver.

Il ne s’agit pas d’un pur problème de statistique, c’est aussi un enjeu en terme de complexité. Si le nombre m de données explose (augmente exponentiellement) en fonction des autres paramètres, aucun algorithme ne fonctionnera en pratique.

Mais ce petit détour vers les maths nous montre que l’on peut donc utiliser le résultat de l’apprentissage pour prendre des décisions garanties. À condition que la modélisation soit correcte et appropriée au problème donné. Si on utilise tout ça sans chercher à bien comprendre, ou pour leur faire dire et faire des choses hors de leur champ d’application, alors ce sera un échec.

Ce n’est donc peut-être pas des algorithmes dont il faut avoir peur aujourd’hui, mais de ceux qui essayent de s’en servir sans les avoir compris.

Philippe Preux, Marc Tommasi, Thierry Viéville et Colin de la Higuera

29 juin 2015
L’apprentissage automatique : pas à pas !
Du 6 au 11 juillet, Lille accueille ICML (International Conference on Machine Learning), le rendez-vous annuel des chercheurs en machine learning, ce qu’on traduit souvent en français par apprentissage automatique ou apprentissage artificiel. Donnons la parole à Colin de la Higuera pour nous faire découvrir ce domaine. Thierry Viéville et Sylvie Boldo.

Apprentissage automatique (machine learning) dites-vous ?

Il est très probable qu’à l’heure où vous lisez ces lignes, vous aurez utilisé le résultat d’algorithmes d’apprentissage automatique plusieurs fois aujourd’hui : votre réseau social favori vous peut-être a proposé de nouveaux amis et le moteur de recherche a jugé certaines pages pertinentes pour vous mais pas pour votre voisin. Vous avez dicté un message sur votre téléphone portable, utilisé un logiciel de reconnaissance optique de caractères, lu un article qui vous a été proposé spécifiquement en fonction de vos préférences et qui a peut-être été traduit automatiquement.

Et même sans avoir utilisé un ordinateur, vous avez été peut être écouté les informations : or la météo entendue ce matin, la plupart des transactions et des décisions boursières qui font et défont une économie, et de plus en plus de diagnostics médicaux reposent bien plus sur les qualités de l’algorithme que sur celles d’un expert humain incapable de traiter la montagne d’informations nécessaire à une prise de décision pertinente.

De tels algorithmes ont appris à partir de données, ils font de l’apprentissage automatique. Ces algorithmes construisent un modèle à partir de données dans le but d’émettre des prédictions ou des décisions basées sur les données [1].

Mais depuis quand confie t’on cela à des algorithmes ?

L’idée de faire apprendre la machine pour lui donner des moyens supplémentaires est presque aussi ancienne que l’informatique. C’est Alan Turing lui-même qui après avoir, en 1936, jeté les bases conceptuelles du calcul sur machine, donc de l’ordinateur, allait s’intéresser à cette possibilité. Il envisage en 1948 des « learning machines » susceptibles de construire elles-mêmes leurs propres codes.

Tout compte fait, c’est une suite logique de cette notion de machine de calcul dite universelle (c’est à dire qui peut exécuter tous les algorithmes, comme le sont nos ordinateurs ou nos smartphone). Puisque le code d’une machine, le programme, n’est qu’une donnée comme les autres, il est raisonnable d’envisager qu’un autre programme puisse le transformer. Donc pourquoi ne pas apprendre de nouveaux programmes à partir de données?

Vue la quantité astronomique de donnée, on peut apprendre simplement en les analysant. Mais les chercheurs se sont rendus compte que dans ce contexte, un programme qui se comporte de manière déterministe n’est pas si intéressant. C’est le moment où on découvre les limites de ce qui est décidable ou indécidable avec des algorithmes. Il faut alors introduire une autre idée : celle d’exploration, de recours au hasard, pour que de telles machines soient capables de comportements non prévus par leur concepteur.

Il y a donc une rupture entre programmer, c’est à dire imaginer et implémenter un calcul sur la machine pour résoudre un problème, et doter la machine de la capacité d’apprendre et de s’adapter aux données. De ce fait, on ne peut plus systématiquement prévoir un comportement donné, mais uniquement spécifier une classe de comportements possibles.

©Mae59

Alors … ça y est ? Nous avons créé de l’intelligence artificielle (IA) ?

C’est une situation paradoxale, car le terme d’IA veut dire plusieurs choses. Quand on évoque l’intelligence artificielle, on pense à apprendre, évoluer, s’adapter. Ce sont des termes qui font référence à des activités cognitives qui nous paraissent un ordre de grandeur plus intelligentes que ce que peut produire un calcul programmé.

Et c’est vrai qu’historiquement, les premiers systèmes qui apprennent sont à mettre au crédit des chercheurs en IA. Il s’agissait de repousser les frontières de la machine, de tenter de reproduire le cerveau humain. Les systèmes proposés devaient permettre à un robot d’être autonome, à un agent de répondre à toute question, à un joueur de s’améliorer défaite après défaite.

Mais, on s’accorde à dire que l’intelligence artificielle n’a pas tenu ses promesses [2]. Pourtant ces algorithmes d’apprentissage automatique, une de ses principales composantes, sont bel et bien présents un peu partout aujourd’hui. Et ceci, au delà, du fait que ces idées sont à la source de nombreuses pages de science-fiction.

C’est peut-être notre vision de l’intelligence qui évolue avec la progression des sciences informatiques. Par exemple, pour gagner aux échecs il faut être bougrement intelligent. Mais quand un algorithme qui se contente de faire des statistiques sur un nombre colossal de parties défait le champion du monde, on se dit que finalement l’ordinateur a gagné « bêtement ». Ou encore: une machine qui rassemble toutes les connaissances humaines de manière structurée pour que chacun y accède à loisir sur simple demande, est forcément prodigieusement intelligente. Mais devant wikipédia, qui incarne ce rêve, il est clair que non seulement une vision encyclopédique de l’intelligence est incomplète, mais que notre propre façon de profiter de notre intelligence humaine est amenée à évoluer, comme nous le rappelle Michel Serres [3].

Passionnant ! Mais à Lille … que va t’il se passer ?

L’apprentissage automatique est maintenant devenu une matière enseignée dans de nombreux cursus universitaires. Son champ d’application augmente de jour en jour : dès qu’un domaine dispose de données, la question de l’utilisation de celles-ci pour améliorer les algorithmes du domaine se pose systématiquement.

Mais c’est également un sujet de recherche très actif. Les chercheurs du monde entier qui se retrouveront à Lille dans quelques jours discuteront sans doute, parmi d’autres, des questions suivantes :
- Une famille d’algorithmes particulièrement efficace aujourd’hui permet d’effectuer un apprentissage profond (le « deep learning »). De tels algorithmes simulent une architecture complexe, formées de couches de neurones artificiels, qui permettent d’implémenter des calculs distribués impossibles à programmer explicitement.
- L’explosion du phénomène du big data est un levier. Là où dans d’autres cas, la taille massive des données est un obstacle, ici, justement, c’est ce qui donne de la puissance au phénomène. Les algorithmes, comme ceux d’apprentissage profond, deviennent d’autant plus performants quand la quantité de données augmente.
- Nul doute que des modèles probabilistes de plus en plus sophistiqués seront discutés. L’enjeu aujourd’hui est d’apprendre en mettant à profit le hasard pour explorer des solutions impossibles à énumérer explicitement.
- La notion de prédiction sera une problématique majeure pour ces chercheurs qui se demanderont comment utiliser l’apprentissage sur une tâche pour prévoir comment en résoudre une autre.
- Les applications continueront à être des moteurs de l’innovation dans le domaine et reposent sur des questions nouvelles venant de secteurs les plus variés : le traitement de la langue, le médical, les réseaux sociaux, les villes intelligentes, l’énergie, la robotique…
Il est possible –et souhaitable- que les chercheurs trouvent également un moment pour discuter des questions de fond, de société, soulevées par les résultats de leurs travaux. Les algorithmes apprennent aujourd’hui des modèles qui reconnaissent mieux un objet que l’œil humain, qui discernent mieux les motifs dans des images médicales que les spécialistes les mieux entrainés. La taille et la complexité des modèles en font cependant parfois des boîtes noires : la machine peut indiquer la présence d’une tumeur sans nécessairement pouvoir expliquer ce qui justifie son diagnostic : sa « décision » reposera peut-être sur une combinaison de milliers de paramètres, combinaison que l’humain ne connaît pas.

Or, quand votre médecin vous explique qu’il serait utile de traiter une pathologie, il vous explique pourquoi. Mais quand la machine nous proposera de subir une intervention chirurgicale, avec une erreur moindre que le meilleur médecin, sans nous fournir une explication compréhensible, que ferons-nous ?

wikipedia

Et .. pour en savoir plus sur tout cela ?

C’est tout à fait passionnant et … très sérieux.

Pour l’apprentissage automatique, nous allons vous lancer un défi. Revenez sur binaire dans quelques jours et nous allons oser vous expliquer ce qui se trouve sous le capot : comment la machine construit des modèles et les exploite ensuite. Et vous verrez que si un sorcier ou une sorcière avait osé proposé une telle machine il y a quelques siècles, c’est sur un bûcher qu’elle ou il aurait fini.

Et pour mieux comprendre toutes les autres facettes de la science informatique deux revues et un blog sont à votre service : comment donner un sens à l’image numérique, comment marche la traduction automatique, en quoi notre cerveau est plus rapide que nous pour reconnaitre un objet , les nouveaux liens entre robots et des humains ? Voici quelques exemples de ce que vous y trouverez.

Colin de la Higuera

Bibliographie et références
- En mai 2015, 4 articles ont été publiés dans Nature sur l’apprentissage artificiel. Parmi celles-ci, l’article de Zoubin Ghahramani.
- Probabilistic machine learning and artificial intelligence. Zoubin Ghahramani. Nature 521, 452–459
- Apprentissage artificiel. Antoine Cornuéjols et Laurent Miclet – Eyrolles Collection : Algorithmes – 2e édition – juillet 2011.
- Le numéro de mai 2015 de Thinkovery contient un long dossier intitulé « La machine peut-elle être intelligente ? »
- Intelligence artificielle. Stuart Russel, Peter Norvig. Pearson Education. Collection Informatique
- Machine Learning. Peter Flach. Cambridge University Press.
- Computing machinery and intelligence. Alan M. Turing. Mind, 59, 433-460 (1950).
23 juin 2015
Décidable, indécidable ?
En informatique, des mots de la vie courante prennent un sens particulier, précis, peut-être inattendu. Nous allons expliquer ici « décidable ».

Gnirut © S. Auvin

En informatique, un problème est décidable s’il est possible d’écrire un algorithme qui résolve ce problème. Certains problèmes sont indécidables. Considérons par exemple le « problème de l’arrêt ». Le problème de l’arrêt consiste à déterminer, étant donné un programme informatique et des données en entrée pour ce programme, si le programme va finir pas s’arrêter ou s’il va continuer pour toujours. Alan Turing a prouvé en 1936 qu’il n’existait pas d’algorithme qui permette de résoudre le problème de l’arrêt, que ce problème était indécidable. L’informatique ne peut donc pas résoudre tous les problèmes. À binaire, on s’en doutait. Encore fallait-il le prouver. Turing l’a fait.

Cette notion de décidabilité se retrouve en logique. Une affirmation logique est dite décidable si on peut la démontrer ou démontrer sa négation dans le cadre d’une théorie donnée. Gödel a démontré (avant Turing, en 1933) un résultat d’incomplétude sur la décidabilité en logique. Certains résultats ne sont donc ni vrais ni faux, mais indécidables : cela signifie que l’on a démontré, à tout jamais, que nous pourrons pas savoir s’ils sont vrais ou faux. Alors si vous avez été frustré parce que vous n’avez pas compris certains cours de maths, consolez vous. Les mathématiques aussi ont des limites. Et oui …

Cette notion d’indécidabilité a une conséquence plus subjective, dans nos rapports avec la science. Nous ne sommes pas confrontés à un dogme surpuissant et sans limite, mais bien à une démarche qui cherche à comprendre ce qu’il est possible de comprendre, qui explore sans cesse ses propres limites.

Pour aller plus loin :
- Consulter l’article Binaire de Sylvie Boldo.
- Interstices nous en dit plus sur ce sujet avec Jean-Gabriel Ganascia.
- J.P. Delayahe nous nous parle de démonstrations mathématiques.
- Wikipedia détaille la définition de décidabilité.
Serge Abiteboul, Thierry Viéville.
17 juin 2015
Science informatique dites vous ? Deux revues et un blog à votre service.

Il est important que, des actrices et acteurs … aux utilisateurs et utilisatrices du numérique, nous partagions une culture en sciences du numérique, pour comprendre et maîtriser les technologies qui en sont issues.

Pour concrétiser ce partage avec le monde de la recherche, la Société Informatique de France, Inria et le CNRS proposent deux revues et un blog : profitons-en !

1024 ? Une revue pour les professionnelles et les professionnels du monde de l’enseignement, de la recherche et de l’industrie de l’informatique qui permet de découvrir les différentes facettes de cette science.

)I(nterstices ? La revue de culture scientifique en ligne qui invite à explorer les sciences du numérique, à comprendre ses notions fondamentales, à mesurer ses enjeux pour la société, à rencontrer ses acteurs et actrices.

Binaire ? Le blog du monde.fr qui parle de l’informatique, de ses réussites, de son enseignement, de ses métiers, de ses risques, des cultures et des mondes numériques.

12 juin 2015
Complexité ? Même pas mal !

En informatique, des mots de la vie courante prennent un sens particulier, précis, peut-être inattendu. Nous allons expliquer ici « complexité ». Thierry Viéville.

© INRIA / Projet VASY- Univ de Eindhoven

Le terme complexité a un sens très précis en informatique, en fait plusieurs sens.

il y a la théorie de la complexité qui étudie la quantité de ressources (par exemple en temps, en espace, en communication) nécessaire pour la résolution de problèmes au moyen de l’exécution d’un algorithme. Ainsi, on dira par exemple d’un algorithme qu’il a une “complexité en temps élevée” non pas parce qu’il est compliqué à comprendre, mais parce qu’il demande un grand nombre d’opérations pour une instance du problème.

Certains problèmes peuvent être résolus extraordinairement vite. Par exemple, chercher un mot dans un dictionnaire d’un milliard de mots peut se faire en … un petit nombre d’opérations élémentaires ! D’autres ont une complexité qui explose avec la taille des données. Par exemple, pour remplir au maximum un sac à dos, sans dépasser une borne fixée, avec des objets de poids différents, cela peut nécessiter d’explorer plus d’un milliard de configurations pour une trentaine d’objets. Pour bien comprendre un problème, il est important d’étudier la complexité des algorithmes qui permettent de le résoudre, voire de découvrir des bornes théoriques qui montrent qu’il est impossible de le résoudre avec des ressources trop limitées.

Une autre notion importante est la mesure de complexité d’un message ou d’une information. C’est la forme “algorithmique” de la mesure de l’information, dite de Kolmogorov. Un message est complexe si le plus petit programme qui génère ce message est obligatoirement de grande taille. Il y aussi une forme “probabiliste”, de Shannon, qui fonde une théorie de l’information plus mathématique. Il est important de connaitre la complexité d’un message quand on veut le transmettre, le compresser ou le chiffrer. Il est aussi amusant de savoir que parmi tous les messages sans fin (de longueur infinie) très peu peuvent être générés par un algorithme. Une infinité non-dénombrable d’entre eux sont complètement imprédictibles.

On voit donc que la notion de complexité s’applique à la fois aux données et aux traitements sur ces données. Elle permet de comprendre les limites de ce que l’on peut faire avec des algorithmes. Avec elle, l’informatique propose des fondements théoriques qui permettent de mieux comprendre les programmes informatiques et les données numériques.

L’article original est à consulter sur le site de pixees.fr. Éléments recueillis grâce à Sylvie Boldo, Florent Masseglia et Pierre Bernhard.

20 mai 2015
Nos ordinateurs ont-ils la mémoire courte ?

Quelles images, quels sons, quels écrits de notre société numérique restera‐t‐il, quand les archéologues du futur, dans quelques siècles, chercheront à reconstituer nos données, désormais de moins en moins « ancrées » dans la matière ? Notre civilisation est-elle encore capable de produire de la mémoire ? Une réponse, positive, est donnée à travers ce reportage vidéo de 52 mn de Zed distribution Télévision.

Depuis que s’est développée l’informatique de masse, nos informations et tout notre patrimoine collectif est codé en binaire sur des supports dont la pérennité semble dérisoire par rapport à la mémoire de papier de nos bibliothèques ou à ce que l’antiquité nous a laissé gravé dans la pierre. Or, nous allons laisser aux enfants de nos enfants pour des siècles et des siècles, un héritage culturel, mais aussi un monstrueux héritage de déchets radioactifs. Il faut arriver à faire que toute cette mémoire ne se perde pas.

Le film chez Zed distribution télévision

En réaction à ce problème majeur, ce reportage montre comment des chercheurs se livrent à une véritable course, une course contre l’oubli. Au-delà des solutions par recopie de nos données à travers la vis sans fin des mutations technologiques de notre monde numérique dans des centres de données, c’est en revenant vers l’encre et le papier que des données qui doivent traverser le temps sont archivées, à côté de véritables message gravés dans la géologie de notre sol, sur du quartz. On se tourne aussi vers un support bien plus fragile mais prodigieusement miniaturisé et pérenne : l’ADN.

Standards pour le codage des données ? Mécanismes de codes correcteurs d’erreurs et de duplication des données pour les rendre robustes aux altérations ? Prise en compte du fait que ces données sont mouvantes pour garder aussi la mémoire de l’histoire de l’évolution de ces données ? Outils informatiques efficaces pour exploiter et garder ce qui est noyé dans la masse des informations humaines ? Ce sont ces questions que le reportage nous offre en partage.

Se pose alors, au-delà de ce reportage, le problème de la pertinence des données, dans une société où la mémoire collective explose. Quelle information pertinente devons-nous collecter ? Que devons nous conserver pour ne pas nous noyer dans un océan de mémoire ? De quel droit à l’oubli disposons-nous face à cette hypermnésie ? Ce qu’il restera se fera-t-il à l’insu de notre plein gré ou thésauriserons-nous ce que nous pensons être de plus précieux ? Et qui peut dire ce qu’il faut garder dans cette arche de Noé de la mémoire humaine ?

Serge Abiteboul, Thierry Viéville.

18 mai 2015
Les limites de la calculabilité

Entretien autour de l’informatique : David Harel

Le Professeur David Harel de l’Institut Weisman a accordé un entretien à Serge Abiteboul et Maurice Nivat. David Harel est une des étoiles de l’informatique. Il a démontré des résultats théoriques éblouissants, apporté des contributions essentielles à l’ingénierie du logiciel et écrit un livre de vulgarisation qui est un point d’entrée exceptionnel sur le domaine. David Harel est aussi très engagé politiquement en Israël dans les mouvements pour la paix.

David Harel

Choisir entre sciences et technologie ?

B : David, quel est celui de tes résultats dont tu es le plus fier ?
DH : si je mets à part mes cinq enfants et cinq petits-enfants, si je ne parle que de mes contributions professionnelles, il m’est difficile ce choisir entre deux : un théorème que j’ai démontré avec Ashok Chandra et le formalisme graphique des « state charts » (diagrammes états-transitions).

Le théorème établi avec Ashok étend la notion de calculabilité de Turing à des structures arbitraires. Dans un premier temps, il a été énoncé pour des structures de bases de données, ensuite il a été étendu à d’autres structures, en particulier par toi, Serge.

Les diagrammes états-transitions ne recèlent en fait aucune théorie ; il s’agit d’un langage visuel pour décrire des systèmes réactifs, riches d’interactions entre leurs composants. Le succès d’un langage se mesure au nombre de gens qui l’utilise. Comme le dit un proverbe anglais, « the proof of the pudding is in the eating » (c’est l’appétit avec lequel on le mange qui démontre la qualité du pudding). Le langage des diagrammes états-transitions a été adopté par de nombreuses personnes et est utilisé couramment dans de nombreuses industries. Il fait aussi partie de normes reconnues et populaires comme UML. L’article originel qui introduit ce langage a été cité plus de huit mille fois. Ce succès est sans doute dû au fait que c’est un langage visuel très clair qui s’inspire de la topologie.

Diagramme états-transitions d’une petite partie d’une bactérie dans son état de nage

B : cela t’a-t-il pris longtemps de concevoir ce concept de diagramme états-transitions ?
DH : non, non, j’étais consultant auprès d’industries de l’aéronautique un jour par semaine, et l’idée de ce langage m’est venue après quelques semaines de discussion avec les ingénieurs. Une représentation graphique m’est apparue comme le meilleur moyen de décrire les genres de comportements que nous cherchions à formaliser. J’en ai parlé à Amir Pnueli, en lui présentant la chose comme une extension très simple de la notion d’automate fini, rien de bien profond. Mais Amir a trouvé cela intéressant et m’a encouragé à en faire un article scientifique, ce que j’ai fait. Cet article a été rejeté à plusieurs reprises par des revues auxquelles je l’avais soumis et il a fallu trois ans avant qu’il ne soit publié. Cela veut bien dire, entre autres choses, qu’il ne faut pas abandonner une idée que l’on croit bonne juste parce que des revues rejettent l’article qui l’expose.

David avec un diagramme d’états-transitions et un peu de logique temporelle. 1984.

Culture informatique

B : nous sommes des admirateurs de ton livre de 1987 intitulé « Algorithmics : the spirit of computing » (Algorithmique : l’esprit du calcul). Tu n’as pas cité cet ouvrage comme une de tes plus importantes contributions ?
DH : il fallait que je choisisse, mais je suis content que vous me parliez de ce livre. C’est une tentative de présenter les idées fondamentales de l’informatique au grand public, aux masses dirait un politicien. Le plus difficile était de choisir ce que j’allais mettre dedans. Notre discipline est toujours jeune, nous manquons de recul. Ce n’est pas facile de distinguer ce qui est vraiment fondamental et qui ne s’effacera pas avec le temps. Il y a eu plusieurs éditions successives mais en fait elles ne sont pas très différentes de la première.

Une expérience très riche pour moi a aussi été une émission de radio, en hébreu, en 1984, au cours de laquelle je devais expliquer, à une heure de grande écoute, ce qu’était l’informatique. Ce n’est pas simple, à la radio, on a les mains liées, on ne peut rien montrer, ni graphique, ni schéma, ni dessein. C’est quand même possible, même si c’est difficile. Beaucoup d’auditeurs ont compris et ont aimé ce que j’ai raconté.

©Addison-Wesley 1987

©Pearson 2004

©Springer 2012

B : qui peut lire ton livre ?
DH : tous ceux qui ont un petit bagage scientifique peuvent comprendre. Quelques connaissances de mathématiques aident et surtout une façon de penser logique ou structurée. Si vous n’avez pas ça, vous risquez de passer à côté de certaines notions, par exemple de la notion de réductibilité d’un problème à un autre. Vous pouvez « réduire » un problème donné A à un autre problème B, en d’autres termes, si vous savez résoudre le problème B, alors vous pouvez aussi résoudre A. Cette technique permet de hiérarchiser la difficulté des problèmes, y compris ceux qui ne sont pas résolubles par une machine, les problèmes que l’on nomme indécidables. La même technique permet de hiérarchiser les algorithmes en fonction de leur efficacité.

Voici que nous avons parlé de trois de mes contributions, l’une scientifique, la seconde plutôt technique et la troisième culturelle, si j’appelle culturelle la partie de la connaissance qui est accessible au plus grand nombre !

Enseignement de l’informatique

B : un des sujets favoris de Binaire est l’enseignement de l’informatique. Penses-tu que l’informatique doit être enseignée à l’école ?
DH : Je n’ai aucun doute là dessus ! Oui ! Mais pas seulement les ordinateurs, ou le « code », ce qu’il faut enseigner c’est vraiment la science informatique. J’ai participé il y a quelques années à la définition d’un programme d’enseignement de l’informatique au lycée dans mon pays, Israël. Jusque là on enseignait seulement une peu de code, c’est-à-dire très peu de raisonnement, très peu d’esprit du calcul. Nous avons proposé le principe de la « fermeture éclair », un principe d’alternance : un peu de théorie, un peu de pratique, un peu de théorie, etc. Le programme israélien actuel comporte deux niveaux, un pour les élèves ordinaires, bases de la notion de calcul et un peu de programmation (je crois qu’elle se fait en Java) et un niveau plus avancé comportant des notions plus approfondies d’algorithmique, y compris les automates finis.

David Harel et Maurice Nivat

C’est important d’enseigner la pensée informatique, (ce que Jeannette Wing appelle « computational thinking ») car cela devient indispensable dans la vie moderne, et pas seulement pour se servir d’un ordinateur ou d’une autre machine plus ou moins électronique. C’est indispensable pour organiser sa vie, par exemple, son emploi du temps, et planifier ses actions.

Un simple exemple est quand vous déménagez avec l’aide de copains qui arrivent tous avec des véhicules de tailles diverses, une berline, une jeep, une camionnette. Il faut placer toutes vos affaires, meubles, cartons dans ces véhicules sans les surcharger. Pour bien comprendre ce problème, il faut savoir qu’il est ce que l’on appelle « NP-difficile », et évidemment comprendre ce que NP-difficile veut dire. Mettre des petites boites dans des grandes est un problème algorithmique, c’est de l’informatique.

En fait, il ne suffit pas d’enseigner l’algorithmique « classique » ; les élèves doivent aussi apprendre ce qu’est un système réactif (cette expression a été proposée par Amir Pnueli et moi-même en 1980) dans lesquels des composants réagissent entre eux et aussi à des sollicitations extérieures venues d’opérateurs humains ou de capteurs. C’est une autre facette de l’informatique qui doit aussi être enseignée.

Elephant, Wikipedia

Le test de l’éléphant

B : nous t’avons entendu poser la question suivante sur le net : quand peut-on dire que l’on a construit un modèle de la nature ?
DH : l’idée est d’étendre le test de Turing à la simulation de systèmes naturels, comme le temps qu’il fait, ou un organisme vivant. Supposons par exemple que nous voulions modéliser un éléphant ? Quand saurons-nous que nous comprenons tout de l’éléphant ? Quand nous aurons fabriqué un modèle exécutable dont le comportement ne se distingue pas de celui d’un éléphant naturel, un éléphant de laboratoire dont personne, quand même les personnes qui connaissent le mieux les éléphants ne peuvent faire de différence au niveau du comportement et des réactions aux sollicitations extérieures entre l’éléphant artificiel et un véritable éléphant. C’est seulement dans ce cas que nous pouvons dire que notre modèle est une théorie de l’éléphant.

Maintenant comparons cela au test de Turing. Si l’ordinateur de Serge, par exemple, passe avec succès le test de Turing, nous pouvons dire qu’il est intelligent et le restera pour toujours. Si mon éléphant de laboratoire passe avec succès le test de l’éléphant que je viens de décrire, cela signifie seulement qu’aujourd’hui les meilleurs connaisseurs des éléphants considèrent mon éléphant comme un modèle valide. Mais si quelqu’un demain découvre quelque nouvelle propriété de l’éléphant que mon modèle d’éléphant ne possède pas, alors mon modèle cesse d’être valide. Ce qui n’est pas une nouvelle catastrophique, bien au contraire ; c’est ça qui est fantastique car c’est comme ça que la science progresse, des modèles nouveaux plus riches viennent se substituer aux anciens. Einstein va plus loin que Newton ; et la mécanique quantique va plus loin qu’Einstein.

A un échelle beaucoup plus modeste, j’ai rencontré ce genre de situation. Nous avions construit un modèle de cellules biologiques. Des biologistes n’aimaient pas un aspect particulier de notre model. Cela les a amenés à poursuivre leurs recherches et en quelques mois ils ont découvert le véritable mécanisme déterminant le comportement de ces cellules ! Un nouveau défi et la science avance !

Quand on essaye de modéliser le vivant, des objets biologiques, ou bien des systèmes extrêmement complexes comme la météo, je pense qu’on ne peut pas espérer la complétude.

Le « Wise computing »

B : peux-tu nous dire sur quoi tu travailles ou réfléchis en ce moment ?
DH : j’appelle cela « wise computing » (calcul sage). Il ne s’agit pas seulement d’écrire que l’ordinateur écrive des programmes intelligents à notre place, il s’agit de développer du logiciel avec la machine, en collaboration avec la machine. Nous sommes déjà habitués à dire à la machine, sous une forme ou une autre, ce que nous voulons qu’elle fasse. Je voudrais que la machine participe aussi activement au processus de développement, comme un partenaire, sur un pied d’égalité ! La machine pourrait vérifier ce que je propose, le clarifier et le préciser, en corriger les erreurs aussi. Mais je voudrais aussi qu’elle en comprenne les intentions, qu’elle pose des questions, qu’elle fasse des suggestions, tout ceci en utilisant les moyens les plus sophistiqués. Ce que moi et mes collaborateurs avons déjà réalisé est encore bien limité mais nous progressons.

Un nain sur les épaules d’un géant

Le géant Orion portant sur ses épaules son serviteur Cedalion (Wikipedia)

B : qu’as-tu envie de dire, David, pour conclure cet entretien ?
DH : je voudrais revenir à Turing. C’est un géant. J’ai travaillé sur la calculabilité à la Turing, sur le test de Turing, sur des problèmes de biologie, liés au travail de Turing sur la morphogenèse. Et je me suis toujours senti comme un nain sur les épaules d’un géant. Cela prend des années de construire une science. Il y a encore des gens qui croient que l’informatique n’en est pas une ou que c’est une science sans profondeur, mais il y en a de moins en moins. Il va falloir encore des années pour qu’il n’y en ait plus du tout. Je n’ai aucun doute qu’un jour Turing parviendra au sommet du panthéon des grands penseurs, pour y rejoindre Newton, Einstein, Darwin et Freud.

David Harel, Institut Weizman

A la mémoire de Ashok Chandra

Ashok Chandra

David Harel et Binaire dédient cet interview à la mémoire de Ashok Chandra, collègue et ami de David, décédé en 2014 Ashok était informaticien dans la compagnie Microsoft. Il dirigeait le Centre de recherche sur les services Internet à Mountain View. Précédemment il avait dirigé l’unité « Bases de Données et Systèmes Distribués » du Centre de recherche de la compagnie IBM à Almaden. Il a été le coauteur de plusieurs articles fondamentaux en Informatique théorique. Entre autres choses, il a introduit les machines de Turing alternées en théorie du calcul (avec Dexter Kozen et Larry Stockmayer), les requêtes conjonctives dans les bases de données (avec Philip Merlin), les requêtes calculables (avec David Harel) et la complexité de communication (avec Merrick Furst et Richard Lipton).

22 avril 2015
Prix Turing : les bases de données à l’honneur

Après avoir beaucoup parlé de Turing, nous ne pouvions pas faire l’impasse sur le prestigieux prix décerné en mars dernier mettant à l’honneur un chercheur pour ses travaux dans le domaine de l’informatique. C’est Michael Stonebraker qui a remporté cette distinction pour ses contributions dans le domaine des bases de données. Pour nous en parler, Patrick Valduriez, spécialiste mondial du domaine et primé en 2014 pour son expertise dans ce domaine (Prix de l’Innovation, Inria, Académie des sciences, Dassault Systèmes), nous présente le lauréat et nous éclaire sur les enjeux des fameux SGBD.

crédit photo M. Scott Brauer

Michael Stonebraker, chercheur au Massachusetts Institute of Technology (USA), vient de remporter le prestigieux Prix Turing de l’ACM, souvent considéré comme « le prix Nobel de l’informatique ». Dans son annonce du 25 mars 2015, l’ACM précise que Stonebraker « a inventé de nombreux concepts qui sont utilisés dans presque tous les systèmes de bases de données modernes… ». Cette reconnaissance au plus haut niveau international me donne l’occasion de donner un éclairage sur la place singulière du domaine de la gestion de données dans la recherche en informatique.

La gestion de données se préoccupe du stockage, de l’organisation, de la recherche et de la manipulation de données de toutes sortes, souvent très grandes et complexes. Le principe fondateur de la gestion de données est l’indépendance des données, qui permet de travailler avec les données à un niveau conceptuel, tout en ignorant les détails d’implémentation. Le modèle relationnel, en s’appuyant sur une théorie simple et solide (ensembles, logique du 1^er ordre) a révolutionné la façon de concevoir les SGBD.

C’est un domaine où le transfert continu de résultats de labos de recherche vers l’industrie a été depuis les débuts remarquable, conduisant notamment au développement des systèmes de gestion de bases de données (SGBD), au cœur de la plupart des systèmes d’information modernes. C’est aujourd’hui un domaine majeur de l’informatique, avec à la fois une grande communauté de recherche et une industrie forte.

L’innovation majeure des SGBD relationnels a été de permettre la manipulation de données avec des langages de requêtes déclaratifs (on définit les données qui nous intéressent et on laisse le système décider comment les calculer) intégrant des concepts puissants comme les transactions qui garantissent que notre travail ne peut pas être compromis par une panne ou un autre utilisateur de la même base de données. Arrivés sur le marché dans les années 1980, les SGBD relationnels ont remarquablement réussi le test du temps, par l’ajout régulier de nouvelles fonctionnalités (par ex. sécurité), de nouveaux types de données (ex. objet, XML ou JSON) et en s’adaptant à toutes sortes de plateformes, depuis les appareils mobiles (par ex. smartphones) jusqu’aux très grands clusters dans des environnements distribués.

Aujourd’hui, avec les nouveaux défis du big data et du cloud, la gestion de données doit être réinventée, tant les besoins des utilisateurs et des applications sont divers et ne peuvent plus s’accommoder de l’aspect « taille unique » des SGBD relationnels. La recherche en gestion de données devient alors pluridisciplinaire, associant notamment chercheurs et grands producteurs de données pour mieux étudier leurs données (analyse de « big data »). En France, ces défis sont au cœur d’initiatives pluridisciplinaires récentes comme le défi CNRS Mastodons (grandes masses de données scientifiques) et le GdR MaDICS (Masses de Données, Informations et Connaissances en Sciences).

En 40 ans de carrière, Stonebraker a profondément marqué le domaine des SGBD, depuis le relationnel au big data. Sa récompense s’ajoute à celles de trois autres prix Turing du domaine : Charles Bachman (1973) pour ses contributions aux SGBD navigationnels, Edgard Frank Codd (1981) pour l’invention du modèle relationnel et James Gray (1998) pour ses contributions aux SGBD et au transactionnel.

Stonebraker a d’abord été un pionnier dans la conception de SGBD relationnels, en dirigeant des projets de recherche influents comme Ingres et Postgres. Il a aussi été un entrepreneur exceptionnel, en créant neuf startups autour de ses projets. Aujourd’hui, Stonebraker poursuit ses travaux au MIT autour des systèmes NoSQL.

Patrick Valduriez, Inria

20 avril 2015
La publication scientifique : Le temps des dérives
Pascal Guitton nous a expliqué les principes de la publication scientifique et son passage au numérique dans un premier article. Il aborde maintenant pour nous des dérives récentes du système. Il nous parle d’un futur souhaitable fait de publications ouvertes et d’épi-journaux. Serge Abiteboul et Thierry Viéville.

Le numérique a contribué à améliorer le travail des chercheurs en enrichissant le contenu des publications numériques, en favorisant la recherche d’un article dans la masse gigantesque de documents disponibles, et en optimisant les modalités et le temps d’accès à l’information. Malheureusement, dans le même temps, ces évolutions se sont accompagnées de dérives qui pourrissent la vie des scientifiques.

Dérive 1 : Le spam dans l’édition scientifique

©Hormel à l’origine le mot SPAM* désignait de la « fake meat »

Certains ont cru détecter la poule aux œufs d’or dans l’évolution numérique de l’édition scientifique. Sont apparues de nulle part des sociétés « expertes» de la création de revues (et de conférences) traitant de tous les sujets et ouvertes à tous. Concrètement, un chercheur reçoit très souvent (plusieurs fois par mois) des messages d’invitation à soumettre ses travaux dans des revues ou des conférences « SPAM (*) » ou alors à participer à leurs comités de lecture qui n’en possèdent que le nom. Certains se laissent abuser, le plus souvent par négligence en n’étant pas assez critique sur la qualité de la revue, parfois par malhonnêteté en espérant augmenter leur visibilité.

L’évaluation par les pairs, comme tout processus humain, peut faillir et conduire à des publications erronées, voire totalement loufoques. Il ne s’agit pourtant là que de dysfonctionnements non représentatifs de la qualité générale du travail de publication. Une évaluation un tant soit peu sérieuse détectera ce type de publication. Il convient toutefois pour les scientifiques de rester vigilants devant l’augmentation récente de ce nombre de situations qui est directement reliée à l’augmentation du nombre de revues et de conférences « parasites ».

Dérive 2 : L’évaluation mal réalisée

©Binaire

Au delà de ces dérives mercantiles, le principal problème résulte de la culture de l’évaluation à outrance qui a progressivement envahi le monde de l’enseignement et la recherche que ce soit au niveau des individus (recrutement, promotions), des laboratoires (reconnaissance, financements) ou des universités/écoles/organismes (visibilité, attractivité).

Entendons-nous bien, ce n’est pas la nécessité d’une évaluation qui est ici remise en cause mais les façons dont elle est trop souvent mise en œuvre. Illustration : dans un premier temps, le nombre de publications d’un chercheur est devenue la référence principale de jugement ; bien que simple et naturel, un comptage brutal ne tient pas compte de leur qualité et de leur ampleur, produisant des « spécialistes » de la production à la chaîne d’articles sans réel impact. (Il est quasiment impossible de s’accorder sur le nombre des articles jamais cités par d’autres scientifiques mais il est élevé). On observe aussi des équipes qui alignent leurs thématiques de recherche sur les sujets « chauds » des revues et/ou synchronisent leurs activités sur le calendrier des conférences importantes, délaissant leur libre arbitre et le propre pilotage de leur recherche.

Dans un deuxième temps, sont apparus des indicateurs numériques sensés remédier à ce problème, en calculant des scores basés sur le nombre de citations que recueille un article. L’idée a d’autant plus de sens que les explosions conjointes au niveau mondial des nombres de chercheurs et de revues ont conduit à une inflation jamais connue jusque là de la production d’articles scientifiques ; s’interroger sur l’impact réel d’une publication est légitime et a suscité de nombreuses méthodes dont les plus connues sont la famille des h-index apparue en 2005 pour les articles et les facteurs d’impact en 2006 pour les revues.

Malheureusement, cette bonne idée souffre de nombreux défauts : tout d’abord, le mélange incroyable entre citations positives (pour mettre en exergue un résultat) et négatives (pour critiquer tout ou partie du travail) ! Ensuite, la taille des communautés qui est le plus souvent oubliée dans l’exploitation de ces indicateurs ; comment raisonnablement comparer des index si le nombre de chercheurs d’un domaine est très différent d’un autre ; pensons par exemple à une thématique émergente qui ne concerne initialement qu’un petit cercle : faut-il l’ignorer parce qu’elle arrive loin dans les classements ? Ce n’est surement pas de cette façon que nous produirons les innovations tant attendues. Par ailleurs, les bases de données utilisées pour calculer ces taux de citation ne couvrent qu’une partie de la littérature scientifique ; en informatique par exemple, moins de la moitié de la production est référencée dans les plus célèbres d’entre elles. Et puis, des esprits malintentionnés ont dévoyé cette bonne idée en mettant en œuvre des pratiques frauduleuses : autocitations abusives, « découpage » artificiel d’un résultat en plusieurs articles pour augmenter le nombre de publications et de citations, cercles de citations réciproques entre auteurs complices, « recommandation appuyée » de certains éditeurs de citer des articles de leur propre revue, etc.

En résumé, ces indicateurs ne devraient fournir qu’un complément d’information à une évaluation plus qualitative et donc plus fine. Malheureusement, une telle analyse nécessite plus de temps et aussi de mobiliser de vrais experts. Il est infiniment plus « facile » de la remplacer par l’examen de quelques chiffres dans un tableur sensés représenter une activité scientifique dont il est bien entendu impossible de réduire ainsi la richesse et la diversité. On peut faire l’analogie avec la qualité d’un livre qui ne serait jugée qu’à travers son nombre de lecteurs ou celle d’une chaîne de télévision qu’à travers son Audimat.

Terminons en rappelant encore une fois qu’il ne s’agit pas d’ignorer ces indicateurs mais bien de les exploiter pour ce qu’ils sont et de les associer systématiquement à des analyses qualitatives réalisées par des experts.

Dérive 3 : le modèle économique

©Binaire

Initialement gérée par les sociétés savantes, l’édition scientifique a progressivement été envahie par une grande diversité d’éditeurs privés. Comme beaucoup d’autres secteurs économiques, elle a connu une forte concentration autour de quelques grands acteurs : Elsevier, Springer, Wiley etc. Depuis sa création, ses ressources provenaient des abonnements que lui payaient les structures académiques pour recevoir les exemplaires des revues souhaitées. Ce système a fonctionné pendant longtemps mais connaît de très grandes difficultés depuis quelques années à cause des augmentations de prix constantes imposées sans réelle justification par ces acteurs dominants. La combinaison de ces hausses avec les baisses que connaissent les budgets de la recherche un peu partout dans le monde a produit un mélange détonnant qui est en train d’exploser. L’attitude intransigeante de ces grands acteurs qui refusent de prendre en compte ces réductions budgétaires et, au contraire, augmentent leurs tarifs et leurs profits est assez surprenante et le changement de modèle économique induit par la transition achat d’exemplaires papier-droit d’accès à des ressources en ligne ne suffit pas à l’expliquer.

Face à cet abus de position dominante, les chercheurs s’organisent pour tenter de résister. En France par exemple, le monde académique s’est mis d’accord pour, d’une part, échanger des informations sur les pratiques respectives vis à vis des éditeurs, et d’autre part, présenter un front uni lors de négociations collectives face à ces sociétés. Certaines communautés, notamment mathématiciennes, françaises et étrangères, se sont mobilisées pour lutter contre ces monopoles en appelant au boycott, non seulement des abonnements, mais également de l’ensemble des processus éditoriaux. En effet, il faut rappeler que sans l’implication primordiale des chercheurs – qui font la recherche, rédigent des articles et les expertisent – offerte gratuitement à ces sociétés privées, elles n’existeraient plus.

Début de solution : l’accès ouvert

Le logo Open Access

C’est notamment pour lutter contre ces dérives en offrant un modèle alternatif que des solutions de type libre accès (Open Access) aux ressources documentaires ont été développées. Initialement, il s’agissait d’offrir un accès gratuit aux publications stockées sur des sites de dépôts gérés par des organisations scientifiques. En France, c’est l’archive ouverte HAL qui joue depuis 2001 un rôle central dans cette démarche en liaison étroite avec les autres grandes archives internationales comme ArXiv créée en 1991. Outre la maîtrise des coûts, l’accès ouvert renforce la visibilité des articles déposés sur une archive ouverte comme le montre plusieurs études.

Ce mouvement en faveur des archives ouvertes est soutenu par de nombreux pays (Canada, Chine, Etats-unis, Grande Bretagne…). Récemment, l’Union européenne et en particulier la France ont pris des positions encore plus nettes en faveur du libre accès. Par exemple, depuis 2013, la direction d’Inria a rendu obligatoire le dépôt des publications sur HAL et seules ces publications sont communiquées aux experts lors des évaluations ou affichées sur le site web de l’Institut.

Les grands éditeurs ont très vite compris le danger pour leurs profits que représentaient ces initiatives ; ils ont donc commencé par adopter des politiques de dénigrement systématique en les moquant, puis, devant l’échec relatif de cette posture, ils ont transformé ce risque en opportunité en se présentant comme les chantres, voire même les inventeurs, de l’accès ouvert et l’expression Open Access fleurit aujourd’hui sur la plupart des sites de ces éditeurs.

Il convient de préciser qu’il existe deux approches principales d’accès ouvert :
- la voie verte (green access) où le dépôt par l’auteur et l’accès par le lecteur sont gratuits ;
- la voie dorée (gold access), dite aussi auteur-payeur, où l’auteur finance la publication (de quelques centaines à quelques milliers d’euros) qui est ensuite accessible en ligne gratuitement.
Le green est aujourd’hui la solution la plus vertueuse mais n’oublions pas que la gratuité n’est qu’apparente car ces infrastructures et ces services représentent un coût non négligeable supporté pour HAL principalement par le CNRS à travers le CCSD. Par ailleurs, certains éditeurs imposent un délai avant le dépôt d’une publication sur une archive ouverte publique (par exemple, 6 mois après sa parution). Outre la légalité parfois discutable de cet embargo, il faut rappeler qu’il est possible de déposer des versions dites preprint, sur des archives ouvertes comme HAL, pour remédier temporairement à ce problème.

Le gold quant à lui présente l’avantage de déplacer en amont et de rendre explicite le coût d’une publication. Cependant, il comporte des inconvénients majeurs, principalement le coût souvent élevé et donc le risque d’accroitre le fossé entre les établissements, voire pays, « riches » et « pauvres ».

Malheureusement, la qualité et la puissance économique du lobbying des grands éditeurs ont réussi à pénétrer beaucoup de cercles de décision nationaux comme européens et à faire confondre l’open access et le gold. Nous entendons et lisons donc des charges contre le libre accès qui n’évoquent que le modèle auteur-payeur et contre lesquelles il est indispensable de faire preuve de pédagogie pour démonter l’artifice.

Encore mieux : les epi-journaux

Le logo http://episciences.org

Au delà du dépôt des articles, il convient de s’interroger sur leur éditorialisation si l’on souhaite proposer une alternative de qualité, et par conséquent crédible, aux revues commerciales. La notion d’epi-journal a donc vu le jour ; il s’agit de construire « au dessus » d’une archive ouverte des structures éditoriales de type revues ou actes. La démarche est tout à fait similaire à celle de l’édition classique : diffusion des règles éditoriales, dépôt des propositions sur un site dédié, expertise par un comité de lecture dont la composition est publique, annonce des résultats aux auteurs, mise en ligne des articles retenus après réalisation des corrections demandées et en respectant une charte graphique, référencement par les moteurs de recherche après saisie des méta-données associées.

Basée sur le projet Episciences, développé et hébergé par le CCSD, il existe dans le domaine Informatique et Mathématiques appliquées une structure qui propose des services pour gérer des épi-journaux :
- les articles sont déposés dans une archive ouverte (HAL, ArXiv, CWI, etc.),
- après lecture et analyse par les éditeurs, les articles soumis reçoivent la validation du comité de lecture,
- ils sont alors publiés en ligne et identifiés exactement comme dans une revue classique (ISSN, DOI, etc.),
- ils sont référencés par les principales plateformes (DOAJ, DBLP, Google scholar…),
- l’epi-journal respecte des règles éthiques,
- il assure un travail de visibilité à travers les conférences et les réseaux sociaux.
Vous pouvez par exemple consulter la revue JDMDH qui vient de démarrer sur ce principe.

Et en conclusion

Ces epi-journaux sont la dernière évolution importante dans le domaine de la publication scientifique. S’ils offrent une réponse potentielle particulièrement adaptée aux problèmes causés par l’augmentation déraisonnable du coût des abonnements aux grands éditeurs, ils sont aujourd’hui encore balbutiants. La principale interrogation provient de leur jeunesse et de leur manque de reconnaissance par les communautés scientifiques. Concrètement, si un jury doit expertiser un dossier individuel ou collectif (équipe, laboratoire), il attachera plus de poids à des publications parues dans des revues installées depuis longtemps et donc plus reconnues.

La seule motivation « militante » pour publier de cette façon ne suffit pas, notamment si l’on pense aux jeunes chercheurs qui sont à la recherche d’un emploi : il est aujourd’hui très difficile de leur faire prendre ce risque sans concertation et réflexion préalables de la part de leurs encadrants qui sont souvent des scientifiques établis qui n’ont plus de souci majeur de carrière. C’est pourquoi il est absolument indispensable que les chercheurs les plus seniors s’impliquent clairement en faveur de ces initiatives : en participant aux comités de lecture de ces épi-journaux afin de les faire bénéficier de leur visibilité individuelle, en contribuant à en créer de nouveaux et surtout en expliquant dans toutes les instances d’évaluation et de recrutement (jurys, comités de sélection, CNU…), la qualité de ces premiers epi-journaux et du crédit que l’on peut leur accorder.

Là encore, ne tombons pas dans l’angélisme, un épi-journal n’est pas un gage de qualité en lui même, mais au moins laissons lui la chance de prouver sa valeur de la même façon qu’une revue papier et évaluons le avec les mêmes critères.

Il s’agit vraiment de bâtir une nouveau paradigme de publication et nous, scientifiques, en sommes tous les premiers responsables avant d’en devenir les bénéficiaires dans un futur proche.

Pascal Guitton, Professeur Université de Bordeaux et Inria

(*) Le spam, courriel indésirable ou pourriel (terme recommandé au Québec) est une communication électronique non sollicitée, en premier lieu via le courrier électronique. Il s’agit en général d’envois en grande quantité effectués à des fins publicitaires. [Wikipedia]. À l’origine le mot SPAM désignait de la « fake meat« .
17 avril 2015
Une complète incomplétude

Kurt Gödel. Il démontre que n’importe quel système logique suffisamment puissant (par exemple pour décrire l’arithmétique) a forcément des propositions qui ne peuvent être ni infirmées, ni confirmées: elles sont indécidables. Ce résultat fut une surprise pour les mathématiciens de l’époque et reste un choc pour qui croit à l’absence de limite en science.

J’ai expliqué l’informatique à ma famille, mon médecin, à mes voisins de train ou d’avion, à des collégiens, des lycéens… J’ai raconté des algorithmes, des histoires, des mots. Pourtant, il y a des concepts que je n’ai jamais osé tenter d’expliquer à des non-informaticiens. Parce que je pensais avoir besoin de trop de pré-requis, parce que c’est trop technique, parce que je ne pensais pas que c’était raisonnablement faisable en un billet de blog.

Eh bien parfois j’ai tort et ça me fait plaisir. Chapeau donc à mon estimé collègue David Monniaux qui tient le blog La vie est mal configurée. Il a écrit un billet

Le théorème de Gödel pour les nuls

où il explique rien moins que les théorèmes d’incomplétude de Gödel, et ce qu’ils ne veulent pas dire (Bogdanov inside). Un peu long, mais logiquement instructif.

Sylvie Boldo

7 avril 2015

Poésie et esthétisme du logiciel

Un nouvel « entretien autour de l’informatique ». Serge Abiteboul et Claire Mathieu interviewent Gérard Huet , Directeur de recherche émérite à Inria. Gérard Huet a apporté des contributions fondamentales à de nombreux sujets de l’informatique, démonstration automatique, unification, édition structurée, réécriture algébrique, calcul fonctionnel, langages de programmation applicatifs, théorie des types, assistants de preuve, programmation relationnelle, linguistique computationnelle, traitement informatique du sanskrit, lexicologie, humanités numériques, etc. Ses travaux sur CAML et Coq (voir encadrés en fin d’article) ont notamment transformé de manière essentielle l’informatique.

B : Tu as eu un parcours de chercheur singulier, avec des contributions fondamentales dans un nombre incroyable de sujets de l’informatique. Est-ce qu’il y a des liens entre tous tes travaux ?
G : Il existe des liens profonds entre la plupart de ces sujets, notamment une vision du cœur de la discipline fondée sur l’algèbre, la logique et les mathématiques constructives. Le calcul fonctionnel (le lambda-calcul dans le jargon des théoriciens) sous-tend nombre d’entre eux. Le calcul fonctionnel, pour simplifier, c’est une théorie mathématique avec des fonctions qui ne s’appliquent pas juste à des réels comme celles que vous avez rencontrées en cours de maths. Ces fonctions, ou plus précisément ces algorithmes, peuvent s’appliquer à d’autres objets et notamment à des objets fonctionnels. Vous pouvez avoir une fonction qui trie des objets. Vous allez passer comme argument à cette fonction une autre fonction qui permet de comparer l’âge de deux personnes et vous obtenez une fonction qui permet de trier un ensemble de personnes par ordre d’âge.

Ce qui montre que ce calcul fonctionnel est une notion fondamentale, c’est à la fois l’ossature des programmes informatiques, et dans sa version typée la structure des démonstrations mathématiques (la déduction naturelle dans le jargon des logiciens). Vous n’avez pas besoin de comprendre tous les détails. La magie, c’est que le même objet mathématique explique à la fois les programmes informatiques et les preuves mathématiques. Il permet également les représentations linguistiques à la fois de la syntaxe, du discours, et du sens des phrases de la langue naturelle (les grammaires de Lambek et les grammaires de Montague dans le jargon des linguistes). Reconnaître cette unité est un puissant levier pour appliquer des méthodes générales à plusieurs champs applicatifs.

Je suis tombé sur d’autres sujets au fil de hasards et de rencontres parfois miraculeuses.

Les programmes sont des preuves constructives

B : Les programmes sont des preuves. Ça te paraît évident mais ça ne l’est pas pour tout le monde. Pourrais-tu nous expliquer comment on est arrivé à ces liens entre programmes et preuves ?
G : Tout commence avec la logique mathématique. En logique, il y a deux grandes familles de systèmes de preuves. La première, la déduction naturelle, avec des arbres de preuves, c’est comme le lambda-calcul typé, et les propositions de la logique sont les types des formules de lambda-calcul. Ce n’est pas quelque chose qui a été compris au début. Le livre standard sur la déduction naturelle, paru en 1965, ne mentionne même pas le λ calcul, car l’auteur n’avait pas vu le rapport. C’est dans les années 70, qu’on a découvert qu’on avait développé deux théories mathématiques équivalentes, chacun des deux domaines ayant développé des théorèmes qui en fait étaient les mêmes. Quand on fait le pont entre les deux, on comprend que, les programmes, ce sont des preuves.

En mathématiques, on raisonne avec des axiomes et des inférences pour justifier la démonstration des théorèmes, mais souvent on évacue un peu la preuve elle-même en tant qu’objet mathématique en soi. La preuve, pour un mathématicien, c’est comme un kleenex : on la fait, et puis ça se jette. La preuve passe, le théorème reste. D’ailleurs, on donne aux théorèmes des noms de mathématiciens, mais, les preuves, on s’en moque. Ça, c’est en train de changer grâce à l’informatique. Pour nous, les preuves sont des objets primordiaux. Plus précisément, ce qui est important pour nous, ce sont les algorithmes. En effet, un théorème peut avoir plusieurs preuves non équivalentes. L’une d’entre elles peut ne pas être constructive, c’est à dire par exemple montrer qu’un objet existe sans dire comment le construire. Ça intéresse moins l’informaticien. Les autres preuves donnent des constructions. Ce sont des algorithmes. Un théorème dit par exemple que si on a un ensemble d’objets que l’on peut trier, alors on peut construire une séquence triée de ces objets. C’est un théorème – il est complètement trivial pour un mathématicien. Mais pour nous pas du tout. Si vous voulez trier un million d’enregistrements, vous aimeriez que votre algorithme soit rapide. Alors les informaticiens ont développé de nombreux algorithmes pour trier des objets qu’ils utilisent suivant les contextes, des preuves différentes de ce théorème trivial qui sont plus utiles qu’une preuve non constructive. Et ce sont de beaux objets !

Voilà, quand on a compris qu’un algorithme c’est une preuve, on voit bien que plusieurs algorithmes peuvent avoir la même spécification et donc que la preuve importe.

B : La mode aujourd’hui est d’utiliser le mot « code » pour parler de programmes informatiques. Tu ne parles pas de code ?
G : Au secours ! Le mot « code » est une insulte à la beauté intrinsèque de ces objets. La représentation d’un entier sous forme de produit de nombres premiers, on ne doit pas appeler cela un « codage » ! Non, cette représentation des entiers est canonique, et découle du Théorème Fondamental de l’Arithmétique. C’est extrêmement noble. Dans le terme « codage », il y a l’idée de cacher quelque chose, alors qu’au contraire, il s’agit de révéler la beauté de l’objet en exhibant l’algorithme.

L’esthétique des programmes

B : Les gens voient souvent les programmes informatiques comme des suites de symboles barbares, des trucs incompréhensibles. C’est beaucoup pour cela que le blog binaire milite pour l’enseignement de l’informatique, pour que ces objets puissent être compris par tous. Mais tu as dépassé l’état de le compréhension. Tu nous parles d’esthétique : un programme informatique peut-il être beau ?
GH : Bien sûr. Son rôle est d’abord d’exposer la beauté de l’algorithme sous-jacent. L’esthétique, c’est plus important qu’il n’y paraît. Elle a des motivations pratiques, concrètes. D’abord, les programmes les plus beaux sont souvent les plus efficaces. Ils vont à l’essentiel sans perdre du temps dans des détails, des circonvolutions inutiles. Et puis un système informatique est un objet parfois très gros qui finit par avoir sa propre vie. Les programmeurs vont et viennent. Le système continue d’être utilisé. La beauté, la lisibilité des programmes est essentielle pour transmettre les connaissances qui s’accumulent dans ces programmes d’une génération de programmeurs à l’autre qui ont comme mission de pérenniser le fonctionnement du système.

Pour les programmes, de même que pour les preuves, il ne faut jamais se satisfaire du premier jet. On est content quand ça marche, bien sûr, mais c’est à ce moment là que le travail intéressant commence, qu’on regarde comment nettoyer, réorganiser le programme, et c’est souvent dans ce travail qu’on découvre les bonnes notions. On peut avoir à le réécrire tout ou en partie, l’améliorer, le rendre plus beau.

Prenez le cas d’Unix ^(*). Unix, c’est beau, c’est très beau ! Il faut savoir voir Unix comme une très grande œuvre d’art. Unix a été réalisé dans le laboratoire de recherche de Bell, par une équipe de chercheurs. Vaughan Pratt ⁽⁺⁾ disait dans les années 80 :« Unix, c’est le troisième Testament ». Vaughan Pratt, c’est quelqu’un d’incroyable ! Il ne dit pas n’importe quoi (rire de Gérard). Eh bien, Unix a été fait dans une équipe de spécialistes de théorie des langages et des automates. C’est une merveille de systèmes communiquant par des flots d’octets, tout simplement. C’est minimaliste. Ils ont pris le temps qu’il fallait, ils ont recherché l’élégance, la simplicité, l’efficacité. Ils les ont trouvées !

B : Parmi tes nombreux travaux, y en a-t-il un qui te tient particulièrement à cœur ?
GH : Je dirais volontiers que mon œuvre préférée, c’est le « zipper ». C’est une technique de programmation fonctionnelle. Elle permet de traverser des structures de données les plus utilisées en informatique comme des listes et des arbres pour mettre à jour leur contenu.

Le zipper (voir aussi la page), je suis tombé dessus pour expliquer comment faire des calculs applicatifs sur des structures de données, sans avoir cette espèce de vision étroite de programmation applicative où, pour faire des remplacements dans une structure de données, tu gardes toujours le doigt sur le haut de ta structure, ton arbre, et puis tu te balades dedans, mais tu continues à regarder ta structure d’en haut. Le zipper, au lieu de cela, tu rentres dans la structure, tu vis à l’intérieur, et alors, ce qui compte, c’est d’une part l’endroit où tu es, et d’autre part le contexte qui permet de te souvenir de comment tu es arrivé là. C’est une structure fondamentale qui avait totalement échappé aux informaticiens. Des programmeurs faisaient peut-être bien déjà du zipper sans le savoir comme M. Jourdain faisait de la prose. J’ai su formaliser le concept en tant que structure de donnée et algorithmes pour la manipuler. Maintenant, on peut enseigner le zipper, expliquer son essence mathématique.

La mystique de la recherche

B : Qu’est-ce qui est important pour réussir une carrière en recherche ?
GH : Le plus important finalement, dans le choix du sujet de recherche, ce sont trois choses : le hasard, la chance, et les miracles. Je m’explique. Premièrement, le hasard. Il ne se contrôle pas. Deuxièmement, la chance. C’est d’être au bon moment au bon endroit, mais surtout de savoir s’en apercevoir et la saisir.

Par exemple, dans le Bâtiment 8 ⁽⁺⁺⁾ où je travaillais à l’INRIA Rocquencourt, il passait beaucoup de visiteurs. Le hasard c’est un jour la visite de Corrado Böhm , un des maîtres du lambda-calcul, une vraie encyclopédie du domaine. Je lui explique ce que je fais, et il me conseille de lire un article qui était alors, en 1975, inconnu de presque tous les informaticiens : c’était l’algorithme de Knuth-Bendix. C’est un résultat majeur d’algèbre constructive permettant de reformuler des résultats d’algèbre de manière combinatoire. La chance, j’ai su la saisir. J’ai vu tout de suite que c’était important. Cela m’a permis d’être un précurseur des systèmes de réécriture un peu par ce hasard. Voilà, j’ai su saisir ma chance. On se rend compte qu’il y a quelque chose à comprendre, et on creuse. Donc il faut être en éveil, avoir l’esprit assez ouvert pour regarder le truc et y consacrer des efforts.
À une certaine époque, j’étais un fréquent visiteur des laboratoires japonais. Une fois, je suis resté une quinzaine de jours dans un laboratoire de recherche. Je conseillais aux étudiants japonais d’être en éveil, d’avoir l’esprit ouvert. Je leurs répétais : « Be open-minded! ». Ils étaient étonnés, et mal à l’aise de questionner les problèmes qui leur avaient été assignés par leur supérieur hiérarchique. Un an plus tard, je suis repassé dans le même labo. Ils avaient gardé ma chaise à une place d’honneur, et ils l’appelaient (rire de Gérard) « the open-mindedness chair » !

B : Esthétique, miracle, troisième testament… Il y aurait une dimension mystique à ton approche de la recherche ?
GH : En fait, souvent, derrière les mystères, il y a des explications. Un exemple : je suis parti aux USA sur le mirage de l’intelligence artificielle. Une fois là-bas, quelle déception. J’ai trouvé qu’en intelligence artificielle, la seule chose qui à l’époque avait un peu de substance, c’était la démonstration automatique. J’ai essayé. Et puis, j’ai fait une croix dessus car cela n’aboutissait pas. Cela semblait inutile, et je voulais faire des choses utiles. Alors j’ai regardé ailleurs, des trucs plus appliqués comme les blocages quand on avait des accès concurrents à des ressources. Par hasard, je suis tombé sur deux travaux. Le premier, un article de Karp et Miller, m’a appris ce que c’était que le Problème de Correspondance de Post (PCP), un problème qui est indécidable – il n’existe aucun algorithme pour le résoudre. Le second était une thèse récemment soutenue à Princeton qui proposait un algorithme pour l’unification d’ordre supérieur. Je ne vais pas vous expliquer ces deux problèmes, peut-être dans un autre article de Binaire. L’algorithme de la thèse, je ne le comprenais pas bien. Surtout, ça ne m’intéressait pas trop, car c’était de la démonstration automatique et je pensais en avoir fini avec ce domaine. Eh bien, un ou deux mois plus tard, je rentre chez moi après une soirée, je mets la clé dans la serrure de la porte d’entrée, et, paf ! J’avais la preuve de l’indécidabilité de l’unification d’ordre supérieur en utilisant le PCP. J’avais établi un pont entre les deux problèmes. Bon ça montrait aussi que le résultat de la thèse était faux. Mais ça arrive, les théorèmes faux. Pour moi, quel flash ! J’avais résolu un problème ouvert important. Quand je parle de miracle, c’est quelque chose que je ne sais pas expliquer. J’étais à mille lieues de me préoccuper de science, et je ne travaillais plus là dessus. C’est mon inconscient qui avait ruminé sur ce problème du PCP, et c’est un cheminement entièrement inconscient qui a fait que la preuve s’est mise en place. Mais il faut avoir beaucoup travaillé pour arriver à ça, avoir passé du temps à lire, à comprendre, à essayer des pistes infructueuses, à s’imprégner de concepts que l’on pense important, à comprendre des preuves. C’est beaucoup de travail. La recherche, c’est une sorte de sacerdoce.

Bon, il faut aussi savoir s’arrêter, ne pas travailler trop longtemps sur un même problème. Faire autre chose. Sinon, eh bien on devient fou.

Caml (prononcé camel, signifie Categorical Abstract Machine Language) est un langage de programmation généraliste conçu pour la sécurité et la fiabilité des programmes. Descendant de ML, c’est un langage de programmation directement inspiré du calcul fonctionnel, issu des travaux de Peter Landin et Robin Milner. À l’origine simple langage de commandes d’un assistant à la preuve (LCF), il fut développé à l’INRIA dans l’équipe Formel sous ses avatars de Caml puis d’OCaml. Les auteurs principaux sont Gérard Huet, Guy Cousineau, Ascánder Suárez, Pierre Weis, Michel Mauny pour Caml ; Xavier Leroy, Damien Doligez et Didier Rémy et Jérôme Vouillon pour OCaml.

Coq est un assistant de preuve fondé au départ sur le Calcul des Constructions (une variété de calcul fonctionnel typé) introduit par Thierry Coquand et Gérard Huet. Il permet l’expression d’assertions mathématiques, vérifie automatiquement les preuves de ces affirmations, et aide à trouver des preuves formelles. Thierry Coquand, Gérard Huet, Christine Paulin-Mohring, Bruno Barras, Jean-Christophe Filliâtre, Hugo Herbelin, Chet Murthy, Yves Bertot, Pierre Castéran ont obtenu le prestigieux 2013 ACM Software System Award pour la réalisation de Coq.

(*) Unix : Unix est un système d’exploitation multitâche et multi-utilisateur créé en 1969. On peut le voir comme l’ancêtre de systèmes aussi populaires aujourd’hui que Linux, Android, OS X et iOS.

(+) Vaughan Pratt est avec Gérard Huet un des grands pionniers de l’informatique. Il a notamment dirigé le projet Sun Workstation, à l’origine de la création de Sun Microsystems.

(++) Bâtiment 8 ; Bâtiment quasi mythique d’Inria (de l’IRIA ou de l’INRIA) Rocquencourt pour les informaticiens français, qui a vu passer des chercheurs disparus comme Philippe Flajolet et Gilles Kahn, et de nombreuses autres stars de l’informatique française toujours actifs, souvent à l’instigation de Maurice Nivat. Gilles Kahn sur la photo était une sorte de chef d’orchestre, parmi un groupe de chercheurs plutôt anarchistes dans leur approche de la recherche.

Gérard Huet avec Gilles Kahn (à droite) © David MacQueen au Bât 8 de Rocquencourt, 1978

27 mars 2015

Dieu a-t-il programmé le monde en Java ?

Serge Abiteboul a rencontré pour Binaire Baptiste Mélès, un jeune philosophe des sciences qui sait aussi écrire du code informatique. Baptiste Mélès a étudié une analogie entre les langages de programmation orientés objet et la monadologie leibnizienne (n’ayez crainte !). Serge vous propose un article très simplifié de cette analogie qui, nous l »espérons, vous donnera envie d’aller lire l’article complet de Baptiste Mélès. La présentation détaillée de cette fameuse monadologie leibnizienne et les liens que Baptiste Mélès tisse avec la programmation orientée objet (avec des exemples de code) vous plongeront dans un univers passionnant où philosophie et informatique dialoguent. Marie-Agnès Enard.

Philosophie des systèmes (puce bleue). Logique, mathématiques, informatique (puce verte). Pensée et mathématiques chinoises (puce rouge). Trois thèmes de recherche qui nourrissent la pensée de Baptiste Mélès.

En informatique, nous utilisons des « langages de programmation » pour dire aux machines ce que nous voulons qu’elles fassent. Ces langages sont très loin des « langages machines », c’est-à-dire des langages que comprennent les machines. Il est nécessaire d’avoir une phase de « compilation » où un programme dans un langage, par exemple Java, que parle le développeur (un être humain) est traduit dans un langage que comprend la machine. Comme une langue naturelle, un langage de programmation s’appuie sur un alphabet, un vocabulaire, des règles de grammaire ; comme dans une langue naturelle, les phrases des langages de programmation (on parle d’instructions) ont une significations. Les différences entre les langages de programmation sont du même ordre que celles entre les langues que parlent les humains – les informaticiens ont juste réinventé Babel. Baptiste Mélès s’intéresse à la philosophie des connaissances mais il a aussi étudié les langages de programmation. Il m’a donc expliqué le lien entre la monadologie leibnizienne et les langages de programmation orientés objet d’où le titre de son article : Dieu a-t-il programmé le monde en Java ?

Baptiste Mélès est parti de taxonomies des langages de programmation et de taxonomies d’écoles de philosophies et il a montré des liens entre ces taxonomies. En résumé, il existe plusieurs grandes familles de langages de programmation : par exemple, les langages impératifs, fonctionnels, logiques, orientés objet. Chacune d’entre elle est « proche » d’une école de philosophie. Pour illustrer cette thèse, Baptiste Mélès s’attache à la famille la plus populaire de nos jours, celle des langages de programmation orientés objet qui inclut des langages comme Java, OCAML, Python, C++, et Ruby. Il nous explique les liens avec la philosophie «monadologique» de Gottfried Wilhelm Leibniz (1646–1716).

La monadologie leibnizienne

Gottfried Wilhelm Leibniz ©wikicommon

Gottfried Wilhelm Leibniz, philosophe et scientifique allemand, voit la nature comme composée de substances simples, les monades, et de substances composées que nous ignorerons ici. Une monade est caractérisée par ses propriétés et par ses «actions internes». Ce qui distingue une monade d’un atome, c’est qu’elle est capable de transformer son état, de réagir à son environnement, c’est-à-dire aux actions d’autres monades. Un monde est défini par les «essences» des monades qui le peuplent. (La vision du monde de Leibniz que je présente ici est évidemment hyper simplifiée par rapport à celle du philosophe.) C’est Dieu qui décide du comportement des différentes essences de monades et de leurs interactions.

Baptiste Mélès écrit : « Pour résumer, la théorie leibnizienne des monades est une doctrine métaphysique dans laquelle les concepts, créés par Dieu, sont organisés de façon hiérarchique et préexistent aux individus ; les individus sont des êtres atomiques et animés, qui, quoique enfermés sur eux-mêmes, n’en sont pas moins capables de se représenter le monde et d’agir sur lui en échangeant des messages grâce à l’action intermédiaire d’une harmonie préétablie par le créateur. »

La programmation orientée-objet

En programmation orientée objet, le programmeur définit des types d’objets (des classes dans la terminologie orientée objet) et les comportements des objets dans ces classes. Concrètement, un objet est une structure de données dans un certain état (typiquement caché pour l’extérieur) qui répond à un ensemble de messages. L’ensemble des messages (des programmes) acceptés par l’objet détermine son comportement. Les objets interagissent entre eux par l’intermédiaire de ces messages. Il n’est pas nécessaire de connaître le programme correspondant à un objet pour pouvoir interagir avec cet objet. Il suffit de connaître son «interface», c’est-à-dire l’ensemble des messages qu’il comprend. (C’est sans doute ce principe d’indépendance qui est à la base du succès de la programmation orientée objet.)

L’analogie entre la monadologie leibnizienne et la programmation objet est claire. Les objets sont des monades. Les classes sont les «essences» de Leibniz. Si le Dieu de la Bible a créé l’homme à son image, les informaticiens ont façonné les développeurs orientés objet à l’image du Dieu de Leibniz. C’est tout sauf innocent.

Du dialogue entre la philosophie et de l’informatique

Les langages orientés objet permettent de mieux comprendre des concepts philosophiques qui peuvent paraître très abstraits. Par elle également, la philosophie permet d’expliquer les raisonnements complexes qui sous-tendent la programmation. Le dialogue entre philosophie et informatique enrichit bien les deux disciplines. On retrouve d’ailleurs dans ce dialogue un de mes thèmes favoris : l’informatique est un lieu naturel de rapprochement entre les sciences dites dures et les sciences humaines. (Voir texte sur les Humanités Numériques). Avec l’informatique, nous avons l’occasion de combler un fossé entre des sciences qui s’est construit depuis le 19ème siècle, et qui n’a pas lieu d’être.

Serge Abiteboul, Inria et ENS Cachan

23 mars 2015
L’ordinateur imite l’homme imitant la femme…

L’intelligence artificielle est un vrai sujet, mais c’est aussi une source de fantasmes dont la forme contemporaine est issue de textes d’Alan Turing. Isabelle Collet, Maître d’enseignement et de recherche à la Faculté des sciences de l’éducation de l’université de Genève, nous offre ici un éclairage inattendu et nous aide à dépasser les idées reçues. Elle attire notre attention sur le fait que c’est avant tout une histoire de « mecs ». À déguster donc… Thierry Viéville.

Quand je faisais mes études d’informatique, j’avais entendu parler du « test de Turing ». Pour moi, il s’agissait simplement de faire passer un test à un ordinateur pour savoir s’il était intelligent (ou s’il était programmé d’une façon suffisamment maline pour donner cette impression).

Face à un ordinateur, l’humain est-il une femme ou un homme ?

En faisant des recherches dans le cadre de ma thèse, j’ai lu un peu plus sur le « test de Turing »… et j’ai découvert avec fascination que quand les informaticiens prétendaient le mettre en place, ils en oubliaient la moitié : le jeu ne se met pas en place avec un humain et un ordinateur, mais avec un homme et une femme. Un observateur devra déterminer lequel de ses interlocuteurs est un homme et lequel est une femme. Il devra les interroger sans avoir aucun autre indice que le contenu des réponses que l’homme et la femme formulent. Puis, au bout d’un « certain temps », on remplace l’homme par l’ordinateur. Si l’observateur pense qu’il joue encore à détecter la différence des sexes et ne remarque rien, c’est que l’ordinateur a l’air au moins aussi intelligent que l’homme. À l’époque, je ne voyais pas bien l’intérêt de ce passage par la différence des sexes… Jusqu’à ce que je lise un texte de Jean Lassègue, auteur d’un autre texte sur Turing sur ce blog, et que je l’associe aux recherches de l’anthropologue Françoise Héritier. Je vais parler ici de cette connexion, avec tous mes remerciements à Jean Lassègue pour son excellente analyse du jeu de l’imitation .

On pourrait considérer que la première partie du jeu (entre un homme et une femme) n’est qu’un prétexte pour permettre ensuite la substitution en aveugle avec l’ordinateur et que Turing aurait pu choisir un autre critère que la différence des sexes pour amorcer le jeu. Pour Jean Lassègue¹, le critère de la différence des sexes est tout à fait capital : « il s’agit de passer d’un écart physique maximal entre êtres humains à un écart maximal entre espèces différentes (si on considère l’ordinateur comme une nouvelle espèce) ». Sur cette base, l’observateur est supposé en déduire que : « puisque la différence physique la plus profonde entre les êtres humains (être homme et être femme) n’est pas apparente dans le jeu n°1, la différence physique encore plus profonde entre les êtres humains d’une part et l’ordinateur d’autre part ne sera pas apparente dans le jeu n°2 non plus. ». Évidemment, si le jeu n°1 échoue, il n’est plus question de passer au jeu n°2 qui perd sa capacité démonstrative.

Lors de la première phase de l’expérience, Turing signale que : « La meilleure stratégie pour [la femme] est sans doute de donner des réponses vraies. Elle peut ajouter à ses réponses des choses comme : ‘‘C’est moi la femme, ne l’écoutez pas’’ mais cela ne mène à rien puisque l’homme peut faire des remarques semblables ».

Photo @Maev59

Pourquoi Turing assigne-t-il ainsi les stratégies de jeu entre l’homme et la femme ? Toujours selon Lassègue, la stratégie de la femme est en fait une absence de stratégie. Dans le jeu de l’imitation, la femme est la seule qui s’imite elle-même, alors que l’homme imite la femme et que l’ordinateur imite l’homme imitant la femme.

Dans une interview, un de ses anciens collègues, Donald Michie, rapporte ces propos de Turing : « Le problème avec les femmes, c’est qu’il faut leur parler. Quand tu sors avec une fille, tu dois discuter avec elle et trop souvent, quand une femme parle, j’ai l’impression qu’une grenouille jaillit de sa bouche. »¹

L’intelligence artificielle est-elle finalement « gendrée » ?

Revenons au jeu de l’imitation : les femmes, qui sont supposée être de manière générale à ce point dépourvues d’à-propos dans une conversation, doivent se contenter d’être elles-mêmes dans ce jeu, c’est-à-dire, indiscutablement une femme, un être incapable de faire abstraction de son sexe. L’homme, par contre, va tenter de tromper l’interrogateur, et pour cela, il devrait être capable de se détacher de son sexe, c’est à dire de son corps sexué, pour réussir à imiter la femme. Et en fin de compte, ce que l’ordinateur va devoir réussir, c’est d’imiter l’homme qui imite la femme, ou, plus simplement, d’imiter la femme.

Finalement, l’homme et l’ordinateur ont des stratégies tout à fait similaires. L’intelligence ainsi imitée par la machine est celle de l’homme et le jeu de l’imitation a pour conséquences, d’une part, d’écarter les femmes dès qu’on parle d’intelligence, et, d’autre part, de placer l’intelligence de l’homme (et non pas de l’humain) à un niveau universel.

Il est en effet remarquable au début du jeu n°1 que Turing semble signifier que la différence des sexes se traduit clairement par les attributs physiques. Plus particulièrement, il pense qu’il y a une essence féminine (différente de l’essence masculine) et qu’une de ses manifestations fiables est l’apparence de la femme. Dans le premier et seul exemple de l’article proposé pour le jeu n°1, l’observateur pose une question relative à la longueur des cheveux de son interlocuteur-trice. Turing reprend ici, volontairement ou non, le présupposé sexiste largement répandu qui prétend, d’une part, que les femmes sont davantage asservies à leur corps que les hommes et, d’autre part, que leur apparence se superpose à leur personnalité. Rousseau disait déjà que la femme est femme à chaque instant, alors que l’homme n’est homme (c’est-à-dire un être mâle) qu’à des instants précis… le reste du temps, il est universel (c’est à dire un universel masculin, puisque de toute manière, la femme n’y est pas conviée).

Notons que pour que le jeu puisse fonctionner, il faut bien que la femme soit elle-même, et ne puisse être qu’elle-même. La différence est alors produite par la capacité de l’homme à se détacher de son corps, car son esprit lui permet d’imiter un être pris dans un autre corps, et ainsi de jouer, sur ce plan, jeu égal avec la machine. On en vient à penser que l’intelligence universelle est plutôt du côté de la machine.

Dans son jeu, Turing se débarrasse de la différence des sexes simplement en se débarrassant des femmes. Si l’intelligence que recherche Turing est universelle, ce n’est pas parce qu’elle a fusionné les sexes, mais parce qu’il n’en reste plus qu’un, auquel peut se comparer l’intelligence artificielle.

On retrouve ce même fantasme quand il décrit les machines autorisées à participer au jeu : « Nous souhaitons enfin exclure de la catégorie des machines les hommes nés de la manière habituelle. […] On pourrait par exemple requérir que les ingénieurs soient tous du même sexe, mais cela ne serait pas vraiment satisfaisant »². Cette phrase, qui peut être considérée comme un trait d’humour, possède en fait deux éléments essentiels pour comprendre la vision que Turing a de la machine. Tout d’abord, la machine est considérée comme étant littéralement l’enfant des ingénieurs, puisque s’il était produit par une équipe d’hommes et de femmes ingénieurs, cela jetterait le doute sur un possible engendrement biologique. D’autre part, pour que la machine puisse être éligible au jeu de l’imitation, une condition nécessaire est qu’elle ne soit pas issue de la différence des sexes.
De plus, l’équipe d’ingénieurs de même sexe qui engendrerait une machine, serait selon toutes probabilités dans l’esprit de Turing, une équipe d’hommes. Sa vision de la création d’une machine de type ordinateur est non seulement un auto-engendrement, mais surtout un auto-engendrement masculin se débarrassant des femmes au moment de la conception sous prétexte, en quelque sorte, de ne pas tricher.

Un paradis sans altérité !

Photo @Maev59

La cybernétique nous explique que, puisque le niveau supérieur de compréhension de l’univers implique l’étude des relations entre ses objets et non la connaissance de la structure des objets, les matières et les corps ne sont pas vraiment ce qui importe. Piégées dans leur corps, les femmes n’ont pas accès à ce niveau supérieur de compréhension de l’univers que propose le paradigme informationnel. Elles en seront même éventuellement écartées pour permettre à l’intelligence d’atteindre un idéal androgyne débarrassé du féminin. A cet instant, la perspective d’un monde idéal dans lequel l’homme pourrait se reproduire à l’identique devient possible.

Les fantasmes d’auto-engendrement apportent une solution à ce que Françoise Héritier³ appelle le privilège exorbitant des femmes à pouvoir se reproduire à l’identique mais aussi au différent. Les femmes sont les seules capables de mettre au monde non seulement leurs filles mais aussi les fils des hommes. Selon Françoise Héritier, on retrouve dans de nombreux mythes des groupes non mixtes vivant séparément et pacifiquement, chacun étant capable de se reproduire à l’identique. L’harmonie primitive résidait dans l’absence d’altérité, jusqu’à ce qu’elle soit gâchée par un événement violent (en général : une copulation que (les) dieu(x) ne désirai(en)t pas).

Philippe Breton estimait dans son livre de 1990 « La tribu informatique » que : « La reproduction au sein de la tribu se fait fantasmatiquement grâce […] à l’union de l’homme et de la machine ». Sur ce point, je ne suis pas d’accord. À mon sens, il n’y a pas d’union avec la machine, mais un auto-engendrement dont la machine est soit le produit (du temps où on fantasmait sur les robots) soit le support (depuis qu’on imagine des IA uniquement logicielle). Or, un auto-engendrement et une reproduction via une « matrice biologique » sont des procédés qui se présentent comme mutuellement exclusifs. C’est pourquoi je suis d’accord quand il ajoute : « Dans ce sens, l’existence même de la tribu informatique est en partie conditionnée par l’exclusion des femmes qui constituent une concurrence non désirée.»

Le monde scientifique des années 1950 peut être un exemple du paradis sans altérité de Françoise Héritier. Le monde de l’informatique d’aujourd’hui n’en est pas très loin. L’auto-engendrement cybernétique au cours duquel l’homme seul duplique son intelligence dans une machine permettrait de faire fonctionner pleinement ce « paradis », il possède le double avantage de supprimer la différence des sexes en écartant les femmes du processus de reproduction et de permettre aux êtres mâles de se reproduire à l’identique.

Isabelle Collet.

1Lee, J. A. N. and Holtzman, G. « 50 Years After Breaking the Codes: Interviews with Two of the Bletchley Park Scientists. » The Annals of the History of Computing vol. 17 n°1 (1995) p. 32-43

2Alan Turing, Jean-Yves Girard, La machine de Turing, 1995

3Françoise Héritier, Masculin / Féminin, Dissoudre la hiérarchie. (2002).

1Jean Lassègue, Turing. 1998.

11 mars 2015
Où sont les femmes ?
C’est une question historique. Binaire l’a posée à une amie historienne, Valérie Schafer de l’Institut des sciences de la communication. Valérie reprend ici un sujet qu’elle a développé au congrès annuel de la Société Informatique de France qui s’est tenu récemment à Orléans. Regard sur l’histoire des femmes et de l’informatique. Serge Abiteboul.

Valérie Schafer

La célébration cette année des deux cents ans de la naissance d’Ada Lovelace, la sortie de The imitation Game dans lequel Keira Knightley incarne la mathématicienne-informaticienne Joan Clarke ou encore la diffusion en France de la série britannique Enquêtes codées, qui permet de découvrir l’univers féminin de Bletchley Park, témoignent de ce que la relation des femmes à l’informatique est ancienne. Le temps serait-il à l’œuvre pour reconnaitre la place qu’elles ont pu occuper aux débuts de l’informatique? Le livre de l’historienne Janet Abbate, Recoding Gender, Women’s changing participation in Computing, s’ouvre ainsi sur un souvenir d’Elsie Shutt, fondatrice en 1958 d’une entreprise informatique qui employait à ses débuts uniquement des programmeuses en freelance travaillant à domicile : elle avoue sa surprise quand elle a rencontré des programmeurs, métier qu’elle considérait comme féminin. Et la journaliste Lois Mandel ne soulignait-elle pas en 1967 dans Cosmopolitan que l’informatique offrait des opportunités absolument remarquables aux femmes, avant de reprendre les propos de la pionnière de l’informatique Grace Hooper, qui comparait la programmation à l’organisation d’un dîner, concluant que les femmes sont naturellement enclines à cette activité ! Si cette idée peut aujourd’hui faire sourire, du moins témoigne-t-elle de ce que les représentations de l’informatique ont profondément évolué.

Les pages d’ouvertures d’un article de Cosmopolitan Magazine en 1967.
Indiana University’s School of Informatics and Computing.

L’historien Nathan Ensmenger [1] a souligné que si l’essentiel des recherches s’est intéressé à « l’histoire cachée » des femmes dans l’informatique, celle-ci ne nous apprend pas seulement sur les femmes, mais aussi sur l’informatique elle-même. On peut notamment retenir :
- La présence nombreuse des femmes aux débuts de l’informatique, à Bletchley Park ou à la Moore School autour de l’Eniac, mais aussi dans le secteur civil que ce soit dans le domaine des cartes perforées, dans les départements scientifiques pour le traitement de données, ou dans la programmation.
- La construction progressive d’une image masculine de l’informatique notamment de la part d’associations professionnelles, comme la Data Processing Management Association dont l’historien Tom Haigh montrait qu’elle avait œuvrée dès les années 1960 à dissocier son image de celle d’un monde professionnel féminin pour mieux valoriser et faire reconnaître son activité. Nathan Ensmenger souligne également le rôle des tests d’aptitude et de personnalités à la fin des années 1950 et dans les années 1960 pour recruter les programmeurs.
- Un autre élément qu’éclaire cette histoire est celui du statut de l’informatique, et en particulier celui de la programmation, à la fois largement féminisée et souffrant à ses débuts d’une moindre reconnaissance que le domaine du matériel. Si la faible féminisation actuelle de l’informatique fait oublier que jusque dans les années 1980 la situation était toute différente, cet oubli tient aussi à ce que certains des emplois confiés aux femmes dans l’informatique étaient alors considérés comme de statut inférieur.
Photo of the U.S. Army. Left: Patsy Simmers, holding ENIAC board Next: Mrs. Gail Taylor, holding EDVAC board
Next: Mrs. Milly Beck, holding ORDVAC board Right: Mrs. Norma Stec, holding BRLESC-I board

Non seulement l’analyse de la place des femmes dans l’informatique ne relève pas d’une histoire compensatoire, qui viserait à chercher quelques rares traces de leur présence, elle est une réalité historique, mais encore son étude et celle des rapports de genre éclairent l’histoire de l’informatique elle-même, son passé et son présent, donnant tout son intérêt à une thématique qui était au cœur du congrès annuel de la SIF qui s’est tenu à Orléans du 3 au 5 février 2015. Au-delà c’est aussi ses futurs que peut accompagner ce regard historique, à l’heure où le milieu informatique s’inquiète de la baisse inédite de la proportion de femmes dans ses rangs depuis vingt ans. L’histoire, en éclairant comment la discipline et les professions informatiques se sont construites [2], permet aussi de ne pas considérer comme acquise ou figée la situation actuelle.

Valérie Schafer, Institut des sciences de la communication – CNRS, Paris Sorbonne, UPMC

Pour aller plus loin
1. Dans le livre collectif, Gender Codes: Why Women Are Leaving Computing?
2. Colloque Femmes, genre et TIC du LabEx EHNE
10 mars 2015
Et un, et deux, et trois femmes Prix Turing !

Après Ada Lovelace et Grace Hopper, et à l’occasion de la Journée internationale de la femme, Anne-Marie Kermarrec nous parle de plusieurs grandes informaticiennes et scientifiques, toutes Prix Turing. Elle achève ainsi sa démonstration – s’il était possible de douter – l’informatique est aussi pour les filles ! Serge Abiteboul.

En 1966, l’ACM crée le prix Turing, l’équivalent du Nobel pour l’informatique, qui récompense les plus grands scientifiques du domaine. Il faudra attendre quarante ans pour voir entrer une femme au palmarès. Depuis, deux autres femmes ont été récompensées par le prestigieux trophée. Ce n’est pas si mal, quand la médaille Fields a récompensé une femme pour la première fois en 2014 !!

Frances Allen Source Wikipedia

2006 : Frances Allen, née en 1932, après voir été la première femme à recevoir le titre d’IBM fellow, est la première à se voir récompenser par le prix Turing pour ses contributions pionnières tant pratiques que théoriques dans l’optimisation des compilateurs. Lors de ses études de mathématiques à l’Université du Michigan, Ann Arbor, elle y prend aussi des cours d’informatique, parmi les premiers dispensés. Elle est engagée par IBM avec l’envie de revenir à ses premières amours et de revenir enseigner les mathématiques quand son prêt étudiant serait soldé. Elle restera 45 ans chez IBM. Sa passion pour la compilation lui vient de la lecture attentive du compilateur Fortran en 1957 quand d’autres lisent des romans ! En bref, un compilateur traduit un langage de programmation de haut niveau, comme le langage Cobol dont Grace Hopper est à l’origine rappelez-vous, un langage adapté à des humains, en instructions qu’un ordinateur peut exécuter. Un compilateur est donc par définition dépendant d’un langage de programmation et d’une architecture machine. Avec son équipe, elle conçoit le premier environnement de compilation multi-langages (Fortran, Autocoder qui est un langage proche de Cobol de Grace Hopper et Alpha). Les trois langages partageaient en particulier un socle d’optimisation qui permettait de produire du code pour les deux architectures du supercalculateur Stretch et de son co-processeur Harvest. Elle travailla ensuite à la conception du premier ordinateur superscalaire (ACS) capable d’exécuter plusieurs instructions simultanément, y compris dans le « désordre ». Il va de soi qu’écrire des compilateurs associés à ce nouveau type d’architecture représentait un incroyable défi, qu’elle a su relever en représentant le code source comme un graphe plutôt que comme une séquence d’instructions. Cette représentation a permis en particulier de pouvoir détecter des relations entre différentes parties du code difficiles à détecter autrement. Son dernier projet a consisté à compiler des programmes séquentiels pour des architectures parallèles.

L’une des grandes vertus scientifiques de Frances Allen, a été à l’instar de Grace Hopper, non pas de réinventer des nouveaux paradigmes en langage de programmation mais de concevoir des mécanismes nouveaux d’analyse et d’optimisation permettant de traiter les langages tels qu’ils étaient utilisés en pratique.

Barbara Liskov
Source Wikipedia

2008 : Barbara Liskov reçoit le prix Turing pour ses travaux dans le domaine des langages de programmation et de la méthodologie polymorphe. Barbara Liskov, née en 1939, fait ses études à Berkeley, passe un doctorat à Stanford avant de rejoindre Mitre Corp où elle crée le système d’exploitation pour l’ordinateur Venus, un système d’exploitation qui permettait d’isoler, en utilisant la notion de machine virtuelle (ça vous rappelle quelque chose ?) pour isoler les actions, et donc potentiellement les erreurs, d’un utilisateur sur une machine partagée entre plusieurs utilisateurs : les débuts du temps partagé. Elle devient professeur au prestigieux MIT en 1971. Elle y conçoit un langage de programmation, appelé CLU, qui introduit les notions de modularité, d’abstractions de données et de polymorphisme (ce qui permet d’utiliser le même code pour des types d’objets différents), notions fondatrice des langages orienté-objet dont le plus connu est le plébiscité Java. Le langage Argus, sur lequel elle travaille plus tard, étend ces concepts pour faciliter la programmation au dessus d’un réseau. C’est d’ailleurs dans le domaine des systèmes distribués, quand plusieurs machines connectées par un réseau exécutent ensemble une application, qu’elle continuera son illustre carrière. Elle est encore extrêmement active aujourd’hui et les travaux actuels du domaine reposent sur bien des concepts qu’elle a introduit en terme de réplication, tolérance aux défaillances, etc. Elles s’est en particulier attaquée à l’algorithmique Byzantine, qui consiste à tolérer la présence d’entités malicieuses (attaques ou fautes matérielles ou logicielles aléatoires) dans un système.

L’avantage de mettre autant de temps à récompenser les femmes dans cette discipline jeune est qu’elles sont toujours actives ! J’ai eu la chance de rencontrer Barbara Liskov, une grande dame de ma discipline, que nous admirons tous beaucoup et qui est en particulier une fervente défenseure de la cause féminine. Elle a beaucoup contribué à renforcer la présence des femmes professeurs au MIT, et met beaucoup d’énergie pour animer la communauté des femmes en système en particulier.

Shafi Goldwasser
Source Wikipedia

2012 : Shafi Goldwasser reçoit, avec Silvio Micali, le prix Turing pour ses travaux dans le domaine de la cryptographie et de la preuve informatique. C’est un peu comme si Babbage avait partagé son prix de la Royal Academy of Astronomy avec Ada… Shafi Goldwasser est née seulement en 1958 et son nom est déjà célèbre dans le domaine de la cryptographie. Cette volontaire et énergique Professeure au MIT est connue en particulier pour ses contributions pionnières dans le domaine de la cryptographie et des « preuves interactives connaissance-zéro ».

Durant ses études à Carnegie Mellon University, Shafi effectue un stage à RAND Corporation qui lui fait découvrir la Californie et surtout Berkeley où elle commence un doctorat sous l’égide du très connu Dave Patterson. Elle rencontre son brillant collaborateur Silvio Micali et commence à s’intéresser à la cryptographie. La cryptographie est un cauchemar à expliquer. Pour simplifier disons que l’une des contributions majeures de Shafi a été cette « preuve interactive connaissance-zéro », qui désigne une méthode dans laquelle une entité prouve à une autre entité qu’une proposition est vraie mais ne donne aucun autre élément que la véracité de la proposition. La dernière fois que l’on m’a expliqué ce concept, c’était justement Shafi Goldwasser, qui nous avait fait le plaisir d’honorer de sa présence un évènement scientifique que nous organisons pour les étudiants. Une célébrité très accessible.

Preuve interactive connaissance-zéro, Wikipedia

Le principe de la « preuve interactive connaissance-zéro » est souvent expliquée de la manière suivante (source wikipedia). Imaginons Peggy (en rose sur l’image, une fois n’est pas coutume) et Victor (en vert), Victor souhaite savoir si Peggy connaît le code d’un passage secret entre une allée A et une allée B d’une cave. L’objectif de Peggy est de lui montrer qu’elle connaît le code sans le divulguer. Peggy entre dans la cave sans que Victor ne sache par quelle allée elle est entrée. Victor lui demande de sortir par l’une des allées, A ou B. Si Peggy connaît le code et que Victor lui demande de sortir par l’allée A, peu importe l’allée par laquelle elle est entrée, elle sortira par A (en ouvrant le passage secret si elle est entrée par B). Sinon elle a seulement une chance sur deux de sortir par l’allée demandée. En répétant cette opération (interactive) plusieurs fois, la probabilité que Peggy sorte par l’allée demandée devient très petite si elle ne connaît pas le code. Ainsi ceci fournit un moyen de vérifier que Peggy connaît le code (preuve) sans que Peggy ait à divulguer d’information (connaissance-zéro). Expliquer cet exemple est déjà un défi, quand à le prouver, cela vaut bien un Turing Award !

À quand la super production Hollywoodienne qui nous portera tout ça à l’écran ?

Anne-Marie Kermarrec, Inria Bretagne

9 mars 2015
La pétulante Grace Hopper
Après Ada Lovelace hier et à l’occasion de la Journée internationale de la femme, Anne-Marie Kermarrec nous parle d’une autre grande pionnière de l’informatique, Grace Hopper. Inventeure d’un des langages de programmation qui a été le plus utilisé, Cobol, Grace Hopper est une grande dame dans un style très différent d’Ada Lovelace. Serge Abiteboul.

Grace Hopper, Wikipedia

Grace Hopper (1906-1992) est américaine, elle obtient un doctorat en mathématiques à Yale et commence à enseigner la discipline à Vassar College en 1931. En 1943, elle s’engage dans l’armée américaine comme beaucoup d’autres femmes, dans l’unité exclusivement féminine WAVES. Ces femmes étaient appelés les « ordinateurs humains » et étaient en charge, pendant que les hommes étaient au front, d’étudier en particulier des trajectoires balistiques. Grace Hopper est affectée à Harvard comme lieutenant pour y programmer l’ordinateur Mark 1. Son supérieur H. Aiken, un peu réticent à l’idée d’avoir comme second une femme, accuse cependant très vite réception des qualités de Grace Hopper pour la discipline. Le Mark 1 est un calculateur générique, programmable par cartes perforées. Grace Hopper s’attèle à la programmation de cette machine dont les résultats seront très importants dans ce contexte de guerre. Grace Hopper décide alors de nommer le processus d’écrire des instructions, le codage (coding). Il est amusant de noter que ce terme, remplacé par celui de programmation, vient d’être récemment remis au goût du jour. À l’issue de la guerre, Grace Hopper ne peut réintégrer la Navy en raison de son âge trop avancé, et doit quitter Harvard qui n’attribue pas de postes de professeurs aux femmes.

Elle rejoint alors Eckert-Machly Computer Corporation, une « startup » qui souhaite commercialiser l’ordinateur, et l’équipe qui développe l’Univac. Grace Hopper est parmi les premières à défendre l’idée d’un langage de programmation qui serait d’une part indépendant des machines (de multiples ordinateurs fleurissent à l’époque) et d’autre part possible d’être exprimé non pas avec des symboles mais à l’aide d’un langage proche de l’anglais, permettant ainsi à des gens qui n’auraient pas de doctorat en mathématiques ou informatique de pouvoir programmer des ordinateurs. Elle introduit alors avec cinquante ans d’avance le concept de réutilisation. Les langages de programmation de haut niveau étaient nés. Elle écrit en 1952 le premier compilateur. Elle introduit en particulier la notion de subroutines, réalise qu’elles peuvent être stockées et assemblées par l’ordinateur lui-même. Elle écrit alors un morceau de code, un compilateur, pour effectuer ces tâches automatiquement. C’est en 1959, qu’avec une poignée d’autres scientifiques, elle pose les bases du langage Cobol, très largement inspiré du FLOW-MATIC qu’elle avait inventé quelques années auparavant. Cobol sera une vraie révolution industrielle.

Enfin, Grace Hopper est connue pour avoir rendu populaire la notion de « bug », même si le terme était déjà utilisé pour désigner des phénomènes inexplicables. Le terme de « bug » est associé à la découverte d’un insecte, en l’occurrence une mite, qui avait provoqué un faux contact et une erreur dans l’exécution d’un programme.

Une féministe à sa manière, Grace Hopper croyait fermement que les femmes disposaient des mêmes capacités (ça c’est faire preuve de féminisme) et des mêmes opportunités (ça moins, un manque de discernement étonnant pour une femme de ce calibre) que les hommes. Ceux qui connaissent Grace Hopper ont en tête l’image de la vieille dame, amiral de l’armée américaine, austère, en uniforme. Grace Hopper s’est pourtant imposée dans ce monde informatique en construction, largement dominé par les hommes, à renforts de sarcasmes, d’humour mais aussi de charme, selon ses propres mots [1]. En revanche, elle n’a jamais admis que les droits des femmes avaient besoin d’être défendus d’une quelconque manière. Trop optimiste sur la condition humaine il semblerait. Qu’importe, son nom aujourd’hui est clairement associée à une réussite féminine en informatique. Toute féministe qu’elle était, il est amusant de noter que le nom Hopper est en fait celui de l’homme avec qui elle s’est mariée en 1930 et dont elle a divorcé en 1945.

Contrairement à Ada Lovelace, Grace Hopper a été très primée tout au long de sa vie. Elle reçoit en particulier en 1969, le prix de l’homme de l’année en informatique (Computer Sciences Man of the Year award). En 1973, elle devient la première personne américaine et la première femme, toutes nationalités confondues, à recevoir la distinction « Distinguished Fellow of the British Computer Society ». En 1971, l’ACM crée le prix Grace Murray Hopper, qui récompense le(la) jeune informaticien(e) de l’année.

À suivre…

Anne-Marie Kermarrec, Inria Bretagne

Pour aller plus loin
1. The queen of Code, directed by Gillian Jacobs. http://fivethirtyeight.com/features/the-queen-of-code/
2. Grace au Letterman Show (en anglais)
3. The Queen of Code
Rear Admiral Grace M. Hopper, USN, Ph.D. Wikipedia
8 mars 2015