Catégorie : Recherche

  • Maurice Nivat : une vision à long terme de la recherche en informatique

    Sur Interstices, la revue scientifique sur les sciences du numérique, Maurice Nivat, ce père de l’informatique théorique qui vient de nous quitter, partageait il y a presque dix ans son émerveillement pour la révolution conceptuelle à laquelle il a grandement participé. Un grand merci de nous permettre de reprendre ce billet ici. Thierry Viéville.

    En 1970, Maurice Nivat, jeune mathématicien, et Marcel-Paul Schützenberger, son père spirituel, nommé depuis peu au directoire de l’IRIA (ancêtre de l’INRIA) avec Henri Boucher, André Lichnerowicz et Jacques-Louis Lions, préparent un événement pour le moins inédit : une conférence de presse pour annoncer la naissance officielle de ce qu’ils baptisent « l’informatique théorique » ! « Je ne sais pas ce qui nous a pris ce jour-là, reconnaît Maurice Nivat. Toujours est-il que près de 40 ans plus tard, la discipline existe bel et bien et que le nombre de chercheurs concerné a été multiplié par cinquante si ce n’est cent. »

    De même, les trois grands chapitres qu’ils énoncent à l’époque, devant une quinzaine de journalistes spécialisés, ont perduré : la théorie des automates et des langages, l’algorithmique et, la théorie de la programmation. Maurice Nivat rappelle ce passé avec une pointe d’étonnement et d’amusement rétrospectif : « On ne s’est finalement pas trompés ». Il faut dire qu’ils n’étaient pas tout à fait novices : leur passion commune pour cette discipline émergente n’était pas nouvelle : « Il nous a fallu environ dix ans, entre 1960 et 1970, pour comprendre ce qu’étaient les langages de programmation, apprendre à les compiler, les traduire, rappelle Maurice Nivat. Cela peut paraître long mais il faut se replacer dans le contexte de l’époque, des machines à calculer programmées en langage machine – on ne parlait pas encore d’ordinateurs mais de machines (ou « bécanes »), ni d’informatique mais de calcul automatique – , des cartes perforées, où toute erreur de poinçonnage se payait au prix de la vérification de la totalité des cartes. »

    Pionnier de la théorie des automates

    C’est à l’Institut Blaise Pascal (le centre de calcul du CNRS qui avait très récemment acquis son premier ordinateur pour remplacer les anciennes machines à manivelle) que dirigeait alors René De Possel, que Maurice Nivat découvre l’informatique, en 1959, à un moment où la discipline n’existait pas encore (le mot apparaît vers le milieu des années 1960). Les chercheurs tentent alors de commander, de « programmer » la toute nouvelle machine de l’Institut : une Bull Gamma AET, une incroyable machine, parmi les premières en France, installée dans la cave, « qui devient rapidement notre temple de la mathématique ». Normalien, théoricien dans l’âme, Maurice Nivat est d’emblée attiré par les langages de programmation de ces machines à calculer, des langages « auxquels pas grand monde ne comprenait grand chose ». On en compte trois en gestation à l’époque : Fortran (le langage des machines d’IBM), Algol 60 développé par un groupe international et Lisp, le langage conçu par John McCarthy.

    « Une seule personne était vraiment capable de faire marcher cette machine : Louis Nolin ! », aime t-il à rappeler, évoquant ainsi son autre maître à penser. Logicien autodidacte, Louis Nolin a commencé par une formation en philosophie avant de s’intéresser à l’informatique. Il a très tôt imaginé qu’on pouvait raisonner sur les programmes comme sur n’importe quel objet mathématique, qu’il devait y avoir une théorie à construire, sur des bases mathématiques, pour faire faire des calculs à ces machines.

    Pourtant, rappelle t-il, « le décalage entre les espoirs que faisait naître l’informatique et les possibilités de ces machines était énorme. On pensait pouvoir tout calculer… mais il fallait pas moins d’une seconde pour aller chercher une seule information sur le tambour de la machine, qui comptait 64 registres en tout et pour tout ! C’était tout simplement un exploit d’inverser une matrice de 15 par 15, un problème mathématique relativement simple que l’on résout aujourd’hui par ordinateur sur des matrices de 450 000 x 450 000 ! ». Ainsi, avec Louis Nolin, il lui a fallu presque deux ans pour concevoir un compilateur d’environ 3 000 lignes de code.

    Une révolution conceptuelle
    Marcel-Paul Schützenberger lors du colloque ICALP en 1972.
    © INRIA

    Maurice Nivat rencontre Marcel-Paul Schützenberger, « Schütz » comme il dit, en 1963 : une révélation. Ce mathématicien autodidacte, psychiatre et médecin de formation, « s’était mis aux mathématiques pendant une de ses campagnes de vaccination pour l’OMS (Organisation mondiale de la santé) en Indonésie… parce qu’il s’ennuyait ». Libertaire, anarchiste, élitiste, maniant avec plaisir le paradoxe, intéressé par tous les problèmes scientifiques, curieux de tout, c’était aussi une des figures de Saint-Germain des Prés aux côtés de Juliette Greco et Boris Vian, qui l’a décrit sous les traits de « l’abominable Docteur Schütz » dans un de ses livres. C’était surtout un génie mathématique.

    Sous sa direction, il prépare sa thèse d’Etat en mathématiques, présentée en 1967, sur « les transductions des langages de Chomsky », des objets mathématiques entièrement développés par des informaticiens. Une première ! « À l’époque, considérer l’informatique comme une discipline mathématique était une véritable révolution conceptuelle, ajoute t-il. La Faculté des sciences de Paris ne comptait pas plus de 15 à 20 professeurs de mathématiques, c’était un cercle fermé, très élitiste et Schütz était très tendu quand j’ai présenté ma thèse, quelque peu exotique mais finalement bien acceptée. »

    Il se souvient « d’une période miraculeuse : on rencontrait des gens de toute espèce. Toutes les opinions étaient bonnes, équiprobables, c’était une période passionnante où tout était à faire, notre champ d’action était pratiquement illimité. Pas besoin de réflexion prospective. » Pendant ces années de gestation de l’informatique, Maurice Nivat met aussi sur pied les premiers programmes d’enseignement de l’informatique dans des universités françaises, à Grenoble et Rennes où il est chargé de conférences pendant sa thèse : « on écrivait les programmes de licence sur un coin de table, dans un bar ! Il m’arrivait d’enseigner le mercredi ce que j’avais appris le mardi soir ! »

    Des langages dotés d’une sémantique

    Cet enthousiasme est encore accru lorsqu’en septembre 1969, il découvre la « théorie de la programmation », en participant à une réunion à Colchester (Grande-Bretagne) qui réunit les fondateurs de la discipline, Dana Scott, Robin Milner, Christopher Strachey, Peter Landin, David Park… Il découvre que les programmes eux-mêmes, ces objets étranges sans véritable statut, peuvent être considérés comme des objets mathématiques, susceptibles de théorèmes. Ces théories prendront beaucoup d’importance par la suite pour la vérification de programmes, pour la production et la manipulation de logiciels de plus en plus gros et complexes.

    Convaincu de l’importance de cette voie de recherche, il n’hésite pas, quelques mois plus tard, en 1970, à placer la théorie de la programmation comme un des trois chapitres fondamentaux de l’informatique théorique, aux côtés de la théorie des automates et des langages sur lesquels il travaille depuis dix ans et l’algorithmique, qui s’est finalement assez peu développé en France bien que les problèmes qu’elle soulève soient innombrables, comme les problèmes dits NP-durs. Aujourd’hui encore, ce professeur émérite à l’Université Denis-Diderot (Paris VII) milite pour sensibiliser les théoriciens aux applications et réciproquement : un débat qui battait son plein dans « ce fabuleux lieu de création qu’était le bâtiment 8 » partagé avec Gérard Berry, Gérard Huet, Philippe Flajolet, Gilles Kahn, Jean Vuillemin, Jean-Marie Cadiou, Jean-Jacques Lévy, Bruno Courcelle, entre l’école française très théoricienne des langages formels, parfois sectaire autour de Schützenberger et des chercheurs inspirés du modèle américain de la programmation.
    Maurice Nivat lors du colloque ICALP, ici avec Maurice Gross.
    © INRIA

    L’émulation s’étend à l’échelle européenne quand, avec Marcel-Paul Schützenberger, ils créent l’Association européenne d’informatique théorique (EATCS European Association for Theoretical Computer Science), dont le premier colloque baptisé ICALP (International Colloquium on Automata, Languages and Programming) a lieu en 1972 à l’IRIA. Les grands noms de la discipline sont au rendez-vous : Michael Rabin, Michael Paterson, Dana Scott, Albert Meyer, Samuel Eilenberg, Corrado Boehm. L’EATCS compte aujourd’hui 2 000 personnes. En 1975, Maurice Nivat lance aussi une revue scientifique, qui fait toujours référence : TCS (Theoretical Computer Science), dont il est rédacteur en chef pendant 25 ans. La revue a publié pas moins de 100 000 pages en 25 ans.

    Le regard du chercheur sur l’informatique

    Loin de rester cantonné dans le bâtiment 8 et son monde aussi ouvert soit-il de chercheurs et d’étudiants en langages algébriques, en sémantique, en parallélisme, Maurice Nivat accepte en 1982 la lourde tache de réfléchir pour les ministères de l’éducation nationale et de la recherche, à la filière électronique. À la suite de son rapport (Savoir et savoir-faire en informatique), il lance une dizaine de « programmes de recherche coordonnés » financés par le programme mobilisateur de la filière électronique qui réunit chercheurs et industriels, dont il préside le conseil scientifique de 1982 à 1992. Intelligence artificielle, architecture machine, parallélisme, programmation… sont autant de sujets qui ont pu bénéficier de ces fonds : « cela a joué un grand rôle dans la recherche en informatique en France » reconnaît-il.

    Pourtant son regard sur l’état actuel de la science informatique est amer : « On nous commente avec emphase les succès d’Ariane ou du TGV… mais les princes qui nous gouvernent ont abandonné l’informatique, pourtant clé de ces succès. Je ne comprends toujours pas pourquoi. Aux États-Unis, l’informatique est l’enjeu du moment, le bouillonnement d’idées y est relayé, financé par les agences fédérales, par les banques… Cette émulation n’existe pas en France : le logiciel n’est pas pris au sérieux, les financements ne sont pas octroyés au bon moment, on finance la création de start-up prometteuses mais ensuite, on ne leur donne pas les moyens de leur développement. » « Les chercheurs en informatique font les frais de l’absence de champ d’application de leurs recherches en France et en Europe, toutes deux dénuées d’industrie informatique, ajoute t-il. C’était criant, en octobre 2007, lors de la première demi-journée consacrée à l’informatique à l’Académie des sciences : nous y avons entendu des exposés brillants mais tellement éloignés de l’informatique réelle, de ce que font les machines. » Selon lui, une révolution totale est nécessaire. La priorité est de décider l’éducation nationale à prévoir un enseignement informatique dans les collèges et les lycées, que l’informatique soit enfin considérée, en France, comme une discipline à part entière. Construire l’avenir suppose de former les jeunes. C’est seulement à ce prix que l’informatique fondamentale restera inventive, ouverte sur les autres disciplines, que ce soit la biologie, la linguistique… et toutes sortes d’applications.

    Contrepoint

    Maurice Nivat a contribué à la formation de nombreux acteurs de la recherche en informatique. L’un d’entre eux, Max Dauchet, Directeur du centre de recherche INRIA Lille – Nord Europe, nous apporte son témoignage :
    « Maurice Nivat a été mon maître, comme il l’a été pour nombre d’entre nous, tant par sa science que par sa personnalité. Et il demeure mon maître. Ses intuitions sont toujours vivantes dans mon esprit – ses indignations aussi. Dans un monde informatique naissant et hésitant, il fut pour nous un repère, tant sur le plan de la science que de son rôle dans la société. Et il le demeure. Comme beaucoup de précurseurs, Maurice n’a jamais été vraiment à la mode. Avoir raison trop tôt est un combat difficile, d’où un certain pessimisme – qui n’a jamais altéré sa combativité. De ce fait, Maurice sous-estime l’influence déterminante qu’il a eue sur la recherche française et européenne en informatique. Ceci mériterait un travail d’érudition. Si l’on mettait bout à bout le devenir de tous ceux et celles qu’il a formés et marqués à vie, l’impact de ses initiatives (EATC, TCS, ICALP, les PRC…), on mesurerait sans doute mieux tout ce que la société lui doit. Merci Maurice. »

      Isabelle Bellin Version originale : https://interstices.info/maurice-nivat-une-vision-a-long-terme-de-la-recherche-en-informatique, publié le 17/03/2008

  • Ciao Maurice

    Maurice Nivat © Inria / Photo : J.M. Ramès.

     

    Tu viens de nous quitter ce jeudi 21 septembre, toi le père de l’informatique française. Le monde du numérique est en deuil, et nous ne trouvons pas encore les mots pour te raconter, pour partager tout ce que tu as pu nous apporter.

    Nous vous invitons à lire l’hommage de Serge Abiteboul :  Adieu Maurice

     

  • L’informaticienne et le musicien

    Vous avez déjà vu une musicienne jouer avec les mains mais sans instrument ou un algorithme générer une musique selon telle ou tel compositeur ? Quelle nouvelle musique va émerger de cette interdisciplinarité avec l’informatique ? Comment font des gens aussi différents pour travailler ensemble ? C’est Marcelo M. Wanderley, professeur à l’Université McGill, guitariste amateur et scientifique qui a bien voulu répondre à nos questions sur ce mélange des genres. Thierry Vieville et Marie-Agnès Enard.

    Prof. Marcelo M. Wanderley
    Marcelo M. Wanderley

    Binaire : étudiant en génie électronique, tu as voulu faire un doctorat en musique et l’on t’a répondu qu’il valait mieux faire une thèse sur un sujet sérieux ! Est-ce incompatible ?

    McGill Digital Orchestra : Fernando Rocha playing rules.

    Marcelo Wanderley : les temps changent ! À l’époque, il y a presque 30 ans, il existait très peu d’endroits où on pouvait combiner musique et génie électronique, surtout où j’habitais, au Brésil. La mentalité dans les écoles de génie électronique était assez «  disciplinaire », c’est-à-dire, ceci est du génie, cela ne l’est pas. Aujourd’hui il existe plusieurs laboratoires de recherche entièrement dédiés à la combinaison des deux disciplines. On y étudie les instruments de musique, on y analyse les performances des interprètes, et on y crée aussi de nouveaux instruments et parfois même de nouvelles formes de musique. On mène par exemple des projets académiques de durée variable (entre quelques mois et quelques années) au niveau du master ou du doctorat entre étudiant.e.s de technologie musicale (dorénavant appelés « ingénieur.e.s ») et des étudiant.e.s en interprétation  (dorénavant appelés « musicien.ne.s »). L’objectif d’un tel projet est typiquement la création, et le développement de manières de jouer, d’un instrument musical numérique, c’est-à-dire, d’un instrument  musical qui utilise un ordinateur comme générateur de sons.

    B : concrètement, comment une informaticienne comme Marie par exemple ou un musicien comme Pierre vont-ils pouvoir collaborer ?

    MW : et bien au début ce n’est jamais facile, il faut que chacun comprenne les buts et les enjeux de l’autre. Alors initialement Marie va avoir l’impression que le musicien lui demande la lune et que ce n’est pas faisable. Pierre lui, lorsque l’informaticienne lui proposera une solution, trouvera que ce n’est pas jouable ou que cela ne correspond pas à sa volonté créatrice du moment.

    B : tu as d’ailleurs fait une analyse de cette interaction entre l’ingénieur et le musicien au cours d’un projet, peux-tu nous la détailler ?

    MW : mon expérience dans plusieurs projets de ce type est la suivante :

    • Les ingénieur-e-s ont tendance à mettre un effort soutenu dans l’avancement du projet, de façon linéaire. Au début du projet, ils vont souvent tester des idées et développer des prototypes (en collaboration avec les musicien.ne.s). Une fois ces idées et prototypes évalués, des variations et modifications sont implémentées de façon similaire jusqu’au développement des versions finales des dispositifs.
    • Les musicien-ne-s par contre ont tendance à mettre de plus en plus d’effort avec l’avancement du projet. Au début le temps est lent c’est celui de la création. Concrètement, ce n’est pas forcément étonnant, ne serait-ce que puisque les musicien-ne-s doivent attendre la disponibilité des prototypes pour pouvoir appréhender ce qui est possible et s’en servir ! Leur effort est décuplé à l’approche du concert.

    Bien entendu, les deux travaillent autant, c’est à dire que les surfaces sous les deux courbes (qui correspondent au travail accumulé par chacune et chacun) sont les mêmes.

    B : que déduis-tu de ce petit modèle de comportement ?

    MW : si on regarde l’intersection entre les courbes linéaire (ingénieurs) et exponentielle (musiciens) il y un temps « t » dont la position peut varier par rapport, entre autres, au type et à la complexité du projet, aux ressources disponibles, ainsi qu’à la personnalité des collaborateurs. Il se situe plutôt entre le milieu et la fin du projet.

    • Avant ce temps « t », les ingénieur-e-s ont tendance à penser que les musiciens ne travaillent pas suffisamment et/ou qu’ils ne sont pas assez impliqués dans le projet. J’appellerais cette partie « la région de frustration de l’ingénieur».
    • Après ce temps « t », les musicien-ne-s ont tendance à penser que les ingénieurs ne travaillent pas suffisamment et/ou qu’ils ne sont pas (ou plus) assez impliqués dans le projet. J’appellerais cette partie « la région de frustration du musicien».

     B : as-tu fais d’autre constats ?

    McGill Digital Orchestra : Chloé Domingues with a T-stick

    MW : Dans mon expérience, les musiciens et les ingénieurs, du fait de leurs études et pratiques respectives, ont deux approches de travail assez différentes. Côté ingénierie, ils sont très souvent focalisés sur la production de prototypes (pratiques) qui illustrent des idées abstraites, tandis que les musiciens sont focalisés sur la production d’un évènement (concert) bien ancré dans le temps. Ainsi le fait qu’un chercheur ou une ingénieure présente son travail de manière moyenne dans un congrès cela est toujours embêtant mais peut être pas catastrophique ; pour un interprète, louper un concert ou avoir une vidéo diffusée largement où il joue mal peut juste sonner la fin de sa carrière.

    De même, dans le cas de la démonstration d’un prototype d’instrument électronique par l’ingénieure, si la démo « ne marche pas », normalement on s’excuse et on réinitialise le système. Ceci est peut-être beaucoup plus compliqué quand une démonstration (interprétation) musicale « ne marche pas » devant un public. La tolérance à l’erreur n’est pas la même

    Par ailleurs, un chercheur ou une ingénieure va rechercher la généricité, faire en sorte que ce qu’il crée soit le plus général et réutilisable possible ; à l’inverse l’artiste (la musicienne par exemple) va chercher plutôt à produire quelque chose d’unique, une « œuvre ». La notion d’ « interprétation », au sens d’une action basée sur une expertise cognitivo-physique se déroulant dans le temps, n’est généralement pas une partie essentielle des travaux en informatique ou en ingénierie. Cela est évidemment le cas pour les musiciens.

    De plus, le pas entre un prototype d’instrument numérique qui marche dans un laboratoire de recherche (environnement contrôlé), quitte à se faire réinitialiser quelques fois par l’ingénieur, et celui dans instrument numérique à part entière qui peut être joué à différents endroits de la planète par un musicien (idéalement sans la présence de l’ingénieur) n’est point négligeable. Il demande parfois une version complètement redessinée du prototype de laboratoire.

    De même, le développement d’une pratique musicale experte avec un nouvel instrument musical demande un effort soutenue et étalé dans le temps. Un collègue musicien m’a même dit une fois (en plaisantant) que pour apprendre2 à programmer il suffit d’une semaine mais que pour apprendre à jouer d’un instrument il faut toute une vie. Comme quoi on est parfois encore loin d’une entente sur l’importance de chaque domaine…

    McGill Digital Orchestra : Mark Marshall, Chloé Domingues, Fernando Rocha, Andrew Stewart in quatuor.

    B : pourtant, de nombreux projets d’informatique musicale ont réussi. Comment ?

    MW : la recherche interdisciplinaire en informatique musicale se pratique depuis l’origine de ce domaine dans les années 50. Comme toute collaboration, une bonne partie de l’entente (ou de la mésentente) entre deux ou plusieurs personnes vient des différentes personnalités. Une discussion ouverte et honnête entre les partenaires est dans mon expérience la meilleure et peut être la seule solution.

    Il est essentiel d’insister sur le fait que les deux domaines de recherche sont à mon avis également importants pour le projet et qu’il n’a pas de notion implicite de ce qui est correct ou incorrect dans la collaboration puisque les référentiels sont très différents.

    Ces façons de travailler, inhérentes à chaque domaine, peuvent mener à de vraies découvertes sur de nouvelles façons de travailler. D’ailleurs, l’interdisciplinarité est un type de recherche qui s’applique évidemment à d’autre champs, au-delà de l’informatique musicale, complémentaire aux méthodes spécialisées1 dites « disciplinaires » (c’est à dire bien définies dans des départements universitaires). En effet, dans le monde réel de nombreux problèmes ont tendance à demander des solutions qui dépassent les limites des disciplines académiques.

    En informatique musicale, cela génère évidemment de nouvelles formes de créations inouïes.

    B : oui mais lorsque le Sacre du printemps se jouait à Paris en 1913, par exemple, ce fut un scandale !

    MW : certes, quelque chose d’inédit ne passait pas ; le travail inter-disciplinaire entre le compositeur Stravinsky et le chorégraphe Nijinski était trop novateur. De même quand on lit certains commentaires de l’entretien d’Arshia Cont, sur ces travaux en informatique musicale, on voit qu’une partie du public n’est pas encore au rendez-vous.

    Et pourtant il y a de belles et précieuses choses qui se font !!!

    Les gestes est une création de Van Grimde Corps Secrets en coproduction avec le CIRMMT – Centre de Recherche Interdisciplinaire en Musique, Médias et Technologie, l’IDMIL – Input Devices and Music Interaction Laboratory de l’École Schulich de l’Université McGill, l’Agora de la danse, le Concertgebouw de Bruges, le Schouwburg d’Arnhem et le Forum/scène conventionnée de Blanc-Mesnil.
    Comment l’apprentissage d’un instrument de musique change-t-il le cerveau? La musique peut-elle aider les personnes à se remettre des accidents vasculaires cérébraux? Ce ne sont que deux des questions auxquelles les chercheurs de l’université de McGill et de l’Institut neurologique de Montréal cherchent à répondre avec la création d’un violoncelle qui peut être joué dans un scanner IRM pour voir comment le cerveau change en présence d’un instrument de musique.
    À l’avant-garde de l’industrie, d’abord petite boutique de guitares montréalaise devenue une florissante entreprise manufacturière, l’entreprise Guitares Godin a collaboré avec le Centre interdisciplinaire de recherche en musique, médias et technologie de l’Université McGill, afin de mettre au point une nouvelle technologie pour analyser le style et le son de divers modèles de guitares, et aider les clients à trouver les caractéristiques recherchées dans un produit fini.
    Haptic Field est une installation d’art immersive et multisensorielle créée au Centre d’art Chronus à Shanghai en Chine en juillet 2016. C’est une installation multi-sensorielle participative qui fusionne la mode contemporaine, la technologie portative et une exploration des sens au-delà du vécu immédiat. En utilisant des vêtements spécialement conçus, Haptic Field crée une expérience physique singulière et étrange, nous donnant l’impression que nos sens sont étirés au-delà des limites du corps.
    « L’ordinateur est un instrument de musique », présentation de mes travaux de recherche « utiliser le numérique pour démocratiser les usages, et partager cet art avec toutes et tous, tout peut être musique ». Ref: usbeketrica.com.

    Interview de Marcelo M. Wanderley (Inria Lille – Nord Europe / McGill University) par Thierry Viéville.

    1 La spécialisation croissante des domaines est un phénomène qui se base sur un processus inéluctable et de longue haleine (cf Thomas Kuhn  « La structure des révolutions scientifiques » Flammarion 2008).
    2 On peut découvrir la programmation et pensée informatique en quelques heures avec la formation Class´Code. Pour devenir un.e professionnel.le de l’informatique il faut, comme pour un instrument de musique, des années d’études et de pratique.

  • La Chaire de Colin

    « Former 300 000 éducateurs, animateurs, enseignants pour que ceux-ci puissent demain utiliser le code informatique dans leurs activités devant les enfants et les adolescents… ». Cela vous rappelle-t-il quelque chose ?  C’est la mission Class’Code, qui mêle formation à distance et temps de rencontre, apprivoisement de la machine et découverte de la pensée informatique sans ordinateur, apprenants et facilitateurs.  Cela vous avait paru un peu fou ? Pourtant, l’UNESCO (oui, oui, l’Organisation des Nations Unies pour l’éducation la science et la culture, elle-même) a été conquise au point d’attribuer à l’Université de Nantes une chaire* « en technologies pour la formation des enseignants par ressources éducatives libres ». Binaire a demandé à Sylvie Alayrangues de nous parler de cette chaire.  Serge Abiteboul.

    À l’origine de cette chaire, on trouve Colin de la Higuera, professeur des universités à Nantes, ex-président de la société informatique de France, ex-éditeur de binaire, déjà à l’origine de Class’Code.

    Colin de la Higuera au Congrés de la SIF à Poitiers, 2017, Photo Jean-François Billaud

    L’ambition de cette chaire est claire : donner une nouvelle dimension au projet Class’Code en travaillant non seulement à son amélioration et à sa pérennisation mais aussi à son extension à l’international et pourquoi pas à d’autres disciplines.

    Pour l’améliorer, des recherches sont d’ores et déjà menées, par exemple, pour évaluer le subtil équilibre entre formation à distance et temps de rencontre. L’extension vers les mathématiques est envisagée, bénéficiant de collaborations déjà existantes, liant la société informatique de France et Inria, les partenaires initiaux du projet, aux sociétés savantes des disciplines concernées. Enfin, dès son lancement, cette nouvelle aventure a également pris une envergure internationale en embarquant parmi ses premiers partenaires la « Knowledge for All Fondation« .

    Et la science informatique ? Elle n’est pas oubliée ! La chaire émarge déjà sur un premier projet européen, X5gon,  où il s’agit justement d’utiliser des techniques d’intelligence artificielle pour naviguer plus facilement et de manière plus pertinente dans un ensemble riche et complexe de ressources éducatives.

    Que dire de plus ? Et bien, que nous souhaitons à Colin de réussir à regrouper autour de lui, comme il a su le faire pour Class’Code, une dream team d’universitaires, de chercheurs, d’entreprises, d’acteurs de l’éducation populaire, de créateurs et de diffuseurs de ressources éducatives, de collectivités… Et peut-être, souhaitons-lui également que cette chaire porte bien haut les valeurs éthiques (communes à l’aventure Class’Code) qui la fondent, dans la vision d’une société solidaire où l’éducation de tous et à tout âge passe aussi par le partage et l’entraide.

    Sylvie Alayrangues, Maitre de Conférence à l’Université de Poitiers

    (*) Une chaire UNESCO lie un établissement d’enseignement supérieur à l’UNESCO autour d’un programme d’une durée initiale de 4 ans. L’objectif de ces programmes est de faire progresser l’enseignement, l’apprentissage ou la recherche dans un des domaines prioritaires de l’UNESCO. Une chaire permet, notamment, de développer des activités au niveau international en bénéficiant des réseaux et de la renommée de l’UNESCO.

  • Miolane’s anatomy

    Nous avons demandé à une amie, Florence Sedes toulousaine de la SiF  de nous présenter les travaux de Nina Miolane, une « numéricienne » parmi les 30 lauréates de la bourse L’Oréal-Unesco pour les Femmes et la Science : « Vers la médecine de demain : une aide numérique au diagnostic humain ». Pierre Paradinas.

    Sélectionnée parmi plus de 1 000 candidates, Nina Miolane est récompensée, après un parcours d’exception et un doctorat obtenu entre Nice et Stanford, entre mathématiques et médecine.

    Photo : Nina Miolane.

    Comment utiliser les mathématiques et les hautes technologies pour transformer la recherche en médecine ? Pouvons-nous créer des outils numériques améliorant la pratique médicale courante et hospitalière ? Le travail de recherche de Nina Miolane développe un des piliers de la médecine de demain : l’anatomie numérique.

    La médecine prévoit d’être transformée au cours des prochaines années grâce aux nouvelles technologies : d’un côté, les technologies d’imagerie (scanners, IRM, etc) et de l’autre côté les technologies du numérique permettant l’analyse de ces images (superordinateurs, calcul distribué, etc). Sa recherche en anatomie numérique s’appuie sur ces deux technologies pour construire, dans l’ordinateur, un modèle de l’anatomie humaine.

    Le modèle d’anatomie numérique contient tout d’abord la forme de chaque organe dans son état sain, ainsi que toutes les formes de l’organe qui correspondent à ses variations saines – par exemple dues à la taille du patient – ou pathologiques. De nombreuses pathologies sont en effet visibles sur les images médicales, comme par exemple la maladie d’Alzheimer qui se caractérise par une atrophie du cortex cérébral et une expansion des ventricules, ces cavités du cerveau contenant le liquide céphalorachidien.

    Dans le cadre du projet récompensé par la bourse l’Oréal-UNESCO, Nina s’est intéressée plus particulièrement à l’anatomie du cerveau. Une hypothèse classique suppose l’existence d’une unique anatomie cérébrale saine de référence. Toutefois, la variabilité des topologies du cerveau, par exemple au niveau des sillons du cortex cérébral, est telle qu’il n’est souvent pas possible de représenter l’anatomie par un cerveau unique. Celui-ci sera soit consistant mais flou au niveau des sillons, soit inconsistant car il représentera seulement une topologie particulière des sillons.

    Ainsi, le modèle d’anatomie développé a la forme d’un arbre : les niveaux élevés représentent l’anatomie saine à grande échelle comme la boite crânienne, et les niveaux bas représenteront les anatomies saines à petite échelle, comme le nombre de sillons. Grâce à la bourse l’Oréal-UNESCO, Nina va pouvoir suivre une (courte) formation en neuro-anatomie et neurosciences, pour confronter l’anatomie obtenue avec son modèle à la connaissance actuelle des spécialistes, et poursuivre ses recherches pot-doctorales entre les Etats-Unis et la France.

    « Nous espérons mieux comprendre, caractériser et diagnostiquer les maladies cérébrales ou neurodégénératives. De plus, ce projet est bien sûr centré sur le cerveau mais est suffisamment générique pour être appliqué ensuite aux autres organes. »

    L’anatomie numérique doit même permettre d’aller plus loin : le projet est de fournir, à terme, la probabilité que le patient développe telle ou telle maladie dans le futur. En effet, l’outil numérique permet de détecter des variations subtiles de formes d’organes et permet de tendre vers un diagnostic avant que les symptômes se développent. Détecter une maladie neurodégénérative de façon pré-symptomatique, comme Alzheimer par exemple, permettrait non pas de la guérir ou de la stopper, mais plutôt de ralentir sa progression de façon à ce que la vie quotidienne du patient ne soit pas affectée.

    Florence Sedes, IRIT

    Pour retrouver les travaux de Nina Miolane, suivre ce lien.

  • Le processeur qui spéculait plus qu’un trader

    portraitNous retrouvons aujourd’hui, Arthur Pérais un des lauréats du prix de thèse Gilles Kahn 2016, décerné par la SiF et patronné par l’Académie des Sciences. Son travail a pour titre  « Increasing the Performance of Superscalar Processors through Value Prediction », il a été soutenu à l’Université de Rennes 1, et préparé dans l’équipe-projet Inria ALF de l’IRISA, sous la direction d’André Seznec. Arthur pour Binaire, nous explique comment on peut revisiter d’anciennes techniques (du milieu des années 90) pour les nouvelles générations de processeurs comme ceux de votre téléphone mobile pour augmenter les performances. Pierre Paradinas

    « Avec deux fois plus de cœurs dans le processeur, l’appareil est deux fois plus performant. » Cet argument de vente est souvent avancé pour vanter les capacités d’un smartphone ou d’un ordinateur.

    Le processeur est le cerveau de la machine, et chacun de ses cœurs a pour rôle de suivre une liste d’instructions : un programme (par exemple, un navigateur web ou un jeu vidéo). Pour accélérer leurs calculs, certains programmes peuvent être divisés en sous-programmes qui vont s’exécuter sur les différents cœurs du processeur en parallèle, tout comme il est possible de faire plusieurs crêpes à la fois quand on dispose de plusieurs crêpières.

    Cependant, si on veut faire une seule crêpe, avoir plusieurs crêpières est inutile. Ainsi, de nombreux programmes ne peuvent pas être divisés en sous-programmes parallèles car les calculs qu’ils effectuent ne s’y prêtent pas.. Dans ce cas, un seul cœur exécute tout le programme.

    Lors de ma thèse, j’ai donc travaillé à améliorer la performance d’un seul cœur grâce à la prédiction de valeurs. La prédiction de valeurs, c’est comme monter une étagère sans lire le manuel, en spéculant sur la position des pièces, des vis et chevilles. Par exemple, au lieu de passer 15 minutes à lire le manuel et 45 minutes à monter l’étagère, on peut gagner 15 minutes en passant directement au montage. La tâche achevée, il faut vérifier qu’on ne s’est pas trompé, mais cela n’empêche pas de commencer à ranger des livres dans l’étagère après 45 minutes, et non 60. Naturellement, si on a fait une erreur lors du montage, il faut tout recommencer.

    illustration-perais

    C’est comme ça que se comporte la prédiction de valeurs : on gagne peu lorsque l’on prédit bien, et on perd beaucoup lorsque l’on prédit mal. Heureusement, les calculs effectués par les programmes sont souvent redondants, et de nombreux résultats peuvent donc être prédits correctement.

    Pour ce faire, un prédicteur de valeurs est ajouté à chaque cœur. Il mémorise les derniers résultats produits par les différentes instructions, et tente d’identifier des motifs qui se répèteraient. Par exemple, une instruction qui dans le passé a produit 1, 2 puis 1 produira sans doute 2 lorsqu’elle sera exécutée à nouveau. Le résultat prédit est utilisé pour exécuter la prochaine instruction sans attendre le « vrai » résultat, ce qui accélère l’exécution du programme.

    Au cours de mon doctorat, j’ai développé des algorithmes de prédictions permettant d’identifier des motifs complexes dans les résultats produits, et j’ai montré comment les implanter dans un processeur de façon réaliste.

    Finalement, afin d’estimer le gain  de performance, j’ai utilisé un programme simulant un processeur moderne. Ce simulateur lit les instructions d’un autre programme (par exemple un navigateur), et l’exécute comme il serait exécuté sur une vraie puce, tout en comptant le temps nécessaire à l’exécution du programme. Par ce procédé, et suivant le programme accéléré, j’ai pu mesurer des gains de performance allant du négligeable jusqu’à plus de 30%, ce qui peut paraître peu mais est très encourageant dans ce domaine.

    Arthur Pérais

  • Podcastscience : Informatique et Ethique

    Puyo (Podcast science)

    Informatique, responsabilité, travail, intelligence artificielle… Podcast science  a reçu un éditeur de Binaire, Serge Abiteboul, et un ami, Gilles Dowek, pour aborder tous ces sujets, avec un objectif: essayer d’imaginer ce que peut être notre avenir !

    Le podcast sur Soundcloud

    Ça dure deux heures et demi, pour bien prendre le temps de raconter, d’expliquer, bref d’approfondir le sujet. Pour qui est vraiment passionné par le sujet, ou … en a assez de l’information saucissonnée en rondelles superficielles.

    Thierry Viéville, Inria et Binaire

  • Vers une théorie de l’intelligence

    Fabriquer de l’intelligence est un défi que l’informatique veut relever. Quand elle réussit, c’est toujours de façon limitée et en évitant d’aborder de front l’intelligence humaine, qui reste mystérieuse. Jean-Paul Delahaye nous en reparle sur Interstices et nous repartageons ce texte ici.. Joanna Jongwane.

    Les machines égalent, voire surpassent les humains dans certaines tâches qui réclament de l’intelligence. C’est le cas des échecs, des dames anglaises… © Thomas Söllner – Fotolia.

    Une première version de l’article d’Interstices que nous reprenons ici est parue dans le dossier n°87 Les robots en quête d’humanité de la revue Pour la Science, numéro d’avril/juin 2015.

    L’idée qu’il existe plusieurs types d’intelligences séduit, car elle évite à chacun de se trouver en un point précis d’une échelle absolue et parce que chacun espère bien exceller dans l’une des formes d’intelligence dont la liste tend à s’allonger. Cette pluralité d’intelligences a été proposée par le psychologue américain Howard Gardner : dans son livre Frame of Mind, de 1983, il énumère huit types d’intelligence. Très critiquée, par exemple par Perry Klein, de l’Université d’Ontario, qui la considère tautologique et non réfutable, cette théorie est à l’opposé d’une autre voie de recherche affirmant qu’il n’existe qu’une sorte d’intelligence à concevoir mathématiquement avec l’aide de l’informatique et de la théorie du calcul.

    Dames, échecs, go, voitures…

    Évoquons d’abord l’intelligence des machines et la discipline informatique nommée « intelligence artificielle ». Il faut l’admettre, aujourd’hui, les machines réussissent des prouesses qu’autrefois tout le monde aurait qualifiées d’intelligentes. Nous ne reviendrons pas sur la victoire définitive de l’ordinateur sur les meilleurs joueurs d’échecs, consacrée en 1997 par la défaite de Garry Kasparov (champion du monde) face à l’ordinateur Deep Blue, unanimement saluée comme un événement majeur de l’histoire de l’humanité.

    À cette époque, pour se consoler peut-être, certains ont remarqué que les meilleurs programmes pour jouer au jeu de go étaient d’une affligeante médiocrité. Or, depuis quelques années, des progrès spectaculaires ont été accomplis. En mars 2013, le programme Crazy Stone de Rémi Coulom, de l’Université de Lille, a battu le joueur professionnel japonais Yoshio Ishida qui, au début de la partie, avait laissé un avantage de quatre pierres au programme. En mars 2016, le programme AlphaGo a battu Lee Sedol considéré comme le meilleur joueur de Go. Des idées assez différentes de celles utilisées pour les échecs ont été nécessaires pour cette victoire de la machine, mais pas plus que pour les échecs on ne peut dire que l’ordinateur joue comme un humain. La victoire de AlphaGo est un succès remarquable de l’Intelligence Artificielle qui prouve d’ailleurs qu’elle avance régulièrement.

    Le succès de l’intelligence artificielle au jeu de dames anglaises est absolu. Depuis 1994, aucun humain n’a battu le programme canadien Chinook et, depuis 2007, on sait que le programme joue une stratégie optimale, impossible à améliorer. Pour le jeu d’échecs, on sait qu’il existe aussi des stratégies optimales, mais leur calcul semble hors d’atteinte pour plusieurs décennies encore.

    L’intelligence des machines ne se limite plus aux problèmes bien clairs de nature mathématique ou se ramenant à l’exploration d’un grand nombre de combinaisons. Cependant, les chercheurs en intelligence artificielle ont découvert, même avec les jeux de plateau cités, combien il est difficile d’imiter le fonctionnement intellectuel humain : aux jeux de dames, d’échecs ou de go et bien d’autres, les programmes ont des capacités équivalentes aux meilleurs humains, mais ils fonctionnent différemment. Cela ne doit pas nous interdire d’affirmer que nous avons mis un peu d’intelligence dans les machines : ce ne serait pas fair-play, face à une tâche donnée, d’obliger les machines à nous affronter en imitant servilement nos méthodes et modes de raisonnement.

    Le cas des véhicules autonomes est remarquable aussi de ce point de vue. Il illustre d’une autre façon que lorsque l’on conçoit des systèmes nous imitant à peu près pour les résultats, on le fait en utilisant des techniques le plus souvent totalement étrangères à celles mises en œuvre en nous par la nature, et que d’ailleurs nous ne comprenons que très partiellement : ainsi, pour le jeu d’échecs, personne ne sait décrire les algorithmes qui déterminent le jeu des champions.

    La conduite de véhicules motorisés demande aux êtres humains des capacités qui vont bien au-delà de la simple mémorisation d’une quantité massive d’informations et de l’exploitation d’algorithmes traitant rapidement et systématiquement des données symboliques telles que des positions de pions sur un damier. Nul ne doute que pour conduire comme nous des véhicules motorisés, l’ordinateur doit analyser des images variées et changeantes : où est le bord de cette rue jonchée de feuilles d’arbres ? Quelle est la nature de cette zone noire à 50 mètres au centre de la chaussée, un trou ou une tache d’huile ? Etc.

    Conduire une voiture avec nos méthodes nécessiterait la mise au point de techniques d’analyse d’images bien plus subtiles que celles que nous savons programmer aujourd’hui. Aussi, les systèmes de pilotage automatisé, tels que ceux de la firme Google, « conduisent » différemment des humains. Ces Google cars exploitent en continu un système GPS de géolocalisation très précis et des « cartes » indiquant de façon bien plus détaillée que toutes les cartes habituelles, y compris celles de Google maps, la forme et le dessin des chaussées, la signalisation routière et tous les éléments importants de l’environnement. Les voitures Google exploitent aussi des radars embarqués, des lidars (light detection and ranging, des systèmes optiques créant une image numérique en trois dimensions de l’espace autour de la voiture) et des capteurs sur les roues.

    Ayant déjà parcouru plusieurs centaines de milliers de kilomètres sans accident, ces voitures sont un succès de l’intelligence artificielle, et ce même si elles sont incapables de réagir à des signes ou injonctions d’un policier au centre d’un carrefour, et qu’elles s’arrêtent parfois brusquement lorsque des travaux sont en cours sur leur chemin. Par prudence sans doute, les modèles destinés au public présentés en mai 2014 roulent à 40 kilomètres par heure au plus.

    Avec ces machines, on est loin de la méthode de conduite d’un être humain. Grâce à sa capacité à extraire de l’information des images et son intelligence générale, le conducteur humain sait piloter sur un trajet jamais emprunté, sans carte, sans radar, sans lidar, sans capteur sur les roues et il n’est pas paralysé par un obstacle inopiné !

    Les questions évoquées jusqu’ici n’exigent pas la compréhension du langage écrit ou parlé. Pourtant, contrairement aux annonces de ceux qui considéraient le langage comme une source de difficultés insurmontables pour les machines, des succès remarquables ont été obtenus dans des tâches exigeant une bonne maîtrise des langues naturelles.

    L’utilisation des robots-journalistes inquiète, car elle est devenue courante dans certaines rédactions, telles que celles du Los Angeles Times, de Forbes ou de Associated Press. Pour l’instant, ces automates-journalistes se limitent à convertir des résultats (sportifs ou économiques, par exemple) en courts articles.

    Il n’empêche que, parfois, on leur doit d’utiles traitements. Ainsi, le 17 mars 2014, un tremblement de terre de magnitude 4,7 se produisit à 6h25 au large de la Californie. Trois minutes après, un petit article d’une vingtaine de lignes était automatiquement publié sur le site du Los Angeles Times, donnant des informations sur l’événement : lieu de l’épicentre, magnitude, heure, comparaison avec d’autres secousses récentes. L’article exploitait des données brutes fournies par le US-Geological Survey Earthquake Notification Service et résultait d’un algorithme dû à Ken Schwencke, un journaliste programmeur. D’après lui, ces méthodes ne conduiraient à la suppression d’aucun emploi, mais rendraient au contraire le travail des journalistes plus intéressant. Il est vrai que ces programmes sont pour l’instant confinés à la rédaction d’articles brefs exploitant des données factuelles faciles à traduire en petits textes, qu’un humain ne rédigerait sans doute pas mieux.

    Un autre exemple inattendu de rédaction automatique d’articles concerne les encyclopédies Wikipedia en suédois et en filipino, l’une des deux langues officielles aux Philippines (l’autre est l’anglais). Le programme Lsjbot mis au point par Sverker Johansson a en effet créé plus de deux millions d’articles de l’encyclopédie collaborative et est capable d’en produire 10 000 par jour. Ces pages engendrées automatiquement concernent des animaux ou des villes et proviennent de la traduction, dans le format imposé par Wikipedia, d’informations disponibles dans des bases de données déjà informatisées.

    L’exploit a été salué, mais aussi critiqué. Pour se justifier, S. Johansson indique que ces pages peu créatives sont utiles et fait remarquer que le choix des articles de l’encyclopédie Wikipedia est biaisé : il reflète essentiellement les intérêts des jeunes blancs, de sexe masculin et amateurs de technologies. Ainsi, le Wikipedia suédois comporte 150 articles sur les personnages du Seigneur des Anneaux et seulement une dizaine sur des personnes réelles liées à la guerre du Vietnam : « Est-ce vraiment le bon équilibre ? », demande-t-il.

    S. Johansson projette de créer une page par espèce animale recensée, ce qui ne semble pas stupide. Pour lui, ces méthodes doivent être généralisées, mais il pense que Wikipedia a besoin aussi de rédacteurs qui écrivent de façon plus littéraire que Lsjbot et soient capables d’exprimer des sentiments, « ce que ce programme ne sera jamais capable de faire ».

    Beaucoup plus complexe et méritant mieux l’utilisation de l’expression « intelligence artificielle » est le succès du programme Watson d’IBM au jeu télévisé Jeopardy ! (voir l’encadré).

    Watson, le programme conçu par IBM a gagné au jeu Jeopardy ! contre deux
    champions humains. © IBM / Sony Pictures.

    La mise au point de programmes résolvant les mots-croisés aussi bien que les meilleurs humains confirme que l’intelligence artificielle réussit à développer des systèmes aux étonnantes performances linguistiques et oblige à reconnaître qu’il faut cesser de considérer que le langage est réservé aux humains. Malgré ces succès, on est loin de la perfection : pour s’en rendre compte, il suffit de se livrer à un petit jeu avec le système de traduction automatique en ligne de Google. Une phrase en français est traduite en anglais, puis retraduite en français. Parfois cela fonctionne bien, on retrouve la phrase initiale ou une phrase équivalente, mais dans certains cas, le résultat est catastrophique.

    Passer le test de Turing

    Nous sommes très loin aujourd’hui de la mise au point de dispositifs informatiques susceptibles de passer le « test de Turing » conçu en 1950. Alan Turing voulait éviter de discuter de la nature de l’intelligence et, plutôt que d’en rechercher une définition, proposait de considérer qu’on aura réussi à mettre au point des machines intelligentes lorsque leur conversation sera indiscernable de celle des humains.

    Pour tester cette indiscernabilité, il suggérait de faire dialoguer par écrit avec la machine une série de juges qui ne sauraient pas s’ils mènent leurs échanges avec un humain ou une machine tentant de se faire passer pour tel. Lorsque les juges ne pourront plus faire mieux que répondre au hasard pour indiquer qu’ils ont eu affaire à un humain ou une machine, le test sera passé. Concrètement, faire passer le test de Turing à un système informatique S consiste à réunir un grand nombre de juges, à les faire dialoguer aussi longtemps qu’ils le souhaitent avec des interlocuteurs choisis pour être une fois sur deux un humain et une fois sur deux le système S ; les experts indiquent, quand ils le souhaitent, s’ils pensent avoir échangé avec un humain ou une machine. Si l’ensemble des experts ne fait pas mieux que le hasard, donc se trompe dans 50 % des cas ou plus, alors le système S a passé le test de Turing.

    Turing, optimiste, pronostiqua qu’on obtiendrait une réussite partielle au test en l’an 2000, les experts dialoguant cinq minutes et prenant la machine pour un humain dans 30 % des cas au moins. Turing avait, en gros, vu juste : depuis quelques années, la version partielle du test a été passée, sans qu’on puisse prévoir quand sera passé le test complet, sur lequel Turing restait muet.

    Le test partiel a, par exemple, été passé le 6 septembre 2011 à Guwahati, en Inde, par le programme Cleverbot créé par l’informaticien britannique Rollo Carpenter. Quelque 30 juges dialoguèrent pendant quatre minutes avec un interlocuteur inconnu qui était dans la moitié des cas un humain et dans l’autre moitié des cas le programme Cleverbot. Les juges et les membres de l’assistance (1 334 votes) ont considéré le programme comme humain dans 59,3 % des cas. Notons que les humains ne furent considérés comme tels que par 63,3 % des votes.

    Plus récemment, le 9 juin 2014 à la Royal Society de Londres, un test organisé à l’occasion du soixantième anniversaire de la mort de Turing permit à un programme nommé Eugene Goostman de duper 10 des 30 juges réunis (33 % d’erreur). Victimes de la présentation biaisée que donnèrent les organisateurs de ce succès, somme toute assez modeste, de nombreux articles de presse dans le monde entier parlèrent d’un événement historique, comme si le test complet d’indiscernabilité homme-machine avait été réussi. Ce n’était pas du tout le cas, puisque le test avait d’ailleurs encore été affaibli : l’humain que le système informatique simulait était censé n’avoir que 13 ans et ne pas écrire convenablement l’anglais (car d’origine ukrainienne !).

    Le test de Turing n’est pas passé

    Non, le test de Turing n’a pas été passé, et il n’est sans doute pas près de l’être. Il n’est d’ailleurs pas certain que les tests partiels fassent avancer vers la réussite au test complet. En effet, les méthodes utilisées pour tromper brièvement les juges sont fondées sur le stockage d’une multitude de réponses préenregistrées (correspondant à des questions qu’on sait que les juges posent), associées à quelques systèmes d’analyse grammaticale pour formuler des phrases reprenant les termes des questions des juges et donnant l’illusion d’une certaine compréhension. Quand ces systèmes ne savent plus quoi faire, ils ne répondent pas et posent une question. À un journaliste qui lui demandait comment il se sentait après sa victoire, le programme Eugene Goostman de juin 2014 répondit : « Quelle question stupide vous posez, pouvez-vous me dire qui vous êtes ? »

    Ainsi, l’intelligence artificielle réussit aujourd’hui assez brillamment à égaler l’humain pour des tâches spécialisées (y compris celles exigeant une certaine maîtrise du langage), ce qui parfois étonne et doit être reconnu comme des succès d’une discipline qui avance régulièrement. Cependant, elle le fait sans vraiment améliorer la compréhension qu’on a de l’intelligence humaine, qu’elle ne copie quasiment jamais ; cela a en particulier comme conséquence qu’elle n’est pas sur le point de proposer des systèmes disposant vraiment d’une intelligence générale, chose nécessaire pour passer le difficile test de Turing qui reste hors de portée aujourd’hui (si on ne le confond pas avec ses versions partielles !).

    Vers l’intelligence générale

    Ces tentatives éclairent les recherches tentant de saisir ce qu’est une intelligence générale. Ces travaux sont parfois abstraits, voire mathématiques, mais n’est-ce pas le meilleur moyen d’accéder à une notion absolue, indépendante de l’homme ?

    Quand on tente de formuler une définition générale de l’intelligence, vient assez naturellement à l’esprit l’idée qu’être intelligent, c’est repérer des régularités, des structures dans les données dont on dispose, quelle qu’en soit leur nature, ce qui permet de s’y adapter et de tirer le maximum d’avantages de la situation évolutive dans laquelle on se trouve. L’identification des régularités, on le sait par ailleurs, permet de compresser des données et de prédire avec succès les données suivantes qu’on recevra.

    Intelligence, compression et prédiction sont liées. Si, par exemple, on vous communique les données 4, 6, 9, 10, 14, 15, 21, 22, 25, 26 et que vous en reconnaissez la structure, vous pourrez les compresser en « les dix premiers produits de deux nombres premiers » et deviner ce qui va venir : 33, 34, 35, 38, 39, 46, 49, 51, 55, 57…

    Ce lien entre intelligence, compression et prédiction a été exprimé de façon formelle par l’informaticien américain Ray Solomonoff vers 1965. Du principe du rasoir d’Ockham Pluralitas non est ponenda sine necessitate (les multiples ne doivent pas être utilisés sans nécessité), il proposait une version moderne : « Entre toutes les explications compatibles avec les observations, la plus concise, ou encore la mieux compressée, est la plus probable. »

    Si l’on dispose d’une mesure de concision permettant de comparer les théories, cette dernière version devient un critère mathématique. La théorie algorithmique de l’information de Kolmogorov, qui propose de mesurer la complexité (et donc la simplicité) de tout objet numérique (une théorie le devient une fois entièrement décrite) par la taille du plus court programme qui l’engendre, donne cette mesure de concision et rend donc possible la mathématisation complète du principe de parcimonie d’Ockham.

    L’aboutissement de cette voie de réflexion et de mathématisation a été la théorie générale de l’intelligence développée par l’informaticien allemand Marcus Hutter, dont le livre Universal Artificial Intelligence, publié en 2005, est devenu une référence. En utilisant la notion mathématique de concision, une notion mathématisée d’environnement (ce qui produit les données desquelles un système intelligent doit tenter de tirer quelque chose) et le principe mathématisé d’Ockham de Solomonoff, M. Hutter définit une mesure mathématique universelle d’intelligence. Elle est obtenue comme la réussite moyenne d’une stratégie dans l’ensemble des environnements envisageables.

    Cette dernière notion (dont nous ne formulons pas ici la version définitive avec tous ses détails techniques) est trop abstraite pour être utilisable directement dans des applications. Cependant, elle permet le développement mathématique d’une théorie de l’intelligence et fournit des pistes pour comparer sur une même base abstraite, non anthropocentrée et objective, toutes sortes d’intelligences. Contrairement à l’idée de H. Gardner, cette voie de recherche soutient que l’intelligence est unique, qu’on peut dépasser le côté arbitraire des tests d’intelligence habituels pour classer sur une même échelle tous les êtres vivants ou mécaniques susceptibles d’avoir un peu d’intelligence.

    Intelligence et compression

    © photology1971 – Fotolia

    Malgré la difficulté à mettre en œuvre pratiquement la théorie (par exemple pour concevoir de meilleurs tests d’intelligence ou des tests s’appliquant aux humains comme aux dispositifs informatiques), on a sans doute franchi un pas important avec cette théorisation complète. Conscients de son importance pour la réussite du projet de l’intelligence artificielle, les chercheurs ont maintenant créé un domaine de recherche particulier sur ce thème de « l’intelligence artificielle générale » qui dispose de sa propre revue spécialisée, le Journal of General Artificial Intelligence (en accès libre).

    Dans le but sans doute d’éviter à la discipline de se satisfaire du développement de sa partie mathématique, un concours informatique a été créé par M. Hutter en 2006. Il est fondé sur l’idée que plus on peut compresser, plus on est intelligent (voir l’encadré).

    La nouvelle discipline aidera peut-être les chercheurs à réaliser cette intelligence générale qui manque tant à nos machines actuelles et les oblige à n’aborder que des tâches spécialisées, le plus souvent en contournant les difficultés qu’il y aurait à employer les mêmes méthodes que les humains, qui eux disposent — au moins de façon rudimentaire ! — de cette intelligence générale.

    Jean-Paul Delahaye, Professeur émérite d’informatique à l’Université des Sciences et Technologies de Lille

    Pour aller plus loin :

    • B. GOERTZEL, Artificial general intelligence : Concept, state of the art, and future prospects, in J. of Artificial General Intelligence, vol. 5(1), pp. 1-48, 2014.
    • G. TESAURO et al., Analysis of Watson’s strategies for playing Jeopardy !, 2014.
    • D. DOWE et J. HERNÀNDEZ-ORALLO, How universal can an intelligence test be, in Adaptive Behavior, vol. 22(1), pp. 51-69, 2014.
    • Le concours de compression de Marcus Hutter

  • La Différentiation Algorithmique ou un éloge de la paresse.

    Exemple Differencation automatique Atlantique
    Influence annuelle de la température sur la circulation océanique autour du 29eme parallèle. Calculer les variations liées à ce modèle est un défi, dont on va parler ici. ©Consortium NEMO / CNRS

    La Différentiation Algorithmique est une technique informatique destinée au monde du calcul scientifique.  La … quoi ? Et bien restez avec nous quelques lignes, Laurent Hascoet, va soulever le capot d’un outil méconnu des sciences et techniques informatiques, qui change pourtant complètement l’ingénierie.
    Sylvie Boldo.

     

    Oh oh j’ai de belles équations. Prenons une personne spécialiste du calcul scientifique, qui vient de choisir avec soin les équations mathématiques qui modélisent précisément le système qu’elle étudie, puis d’écrire un programme (l’algorithme) qui résout ces équations. Elle est fière d’elle-même, et elle a bien raison, car à l’issue de cet énorme travail, elle a une description quantitative de ce qu’elle doit étudier, développer ou améliorer.
    Elle dispose en fait d’un simulateur, c’est à dire d’une boîte munie d’un grand nombre de petits leviers (des paramètres) qui, pour chaque réglage des leviers, calcule l’état résultant du système étudié.

    Exemple Differencation automatique SonicBoom
    Gradient (voir texte) calculé avec le logiciel Tapenade, du bang sonique au sol par rapport à la forme de l’avion. Le calcul montre que pour réduire le bang, il faut tirer la « peau » vers l’extérieur par endroit (zone rouges) et l’enfoncer ailleurs (zones bleues). © Dassault aviation / INRIA

    Euh : Par exemple ? Eh bien, par exemple, pour étudier les performances d’un bateau, d’un avion ou d’un moteur à partir de leur géométrie, ce simulateur est bien plus rapide et plus économique que de construire réellement l’objet puis de le tester. Autre exemple : la simulation de l’évolution de l’atmosphère et de l’océan à partir de leur état actuel, pour dans cinq jours ou pour dans cent ans.

    Toujours plus ! Ce simulateur est tellement commode que le spécialiste veut maintenant aller plus loin, et chercher le réglage des leviers qui produit le meilleur état possible, ou en tout cas le plus proche d’un état cible prédéfini.La meilleure forme d’avion, par exemple, ou ce qu’il faudrait faire au niveau planétaire pour infléchir le réchauffement climatique.
    Problème difficile car les leviers sont nombreux, ils ont des tas de positions possibles, et les essayer toutes prendrait un temps colossal.

    La dérivée ou différentielle ? C’est le calcul de la variation locale d’une fonction (ici la droite bleue donne la direction de variation de la courbe rouge); cela permet de savoir par exemple dans quel direction trouver le minimum de cette fonction. ©wikimedia.org

    Le retour des maths. Heureusement en calcul scientifique la plupart des problèmes sont « différentiables ». Cela veut dire qu’il existe une opération mathématique (la différentiation) qui donne, à partir des équations, de nouvelles équations pour les « tendances » du système (on dit aussi son gradient).
    Pas à pas, en suivant ce gradient et en le recalculant à chaque pas, on avance sur la ligne de plus grande pente jusqu’à atteindre un optimum (local).
    Grâce à ce gradient tout est plus rapide, puisqu’il dit dans quel sens bouger chaque levier pour se rapprocher de l’état cible. On peut atteindre la position optimale des leviers en quelques pas seulement. Les domaines d’application sont immenses : ingénierie, aéronautique, climatologie, biologie ou même économie.

    Exemple Differencation automatique Sbend1

    Exemple Differencation automatique Sbend3 Écoulement perturbé par son passage dans un tuyau coudé. On calcule automatiquement le gradient (voir texte) de la perte de pression sur la paroi du tuyau, avec le logiciel Tapenade. ©Queen Mary University of London

    Tout ça c’est bien joli, mais … ! Notre spécialiste vient de travailler des mois à choisir ses équations puis à écrire le programme qui les résout, pour découvrir maintenant qu’il faut écrire les équations différentiées pour le gradient puis écrire le nouveau programme qui les résout. Écrire les équations du gradient, passe encore, mais le programme pour les résoudre sera drôlement dur à écrire. Ce gradient est une chose plutôt abstraite et on pourra moins s’aider de son intuition. Et si on se trompe (et on se trompe toujours au moins une fois), comment aller chercher le bug dans tout ce fatras de calculs ?
    Avouez qu’il y a de quoi hésiter un peu!

    Pourrait-on être plus astucieux ?  C’est là qu’intervient la Différentiation Algorithmique. Après tout, l’algorithme du simulateur lui-même est « presque » équivalent aux équations mathématiques qu’il résout (pour ceux qui veulent le détail: la grosse différence est qu’il « discrétise » en échantillonant l’espace et le temps; tout ça cause de légères approximations, et on peut vivre avec). Bref, les équations mathématiques et l’algorithme informatique sont presques interchangeables.
    Certes l’algorithme est bien moins élégant, moins concis, mais il aboutit au même résultat à l’issue d’une longue chaîne de milliards d’opérations élémentaires (additions, multiplications, divisions…). Et comme on sait écrire le gradient d’une telle chaîne de fonctions élémentaires, il suffit d’appliquer mécaniquement la recette. Souvenez-vous. C’était au lycée, on parlait de la dérivée de «f rond g». On peut donc transformer directement l’algorithme du simulateur en un nouvel algorithme qui calcule son gradient. C’est la Différentiation Algorithmique (DA).

    grace-hopper
    De même que Grace Hopper a bouleversé l’informatique en permettant de coder les programmes non pas en binaire mais avec des instructions lisibles par des humains, un compilateur se chargeant de la traduction, la DA permet de traduire automatiquement un programme informatique en un autre. © Vassal College

    Et c’est là que l’informatique vient à la rescousse. On y est presque. Si l’algorithme du simulateur est court, on peut écrire à la main l’algorithme de son gradient. Il faut cependant être rigoureux et systématique car c’est une transformation lourde, en particulier parce que le gradient se calcule « en marche arrière » de l’algorithme du simulateur.
    Mais le code du simulateur se mesure plutôt en milliers de lignes et il est quasiment impossible de le transformer  sans se tromper. Voie sans issue ? Non, parce qu’une grande force de l’informatique est qu’on peut écrire des programmes qui travaillent sur presque tout, y compris d’autres programmes. Un peu comme les compilateurs qui transforment un code informatique en langage machine.
    Puisque la DA est complètement mécanique, laissons le travail à l’ordinateur. L’outil de DA va analyser l’algorithme source et produire l’algorithme gradient, en quelques secondes pour un code de plusieurs milliers de lignes. Cerise sur le gâteau l’outil de DA, tout comme un compilateur, emploie des analyses sophistiquées pour optimiser le gradient, pour le rendre plus rapide et moins gourmand en mémoire.

    Tapenade www-tapenade.inria.fr un système de DA …©TROPICS-Inria

    Du laboratoire de recherche au monde industriel. Depuis plusieurs années, une équipe d’Inria étudie la DA et développe Tapenade, un outil de DA. Même si cet outil sert surtout à tester les nouvelles méthodes pour rester en pointe dans la recherche, il a aussi un joli succès auprès d’utilisateurs industriels qui ont acquis une licence pour l’utiliser dans leur chaîne de développement. On y retrouve l’aéronautique avec Dassault Aviation, Rolls-Royce ou Boeing, la chimie avec BASF ou Cargill, le pétrole avec Total ou Exxon-Mobil, mais aussi quelques banques et institutions financières. Parallèlement, de nombreux centres académiques l’utilisent gratuitement pour leurs recherches, et un serveur web permet de l’utiliser directement sans installation.

    Laurent Hascoet.

  • La fouille de données et de texte au service des sciences

    Cet article est publié en collaboration avec The Conversation

    La société se trouve à la croisée des chemins. Aller vers des données ouvertes ou contractualiser ad nauseam. Le sujet a une importance considérable pour les chercheurs, mais aussi pour l’industrie. Binaire a demandé à un ami d’Inria, Florent Masseglia,  de nous éclairer sur les enjeux. Serge Abiteboul.

    Florent Masseglia © Inria / Photo H. Raguet
    Florent Masseglia © Inria / Photo H. Raguet

    Pour les chercheurs, accéder aux publications de leurs pairs est une nécessité quotidienne. Mais avec l’accélération constante de la production d’écrits scientifiques arrivent deux constats :

    • Il peut devenir humainement difficile de faire le tri, manuellement, dans l’ensemble de la production scientifique.
    • Les machines pourraient faire sur ces écrits ce qu’elles font déjà très bien sur le big data : transformer les données en valeur.

    Pour un acteur industriel, la valeur extraite à partir des données peut-être commerciale. C’est ce que le business a très bien compris, avec des géants du Web qui font fortune en valorisant des données (par exemple, en créant des profils utilisateurs pour vendre de la publicité ou des services). Mais valoriser des données ce n’est pas obligatoirement en tirer un profit commercial. Cette valorisation peut se traduire dans l’éducation, dans les sciences, dans la société, etc. C’est exactement ce que le TDM (Text and Data Mining, la fouille de textes et de données) peut faire quand il est appliqué aux données de la recherche : créer de la valeur scientifique.

    Pour expliquer cela, j’aimerais introduire rapidement les notions de données et d’information. J’emprunte ici l’introduction de l’excellent article sur « les données en question », de Patrick Valduriez et Stéphane Grumbach  : « Une donnée est la description élémentaire d’une réalité ou d’un fait, comme par exemple un relevé de température, la note d’un élève à un examen, l’état d’un compte, un message, une photo, une transaction, etc. Une donnée peut donc être très simple et, prise isolément, peu utile. Mais le recoupement avec d’autres données devient très intéressant. Par exemple, une liste de températures pour une région donnée sur une longue période peut nous renseigner sur le réchauffement climatique. »

    La température à un instant précis est donc une donnée. L’évolution de cette température dans le temps peut apporter une information.

    Le data mining, ou la fouille de données, c’est l’ensemble des méthodes et des algorithmes qui vont permettre à ces données de nous parler. La fouille de données peut nous révéler des informations que l’on n’aurait peut-être jamais soupçonnées et que l’on ne pourrait pas obtenir en explorant ces données « à la main ». Des informations utiles et qui auront un impact sur nos décisions. Et plus la quantité d’information est grande, plus la crédibilité des informations découvertes est renforcée.

    noun_406774_ccPour découvrir ces informations nouvelles, chaque algorithme fonctionne comme un engrenage. Et dans l’engrenage d’un algorithme de fouille de données, les pièces (les roues dentées) vont s’imbriquer et se mettre en mouvement. Elles vont dialoguer entre elles. Chaque pièce, chaque roue dentée, va jouer un rôle précis en travaillant sur une source de données particulière. On peut ainsi fabriquer un engrenage à chaque fois qu’on veut découvrir des informations dans les données.

    Si vous voulez découvrir une éventuelle relation entre la météo et la fréquentation des médiathèques, vous pouvez fabriquer un engrenage qui utilisera deux roues. Une roue pour travailler sur les données de la météo des dernières années. Et une autre qui travaillera sur les données de fréquentation des médiathèques. Si ces données sont accessibles, que vous connaissez leur format et leur emplacement, alors il ne reste plus qu’à fabriquer les roues de l’engrenage et les assembler !

    Mais vous pouvez aller encore plus loin. Par exemple, si vous ne savez pas encore quelle information sera révélée mais vous pensez qu’elle se trouve quelque part entre la météo, la fréquentation des médiathèques, et le budget que ces dernières allouent aux activités pour la jeunesse. Est-ce la météo qui influence la fréquentation ? Ou plutôt le budget ? Ou bien les deux ? Et c’est là tout l’intérêt de la fouille de données. On ne sait pas, à l’avance, ce que les algorithmes vont nous permettre de découvrir. On ne sait pas quelles sources de données seront les plus impliquées dans l’information à découvrir. Alors on croise des données, et on met les engrenages en place. Plus on utilise de sources de données différentes et plus on peut découvrir des informations qui étaient peut-être au départ insoupçonnables !

    L’open-access, ça change quoi pour le TDM ?

    noun_22108_ccLes données de la recherche (publications, projets, données d’expérimentations, etc.) sont un véritablement gisement pour les algorithmes de fouille de données. Pour expliquer cela, fabriquons ensemble un engrenage qui fonctionne sur ces données pour découvrir de nouvelles informations dans un domaine scientifique comme, par exemple, l’agronomie. Nous voulons savoir s’il y a des facteurs qui favorisent l’apparition d’un bio-agresseur. Nous aimerions utiliser des données concernant les champs (pour chaque champ : le type de culture, la hauteur de haie, type de faunes, bosquets, etc.) mais nous voudrions aussi utiliser des données concernant l’environnement (la météo, les zones humides, etc.) et enfin nous allons utiliser des études scientifiques existantes sur les bio-agresseurs (comme leur localisation, périodes d’apparitions, etc.). En utilisant l’ensemble de ces données, à très grande échelle, nous espérons découvrir un ensemble de facteurs souvent associés à la présence de ces bio-agresseurs, ce qui permettra de mieux lutter contre ces derniers.

    La bonne nouvelle, c’est que toutes ces données existent ! Et les algorithmes, eux aussi, existent… Cependant, le monde de la recherche française se trouve face à deux voies.

    Dans la première voie, toutes ces données sont accessibles facilement. Les données concernant les champs et leur environnement sont publiques. Les données concernant les articles scientifiques le sont, au moins, pour la communauté académique. C’est la voie de l’open-access.

    Dans la deuxième voie, toutes les données ne sont pas accessibles librement. On peut avoir accès aux données concernant les champs car elles sont toujours publiques, mais pour les autres c’est plus difficile. Par exemple, les articles scientifiques sont la propriété des éditeurs. Ou encore, les données d’expérimentations sont sur des ordinateurs de différents chercheurs et ne sont pas rendues publiques. Pour y accéder, il faut passer par des filtres, mis en place par les ayants-droit selon leurs conditions. C’est la voie de la contractualisation du TDM.

    En avril 2016, la France doit faire un choix entre ces deux voies. Le sénat étudie le projet de loi pour « une république numérique ». C’est la souveraineté scientifique de la France qui est en balance dans ce débat.

    Avec l’open-access pour le TDM, vous pouvez regarder librement le format de toutes les données. Vous pouvez les lire, les copier, les transformer, etc. Vous pouvez fabriquer vos propres roues dentées pour qu’elles travaillent sur ces données. Et vous pouvez donc fabriquer vos propres engrenages. Sans limite. Sans condition, autre que l’éthique scientifique.

    Graphe de données du moteur de recherche exploratoire Discovery hub © Inria / WIMMICS
    Graphe de données du moteur de recherche exploratoire Discovery hub © Inria / WIMMICS

    Avec la contractualisation, ce sont les ayants-droit qui vont fabriquer les roues pour vous. Si la roue n’est pas au bon format pour votre engrenage, si elle n’est pas compatible avec ses pièces voisines, ou alors si elle vient tout simplement à manquer… Alors votre engrenage ne tournera pas. Et il n’est pas question de remplacer la roue mise en cause par une autre car les données, hébergées chez l’ayant-droit, ne sont accessibles que par cette roue et aucune autre. Cependant, si on ne peut pas fabriquer l’engrenage qui utilise toutes les données, alors on pourrait se contenter d’un engrenage plus petit, qui n’utilise que les roues fabriquées par un seul et même ayant-droit, donc compatibles entre elles. Oui, mais cet engrenage ne fonctionnerait que sur les données de ce dernier. Les nouvelles informations découvertes le seraient donc sur un sous-ensemble très restreint des données. On ne verrait alors qu’une toute petite partie de l’image globale. Cela n’aurait aucun sens. De plus, il se trouve que certains organismes de recherche traitent avec 80 éditeurs différents ! Il faudrait alors fabriquer 80 engrenages différents au lieu d’un seul ? Le pire c’est que, utilisés tous ensemble, ces 80 engrenages n’arriveraient pas à la cheville de l’engrenage global fabriqué pour l’ensemble des données. Tout simplement parce que l’engrenage global peut croiser toutes les données alors que ces 80 engrenages différents, avec chacun des roues différentes, ne peuvent pas le faire. Ils n’ont accès qu’à un sous-ensemble des données et dans leur cas l’union ne fait pas la force… Ils ne peuvent pas s’échanger les données entre eux pour les croiser. Ainsi, pour lutter contre nos bio-agresseurs, mais aussi de manière générale pour extraire de nouvelles informations et découvrir des connaissances dans tous les domaines scientifiques, la recherche française doit pouvoir utiliser le tandem TDM & open access !

    Effectivement, dans le cas de l’open-access, ce serait radicalement différent. Puisque les données seraient accessibles facilement, il deviendrait tout à fait possible pour notre engrenage de trouver, par exemple, des liens entre quelques variables qui concernent les champs, d’autres variables sur l’environnement, et encore avec d’autres variables issues d’articles scientifiques sur les bio-agresseurs. Et les informations découvertes auraient alors une sorte de force statistique bien plus grande. Elles seraient validées par le fait que l’on travaille sur l’ensemble des données. Sans restriction.

    Grâce au droit d’exploiter les données de la recherche en open-access avec des outils de TDM complets, la recherche française disposera, comme ses concurrentes anglaises, japonaises, américaines ou allemandes, d’une vue d’ensemble sur les données, dont elle manque aujourd’hui. Et ce n’est pas un problème de technologie. La technologie est disponible. Elle fonctionne très bien dans d’autres domaines et elle est largement prometteuse pour les données scientifiques ! Si on leur donnait accès aux données de la recherche, les engrenages de la fouille de données fonctionneraient certainement à plein régime pour révéler des informations qui seraient peut-être surprenantes, ou qui pourraient confirmer des théories. Mais cela ne pourrait aller que dans une seule direction : encore plus de découvertes scientifiques.

     Florent Masseglia, Inria

  • Hyperviseur, même pas peur !

    Dans le cadre d’une nouvelle rubrique « Il était une fois… ma thèse », Binaire a demandé à Pauline Bolignano, qui effectue sa thèse à Inria Rennes Bretagne Atlantique et dans la société Prove & Run de nous présenter ses travaux. Par ailleurs, Binaire tient à remercier Pauline et Charlotte qui en discutant ont initié l’idée de cette rubrique. Nous attendons impatiemment la suite des autres histoires de thèses… Binaire.

    PaulineBolignano« – Tu penses que c’est possible que quelqu’un pirate ton portable et écoute tes conversations, ou accède à tes données bancaires ?

    – Non ça n’arrive que dans les séries ça ! Et puis moi de toute façon je ne télécharge que des applis de confiance…»

    En fait, avec en moyenne 25 applications installées sur un téléphone, nous ne sommes pas à l’abri d’un bug dans l’une d’entre elles.

    Il y a même fort à parier que nos applications contiennent toutes plusieurs bugs. Or, certains bugs permettent à une personne mal intentionnée, sachant l’exploiter, d’accéder à des ressources privées. Ce problème est d’autant plus préoccupant que de plus en plus de données sensibles transitent sur nos téléphones et peuvent interférer entre elles. C’est encore pire quand les téléphones servent à la fois pour un usage personnel et professionnel !

    Actuellement, l’accès aux ressources (appareil photo, micro, répertoire et agendas,…) dans un smartphone se fait un peu comme dans un bac à sable : toutes les applications peuvent prendre le seau et la pelle des autres, et rien n’empêche une application de détruire le château d’une autre… L’angoisse !

    Pour mettre de l ‘ordre dans tout ça, une solution est d’ajouter une couche de logiciel qui contrôle de manière précise l’accès aux ressources, une sorte de super superviseur ; d’ailleurs, on appelle ça un hyperviseur. L’hyperviseur permet par exemple d’avoir deux « bacs à sable » sur son téléphone, de telle manière qu’aucune information sensible ne fuite entre les deux. Cela n’empêche pas les occupants d’un même bac à sable de se taper dessus avec des pelles mais on a la garantie que cela n’a pas d’impact sur le bac d’à coté. L’hyperviseur peut également interdire aux applications l’accès direct aux ressources. Il autorise les occupants du bac à sable de faire un pâté mais c’est lui qui tient le seau. Il peut de cette manière imposer qu’un voyant lumineux s’allume lorsque le micro est en marche. On a ainsi la certitude que lorsque le voyant est éteint, le micro est éteint et que personne ne peut nous écouter.

    Vous l’avez peut être remarqué, il nous reste un problème majeur : comment s’assurer que l’hyperviseur n’a pas de bug ? L’hyperviseur ayant accès à toutes les ressources, un bug chez lui peut avoir des conséquences très graves. Il devient donc une cible de choix pour des pirates. Si on se contente de le tester, on passe potentiellement à coté de nombreux bugs. En effet la complexité d’un hyperviseur est telle que les tests ne peuvent pas prévoir tous les cas d’usage. La seule solution qui permette de s’approcher  de l’absence de bug est la preuve formelle de programme. L’idée est d’exprimer des propriétés sur le programme, par exemple « les occupants d’un bac à sable n’interfèrent pas avec les occupants d’un autre bac à sable », puis de les prouver mathématiquement. Les propriétés sont exprimées dans un langage informatique et on les prouve grâce un outil qui vérifie que nos preuves sont correctes (et qui parfois même fait les preuves à notre place !).

    Actuellement la preuve de programme n’est pas très répandue car elle est très couteuse et longue à mener. Elle est réservée aux systèmes critiques. Par exemple, des propriétés formelles ont été prouvées sur les lignes automatiques (1 et 14) du métro parisien. Je prouve en ce moment des propriétés d’isolation sur la ressource « mémoire » d’un hyperviseur, c’est à dire qu’il n’y a pas de mélange de sable entre deux bacs à sable. Le but de ma thèse est de fournir des méthodes afin d’alléger l’effort de preuve sur ce type de systèmes.

    Pauline Bolignano, Inria Rennes Bretagne Atlantique et Prove & Run.

     

  • Disparition d’un pionnier des langages de programmation

    Le langage Algol 60 a été un des premiers langages de programmation, et a eu une importance considérable. Peter Naur a été un de ces concepteurs.  À l’occasion de son décès, Binaire a demandé à deux amis de revenir sur la contribution de Peter Naur à l’informatique. Une note biographique a été préparée par Pierre Mounier Kuhn historien des sciences. Sacha Krakowiak qui vient d’être nommé membre d’honneur de la Société Informatique de France nous parle de l’influence de Peter Naur et d’Algol sur la pensée informatique à travers des souvenirs et anecdotes. Pierre Paradinas

    Le Danois Peter Naur laisse son nom à la Backus-Naur Form, l’une de ses principales contributions à l’élaboration du langage Algol 60 et à l’étude des langages de programmation. Il reçut le prix Turing en 2005 : « for fundamental contributions to programming language design and the definition of Algol 60, to compiler design, and to the art and practice of computer programming ».

    Peu convaincu de l’existence d’une computer science, il a enseigné une discipline qu’il nommait datalogie.

    Né en 1928, Peter Naur étudia l’astronomie à l’université de Copenhague et devint assistant à l’observatoire. Un séjour à Cambridge en 1950-1951 lui permit de mener des recherches dans deux domaines qui émergeaient dans les années 1950 : la radioastronomie et la programmation d’ordinateurs (rappelons que l’équipe de Maurice Wilkes à Cambridge a publié le premier traité de programmation en 1951). Naur fait partie de cette première génération d’informaticiens qui provenaient de disciplines préexistantes, et où certains astronomes jouèrent un rôle moteur. L’astronomie le conduisit aux États-Unis, où il rencontra notamment Howard Aiken à Harvard et John von Neumann à Princeton – respectivement le dernier représentant de la filière des calculateurs programmables inspirée par Babbage et l’inventeur du concept d’ordinateur à programme enregistré.

    Rentré au Danemark, Peter Naur rejoignit à Copenhague le centre de calcul Regnecentralen, participant à la conception et à la programmation du premier ordinateur danois, Dask. Il s’intégra alors au comité international de chercheurs qui développaient un nouveau langage de programmation, bientôt baptisé Algol 60. Se passionnant pour ce projet, il devint le principal auteur du rapport décrivant ce langage – rapport présenté en 1959 au premier congrès mondial de traitement de l’information, tenu à Paris sous les auspices de l’Unesco. C’est lui qui prit la décision, vivement discutée alors, d’y inclure les procédures récursives. Collaborant avec John Backus, l’inventeur de Fortran chez IBM, il y introduisit également un procédé de notation formelle, connu depuis sous le nom de Backus-Naur Form (BNF). La BNF permettait de définir rigoureusement la syntaxe des langage de programmation et, au-delà, de les étudier et de les enseigner d’une manière formalisée.

    Dans la décennie suivante, tout en dirigeant l’Algol Bulletin et le journal scandinave BIT, Peter Naur contribua à établir l’informatique comme discipline académique au Danemark. En 1966, il inventa un mot pour la nommer : datalogie. Cette « science des données » est d’abord une réaction contre le terme computer science ; elle est plus proche de l’informatique, définie en France par un autre astronome, Jacques Arsac, comme la science des structures d’information. Naur, tout en enseignant les fondements de l’informatique, incitait vivement ses étudiants à travailler sur ses applications dans d’autres domaines. En 1969 il fut nommé professeur à l’Institut de Datalogie à l’université de Copenhague, où il passa toute la suite de sa carrière jusqu’à sa retraite en 1999, à 70 ans.

    Son insistance à distinguer sa datalogie de la computer science l’amena en 1970 à s’opposer vigoureusement à la doctrine de Programmation Structurée promue par Edsger Dijkstra et Niklaus Wirth. Tandis que ceux-ci prêchaient comment l’on devrait idéalement programmer, Naur mena des enquêtes empiriques pour observer comment l’on pratiquait la programmation[1].

    Après sa retraite, ses préoccupations se déplacèrent vers des problèmes de philosophie et de psychologie. Il exposa ses réflexions dans un article, « A Synapse-State Theory of Mental Life » (2004). Puis dans une conférence à l’ACM Turing Lecture, « Computing vs. Human Thinking »[2], concluant que « le système nerveux n’a aucune similitude avec un ordinateur ». Et que le test de Turing est à rejeter.

    Naur était profondément convaincu que le travail descriptif est au cœur de la science, beaucoup plus que la recherche des « causes ».

    [1] P. Naur, Concise Survey of Computer Methods, 1974.
    [2] http://amturing.acm.org/vp/naur_1024454.cfm ou https://www.youtube.com/watch?v=mYivRwrATTA

    Pour en savoir plus :

    Sacha Krakowiak nous parle de Peter NaurBinaire : Sacha, peux-tu nous dire comment tu as rencontré Peter Naur ?
    Sacha : En juillet 1962, je prenais mes fonctions au Bassin d’Essai des Carènes de la Marine Nationale, où j’étais chargé d’études sur des problèmes d’hydrodynamique. Quelques mois plus tard, arrivait un ordinateur Gier (construit par la société danoise Regnecentralen). Pourquoi cette machine ? Simplement parce que le directeur du Bassin, à l’époque l’ingénieur général Roger Brard, était ami de son homologue danois, qui avait lui même acquis cette machine; ils comptaient ainsi échanger des programmes d’application (ce qui fut fait). Je n’avais aucune notion d’informatique, mais je suis allé voir la machine par curiosité, et j’ai demandé comment s’en servir. On m’a alors donné un petit fascicule gris, d’allure rébarbative, intitulé « Revised Report on the Algorithmic Language Algol 60 », réalisé par Peter Naur. Je l’ai emporté chez moi et je me suis plongé dedans. Cela a été un des plus grands chocs intellectuels de ma carrière. La description du langage en BNF, et la récursivité des définitions ont été pour moi un éblouissement. Peu de temps après, j’écrivais mon premier programme. Quelques mois plus tard, j’étais responsable du service informatique du Bassin des Carènes…

    Binaire : Mais qu’est-ce qu’il y avait de si génial dans ce livre ?
    SK : Le point de départ est donc le langage de programmation, Algol 60, pour ALGOrithmic Language 1960. Peter Naur et Jørn Jensen avaient réalisé le premier compilateur du langage complet – donc un programme qui traduisait des programmes écrits en Algol 60 en code exécutable par une machine. Le Gier était équipé de ce compilateur d’Algol 60. Cette réalisation était en soi un exploit, non seulement conceptuel, mais aussi technique, car la mémoire centrale de la machine était minuscule (1000 mots de 40 bits). Il fallait 6 passes au compilateur pour transformer le programme en code exécutable. Un autre trait remarquable du Gier était son lecteur de ruban perforé, qui lisait 2000 caractères par seconde : le ruban s’échappait du lecteur à grande vitesse et était recueilli dans une corbeille placée 2 mètres plus loin ! La première passe du compilateur traitait le programme lu à la volée à cette même vitesse.

    Photo S. Krakoowiak
    Couverture du petit livre gris.Crédit Photo S. Krakowiak

    En fait, Peter Naur était venu au Bassin préparer l’arrivée de la machine, mais c’était avant ma propre arrivée, et je ne l’ai pas rencontré alors. Apparemment, il n’avait pas été impressionné par les pratiques courantes : on m’a rapporté qu’il avait parlé de «programmation de l’âge de pierre»… Il est vrai que la programmation se faisait alors principalement en assembleur.

    J’ai soigneusement gardé le petit livre gris et j’avoue qu’il m’arrive encore de m’y plonger de temps en temps. La citation de Wittgenstein qui figure en épigraphe m’avait à l’époque intrigué. En rassemblant mes bribes d’allemand scolaire, j’étais arrivé à la traduire : « Ce qui peut se dire, peut se dire clairement ; et sur ce dont on ne peut parler, il faut garder le silence ». Cette phrase s’applique parfaitement au Rapport Algol 60.

    Une page du manuel Algol 60 à propos du "si alors sinon, et du GOTO". Photo S. Krakowiak
    Une page du manuel Algol 60 à propos du « si alors sinon, et du goto ».
    Crédit Photo S. Krakowiak

    Interview réalisé par Serge Abiteboul et Pierre Paradinas

  • Jon McCormack, codeur créatif

    Cet article est publié en collaboration avec TheConversation.

    sensiLab director, Professor Jon McCormack

    Dans le cadre des « Entretiens autour de l’Informatique« , Binaire a rencontré l’artiste et chercheur Jon McCormack, grande figure du creative coding, un courant peu représenté en France qui fait de l’informatique un moyen d’expression. Non content d’avoir ses œuvres exposées dans salles les plus prestigieuses, comme le Musée d’Art Moderne de New York, Jon McCormack est professeur d’informatique à Monash University à Melbourne, et Directeur du Sensilab. Jon McCormack parle de créativité et d’ordinateurs à Charlotte Truchet, de Binaire.

    Dans votre travail, vous vous êtes souvent intéressé à des processus génératifs. Pourriez-vous nous en décrire un exemple ?

    Oui, j’ai par exemple une exposition en ce moment à Barcelone intitulée « Fifty sisters », une oeuvre créée pour le Musée Ars Electronica. Il s’agit une série de cinquante images évolutives, créées à partir d’un modèle de la croissance des plantes. A la base, j’ai choisi d’utiliser des logos de compagnies pétrolières. J’ai repris des éléments géométriques de ces logos, qui viennent nourrir le modèle de développement. Ensuite, j’utilise une grammaire, un ensemble de règles qui modélisent l’évolution d’une plante – à l’origine, cette grammaire permet de représenter la structure de plantes du Jurassique. J’utilise cette grammaire dans un processus itératif qui alterne des étapes de calcul par l’ordinateur, et des choix de ma part. D’abord, à partir des logos pétroliers, l’ordinateur calcule une premier génération de plantes en appliquant la grammaire. Cela produit plusieurs plantes, parmi lesquelles je choisis celles qui me semblent les plus étranges, ou intéressantes. Et l’on recommence. C’est donc bien l’humain qui conduit l’algorithme.

    De cette façon, les plantes sont réellement constituées d’éléments graphiques des logos. Les images finales ont des structures très complexes, et elles sont calculées à très haute définition de façon à ce que l’on puisse zoomer dans les plantes et découvrir de nouveaux détails.

    C’est un sacré travail !

    Evolved plant form based on the Shell logo, part of the the Fifty Sisters series
    Plante ayant évolué à partir du logo Shell, de la série des Fifty Sisters (crédit Jon McCormack)

    Oui, en fait la partie la plus dure a été de calculer le rendu. J’avais loué une ferme d’ordinateurs, mais au bout de 24h nous nous sommes fait jeter dehors parce que nous consommions trop de temps de calcul ! Alors, nous avons installé le programme qui calcule le rendu, petit morceau d’image par petit morceau d’image, sur tous les ordinateurs inutilisés du labo, ceux de tout le monde… C’est impressionnant car la grammaire qui sert à faire les générations est très courte, elle fait 10 lignes, et elle génère pourtant des objets extrêmement complexes.

    Comment avez-vous découvert l’informatique ?

    J’ai toujours aimé les ordinateurs, depuis l’enfance. Dans mon école, il y avait un ordinateur, un seul, c’était un TRS80 de Radioshack. Personne ne voulait l’utiliser. Je l’ai trouvé fascinant, parce qu’il faisait des calculs, et qu’il permettait de générer des choses. Le TRS80 avait des graphismes très crus, mais on pouvait faire des images avec, allumer des pixels, les éteindre… D’abord, je l’ai utilisé pour dessiner des fonctions, et puis j’ai commencé à écrire mes propres programmes : je voulais voir les fonctions en 3D. Aujourd’hui, la 3D est une technique couramment utilisée, mais ce n’était pas le cas alors ! Donc j’ai programmé une visualisation 3D. Elle n’était pas parfaite, mais elle me suffisait. C’est là que j’ai compris que l’ordinateur permettait de faire des films, de l’animation, de l’interaction. Il faut dire que c’est fascinant de construire un espace et un temps qui reflètent la réalité, même si cette réflexion n’est pas parfaite.

    Est-ce qu’il y a aujourd’hui des nouveaux langages artistiques basés sur les données numériques ou l’algorithmique ?

    C’est une question difficile. Je ne crois pas que l’ordinateur soit accepté, en soi, dans le courant dominant de l’art contemporain (« mainstream art »). Il y a des résistances. Par moment, le monde de l’art accepte l’ordinateur, puis il le rejette. Je ne pense pas que l’on puisse dire que les ordinateurs soient devenus centraux dans la pratique artistique. Mais je crois que l’informatique a ouvert des possibilités artistiques, qu’elle apporte quelque chose de réellement nouveau. C’est un peu comme le bleu. Autrefois, on ne savait pas fabriquer la couleur bleue. Dans l’histoire de l’art, la découverte du bleu a été un évènement important. C’était une question scientifique, un vrai problème technologique. Lorsque l’on a commencé à le fabriquer, le bleu était cher. Dans les peintures du début de la Renaissance, on ne l’utilisait que pour les personnes très importantes.

    Pour moi, l’ordinateur suit un chemin similaire à celui du bleu. C’est vrai dans l’art pictural mais aussi dans la musique, le cinéma, l’architecture…

     

    Fifty Sisters at the Ars Electronica Museum, April 2013
    Jon McCormack devant l’exposition Fifty Sisters au musée Ars Electronica, avril 2013 (crédit Jon McCormack)

    Pensez-vous que les artistes doivent apprendre l’informatique ?

    Je ne le formulerais pas de façon aussi stricte. Je ne dirais pas qu’ils en ont besoin, qui est un terme trop fort, mais qu’ils devraient. Au delà des artistes d’ailleurs, tout le monde devrait apprendre au moins un peu d’informatique. C’est indispensable pour comprendre le monde, au même titre que les mathématiques ou les autres sciences.  C’est important d’ajouter aux cursus la pensée algorithmique et la programmation. Et cela ouvre de nouvelles possibilités pour tout le monde, comme aucun autre medium ne le fait.

    Est-ce que le code créatif est une activité similaire à la programmation classique, ou différente ?

    Je crois que c’est juste un outil pour la créativité, car toutes les activités créatives ont été numérisées. C’est lié à ce que nous disions tout à l’heure : les gens qui travaillent dans le design, la musique ou l’architecture, utilisent l’ordinateur tout le temps, même si ce n’est que pour éditer des fichiers.

    Prenons l’exemple de Photoshop. C’est un outil fabriqué par d’excellents développeurs, qui y ont ajouté d’excellentes fonctionnalités. Mais ce sont leurs fonctionnalités. Quand on l’utilise, on n’exprime pas ses idées, mais les leurs. Et tout le monde fait la même chose ! Dès lors, la question devient : voulez-vous exprimer votre créativité, ou celle de quelqu’un d’autre ?

    Ici nous avons un projet en cours d’examen avec l’Université de Sydney pour enseigner le code créatif aux biologistes. Ils ont de gros besoins en visualisation de données statistiques, et ils utilisent en général des outils dédiés très classiques comme Excel ou le langage R. Mais l’outil a une énorme influence sur ce que l’on fait et la façon dont on perçoit les choses. Nous voulons leur apprendre à fabriquer leurs propres outils.

    Tout le monde devrait apprendre le code créatif : les ingénieurs, les biologistes, les chimistes, etc. !

    Dans le futur, quelle technologie vous ferait vraiment rêver ?

    Pour certains projets, nous avons eu ici des interfaces avec le cerveau. Pendant longtemps, la conception des ordinateurs s’est faite sans considérer le corps humain. On accordait peu d’importance au fait que nous sommes incarnés dans un corps. Regardez le clavier ! Maintenant, on a les écrans tactiles.

    La question est maintenant de concevoir des machines qui fonctionnent avec nos corps. Regardez les travaux de Stelarc sur l’obsolescence du corps humain. Il s’agit de se réapproprier la technologie. Alors que l’on voyait l’ordinateur comme un outil externe, le corps devient un outil d’interaction. C’est le même principe que la cane pour les aveugles : au début, quand on a une cane, on la voit comme un objet externe. Mais on peut l’utiliser pour tester une surface par exemple, ou pour sentir un mur. Elle devient une extension du corps. Je pense que l’on peut voir la technologie comme extension du corps humain.

    Entretien réalisé par Charlotte Truchet 

    Image of the artwork "Bloom" at Kelvin Grove Road, QUT Creative Industries Precinct.
    Photographie de l’oeuvre Bloom installée à Kelvin Grove Road, QUT Creative Industries Precinct (crédit Jon McCormack)

  • Les maths pour aider notre planète

    À quoi servent les mathématiques ? Il faut évidemment rappeler que  « […] le but unique de la science, c’est l’honneur de l’esprit humain et […] sous ce titre, une question de nombres vaut autant qu’une question de système du monde »

    Mais cela ne les empêche pas de nous aider aussi au quotidien et il y a bien peu de secteurs de l’activité humaine dont elles soient absentes. C’est particulièrement vrai pour la compréhension de notre environnement : climat, économie, géologie, écologie, science spatiale, régulation démographique, politique mondiale, etc.

    breves de maths
    Aller sur le site

    Le livre collectif Brèves de maths (Éditions Nouveau Monde) illustre, de façon accessible, la variété des problèmes scientifiques dans lesquels la recherche mathématique actuelle joue un rôle important. Cet ouvrage propose une sélection des meilleures contributions du projet Un jour, une brève de l’initiative internationale Mathématiques de la planète Terre.

    3-couv_maths

    Antoine Rousseau est chercheur et consacre une partie de son activité à la médiation scientifique.

  • A la conquête de l’« isomorphisme de graphes »

    La recherche aime bien avoir ses challenges qui galvanisent les énergies. L’intérêt d’un tel challenge peut avoir de nombreuses raisons, la curiosité (le plus ancien os humain), l’importance économique (une énergie que l’on puisse stoker), la difficulté technique (le théorème de Fermat). En informatique, un problème tient de ces deux dernières classes : c’est l’«isomorphisme de graphe» (nous allons vous dire ce que c’est !) . On comprendra l’excitation des informaticiens quand un chercheur de la stature de Laszlo Babai de l’Université de Chicago a annoncé une avancée fantastique dans notre compréhension du problème. Binaire a demandé à une amie, Christine Solnon, Professeure à l’INSA de Lyon, de nous parler de ce problème. Serge Abiteboul, Colin de la Higuera.

    À la rencontre de Laszlo et de son problème

    Laszlo Babai, professeur aux départements d’informatique et de mathématiques de l’université de Chicago, a présenté un exposé le 10 novembre 2015 intitulé Graph Isomorphism in Quasipolynomial Time. Si le nom « isomorphisme de graphes » ne vous dit rien, vous avez probablement déjà rencontré ce problème, et vous l’avez peut être même déjà résolu « à la main » en comparant, par exemple, des schémas ou des réseaux, afin de déterminer s’ils ont la même structure.

    Le problème est déroutant et échappe à toute tentative de classification : d’une part, il est plutôt bien résolu en pratique par un algorithme qui date du début des années 80 ; d’autre part, personne n’a jamais réussi à trouver un algorithme dont l’efficacité soit garantie dans tous les cas. Mais surtout, il est un atout sérieux pour tenter de prouver ou infirmer la plus célèbre conjecture de l’informatique : P≠NP.

    Nous allons donc présenter ici un peu plus en détails ce problème, en quoi il occupe une place atypique dans le monde de la complexité des problèmes, et pourquoi l’annonce de Babai a fait l’effet d’une petite bombe dans la communauté des chercheurs en informatique.

    Qu’est-ce qu’un graphe ?

    Pour résoudre de nombreux problèmes, nous sommes amenés à dessiner des graphes, c’est-à-dire des points (appelés sommets) reliés deux à deux par des lignes (appelées arêtes). Ces graphes font abstraction des détails non pertinents pour la résolution du problème et permettent de se focaliser sur les aspects importants. De nombreuses applications utilisent les graphes pour modéliser des objets. Par exemple:

    By Tibidibtibo (Own work) [CC BY-SA 3.0 (http://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons
    By Tibidibtibo (Own work) [CC BY-SA 3.0 (http://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons
    		 Un réseau de transport (routier, ferroviaire, métro, etc) peut être représenté par un graphe dont les sommets sont des lieux (intersections de rues, gares, stations de métro, etc) et les arêtes indiquent la possibilité d’aller d’un lieu à un autre (par un tronçon de route, une ligne de train ou de métro, etc.)

    HERE
    By This SVG image was created by Medium69. Cette image SVG a été créée par Medium
    		 Une molécule peut être représentée par un graphe dont les sommets sont les atomes, et les arêtes les liaisons entre atomes.

    G1
    https://www.flickr.com/photos/jurvetson/2234378275
    		 Un réseau social peut être représenté par un graphe dont les sommets sont les membres, et les arêtes les relations entre membres

    Le problème d’isomorphisme de graphes

    Étant donnés deux graphes, le problème d’isomorphisme de graphes (Graph Isomorphism Problem) consiste à déterminer s’ils ont la même structure, c’est-à-dire, si chaque sommet d’un graphe peut être mis en correspondance avec exactement un sommet de l’autre graphe, de telle sorte que les arêtes soient préservées (deux sommets sont reliés par une arête dans le premier graphe si et seulement si les sommets correspondants sont reliés par une arête dans le deuxième graphe). Considérons par exemple ces trois graphes :

    G1
    G1
    		 Les graphes G1 et G2 sont isomorphes car la correspondance

    { a ↔ 1; b ↔ 2; c ↔ 3;
    d ↔ 4; e ↔ 5; f ↔ 6; g ↔ 7}

    préserve toutes les arêtes.

     

     

    Par exemple :

    – a et b sont reliés par une arête dans G1, et 1 et 2 aussi dans G2

    – a et c ne sont pas reliés par une arête dans G1, et 1 et 3 non plus dans G2 ;

    etc.

     

    En revanche, G1 n’est pas isomorphe à G3

    (ce qui n’est pas évident à vérifier).

    G2
    G2

    G3
    G3

    Notons qu’il est plus difficile de convaincre quelqu’un que les graphes G1 et G3 ne sont pas isomorphes car nous ne pouvons pas fournir de « certificat » permettant de vérifier cela rapidement, comme nous venons de le faire pour montrer que G1 et G2 sont isomorphes. Pour se convaincre que deux graphes ne sont pas isomorphes, il faut se convaincre qu’il n’existe pas de correspondance préservant les arêtes, et la question de savoir si on peut faire cela efficacement (autrement qu’en énumérant toutes les correspondances possibles) est véritablement au cœur du débat.

    Ce problème se retrouve dans un grand nombre d’applications : dès lors que des objets sont modélisés par des graphes, le problème de la recherche d’un objet identique à un objet donné, par exemple, s’y ramène. Il est donc de première importance de disposer d’algorithmes efficaces.

    Mais, au delà de cet aspect pratique, le problème occupe aussi une place très particulière dans un monde théorique au sein de la science informatique : celui de la complexité .

    Petite digression sur la complexité des problèmes

    La théorie de la complexité s’intéresse à la classification des problèmes en fonction de la complexité de leur résolution.

    La classe des problèmes faciles (P). La classe P regroupe tous les problèmes « faciles ». Nous dirons qu’un problème est facile s’il existe un algorithme « efficace » pour le résoudre, et nous considèrerons qu’un algorithme est efficace si son temps d’exécution croît de façon polynomiale lorsqu’on augmente la taille du problème à résoudre. Par exemple, le problème consistant à trouver un chemin reliant deux sommets d’un graphe appartient à la classe P car il existe des algorithmes dont le temps d’exécution croît de façon linéaire par rapport à la taille du graphe (son nombre de sommets et d’arêtes).

    La classe des problèmes dont les solutions sont faciles à vérifier (NP). La classe NP regroupe l’ensemble des problèmes pour lesquels il est facile de vérifier qu’une combinaison donnée (aussi appelée certificat) est une solution correcte au problème. Par exemple, le problème de recherche d’un chemin entre deux sommets appartient également à NP car étant donnée une succession de sommets, il est facile de vérifier qu’elle correspond bien à un chemin entre les deux sommets. De fait, tous les problèmes de P appartiennent à NP.

    La question inverse est plus délicate, et fait l’objet de la célèbre conjecture P≠NP.

    La classe des problèmes difficiles (NP-complets). Certains problèmes de la classe NP apparaissent plus difficiles à résoudre dans le sens où personne ne trouve d’algorithme efficace pour les résoudre. Les problèmes les plus difficiles de NP définissent la classe des problèmes NP-complets.

    Considérons par exemple le problème consistant à rechercher dans un réseau social un groupe de personnes qui sont toutes amies deux à deux. Le problème est facile si on ne pose pas de contrainte sur la taille du groupe. Il devient plus difficile si on impose en plus que le groupe comporte un nombre fixé à l’avance de personnes. Si on modélise le réseau social par un graphe dont les sommets représentent les personnes et les arêtes les relations entre les personnes, alors ce problème revient à chercher un sous-ensemble de k sommets tous connectés deux à deux par une arête. Un tel sous-ensemble est appelé une clique.

    Si nous avons un sous-ensemble de sommets candidats, alors nous pouvons facilement vérifier s’il forme une clique ou non. En revanche, trouver une clique de taille donnée dans un graphe semble plus difficile. Nous pouvons résoudre ce problème en énumérant tous les sous-ensembles possibles de  sommets, et en testant pour chacun s’il forme une clique. Cependant, le nombre de sous-ensembles candidats explose (c’est-à-dire,  croît exponentiellement) en fonction du nombre de sommets des graphes, ce qui limite forcément ce genre d’approche à des graphes relativement petits.

    Actuellement, personne n’a trouvé d’algorithme fondamentalement plus efficace que ce principe fonctionnant par énumération et test. Évidemment, il existe des algorithmes qui ont de bien meilleures performances en pratique (qui utilisent des heuristiques et des raisonnements qui permettent de traiter des graphes plus gros) mais ces algorithmes ont toujours des temps d’exécution qui croissent de façon exponentielle par rapport au nombre de sommets.

    La question pratique qui se cache derrière la question « P≠NP ? » est : Existe-t-il un algorithme efficace pour rechercher une clique de k sommets dans un graphe ?

    Autrement dit : est-ce parce que nous ne sommes pas malins que nous n’arrivons pas à résoudre efficacement ce problème, ou bien est-ce parce que cela n’est pas possible ?

    Il existe un très grand nombre de problèmes NP-complets, pour lesquels personne n’a réussi à trouver d’algorithme efficace. Ces problèmes interviennent dans de nombreuses applications de la vie quotidienne : faire un emploi du temps, ranger des boites rectangulaires dans un carton sans qu’il n’y ait de vide, chercher un circuit passant exactement une fois par chacun des sommets d’un graphe, etc. Pour ces différents problèmes, on connait des algorithmes qui fonctionnent bien sur des problèmes de petite taille. En revanche, quand la taille des problèmes augmente, ces algorithmes sont nécessairement confrontés à un phénomène d’explosion combinatoire.

    Un point fascinant de la théorie de la complexité réside dans le fait que tous ces problèmes sont équivalents dans le sens où si quelqu’un trouvait un jour un algorithme efficace pour un problème NP-complet (n’importe lequel), on saurait en déduire des algorithmes polynomiaux pour tous les autres problèmes, et on pourrait alors conclure que P = NP. La question de savoir si un tel algorithme existe a été posée en 1971 par Stephen Cook et n’a toujours pas reçu de réponse. La réponse à cette question fait l’objet d’un prix d’un million de dollars par l’institut de mathématiques Clay.

    La classe des problèmes ni faciles ni difficiles (NP-intermédiaires). Le monde des problèmes NP serait bien manichéen s’il se résumait à cette dichotomie entre les problèmes faciles (la classe P) et les problèmes dont on conjecture qu’ils sont difficiles (les problèmes NP-complets). Un théorème de Ladner nous dit qu’il n’en est rien : si la conjecture P≠NP est vérifiée, alors cela implique nécessairement qu’il existe des problèmes de NP qui ne sont ni faciles (dans P) ni difficiles (NP-complets). Ces problèmes sont appelés NP-intermédiaires. Notons que le théorème ne nous dit pas si P est différent de NP ou pas : il nous dit juste que si P≠NP, alors il existe au moins un problème qui est NP-intermédiaire… sans nous donner pour autant d’exemple de problème NP-intermédiaire. Il faudrait donc réussir à trouver un problème appartenant à cette classe pour démontrer que P≠NP. On dispose d’une liste (assez courte) de problèmes candidats (voir par exemple https ://en.wikipedia.org/wiki/NP-intermediate)… et c’est là que l’isomorphisme de graphes entre en jeu.

    Que savait-on sur la complexité de l’isomorphisme de graphes jusqu’ici ?

    Nous pouvons facilement vérifier que deux graphes sont isomorphes dès lors qu’on nous fournit une correspondance préservant les arêtes (comme nous l’avons fait précédemment pour les graphes G1 et G2). On peut donc facilement vérifier les solutions, nous sommes dans la classe NP. Mais sa complexité exacte n’est pas (encore) connue. Des algorithmes efficaces (polynomiaux) ont été trouvés pour des cas particuliers, les plus utilisés étant probablement pour les arbres (des graphes sans cycle) et les graphes planaires (des graphes qui peuvent être dessinés sur un plan sans que leurs arêtes ne se croisent). Dans le cas de graphes quelconques, les meilleurs algorithmes connus jusqu’ici ont une complexité exponentielle. Pour autant, personne n’a réussi à démontrer que le problème est NP-complet.

    Il est donc conjecturé que ce problème est NP-intermédiaire. C’est même sans aucun doute le candidat le plus célèbre pour cette classe, d’une part parce qu’il est très simple à formuler, et d’autre part parce qu’on le retrouve dans de nombreux contextes applicatifs différents.

    Que change l’annonce de Babai ?

    L’annonce de Babai n’infirme pas la conjecture selon laquelle le problème est NP-intermédiaire, car son nouvel algorithme est quasi-polynomial, et non polynomial.

    Plus exactement, pour les matheuses et les matheux, si les graphes comportent n sommets, alors le temps d’exécution de l’algorithme croît de la même façon que la fonction 2log(n)c où c est une valeur constante. Si c est égal à 1, alors l’algorithme est polynomial. Ici, c est supérieur à 1, de sorte que l’algorithme n’est pas polynomial, mais son temps d’exécution se rapproche plus de ceux d’algorithmes polynomiaux que de ceux d’algorithmes exponentiels.

    Ce résultat est une avancée majeure parce qu’il rapproche le problème de la classe P, mais aussi parce que l’existence de cet algorithme quasi-polynomial ouvrira peut être une piste pour trouver un algorithme polynomial, ce qui permettrait d’éliminer le problème de la courte liste des problèmes dont on conjecture qu’ils sont NP-intermédiaires. Notons que le dernier problème qui a été enlevé de cette liste est le problème consistant à déterminer si un nombre entier donné est premier, pour lequel un algorithme polynomial a été trouvé en 2002.

    D’un point de vue purement pratique, en revanche, cette annonce risque fort de ne pas changer grand chose quant à la résolution du problème, car on dispose déjà d’algorithmes performants : ces algorithmes sont capables de le résoudre pour la très grande majorité des graphes, et n’ont un temps d’exécution exponentiel que pour très peu de graphes.

    Christine Solnon, INSA Lyon

    Pour aller plus loin :

    • De l’annonce au résultat établi. Le résultat de Babai en est encore au stade de l’annonce. Il faut maintenant qu’il soit détaillé dans un ou plusieurs articles, vérifiés par ses pairs, puis publiés dans des journaux. Ce résultat viendra alors grandir le corpus des vérités scientifiques établies. Il peut arriver que lors de ce cheminement, on trouve des « trous » dans la démonstration ; c’est arrivé pour le théorème de Fermat et ils ont été comblés. Il se peut aussi qu’on trouve une erreur dans la démonstration (y compris après la publication de l’article) ce qui renvoie les scientifiques à leurs tableaux noirs
      .
    • Voir, par exemple, https ://fr.wikipedia.org/wiki/Liste_de_problèmes_NP-complets, pour une liste des problèmes les plus connus.

    • Pour un exemple d’algorithme pratique,  l’algorithme Nauty 4 introduit en 1981 par Brendan McKay.

    • László Babai, né le 20 juillet 1950 à Budapest, est un professeur de mathématiques et d’informatique hongrois, enseignant actuellement à l’université de Chicago. Il est connu pour les systèmes de preuve interactive, l’introduction du terme « algorithme de Las Vegas » et l’utilisation de méthodes de la théorie des groupes pour le problème de l’isomorphisme de graphes. Il est lauréat du prix Gödel 1993. Wikipedia (2016).

  • De la science au service de notre planète dans l’Interstices de la COP21

    interstices-cop21-a-1
    Jocelyne Ehrel

    Montée du niveau des mers, érosion côtière, perte de biodiversité… Les impacts sociétaux de ces bouleversements dus au réchauffement climatique ne seront pas dramatiques dans un futur proche si et seulement si nous changeons radicalement nos comportements collectifs et individuels et mettont en place de vraies solutions.

    interstices-cop21-a-2
    Joanna Jongwane

    L’informatique et les mathématiques appliquées contribuent à relever le défi de la transition énergétique, pour  changer par exemple l’usage des voitures en ville ou encore pour contrôler la consommation d’énergie dans les bâtiments. A contrario, quand la nature et la biodiversité inspirent les informaticiens, cela aboutit à des projets d’écosystèmes logiciels qui résistent mieux à divers environnements.

    interstices-cop21-0
    Accéder au dossier

    C’est sur Interstices,  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 que chercheuses et chercheurs nous proposent de découvrir quelques grains de science sur ces sujets. Morceaux choisis :

    interstices-cop21-1
    Accéder au document

    «Le niveau des mers monte, pour différentes raisons liées au réchauffement climatique. Les glaciers de  l’Antarctique et du Groenland, qu’on appelle calottes polaires ou inlandsis, jouent un rôle majeur dans l’évolution du niveau des mers. Peut-on prévoir l’évolution future de ces calottes polaires et en particulier le vêlage d’icebergs dans l’océan ?»

    interstices-cop21-2
    Accéder au document

    «À l’heure de la COP21, toutes les sonnettes d’alarme sont tirées pour alerter sur l’urgence climatique. Si les simulations aident à prédire les évolutions du climat, elles peuvent aussi être vues comme un outil de dialogue science-société, selon Denis Dupré. On en parle avec lui dans cet épisode du podcast audio.»

    interstices-cop21-3
    Accéder au document

    «Si au lieu de distribuer des millions de copies identiques, les fabricants de logiciels avaient la possibilité de distribuer des variantes, et que ces variantes avaient la possibilité de s’adapter à leur environnement, ces « écosystèmes logiciels » ne pourraient-ils pas renforcer la résistance de tous les services qui nous accompagnent au quotidien ?»

    Envie d’en savoir plus ? La suite sur http://interstices.info/cop21

    Extraits d’Interstices, Joanna Jongwane, Rédactrice en chef d’Interstices et Jocelyne Erhel, Directrice de Recherche et Responsable scientifique du comité éditorial, avec Christine Leininger et Florent Masseglia membres du comité exécutif.

  • La programmation par contraintes expliquée à ma garagiste ou à mon fleuriste

    Parmi les grandes familles d’approches et de langages informatiques, on entend parfois parler de « programmation par contraintes ». Un chercheur du domaine vous expliquerait peut-être que « c’est un paradigme de programmation déclarative permettant de traiter des problèmes fortement combinatoires ». Euh… Heureusement, Binaire a son joker : une enseignante-chercheure Charlotte Truchet, spécialiste du domaine, qui sait expliquer ses recherches. Thierry Viéville.

    Photo de www.picturalium.com CC-BY

    Venez, je vous emmène visiter la boutique de Denis, fleuriste dans un petit village, un beau matin de printemps. Denis vend des fleurs à l’unité, et des bouquets. Comme c’est le printemps, il a ce matin un beau stock de fleurs fraîches, disons : bégonias, marguerites, roses, hortensias et pissenlits. Chaque fleur a des caractéristiques différentes (certaines fleurs sont par exemple associées à des occasions particulières), un standing différent (qui influence le prix), une couleur, etc.

    Le matin, à l’ouverture, Denis prépare des bouquets tout prêts pour les clients pressés. Attention, l’exercice est délicat, il ne peut pas faire n’importe quoi. D’abord, il ne peut pas utiliser plus de fleurs qu’il n’en a en stock. Ensuite, il a des goûts : Denis aime bien l’association bégonia-rose, mais il n’aime pas les bouquets mélangeant des pissenlits et des marguerites, il préfèrerait fermer boutique plutôt que vendre de telles horreurs. Et puis, il doit faire tourner son commerce, et pour cela, il doit vendre ses bouquets à un bon prix, qui dépend des marges qu’il réalise sur chaque fleur du bouquet. Bref, Denis se trouve devant un problème compliqué : comment composer ses bouquets, en tenant compte de ses goûts, ses stocks et ses coûts ?

    Il pourrait faire ses bouquets au petit bonheur, un peu au hasard, mais il rencontre un problème. Un phénomène tragique l’attend au tournant : l’explosion combinatoire. Un bien grand mot pour dire que le nombre de bouquets possibles est gigantesque, le nombre de possibilités à considérer dépasse l’entendement du pauvre Denis. Imaginons que Denis ait en stock 10 bégonias, 20 marguerites, 15 roses, 5 hortensias et 30 pissenlits. Il peut mettre dans son bouquet : 1 bégonias et rien d’autre, 2 bégonias et rien d’autre, … et ainsi de suite jusqu’à 10 bégonias et rien d’autre. Puis il attaque la série de bouquets avec seulement des marguerites (20 possibilités), seulement des roses (15 possibilités), etc. Ensuite, il commence à associer des fleurs : 1 bégonia, 1 rose et rien d’autre, 1 bégonia et 2 roses, etc : encore un sacré paquet de possibilités, 62496 exactement. Et on est encore loin du compte ! Bref, le nombre de possibilités est vraiment très grand, même pour un seul bouquet (11*21*16*6*31-1 soit environ 680 000). Mais surtout, ce nombre augmente de façon catastrophique dès que l’on augmente le nombre de bouquets : pour deux bouquets, on a 680 000 au carré possibilités, soit environ 470 milliards, pour trois bouquets, 680 000 au cube que je n’ai même pas envie de calculer, etc. C’est la catastrophe (et le « fortement combinatoire » de la phrase du chercheur). Pauvre fleuriste en ce triste matin de printemps !

    © www.theplantgame.com Fleurs et Informatique : quand les plantes s’étudient avec les sciences du numérique

    Vous me direz, taratata, mon fleuriste fait des bouquets tous les jours, et il n’en fait pas un plat. C’est vrai : en fait, Denis n’a pas besoin d’essayer toutes les possibilités, et c’est ce qui le sauve. Il sait que certaines possibilités sont impossibles pour des raisons diverses. Ce que faisant, il raisonne sur les contraintes de son problème : stocks, goûts et coûts. Par exemple, Denis veut gagner de l’argent, et on peut supposer que les bouquets plus variés se vendent plus chers : Denis évite donc les bouquets monofleurs, ce qui élimine déjà 10 + 20 + 15 + 5 + 30 possibilités. C’est une petite simplification, mais elle est gratuite à opérer, donc elle fait gagner du temps. De même, il n’aime pas la combinaison pissenlits-marguerites. Si on interdit la présence de ces deux fleurs simultanément, on économise 630 000 possibilités ! Avant de crier victoire, remarquons qu’il en reste encore plus de 50 000. Mais tout de même, c’est un pas de géant. Denis n’a donc pas besoin d’essayer toutes les possibilités : il fait des bouquets guidé par son intuition. Ce type de raisonnement, qui permet d’éliminer des possibilités parce qu’elles sont à l’évidence inutiles dans le problème, est au cœur de la programmation par contraintes.

    Représentation graphique d’un problème de programmation par contraintes, © users.cecs.anu.edu.au/~jks/G12

    La programmation par contraintes consiste à faire des beaux bouquets dans un monde assez similaire à la boutique de Denis, mais un peu plus formel. On travaille sur des problèmes avec des inconnues, les variables : ici, le nombre de chaque fleur par bouquet. On ne sait pas combien valent ces variables, justement, c’est ce que l’on cherche. Cela dit, ces variables doivent rester dans un ensemble donné : de même qu’on sait qu’il y a 15 roses en stock (donc le nombre de roses dans chaque bouquet est entre 0 et 15), chaque variable vient avec un domaine de valeurs possibles. Si on note R1 le nombre de roses dans le premier bouquet, on appelle domaine de R1 l’ensemble des entiers entre 0 et 15.

    Enfin, on écrit des contraintes sur les variables. Supposons pour simplifier que Denis se contente de deux bouquets, car son échoppe est modeste. D’abord, il faut s’assurer qu’il ne dépense pas plus que ses 15 roses en stock : cela se formalise avec une contrainte R1+R2<= 15, et de même pour les bégonias, pissenlits, marguerites et hortensias. Ensuite, Denis peut ajouter des contraintes en fonction de ses envies. Comme il déteste l’association marguerites-pissenlits, il peut écrire : M1*P1=0, ce qui force au moins l’une des deux valeurs à être nulle. S’il aime bien les roses et les bégonias, il peut imposer d’en avoir un minimum dans son gros bouquet : par exemple, R1>5 et B1>5. Et ainsi de suite. Les coûts aussi peuvent être écrits avec une formule similaire, en soustrayant au prix du bouquet la somme des prix de chaque fleur.

    Ce que l’on appelle contrainte, c’est une formule construire comme cela, à partir des variables du problème et avec des formules mathématiques. Il y a mille et une façons d’écrire ces formules, c’est une étape importante et difficile que l’on appelle « modélisation du problème ». On obtient un problème de satisfaction de contraintes (souvent abrégé en CSP, pour Constraint Satisfaction Problem en anglais) : le problème formalisé avec des variables, des domaines et des contraintes. Résoudre le problème, c’est faire un bouquet, ou encore trouver pour chaque variable une valeur de son domaine telle que les contraintes soient vraies.

    © www.theplantgame.com

    Au lieu de réfléchir, Denis pourrait utiliser un solveur de contraintes, c’est-à-dire un programme qui résout pour lui le CSP des bouquets, un programme qui sait résoudre de tels problèmes en général. Un solveur de contraintes commence par procéder à un raisonnement sur les contraintes pour éliminer des valeurs inutiles dans les domaines : par exemple, la contrainte R1>5 permet d’éliminer 0,1, 2, 3 et 4 du domaine de R1. En général, cela ne suffit pas à résoudre le problème, il reste encore de nombreuses possibilités. Alors, le solveur devient « bourrin » : il fait des essais. Il donne une valeur à une variable (il commence un bouquet avec 1 rose), il re-raisonne un petit coup et si ça ne suffit pas, il continue (il ajoute des bégonias), etc. Un solveur alterne ainsi des étape de raisonnement et des étapes de commencements de bouquets, ce que l’on appelle instanciation. S’il s’avère que le bouquet commencé est mauvais, et qu’on n’arrive pas à le compléter correctement (par exemple, si on a commencé avec 1 marguerite et 1 pissenlit), le solveur trouve un échec : il revient en arrière, enlève le nombre de fleurs qu’il faut (il enlève le pissenlit) et ré-essaie autrement (avec 0 pissenlits).

    Bref, un solveur de contraintes commence des tonnes de bouquets et finit bien par un trouver un qui convienne. Si le problème a une solution, il la trouve. S’il n’en a pas, il le prouve, ce qui est toujours bon à savoir : Denis est trop exigeant, voilà tout. Il faut qu’il reconsidère ses contraintes.

    Il reste encore des choses à noter dans l’échoppe de Denis.

    D’abord, à aucun moment, Denis n’a réfléchi à une méthode de résolution pour son problème. Il s’est contenté de décrire ce qu’il voulait, et se moque bien de savoir comment le solveur travaille. C’est ce que l’on appelle de la programmation déclarative dans le jargon informatique. C’est assez rare en informatique (pas le jargon, la programmation déclarative). En programmation, en général, il faut construire un algorithme qui arrive à obtenir le résultat voulu. Ici, ce n’est pas la peine, et c’est très pratique pour Denis, qui n’y connaît rien en algorithmique.

    Ensuite, quand j’ai dit que le fleuriste pouvait écrire des formules pour décrire les bouquets, je vous ai arnaqués ! En informatique, pour pouvoir écrire une formule, il faut savoir dans quel langage, sinon on écrit n’importe quoi. Ainsi Denis a le droit d’écrire R1>5 mais il n’aurait pas le droit d’écrire R1/(bleu vif)+(il existe une herbe verte)=beaucoup de tune. En fait, il existe des langages de contraintes que l’on sait traiter et Denis doit s’y tenir. La plupart des solveurs de contraintes autorisent des langages assez proches les uns des autres. On a le droit aux formules mathématiques basiques, construites avec des nombres, des opérations comme +, -, *, etc, et des prédicats comme =, <, /=. Et, on a aussi le droit d’utiliser des contraintes « prêtes à l’emploi », faites sur mesure par les chercheurs pour faciliter la vie de Denis. On les appelle contraintes globales. Elles sont recensées dans un grand catalogue qui en compte plus de 350 (http://sofdem.github.io/gccat/gccat/sec5.html). N’hésitez pas à aller les visiter, c’est un peu austère mais vous aurez sous vos yeux l’état de l’art de la recherche sur les contraintes globales !

    choco-solver.org est un solveur de contrainte libre et dont le code est ouvert

    La plus célèbre et la plus couramment utilisée des contraintes globales est certainement celle que l’on appelle alldifferent. Pour la comprendre, il faut imaginer qu’un jour, Denis se réveille d’humeur fantasque. En ce beau matin de printemps, il se dit : j’en ai assez de faire des bouquets ennuyeux avec 6 bégonias et 6 roses. Ça tombe mal dans le vase. Aujourd’hui, j’ai envie de bouquets bizarres, étonnants, asymétriques. Aujourd’hui, je veux des compositions avec un nombre différent de chaque fleur ! Le malheureux perd un peu la boule, si vous voulez mon avis, mais on n’y peut rien.

    Il se met donc à composer des bouquets où il est interdit d’avoir autant de roses que de bégonias, autant de bégonias que de marguerites, etc. Essayons d’y réfléchir. Ce matin là, il lui reste 3 camélias, 2 bégonias, 25 tulipes, 7 poinsettias et 2 hortensias. Il veut faire un gros bouquet avec un peu de chaque fleur (C>0, B>0, etc). Comme il n’a que 2 bégonias et 2 hortensias, il peut déduire qu’il doit forcément mettre dans son bouquet exactement 3 camélias, et au moins 3 tulipes et poinsettias. En effet, s’il met 1 bégonia, il est obligé de mettre 2 hortensias (donc plus de trois des autres fleurs). De même, s’il met 1 hortensia, il doit mettre 2 bégonias et rebelote (plus de trois des autres fleurs). Dans tous les cas, il doit mettre au moins 3 camélias et au plus 3 camélias (car il n’en a pas plus en stock), donc exactement 3 camélias, et plus de 4 tulipes et poinsettias.

    Voilà qui aide grandement ! On élimine d’un seul coup beaucoup de possibilités, on trouve même directement le bon nombre de camélias ! Même si l’exemple choisi ici est simple, il faut imaginer qu’on pourrait appliquer le même raisonnement pour des nombres beaucoup plus grands. Il faut bien voir que pour trouver cette simplification, Denis a dû cette fois raisonner sur toutes les fleurs en même temps. C’est le principe d’une contrainte globale : elle exprime une propriété globale sur plusieurs variables en même temps, soit pour raisonner plus efficacement, soit pour exprimer des propriétés plus complexes que le langage basique sus-cité. Une contrainte globale embarque sa propre méthode de déduction, qui est utilisée directement par le solveur.

    Les questions explorées par les chercheurs en contraintes sont évidemment nombreuses et dépassent parfois un peu le cadre de la boutique du fleuriste, mais elles tournent tout de même beaucoup autour de l’organisation du procédé décrit plus haut  : comment bien modéliser un problème ? Comment rendre la résolution efficace ? Comment bien programmer le solveur ? Peut-on le rendre interactif ? Peut-on écrire des contraintes un peu subtiles, pour exprimer par exemple des préférences ? Et cætera.

    Quant aux applications, elles sont assez variées. Une contrainte comme alldifferent écrit par Denis porte sur des fleurs, mais elle aurait aussi bien pu porter sur des avions (à ranger dans un aéroport), des fréquences (à placer dans une bande radio), des régions limitrophes (à colorier sur une carte), des notes de musique (à organiser harmonieusement sur une partition), des cartons de formes diverses (à ranger dans un container), des enseignements (à placer dans des emplois du temps), etc. On trouve donc la programmation par contraintes, avec ses cousins comme la programmation linéaire en nombres entiers, les métaheuristiques, l’optimisation linéaire ou non-linéaire, etc, dans beaucoup d’applications où le nombre de variables est très grand comme la logistique ou l’ordonnancement de tâches. Mais sa nature déclarative (qui permet de fabriquer des langages à destination de non-informaticiens) la tourne aussi vers des applications moins informatico-centrées, comme en médecine, musique, visualisation, graphisme, biologie, urbanisme, etc.

    Charlotte Truchet, Université de Nantes
    @chtruchet

  • Sex and the Algorithm

    « Sex truly was the original sin »
    Christos Papadimitriou

    Christos Papadimitriou.
    Christos Papadimitriou

    Ce que nous avons retenu de la sélection naturelle, c’est que les mieux adaptés, les plus forts, se reproduisent et finissent par l’emporter, et pour ce qui est de la génétique, c’est qu’on prend au hasard 50% des gènes de chacun des deux membres d’un couple pour obtenir un nouvel individu. Christos Papadimitriou, professeur à Berkeley, et ses collaborateurs étudient ces phénomènes. Christos est un des plus brillants chercheurs en informatique. Il s’est aussi intéressé, entre autre, à la finance, et la biologie. Nous allons essayer de vous présenter son point de vue, en le simplifiant à outrance tout en le prolongeant aussi. Si vous lisez l’anglais, et si le sujet vous intéresse, n’hésitez pas à aller lire un article plus technique [1].

    Si par chance, on a obtenu un individu avec des gènes d’enfer, il se reproduit et ses enfants n’héritent que de la moitié de ses gènes. Cela se dilue à chaque génération. La reproduction sexuée détruit-elle ce qui marche bien ? Est-elle débile ? Et pourtant… La reproduction sexuée est la norme dans la nature, la reproduction asexuée rare. Pourquoi ? Les chercheurs ne sont pas d’accord sur les explications. Christos et ses collègues proposent une théorie passionnante. En fait, ils montrent que c’est à cause de l’effet de dilution que la reproduction sexuée « gagne ».

    La structure d’une partie de la double hélice de l’ADN. Wikipédia.
    La structure d’une partie de la double hélice de l’ADN. Wikipédia.

    Une analogie est celle de l’investissement boursier. On pourrait imaginer qu’une bonne stratégie consiste à acheter quelques rares titres super performants. Mais en fait un bon investisseur va varier son portefeuille, achetant aussi des titres qui réussissent moins bien, pour pouvoir s’adapter à des changements de l’environnement bancaire. La reproduction asexuée serait parfaite dans une nature figée. Mais la nature change sans cesse, et la reproduction est bien plus à même de suivre ses transformations. C’est cette intuition qui conduit les investisseurs à panacher leurs portefeuilles.

    Christos et ses collègues ont démontré cette thèse dans des simulations informatiques que nous allons vous expliquer. Pour cela considérons deux algorithmes très utilisés en informatique. Dans les deux cas, on part d’une population de candidats possibles pour résoudre un problème particulier et on essaie d’aller vers des candidats de plus en plus performants pour résoudre ce problème. Très grossièrement :

    •  Les algorithmes de recuit simulé et la reproduction asexuée. On laisse chaque individu se reproduire en se modifiant aléatoirement. Pour choisir au hasard qui se reproduit, on privilège ceux qui sont le plus performants.
    • Les algorithmes génétiques et la reproduction sexuée. On choisit au hasard deux individus et on les combine pour obtenir un nouvel individu. Là aussi, on biaise le processus en laissant les « meilleurs » se reproduire plus que les autres.

    Si on donne un problème fixe aux algorithmes génétiques, qui semblent pourtant imiter la solution majoritaire dans la nature, ils marchent moins bien que les algorithmes de recuit simulé. Mais si on laisse le problème muter sans arrêt, c’est le contraire qui se passe. La reproduction sexuée est mieux adaptée dans un monde en changement perpétuel.

    Une remarque essentielle est que la reproduction sexuée favorise les systèmes dont on peut combiner efficacement deux individus. Dans la nature, cela conduit donc à des systèmes biologiques se reproduisant de manière sexuée. En informatique, on est confronté à une difficulté, celle de combiner deux individus. Que convient-il de recombiner pour retrouver dans les algorithmes sexués, l’efficacité constatée dans la nature ? Un petit détour par la fiction s’impose.

    et-sexuality-binaire-rayclid-vbIsaac Asimov a imaginé, dans la nouvelle « What is this thing called love » [2], une race extraterrestre ne connaissant que la reproduction asexuée (un parent donne naissance, tout seul, à un enfant qui lui ressemble beaucoup), et ayant appris que sur la planète Terre une race se reproduisait de manière sexuée (deux parents mélangeant leurs gènes pour donner un enfant). Pour eux, si c’est le cas, il leur faut absolument détruire cette race sans tarder, car un tel processus permettra fatalement aux humains de donner naissance un jour à une race supérieure qui dominera l’univers, du fait des possibilités infinies d’amélioration de leurs capacités, et ce de manière beaucoup plus rapide que les autres races. L’anecdote de l’histoire est qu’ils enlèvent un couple de terriens, et leur demandent naïvement de leur faire une démonstration de reproduction sexuée. La femme et l’homme, dignes représentants de la morale puritaine qu’Asimov caricature ici, refusent d’une manière telle que les extraterrestres repartent, convaincu que toutes ces histoires de reproduction sexuée ne sont qu’élucubrations de leurs savants, et qu’ils peuvent laisser cette planète tranquille. Bien entendu, quelques minutes plus tard, le couple passe à l’action, finalement…

    ordMais imaginons que ces extraterrestres, au lieu d’être horrifiés à l’idée de cette race se reproduisant de manière sexuée, se soient au contraire mis en tête de tenter de l’imiter avec une compréhension du phénomène, et des expertises en biologie, très superficielles. Ils auraient par exemple tenté d’échanger des organes entre différents individus, genre « je prend le corps d’une personne pour y mettre le cerveau exceptionnel d’une autre ». Il est clair que le résultat aurait été en deçà de leurs espérances, à supposer qu’ils aient même réussi à garder les personnes en vie. Car la reproduction sexuée se déroule dans la nature au niveau des chromosomes, et qu’un chromosome n’est pas une partie de la solution (l’organisme), mais une partie de la machinerie qui construit l’organisme via le phénomène éminemment complexe de la morphogénèse. Pour que la reproduction sexuée donne les résultats escomptés, il faut donc qu’elle s’effectue à un niveau suffisant de complexité pour que la substantifique moelle de ce qui rend un individu supérieur aux autres (dans un concours de beauté, ou en mathématiques) soit effectivement recombinée.

    Revenons aux algorithmes, et à l’autre face de l’informatique, lorsque celle-ci résout des problèmes hors de portée du mathématicien, en s’inspirant éventuellement de la nature, mais sans aucune obligation de réalisme. Ici également, ce qui rend une solution meilleure que les autres n’est pas forcément directement l’un des composants utilisés pour la représenter. Et un croisement qui se contentera d’échanger des « bouts de solutions » comme par exemple dans le modèle qu’utilise Christos, ne tirera effectivement pas partie de la puissance potentielle de la reproduction sexuée.

    Prenons un exemple que les informaticiens adorent, par sa complexité malgré la simplicité de son énoncé, la résolution du problème dit « du voyageur de commerce » : un VRP doit visiter un certain nombre de villes en faisant le minimum de kilomètres. Une solution est donc décrite par la liste des villes dans l’ordre de parcours. Il est clair qu’ici, la méthode consistant à croiser deux listes en les coupant en deux au hasard et en raboutant le début de l’une avec la fin de l’autre ne permet même pas d’obtenir des nouvelles liste valides : il manquera quasiment inévitablement des villes dans les deux nouvelles listes. C’est d’ailleurs l’exemple qu’utilise Christos pour illustrer précisément la difficulté de concevoir un croisement par recombinaison basique de parties de solution. Mais un chercheur japonais a récemment proposé [3] un processus de croisement de deux listes, plutôt complexe, qui réussit l’exploit de mélanger deux listes en extrayant de chacune ce qui fait qu’elle est peut-être un début de bonne solution au problème, tout en contenant suffisamment de hasard pour créer cette race destinée inévitablement à dominer l’univers, c’est-à-dire ici trouver la meilleure solution possible pour notre VRP. Son algorithme génétique détient aujourd’hui plusieurs records du monde … sur des problèmes de VRP classiques, c’est-à-dire statiques.

    Au fond, il existe plusieurs manières de pratiquer la sexualité, pour les algorithmes comme dans la vie, et toutes ne sont pas aussi performantes. Nous n’en sommes certainement qu’au début de cette direction de recherche mais elle est prometteuse.

    Vous aviez peut-être l’impression que le sexe domine le monde. Vous aviez raison, mais peut-être pas pour les bonnes raisons…

    Serge Abiteboul, Inria & ENS Cachan, and Marc Schoenauer, Inria & Université Paris Saclay

    Pour aller plus loin :

    [1] Algorithms, games, and evolution, Erick Chastaina, Adi Livnatb, Christos Papadimitriouc,1, and Umesh Vaziranic
    [2] Isaac Asimov. What Is This Thing Called Love? (short story). Voir l’article Wikipedia avec ce titre (en anglais, la page française correspondante étant à peu près vide).
    [3] A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem. Yuichi Nagata and Shigenobu Kobayashi.  INFORMS Journal on Computing, 25(2):346-363, 2013.

  • Open Access : En avant !

    On parle beaucoup d’open access en ce moment notamment avec un article très disputé de la Loi pour une République Numérique. Nous fêtons du 19 au 25 octobre l’Open Access Week, la semaine du libre accès, « un événement annuel du monde scientifique marqué par l’organisation de multiples conférences, séminaires ou annonces sur le thème du libre accès et sur le futur de la recherche académique dans de nombreux pays. » L’open access des résultats de la recherche académique, notamment quand elle est subventionnée par l’état, semble une évidence. À l’heure du Web, c’est pourtant loin d’être la règle. Laurent Romary, chercheur chez Inria, aborde le sujet. Serge Abiteboul.

    Le libre accès (en anglais : open access) est la mise à disposition en ligne de contenus numériques, qui peuvent eux-mêmes être soit libres (Creative commons, etc.), soit sous un des régimes de propriété intellectuelle. L’open access est principalement utilisé pour les articles de revues de recherche universitaires, sélectionnés par des pairs… Wikipedia 2016.

    PASTILLE_6_Agri
    Le logo de l’open-access : une image … en accès libre !

    La semaine de l’accès libre doit être aussi celle de la pensée libérée. Alors que le sujet n’a jamais été aussi prégnant dans les agendas politiques avec la discussion sur la loi pour une République Numérique et son fameux article 9 sur le « Libre accès aux publications scientifiques de la recherche publique », on peut essayer d’identifier qui a la maîtrise conceptuelle des débats. La lecture du projet d’article laisse perplexe. On ne peut que se féliciter que l’open access soit mentionné explicitement dans la loi et que la notion de « Commun », essentielle en particulier dans l’activité scientifique, apparaisse en tant que telle. Mais tout reflète ici une vision guidée par les vieux mécanismes de l’édition privée, pour ne pas dire papier. On sourirait presque à la référence faite à une parution d’« au moins une fois par an » alors que les journaux électroniques (et libres) modernes publient de plus en plus souvent au fil de l’eau, article par article. On grince à la lecture que des contraintes peuvent peser sur le manuscrit auteur alors que le chercheur et ses confrères chargés de la relecture ont été les seuls à fournir une création de l’esprit. On se désole de voir repris la notion d’embargo (i.e. de « délai de publication ouverte  »), inventée par l’édition commerciale et qui limite la diffusion des savoirs au moment même où cette diffusion serait la plus utile : le temps de l’expression des idées. On ne doute plus avec la dernière phrase dont le seul but est qu’ « aucune exploitation commerciale » ne puisse avoir lieu, alors que l’on souhaite évidemment que les contenus scientifiques (indépendamment de leur forme écrite) soient le plus vite possible des générateurs de prospérité scientifique, sociétale et économique, comme le demande d’ailleurs explicitement la puissance publique qui, faut-il le rappeler, finance une grande partie de la recherche.

    Dans le même temps, on assiste à cette même perte de maîtrise de l’agenda au niveau européen avec des prises de position très conservatrices prises par des institutions telles que la société Max Planck en Allemagne ou exprimées dans des rapports officiels en Angleterre. On semble se précipiter dans les bras du modèle auteur-payeur là aussi inventé par l’édition privée, qui présente tous les risques de coûter au milieu académique bien plus cher que les abonnements eux-mêmes.

    Les chercheurs sont perdus. Il ne savent plus à quel modèle se vouer. Quels droits ont-ils de déposer dans des archives ouvertes telles que HAL ou arXiv alors qu’un éditeur comme Elsevier change régulièrement de politique rendant celle-ci illisible ? Doivent-ils tout aussi bien se laisser tenter par les miroirs aux alouettes que sont Mendeley, Academia ou Research Gate, dont les perspectives économiques ne sont pas nécessairement compatibles avec les besoins de la communication et de la préservation des communs de la science ? Doivent-ils simplement obtempérer quand on leur demande dans le cadre de modèles dits hybrides (*) de payer pour que leur article de revue scientifique soit en « open access » à la date de publication ?

    Que faire alors ? Probablement travailler à l’identification du modèle que l’on souhaite vraiment mettre en œuvre pour favoriser la diffusion libre des savoirs.

    http://www.episciences.org une plateforme pour réaliser des revues à moindre coût et de mettre en œuvre le libre accès aux versions électroniques des articles.

    De quoi parle-t-on ? De mécanismes de communication scientifique que les chercheurs et leurs institutions ont choisis et dont ils possèdent l’entière maîtrise, notamment pour décider des conditions de diffusion et de réutilisation des contenus. De plates-formes de publications qui dépendent de la force publique, et dont les services ne peuvent être délégués que dans un cadre réellement concurrentiel. De la possibilité de pouvoir — enfin — prendre toute la dimension du passage au tout numérique et de voir s’il est possible de communiquer les résultats de recherche autrement : nouveaux modes de qualification et de certification, impact sur les (et symétriquement, des) réseaux sociaux, prise en compte des données de recherche, nouveaux indices d’impact ou de notoriété.

    Un doux rêve ? Il semble que certaines institutions ont décidé d’agir dans ce sens. Pour preuve, Inria, forcément bien placée pour comprendre les défis du numérique, demande à tous ses chercheurs de communiquer autrement :

    • un article de recherche est pris en compte dans l’évaluation d’une équipe uniquement s’il est disponible en accès libre dans le système public HAL,
    • le modèle hybride de financement des publications doit être refusé,
    • et enfin, l’institut encourage des contributions à la définition et à la vie de nouveaux journaux qui reposent sur des plates-formes publiques telles qu’Episciences.org.

    Le message est clair : les chercheurs doivent mettre leurs productions scientifiques au service de toutes et tous !

    Ce qui est possible chez Inria l’est-il plus largement dans d’autres institutions et dans la communauté de recherche au sens large ? Cette semaine de l’open access est-elle celle du conservatisme vis-à-vis des modèles existants ou celle de la créativité et du courage ?

    Laurent Romary, Inria.

    Pour ce qui est de la Loi sur la République numérique, Binaire soutient la proposition d’Inria.

    (*) Modèle hybride : la revue est diffusée de façon traditionnelle sur abonnement, mais l’auteur d’un article peut également payer pour que celui-ci soit disponible en accès libre. Les chercheurs paient donc deux fois : pour publier et pour accéder.

    Pour aller plus loin :

     

  • Christine Paulin et les Logiciels Zéro Défaut

    Nous avons tous été exposés à des bugs, des programmes informatiques qui bloquent ou ne fonctionnent pas comme prévu. Des informaticiens s’attaquent à ce problème essentiel et Christine Paulin-Mohring, professeur à l’Université Paris Sud, en fait partie. Elle a reçu récemment le prestigieux prix ACM Software System, conjointement avec d’autres développeurs du logiciel Coq, et cette année le prix Monpetit de l’Académie des sciences pour ses travaux sur la vérification de logiciels. Binaire a profité de ces occasions pour demander à un spécialiste du domaine, Jean-Christophe Filliâtre, de nous parler de la recherche de Christine. Serge Abiteboul et Anne-Marie Kermarrec.

    Christine Paulin, ©Inria
    Christine Paulin-Mohring, © Inria

    Au début des années 80, Gérard Huet initie la construction d’un démonstrateur interactif de théorèmes à l’Inria Rocquencourt. Ce sera le logiciel Coq. C’est un assistant de preuve. Contrairement à un démonstrateur automatique de théorème, qui essaie de trouver par lui-même une preuve d’une proposition logique qu’on lui soumet, un assistant de preuve comme Coq s’appuie sur une coopération avec un humain qui lui propose des chemins pour arriver à une preuve. Un tel assistant de preuve est un outil incomparable, par sa capacité à vérifier les hypothèses logiques de l’humain et, quand il est aussi sophistiqué que Coq, à « remplir les trous », prouvant automatiquement des étapes parfois complexes. De tels assistants permettent de s’attaquer à des théorèmes au delà de ce qui est envisageable aujourd’hui avec des démonstrateurs purement automatiques.

    Thierry Coquand et Gérard Huet ont conçu la logique sous-jacente de Coq, le calcul des constructions. Christine Paulin, elle, a étendu cette logique avec une nouvelle construction, les types inductifs, et un mécanisme d’extraction qui permet d’obtenir automatiquement un programme zéro défaut à partir d’une preuve.

    Les types de données sont des composants essentiels des langages de programmation ; un entier ou un tableau d’entiers sont des exemples de types. La logique de Coq permettait déjà de raisonner sur un système de type assez riche. Christine Paulin l’a étendue pour pouvoir parler de « types inductifs ». Un type inductif est un type de données qui est défini en faisant référence au type que l’on est justement en train de définir. Par exemple, une liste de machins est soit une liste vide, soit un machin suivi d’une liste de machins. C’est un tour de force technique que d’avoir introduit de tels types dans le logiciel Coq et cela l’a considérablement enrichi. Grâce à cela, des résultats mathématiques majeurs ont pu être vérifiés avec Coq. Ainsi, Georges Gonthier et son équipe ont pu valider le théorème des quatre couleurs, qui dit que toute carte peut être coloriée avec quatre couleurs uniquement, en assurant que deux régions contigües reçoivent toujours deux couleurs distinctes, et plus récemment le théorème de Feit-Thompson, un résultat de théorie des groupes dont la preuve tient sur plus de deux cent cinquante pages.

    Une contribution essentielle de Christine Paulin au logiciel Coq est un mécanisme par lequel une preuve vérifiée par Coq peut être automatiquement convertie en un programme zéro défaut. Si par exemple on a fait la preuve que tout entier pair est le double d’un autre entier, alors on obtiendra automatiquement un programme qui calcule cet entier, c’est-à-dire un programme qui divise par deux. Par ce mécanisme, le logiciel Coq peut être utilisé pour vérifier des logiciels. Xavier Leroy a du reste développé avec Coq un compilateur(*)  du langage C, CompCert, qui est zéro défaut.

    Plus généralement, grâce à ces travaux et ceux de Christine en particulier, il est possible d’obtenir un programme qui résout un problème potentiellement très complexe et dont on est certain qu’il est garanti conforme à ses spécifications. Les exemples ne manquent pas pour illustrer à quel point il est important qu’un programme informatique fasse exactement ce pour quoi il a été conçu : on imagine aisément l’étendue des problèmes qui découleraient d’un Airbus, d’une banque ou d’une centrale nucléaire qui « buguent ».

    Coq est développé depuis plus de trente ans au sein d’équipes de recherche françaises, mobilisant des talents chez Inria, au CNRS, à l’École Polytechnique, à l’ENS Lyon et dans des universités comme Paris Sud et Paris Diderot. L’impact de Coq sur la communauté scientifique est immense. (Le logiciel Coq a reçu en 2013 le prix ACM SIGPLAN in Programming Languages, un prix international prestigieux.) Christine Paulin a contribué de façon essentielle au logiciel Coq et à son succès.

    Jean-Christophe Filliâtre, Université Paris Saclay

    (*) Un compilateur C est un programme informatique qui transforme un code source écrit en C, en langage machine de manière à ce qu’un ordinateur, dont la langue maternelle n’est pas le C mais le binaire (un ordinateur comprend des 0 et des 1), puisse l’exécuter.