décembre 2015 – binaire

28 décembre 201516 décembre 2015

Raspberry pi : la petite histoire d’une grande idée

Le Raspberry Pi (prononcé comme « Raze » « Berry » « Paille » en anglais) est un petit ordinateur de la taille d’une carte bancaire. Il a été conçu par une fondation éducative à but non-lucratif pour faire découvrir le monde de l’informatique sous un autre angle. C’est Alan, franco-irlandais qui nous raconte cette belle histoire. Charlotte Truchet et Pierre Paradinas.

Le récemment lancé « PiZero » : 60 x 35mm : commercialisé en France pour €8,90 Crédit Photo : Alex Eames – RasPi.TV

Une fracture entre informatique et société

Au milieu des années 2000, Eben Upton de la Faculté des Sciences Informatiques de l’Université de Cambridge (« Computer Science Lab ») en Angleterre s’est rendu compte d’un gros problème. Avec ses collègues, ils ont observé un déclin très marqué dans le nombre de candidats se présentant pour poursuivre des études en informatique. Entre l’année 1996 (année de sa propre entrée « undergraduate » à Cambridge) et 2006 (vers la fin de son doctorat), les dossiers de demande pour accéder à la Faculté se sont réduits de moitié. Le système de sélection britannique des futurs étudiants est basé sur des critères de compétition, compétence, expérience et des entretiens individuels. Eben, qui avait tenu le rôle de « Directeur des Études » également, était bien placé pour remarquer une deuxième difficulté. Au-delà du « quantitatif », les candidats qu’il rencontrait, malgré leur grand potentiel et capacités évidentes, avaient de moins en moins d’expérience en matière de programmation. Quelques années plus tôt, le rôle des professeurs était de convaincre les nouveaux arrivants en premier cycle universitaire qu’ils ne savaient pas tout sur le sujet. A l’époque de la première « bulle internet », beaucoup parmi eux avait commencé leur carrière d’informaticien dès leur plus jeune âge. Ils étaient familier avec plusieurs langages allant des « Code machine » et « Assembleur » (les niveaux les plus proches de la machine) jusqu’aux langages de plus haut niveaux. Au fil des années, cette expertise était en berne, à tel point qu’autour de 2005, le candidat typique maîtrisait à peine quelques éléments des technologies de l’internet, HTML et PHP par exemple.

En parallèle, les membres du monde académique anglais étaient bien conscients de la nécessité croissante pour l’industrie, et la société plus globalement, d’avoir une population formée à la compréhension du numérique. Le numérique était désormais omniprésent dans la vie quotidienne. Et ce sans parler des besoins spécifiques en ingénierie et sciences. De façon anecdotique, les cours de TICE à ce moment-là étaient souvent devenus des leçons de dactylographie et d’utilisation d’outils bureautiques. Bien que ce soit important, le numérique ne pouvait pas se résumer à ça. Face à ce dilemme, Dr Upton et ses autres co-fondateurs de la Raspberry Pi Foundation se posaient deux questions : pourquoi en est-on arrivé là et comment trouver une solution pour répondre à leur besoin immédiat, local (et peut-être au-delà) ?

Comprendre la cause avant de chercher le remède

L’explication qu’ils ont trouvée était la suivante. Dans les années 80, sur les machines de l’époque, on devait utiliser des commandes tapées dans une interface spartiate pour faire fonctionner, et même jouer sur les ordinateurs. Par exemple pour moi, c’était un « BBC Micro » d’Acorn en école primaire en Irlande comme pour Eben chez lui au Pays de Galles. C’était pareil en France, avec des noms comme Thomson, Amstrad, Sinclair, ou Commodore,… qui rappellent des souvenirs de ces années-là. Depuis cette date, nous étions passés à des ordinateurs personnels et consoles de jeu fermés et propriétaires qui donnaient moins facilement l’accès au « moteur » de l’environnement binaire caché sous le « capot » de sur-couches graphiques. Bien que ces interfaces soient pratiques, esthétiques et simples à l’utilisation, elles ont crée une barrière à la compréhension de ce qui se passe « dans la boîte noire ». Pour tous, sauf une minorité d’initiés, nous sommes passés d’une situation d’interaction avec une maîtrise réelle et créative, à un fonctionnement plutôt de consommation.

Quand une solution permet de changer le monde

Leur réponse à ce problème a été de concevoir une nouvelle plate-forme informatique accessible à tous autant par sa forme, que par son prix, et ses fonctionnalités. L’idée du Raspberry Pi est née et le produit fini a été lancé le 29 février 2012.

Le Raspberry Pi est un nano-ordinateur de la taille d’une carte bancaire (Modèle 2 : 85mm x 56.2mm). Le prix de base, dès le début, a été fixé à $25 USD (bien que d’autre modèles existent à ce jour de $5 à $35). Le système d’exploitation conseillé est l’environnement libre et gratuit GNU/Linux (et principalement une « distribution » (version) dite Raspbian). Le processeur est d’un type « ARM » comme trouvé dans la plupart des smartphones de nos jours. Tout le stockage de données se fait par défaut par le biais d’une carte Micro SD. L’ordinateur est alimenté par un chargeur micro-USB comme celui d’un téléphone portable. Le processeur est capable de traiter les images et vidéos en Haute Définition. Il suffit de le brancher sur un écran HDMI ou téléviseur, clavier, souris par port USB et éventuellement le réseau et nous avons un ordinateur complet et fonctionnel. Avec son processeur Quad Cœur 900 Mhz et 1 Go de mémoire vive, le Modèle 2 est commercialisé en France aux alentours d’une quarantaine d’Euros. A la différence de la plupart des ordinateurs en vente, la carte comporte 40 broches « GPIO » (Broches/picots d’Entrée-Sortie générale). C’est une invitation à l’électronique et l’interaction avec le monde extérieur. En quelques lignes de code, l’informatique dite « physique » devient un jeu d’enfant. Brancher résistance et une DEL et un bouton poussoir en suivant un tutoriel et les enfants découvrent immédiatement des concepts de l’automatisation et de robotique. C’est assez impressionnant que ce même petit circuit imprimé, que l’on peut facilement mettre entre les mains d’un enfant de 5 ans, est de plus en plus utilisé dans des solutions industrielles embarquées et intégrées.

Le nom « Raspberry Pi » vient du mot anglais pour la framboise (les marques de technologie prennent souvent les noms d’un fruit) et de « Python », un langage de programmation abordable, puissant et libre. Au début les inventeurs pensaient peut-être dans leur plus grands rêves vendre 10,000 unités. A ce jour, c’est bien plus de 6 millions de Raspberry Pi qui ont été vendus dans le monde entier. En se consacrant initialement 100% de leurs efforts en développement matériel aux cartes elles-mêmes, la Fondation a fait naître à leur insu tout un écosystème autour de la création d’accessoires et périphériques. Les « produits dérivés » vont de toute sorte de boîtier jusqu’à divers cartes d’extension pour tout usage imaginable.

Alan_McCullagh-Piano_HAT — Le Piano HAT : une carte d’extension pour apprendre à s’amuser en musique, avec un boitier Pibow coupé Crédit Photo : Pimoroni.com

De plus, ils ont su créer d’autres emplois « chez eux » grâce à l’ordinateur – aujourd’hui les cartes sont fabriqués « Made in Wales » (dans une usine de Sony au Pays de Galles). Il existe aussi un communauté global de passionnés de tout âge et tout horizon qui promeuvent la pédagogie numérique, réalisent des projets, organisent des événements et assurent de l’entre –aide autour de la « Framboise π« . La France n’est pas une exception avec pas mal d’activité dans l’Hexagone. La barrière initiale de la langue anglaise joue sans doute un rôle dans son manque de notoriété et utilisation par un plus grand publique chez nous – pour l’instant ce bijou technologique reste en grande partie le domaine des technophiles/ »geeks » et des lycées techniques.

Éducation

Le succès commercial fulgurant du Raspberry Pi fait oublier parfois que le but principal de la Fondation reste axé sur l’éducation. L’argent gagné à travers les ventes est réinvesti dans des actions et des fonds permettant de faire avancer leurs objectifs. Ce dernier temps, la Fondation a pu engager des équipes de personnes intervenant sur divers projets et initiatives un peu partout dans le monde. Ça concerne l’informatique, mais pas seulement. Dans le monde anglo-saxon, on parle souvent de « STEM », voire « STEAM » – acronyme pour la promotion des Sciences, Technologie, Ingénierie (Engineering), les Arts et Mathématiques. En France, le Raspberry Pi pourrait bien STIM-uler plus d’intérêt dans ces disciplines aussi !

Utilisation

Les applications potentielles de cet outil sont sans fin. Un petit tour d’internet laisse pas de doute sur les possibilités. Sortie de sa boîte, ça permet une utilisation en bureautique avec Libre Office, accès internet avec un navigateur web, l’apprentissage de la programmation avec Scratch, Python et Minecraft Pi ou Ruby et Sonic Pi. Plus loin il existe tout l’univers d’utilitaires libres et gratuits sous GNU/Linux.

Pour donner quelques exemples rapides intéressants :

On peut créer son centre média centre avec OSMC.
On peut faire du « retrogaming » avec Recalbox.
On peut concevoir son Robot.
On peut prendre des photos de la Stratosphère.
On peut construire sa propre Station Météo.
On peut surveiller à distance son Poulailler « connecté ».

Et enfin, on peut même envoyer ses expériences scientifiques dans l’Espace ! Dans l’esprit de la récente semaine d’une « Heure de Code« , dans le projet AstroPi, deux Raspberry Pi viennent d’être envoyés sur la Station Spatiale Internationale embarquant des capteurs et du code crée lors d’un concours par des enfants de primaire et secondaire en Grande Bretagne. Ça fait rêver !

Alan_McCullagh-Astro_Pi — Astro Pi : un concours pour des jeunes en Grande Bretagne pour envoyer leur Code sur l’ISS (Station Spatiale Internationale) Crédit Photo : Fondation Raspberry Pi {Artiste : Sam Adler}

Comme dit François Mocq, auteur et blogueur de « Framboise 314.fr« , il y a bien une limitation à ce que nous pouvons faire avec un Raspberry Pi. C’est notre imagination !

Cet article a été écrit via un Raspberry Pi.

Pour plus d’information, rendez-vous sur « http ://raspberrypi .org » (site officiel de la Fondation – anglophone) et/ou « http ://framboise 314.fr » (notre référence francophone).

Alan Mc Cullagh (Club Code France)

27 décembre 201521 décembre 2015

Peut-on avoir confiance dans le vote électronique ?

Véronique Cortier est une spécialiste de la vérification qui a déjà écrit plusieurs articles passionnants pour Binaire, notamment sur le vote électronique. Elle intervient cette fois au Café techno d’Inria Alumni.

Café techno : Inria Alumni, en partenariat avec NUMA et le blog binaire, vous invite à débattre avec Véronique Cortier, Cnrs, Loria, le Lundi 18 janvier 2016, de 18:30 à 20:30.

NUMA Sentier, 39 rue du Caire, 75002 Paris

Peut-on avoir confiance dans le vote électronique ?

L’irruption des scrutins par voie numérique (on parle de « vote électronique ») soulève de nombreux enjeux en termes de garanties de bon fonctionnement et de sécurité informatique : comment m’assurer que mon vote sera bien pris en compte ? Est-ce qu’un tiers peut savoir comment j’ai voté ? Puis-je faire confiance au résultat annoncé ? Ces questions sont parfaitement légitimes et les systèmes de vote électronique n’y apportent pas encore de réponse claire. Mais les mêmes questions se posent pour les scrutins plus classiques qui ont recours au « papier ».

Existe-t-il un système de vote idéal ?

Pour vous inscrire : numa

Serge Abiteboul

21 décembre 201518 décembre 2015

Jon McCormack, codeur créatif

Cet article est publié en collaboration avec TheConversation.

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 !

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)

18 décembre 201518 décembre 2015

Drôle de drones

« C’est notamment grâce aux technologies de l’analyse d’images et de la vision
par ordinateur que Delair-Tech pourra devancer ses compétiteurs ».
Olivier Faugeras, chercheur Inria Sophia, Membre de l’Académie des Sciences.

Contrairement aux drones grand public les plus répandus avec hélice, les drones professionnels de Delair-tech ressemblent à des avions miniatures. On retrouve dans le monde des drones la même distinction qu’entre hélicoptère et avion. L’avantage des drones à voilure fixe (et pas tournante), c’est leur autonomie qui leur permet de parcourir de grandes distances et de couvrir ainsi de larges zones.

L’agriculture. A cause de la plus grande autonomie des drones à voilure fixe, l’un de leurs marchés les plus prometteurs n’est autre que l’agriculture. Un drone de Delair-tech permet par exemple de détecter depuis le ciel les parcelles d’un champ qui ont besoin d’azote. « La société était très orientée hardware au départ, mais nous travaillons de plus en plus sur des logiciels, notamment de traitement d’image » explique Benjamin Benharrosh, cofondateur de la startup. Pour analyser la quantité d’azote présente localement dans un champ, leurs logiciels permettent de réaliser une carte multispectrale et à partir de cela de calculer des indices biophysiques en différents points. Dans le cadre d’un projet de recherche sur quatre ans lancé en partenariat notamment avec l’INRA, Delair-tech cherche aussi à détecter des maladies des cultures, les besoins en désherbage, ou à permettre de mieux contrôler l’hydratation.

Les mines et le BTP. Si l’agriculture est un domaine porteur pour Delair-tech, le plus développé pour l’instant reste celui des mines et du bâtiment. « Les géomètres sont habitués à gérer des révolutions technologiques fréquentes. Beaucoup d’entre eux utilisent déjà des drones. » explique Benjamin Benharrosh. Delair-tech les aide par exemple à reconstituer un modèle 3D du terrain. Les drones peuvent aussi participer à la surveillance et l’inspection de réseaux comme des lignes électriques ou des voies ferrées. Des drones permettent de détecter par exemple de la végétation qui s’approche trop près de lignes électriques, ou des pelleteuses qui creusent un terrain alors qu’un oléoduc passe en-dessous. Si reconnaître de la végétation est une tâche relativement simple à l’aide de marqueurs de chlorophylle, pour reconnaître une pelleteuse, il faut avec des algorithmes de reconnaissance de formes ; c’est bien plus compliqué.

Dans le domaine de Delair-tech, les challenges sont très techniques. Pour obtenir l’autorisation de voler hors du champ visuel de l’opérateur, il a fallu construire un drone de moins de deux kilos. Cela écartait la solution simple qui consistait à combiner des composants du marché. Pour cela, la R&D de Delair-tech a dû monter en compétences dans des domaines aussi variés que les matériaux composites, les télécoms, les système embarqués, la mécanique. Une autre contrainte sérieuse est mentionnée par Benjamin Benharrosh : « La réglementation nous oblige à garder le contact avec le drone en permanence ». Une borne Wifi permet de garder ce contact jusqu’à une vingtaine de kilomètres. Et au delà, il faut installer des antennes relais.

La France est l’un des premiers pays au monde à avoir régulé les vols de drones hors vue. Le drone doit être léger, pour minimiser les risques en cas de chute. Il doit permettre un retour vidéo vers son opérateur, qui doit garder en permanence une communication avec lui. On ne peut pas par exemple passer par la 3G d’un opérateur, qui n’est pas considérée comme assez fiable. Le drone doit de plus inclure un système de défaillance permettant un retour forcé en cas de perte de contact, et d’un système de sécurité le conduisant à tomber avec peu d’énergie en cas de problème plus sérieux.

Pour être autorisé à réaliser des vols hors du champ visuel en France, un des premiers pays à avoir légiféré sur les drones hors vue, des drones de Delair-tech ont dû passer tous les tests exigés dans l’hexagone. Pourtant 75 % du chiffre d’affaire de la startup est réalisé à l’étranger dans les quelques pays ayant déjà mis en place une régulation… ainsi que dans ceux n’en ayant pas encore.

Le marché de Delair-tech est très compétitif. Les challenges sont techniques, principalement logiciels : étude topographique, génération et analyse de carte multispectrale, reconnaissance d’image… Ils sont loin d’être tous résolus avant que, par exemple, les drones de Delair-Tech puissent voler au dessus de 150m et se mêler au trafic aérien.

Serge Abiteboul, Marie Jung

Pour en savoir plus :

Vidéos de promo de Delair-tech sur Youtube
Notamment une opération anti braconnage en Tanzanie

16 décembre 201516 décembre 2015

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.

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.

Disponible chez l’éditeur : http://www.nouveau-monde.net/livre/?GCOI=84736100224280

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

11 décembre 201515 décembre 2015

La data et le territoire

Nous entamons, avec cet article, une collaboration avec theconversation.fr.

L’agriculture elle-aussi a été impactée par l’informatique. Dans le cadre des « Entretiens autour de l’informatique », Serge Abiteboul et Claire Mathieu ont rencontré François Houllier, Président directeur général de l’INRA, l’Institut National de Recherche en Agronomie. François Houllier raconte à Binaire les liens riches et complexes entre les deux disciplines, et ses inquiétudes autour du changement climatique.

François Houllier, PDG Inra — François Houllier, PDG de l’INRA

La gestion des ressources forestières

Monsieur Houllier, qui êtes vous ?
François Houllier : Au départ, je suis un spécialiste de l’inventaire et de la modélisation des ressources forestières. J’ai été chercheur dans ce domaine. Aujourd’hui, je suis président directeur général de l’INRA. J’ai rencontré l’informatique dès le début de ma carrière, avec, pour ma thèse de doctorat l’utilisation de bases de données pour le dénombrement et la mesure d’arbres à partir de photos aériennes et d’observations de terrain. A l’Inventaire Forestier National, j’ai développé des modèles de production de forêt pour simuler les évolutions de massifs forestiers à l’échelle de cinq, dix, vingt ou trente ans, grâce aux bases de données et aux ordinateurs. Dans les années 80, nous avons réalisé un service « Minitel vert » pour donner accès librement aux informations statistiques sur les bois et les forêts dans un département ou une région. J’ai aussi dirigé des laboratoires de recherche où l’informatique était très présente, par exemple le laboratoire AMAP à Montpellier qui a essaimé en Chine, à l’École centrale de Paris et à l’Inria avec des chercheurs qui travaillaient sur la modélisation de l’architecture des plantes, de leur topologie, de leur géométrie et de leur morphogenèse. Cela demandait de faire dialoguer des botanistes, des agronomes, des écologues et des forestiers ayant le goût de la modélisation, avec des chercheurs qui maîtrisent les méthodes statistiques, les mathématiques appliquées, l’informatique.

La modélisation mathématique et informatique a pris une place considérable en agronomie ?
FH : Pour les forêts, ma spécialité initiale, la modélisation est particulièrement importante. On inventorie les forêts à l’échelle nationale et on se demande quelles seront les ressources en bois et la part qui pourra être exploitée dans dix, vingt ou cinquante ans. Nous sommes sur des échelles de temps longues, où l’expérience passée aide, mais où nous devons nous projeter dans le futur. Il faut tenir compte des problèmes de surexploitation ou de sous-exploitation, utiliser les techniques de sondage et la télédétection pour acquérir massivement des données. Nous partons de toutes les données dont nous disposons et, avec des modèles, nous essayons de prédire comment les forêts vont évoluer. C’est un peu comme les études en démographie humaine. Les particularités pour les forêts, c’est que les arbres ne se reproduisent pas comme des mouettes ou des humains, et qu’ils ne se déplacent pas. Mais, même si nos modèles sont parfois un peu frustes, les entreprises qui investissent dans les forêts, notamment pour alimenter les scieries ou les papeteries, attendent des prédictions raisonnables pour rentabiliser leurs investissements qui sont sur du long terme.

Les changements climatiques et la COP21

Quand vous vous projetez ainsi dans l’avenir, vous rencontrez la question du changement climatique. Ce changement a un impact sur les forêts ?
FH : Quand j’ai commencé à travailler sur les forêts, à la fin des années 1980, la question du changement climatique ne se posait pas. J’ai rencontré le sujet à l’occasion d’un séminaire réalisé par un chercheur travaillait sur le dépérissement des forêts. Il avait trouvé un résultat alors invraisemblable : le sapin grossissait dans les Vosges comme il n’avait jamais grossi depuis un siècle, plus de 50% plus vite que le même sapin un siècle plus tôt. C’était d’autant plus imprévisible qu’au départ ce chercheur s’intéressait au dépérissement des forêts du fait de ce qu’on appelait les « pluies acides ». Son résultat a ensuite été confirmé. L’explication ? Ce n’était pas le climat en tant que tel, la pluviométrie ou la température même si leurs variations interannuelles ont des effets sur la croissance des arbres. Cela venait de différents facteurs, dont l’accroissement de la teneur en CO2 de l’air et surtout les dépôts atmosphériques azotés qui ont un effet fertilisant. Ce n’est pas simple de séparer les différents facteurs qui ont des effets sur la croissance des autres effets potentiellement négatifs du changement climatique. Ce changement climatique, forcément, va avoir des effets majeurs sur les forêts, des effets immédiats et des effets décalés. Par exemple, comme un chêne pousse en bonne partie en fonction du climat de l’année antérieure, il y a un effet d’inertie. Quand j’ai commencé mes recherches, nous considérions le climat comme une constante, avec des variations interannuelles autour de moyennes stables. Maintenant, ce n’est plus possible.

Cela nous conduit à l’impact du changement climatique sur l’agriculture…
FH : Nous avons des échelles de temps très différentes entre les forêts et, par exemple, les céréales. Prenons le blé et son rendement depuis un siècle. On observe une faible augmentation de 1900 à 1950, puis une forte augmentation, d’un facteur quatre environ, de 1950 à 1995, et puis… la courbe devient irrégulière mais plutôt plate. (Voir la figure.) Comment expliquer cette courbe ? Après 1950, les progrès viennent des engrais, de nouvelles pratiques de culture, et beaucoup de la génétique.

En amélioration génétique des plantes, ça se passe un peu comme dans le logiciel libre avec un processus d’innovation ouverte où chacun peut réutiliser les variétés précédemment créées par d’autres améliorateurs. Chaque année, les sélectionneurs croisent des variétés ; ils filtrent ces croisements pour obtenir de nouvelles variétés plus performantes. Cela prend une dizaine d’années pour créer ainsi une nouvelle variété qui est ensuite commercialisée sans pour autant que son obtenteur paie de royalties à ceux qui avaient mis au point les variétés parentes dont elle est issue. Le progrès est cumulatif.

En 1995, les généticiens avaient-il atteint le rendement maximal ? Pas du tout. Le progrès génétique a continué, et aurait dû entraîner une hausse des rendements de l’ordre de 1% par an. Alors pourquoi la stagnation ? Des modèles ont montré qu’environ la moitié du progrès génétique a été effacée par le réchauffement climatique et par la multiplication des événements climatiques défavorables, et l’autre moitié a été perdue du fait des changements de pratiques agricoles, notamment de la simplification excessive de l’agriculture, un effet beaucoup plus subtil. Il y a plusieurs décennies, on avait des rotations, avec des successions d’espèces par exemple entre le blé et des légumineuses, telles que le pois. Quand on arrête ce type de rotations, le sol devient moins fertile.

Vous voyez, ce n’est pas simple de comprendre ce qui se passe quand on a plusieurs facteurs qui jouent et dont les effets se combinent. Nous travaillons beaucoup dans cette direction. Nous utilisons des modèles prédictifs pour déterminer selon différents scénarios climatiques et selon les endroits du globe, si les rendements agricoles vont augmenter ou pas. Les bases écophysiologiques de ces modèles sont bien connues mais il y a beaucoup de facteurs : la qualité des terres et des sols, le climat et les variations météorologiques, les espèces et les variétés, les pratiques agronomiques et les rotations. La complexité est liée au nombre de paramètres qui découlent de ces facteurs. En développant de nouveaux modèles, on comprend quelles informations manquent, on se trompe, on corrige, on affine les paramètres. C’est toute une communauté qui collectivement apprend et progresse par la comparaison des modèles entre eux et par la confrontation avec des données réelles.

Ce que nous avons appris. Pour les 10 ans à 20 ans qui viennent, pratiquement autant de prédictions indiquent des augmentations que des réductions des rendements agricoles, au niveau global. Mais si on se projette en 2100, 80% des prédictions annoncent des diminutions de rendement. Même s’il y aura des variations selon les endroits et les espèces, la majorité des cultures et des lieux seront impactés négativement !

Cela pose de vraies questions. Pour nourrir une population qui croît, on doit accroître la production. On peut le faire en augmentant le rendement ; c’est ce qui s’est passé quand l’Inde a multiplié en cinquante ans sa production de blé par six sans quasiment modifier la surface cultivée. Ou alors on peut utiliser des surfaces supplémentaires, par exemple en les prenant sur les forêts, mais cela pose d’autres problèmes. La vraie question, c’est évidemment d’arriver à produire plus de manière durable. Et avec le changement climatique, on peut craindre la baisse des rendements dans beaucoup d’endroits.

Image satellitaire infra-rouge. IGN. Via INRA.

Le monde agricole s’intéresse beaucoup au big data. Comme ailleurs, cela semble causer des inquiétudes, mais être aussi une belle source de progrès. Comment voyez-vous cela ?
FH : Nous voyons arriver le big data sous deux angles différents, sous celui de la recherche et sous celui de l’agriculture.

Premier angle : la recherche, pour laquelle le big data a une importance énorme. Considérons, par exemple, l’amélioration génétique classique : on cherche à utiliser de plus en plus précisément la connaissance du génome des animaux et des végétaux en repérant des « marqueurs » le long des chromosomes ; ces marqueurs permettent de baliser le génome et de le cartographier. Les caractères intéressants, comme le rendement ou la tolérance à la sécheresse, sont corrélés à de très nombreux marqueurs. On va donc faire des analyses sur les masses de données dont on dispose : beaucoup d’individus sur lesquels on identifie la présence ou l’absence de beaucoup de marqueurs qu’on corrèle avec un grand nombre de caractères. L’objectif c’est de trouver des combinaisons de marqueurs qui correspondent aux individus les plus performants. On sait faire cela de mieux en mieux, notamment à l’INRA. Les grands semenciers le font aussi : ils investissent entre 10 et 15% de leurs ressources dans la R&D. Aujourd’hui, la capacité bioinformatique à analyser de grandes quantités de données devient un facteur limitant.

On peut aussi considérer le cas des OGM, avec le maïs. La tolérance à un herbicide ou la résistance à un insecte ravageur peuvent être contrôlées par un seul gène ou par un petit nombre de gènes. Par contre, le rendement dépend de beaucoup de gènes différents : des dizaines, voire des centaines. D’où deux stratégies assez différentes. Pour les caractères dont le déterminisme génétique est simple, on peut utiliser une approche de modification génétique ciblée, les fameux OGM. Pour les caractères dont le déterminisme est multifactoriel, l’approche « classique » accélérée par l’usage des marqueurs associés aux gènes est celle qui marche actuellement le mieux. Donc, pour disposer d’un fond génétique qui améliore le rendement, le big data est la méthode indispensable aussi bien en France, sans OGM, qu’aux Etats-Unis, avec OGM.

Deuxième angle : l’utilisation du big data chez les agriculteurs. Un robot de traite est équipé de capteurs qui produisent des données. Un tracteur moderne peut aussi avoir des capteurs, par exemple pour mesurer la teneur en azote des feuilles. Avec les masses de données produites, nous avons vu se développer de nouveaux outils d’analyse et d’aide à la décision pour améliorer le pilotage des exploitations. Mais ce qui inquiète le monde agricole, c’est qui va être propriétaire de toutes ces données ? Qui va faire les analyses et proposer des conseils sur cette base ? Est-ce-que ces données vont être la propriété de grands groupes comme Monsanto, Google, ou Apple ou les fabricants de tracteurs ? En face de cela, même les grandes coopératives agricoles françaises peuvent se sentir petites. Le contrôle et le partage de toutes ces données constituent un enjeu stratégique.

L’agriculteur connecté

Il ressort de tout cela que l’agriculteur est souvent très connecté ?
FH : Il reste bien sûr des zones dans les campagnes qui sont mal couvertes par Internet, mais ce n’est pas la faute des agriculteurs. Les agriculteurs sont plutôt technophiles. Quand les tracteurs, les robots de traites ou les drones sont arrivés, ils se sont saisis de ces innovations. Il en va de même avec le numérique. Les agriculteurs qui font de l’agriculture biologique sont eux aussi favorables au numérique. Les nouvelles technologies permettent aux agriculteurs de gagner du temps, d’améliorer leur qualité de vie, de réduire la pénibilité de certaines activités. Ils sont conscients des améliorations que les applications informatiques peuvent leur apporter.

Automate de caractérisation des plantes. INRA.

La data et le territoire

Ils sont connectés et solidaires ?
FH : Les agriculteurs ont l’habitude de partager des pratiques et des savoir faire, ou des matériels agricoles, et d’exprimer des formes de solidarité. Par exemple, dans un même territoire, ils échangent « par dessus la haie », c’est-à-dire qu’ils regardent ce qui se fait à côté et imitent ce qui marche chez leurs voisins. Dans le domaine de la sélection animale la recherche publique, l’INRA, travaille depuis longtemps avec les différents organismes qui font de l’insémination artificielle et qui sélectionnent les meilleurs animaux pour la production de lait ou de viande, par exemple. Les races bovines sont certes différentes mais certaines méthodes sont identiques, comme le génotypage qui consiste à déterminer tout ou partie de l’information génétique d’un organisme. Jusqu’à récemment, il existait une forte solidarité entre les différentes filières animales : d’une certaine manière, les progrès méthodologiques réalisés sur les races bovines dédiées à la production laitière bénéficiaient aux autres races puis ensuite aux ovins ou aux caprins.

Ces dernières années, l’arrivée de nouvelles formes d’analyse à haut débit, très automatisées, spécialisées, a induit des changements. Cela a conduit au développement d’activités concurrentielles. Par exemple, il y a des sociétés qui proposent des services de génotypage pour analyser des milliers de bovins en identifiant leurs marqueurs génétiques. Ça peut se faire n’importe où dans le monde, à Jouy-en-Josas, comme au Canada : il suffit d’envoyer les échantillons. Les solidarités territoriales ou nationales qui existaient sont en train de se fracturer sous les effets combinés de la mondialisation et du libéralisme. Elles sont en train de se défaire du fait de la compétition au sein de métiers qui se segmentent, et de la création d’opérateurs internationaux sans ancrage territorial. Regardez le big data : les données ne sont pas localisées ; elles ne sont pas ancrées dans un territoire ; les calculs se réalisent quelque part « dans le cloud ». C’est une cause de l’inquiétude actuelle de nos collègues des filières animales ou végétales : l’angoisse du big data ne vient pas de la technologie en tant que telle, mais plutôt de la perte d’intermédiation, de la perte du lien avec le territoire.

L’agronome et l’agriculteur

Dans d’autres sciences, la distance entre les chercheurs et les utilisateurs de leurs recherches est souvent très grande. On a l’impression en vous entendant que c’est moins vrai des agronomes.
FH : Ça dépend. Prenez un chercheur qui travaille sur les mécanismes cellulaires fondamentaux de recombinaison génétique. Il révolutionnera peut-être la sélection végétale dans vingt ans, mais il peut faire des recherches sur ce sujet sans rencontrer d’agriculteurs. Nous avons des recherches de ce type à l’INRA, mais nous assurons aussi une continuité avec des travaux plus en aval au contact du monde agricole. Le plus souvent, nous ne réalisons pas nous mêmes les applications ; cela peut être fait par des entreprises, par des instituts techniques dédiés ou par des centres techniques industriels, financés pour partie par l’État et pour beaucoup par des fonds professionnels. De tels instituts existent pour les fruits et légumes, pour les céréales, pour les oléagineux, pour l’élevage en général ; il en existe un spécifique pour le porc, et un pour la volaille. Nous collaborons avec eux.

Informatique et agriculture

Comment se passe le dialogue entre vos spécialistes d’agronomie et les informaticiens ?
FH : Nous avons de plus en plus de besoin de compétences en modélisation, en bioinformatique, en mathématiques appliquées, en informatique, avec des capacités à conceptualiser, à traiter des grands ensembles de données, à simuler… Quelles sont les compétences d’un chercheur qu’on embauche à l’INRA aujourd’hui ? Cela évolue, les métiers changent et on en voit naître de nouveaux. Mais il est clair que même dans des disciplines « anciennes » comme l’agronomie ou la physiologie, les jeunes chercheurs que nous recrutons doivent et devront avoir des compétences ou pour le moins une sensibilité affirmée pour l’informatique et le big data. Nous avons fait un exercice de gestion prévisionnelle des emplois et des compétences : il en ressort que beaucoup des nouveaux besoins exprimés relèvent du numérique au sens large. Nous nous posons sans arrêt ces questions : quelle informatique voulons-nous faire ou avoir en interne ? Que voulons-nous faire en partenariat, notamment avec Inria avec qui nous collaborons beaucoup ? Parmi les organismes de recherche finalisés et non dédiés au numérique, nous sommes l’un des rares à être doté d’un département de mathématiques et informatique appliquées, héritier du département de biométrie. Même si c’est le plus petit des 13 départements de l’INRA et si ce n’est pas notre cœur de métier, de telles compétences sont vraiment essentielles pour nous aujourd’hui.

Entretien recueilli par Serge Abiteboul et Claire Mathieu

SAS, un grand éditeur de logiciel américain spécialiste de la statistique, doit beaucoup à l’agriculture. Quand ce n’était encore qu’une startup de l’Université de Caroline du Nord, SAS a eu besoin de puissances de calculs. C’est le monde agricole, le service de recherche agronomique du ministère de l’agriculture des États-Unis, qui a fourni l’accès à des moyens de calcul. Ce n’est pas vraiment surprenant quand on sait que l’agriculture a été très tôt un objet d’étude privilégié des statisticiens et a donné lieu à beaucoup de développements méthodologiques originaux. Voir https://en.wikipedia.org/wiki/Maurice_Kendall

Dans le même ordre d’idée, c’est intéressant de savoir que c’est l’INRA qui a commandé l’un des premiers ordinateurs personnels équipés d’un microprocesseur, le premier Micral vers 1970. Il était destiné à des études de bioclimatologie dirigées par Alain Perrier. Voir https://en.wikipedia.org/wiki/Micral

10 décembre 201524 janvier 2017

Il était une fois l’Internet à la Cité des Sciences

Ce conte pour enfant, un spectacle « coup de cœur » de binaire, passe à la Cité des Sciences. Voir l’article de Valérie Schafer. Entrée libre dans la limite des places disponibles.

mardi 22 décembre – 14h & 16h30
mercredi 23 décembre – 14h & 16h30
jeudi 24 décembre – 14
mardi 29 décembre – 14h & 16h30
mercredi 30 décembre – 14h & 16h30
jeudi 31 décembre – 14

Et depuis : Mercredi 8 Février 2017 à 15h30 à la Gaité Lyrique

06 décembre 201505 décembre 2015

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	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.)
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.
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 :

Les graphes G₁ et G₂ 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 G₁, et 1 et 2 aussi dans G₂

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

etc.

En revanche, G₁ n’est pas isomorphe à G₃

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

Notons qu’il est plus difficile de convaincre quelqu’un que les graphes G₁ et G₃ 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 G₁ et G₂ 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 G₁ et G₂). 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 2^{log(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).

05 décembre 201520 mars 2024

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

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.

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.