Science et Technique

Quelques remarques de Maurice Nivat
 

   La technique qui est l'action sur le réel peut-elle se passer de la science qui est l'effort de comprendre le réel, de l'expliquer et d'en prédire le comportement ?

   Et réciproquement peut-on concevoir une science sans technique ?

   Le module d'informatique de la classe de seconde devrait être l'occasion d'amener les élèves à une réflexion sur ce sujet, peu évoqué dans l'enseignement secondaire et généralement mal traité.

   Mais plus le temps passe, plus j'ai l'impression qu'il y a une incompréhension fondamentale de ce qu'est l'informatique et des raisons qui font qu'elle est en ce moment le principal facteur d'innovation dans de très nombreux secteurs de l'activité humaine.

__________________________________

   Je tente ci-dessous de montrer sur un exemple ce qu'est la problématique informatique et comment on pourrait la faire appréhender par des élèves de seconde.

   Un problème typiquement informatique est celui du « bin packing » que j'ai envie d'appeler problème de l'emballage : un version statique peut être décrite de la façon suivante.

   Visiblement c'est un problème dont au moins l'énoncé est fort simple et compréhensible sans aucun mal par tous les élèves d'une classe de seconde. Il est aussi patent que c'est un problème pratique qui se pose avec des variantes qui ne sont pas essentielles à beaucoup de gens.

   Je proposerais volontiers qu'une part notable de l'horaire d'informatique soit consacrée à ce problème et à se poser la question : comment remplit-on une boîte au mieux, c'est à dire en laissant dans la boîte le minimum de place vide ?

   On va commencer à mettre un premier objet, que l'on pourrait choisir au hasard, mais on va simplement prendre le premier qui se présente, les objets étant supposés rangés dans un certain ordre, puis on en cherche un deuxième qui veut bien rentrer à côté du premier, puis un troisième... À chaque étape, on parcourt la liste des objets qui sont rangés dans un certain ordre et on met le premier qui veut bien rentrer dans la boîte en train d'être remplie.

   Pour ranger tous les objets, quand on a rempli une boîte, on commence à en remplir une autre et ainsi de suite. Voilà une méthode simple et simple à décrire en français.

   Elle appelle cependant de nombreux commentaires : on n'est pas du tout sûr que chaque boîte, à commencer par la première, est remplie au mieux et de toute façon nous n'avons pas suffisamment décrit comment nous remplissons les boîtes. Des exemples permettent de s'assurer facilement, que le coefficient de remplissage de chaque boîte peut varier énormément selon l'ordre dans lequel on y fait rentrer les objets.

   On peut donc extraire du problème général de l'emballage un sous problème : ranger au mieux dans une boîte rectangulaire des objets rectangulaires donnés ; visiblement l'ordre dans lequel on les met importe ainsi que le façon de les mettre.

   C'est le problème du sac à dos, bien connu de tous les jeunes, un peu stylisé puisque dans la pratique le sac à dos est un volume qui n'est pas cubique et les objets que l'on y met ne sont pas cubiques non plus ; et en plus au lieu de se poser le problème en trois dimensions on se le pose en deux dimensions seulement. Tout le monde est à peu près d'accord sur la méthode : on met d'abord dans le sac les objets les plus gros que l'on ait à y mettre, sauf que si l'on voit un trou dans lequel on peut glisser un petit objet on en profite.

   Fort bien, agissons : il n'est pas difficile de montrer sur des exemples que cette méthode ne conduit pas toujours au meilleur remplissage. On peut en particulier se focaliser sur le problème particulier de remplir exactement, quand cela est possible, la boîte avec les objets rectangulaires donnés, problème de pavage et ceci est une excellente occasion de faire du « back tracking » ou « retour arrière » consistant à essayer toutes les façons possibles de disposer les petits rectangles dans les grands. C'est la méthode de base, pas très maligne, dont la mise en oeuvre nécessite seulement de définir un ordre sur les débuts de rangements des petits rectangles dans le grand afin de ne pas en oublier et de ne pas recommencer deux fois la même chose. C'est aussi l'occasion d'aborder la difficulté du problème posé et de constater que la solution du problème est potentiellement exponentielle en le nombre de petits rectangles, et de dire aux élèves que toutes les méthodes connues sont exponentielles, que l'on est en présence d'un problème NP-difficile, même NP-complet (en ce sens que si l'on trouvait un moyen de résoudre ce problème en temps polynomial, ce sont des quantités d'autres problèmes qui seraient alors résolus en temps polynomial). La technique du retour arrière consistant à faire tous les essais possibles est beaucoup plus intéressante qu'on ne le croit car elle peut même être assez performante si l'on s'aperçoit assez tôt qu'un essai va être infructueux et on l'arrête dès que l'on s'en aperçoit : toutes les remarques sont bonnes pour ce faire et les élèves peuvent faire preuve là à la fois de bon sens (s'il est patent qu'un essai que l'on est en train de faire ne peut aboutir) et d'imagination en faisant des remarques plus subtiles.

   Restons un moment avec ce problème en forme de casse-tête puisque la solution exacte peut être très difficile à trouver ; on peut se poser diverses questions :

• trouver des méthodes qui, si elles ne marchent pas toujours, marchent souvent, ou dans la plupart des cas, ce que nous appellerons des « heuristiques », par exemple mettre d'abord les plus grands des petits rectangles, ou bien tapisser d'abord au mieux le fond de la grande boîte en évitant que le profil supérieur de la figure formée par les petits rectangles accolés qui garnissent le fond de la grande boîte soit trop « irrégulier » (à vrai dire, on peut laisser là totalement libre cours à l'imagination des enfants, et ils en ont beaucoup, surtout quand il s'agit d'un problème très concret comme celui-ci) ;

• réfléchir à ces heuristiques pour tenter de les comparer et de pouvoir en déclarer certaines « meilleures » que d'autres, en donnant peut-être un sens précis à « meilleur ». On peut certainement dire H1 meilleure que H2 si H1 trouve la solution chaque fois que H2 la trouve et la trouve aussi dans au moins un cas où H2 ne la trouve pas : peut-on exhiber deux heuristiques H1 et H2 telles que H1 soit meilleure que H2 en ce sens ?

   Nous sommes là en pleine informatique sans qu'il ait été vraiment question d'ordinateurs de programmation ni de logiciel. Évidemment, l'on s'apercevra très vite que, à la main, on ne peut traiter que des exemples ridiculement petits, une dizaine de petits rectangles à manipuler pour en recouvrir exactement un grand exige déjà beaucoup de patience. Mais les ordinateurs sont là pour cela : il n'est pas difficile de construire un logiciel permettant d'avoir sous les yeux en permanence le début d'un remplissage, la liste des objets encore à mettre et de disposer un objet que l'on choisit, que l'on fait tourner éventuellement avec la souris et que l'on transporte toujours avec la souris à l'emplacement que l'on souhaite lui faire occuper. Ce même logiciel peut permettre de définir une stratégie de remplissage et de laisser l'ordinateur la mettre en oeuvre tout en observant tout ce qu'il fait, ou encore de faire exécuter par l'ordinateur des vérifications pour s'assurer que le début de remplissage n'est pas déjà voué à l'échec.

   Les détracteurs de la programmation pensent que celle ci se fait toujours ab ovo, en partant de rien d'autre que le jeu d'instructions qui existent dans un langage de programmation universel, mais rien n'est plus faux, la programmation est ce qu'on veut qu'elle soit, et s'agissant d'un problème comme celui que nous décrivons on peut choisir des instructions élémentaires adaptées qui enlèvent à la programmation tout ce qu'elle peut avoir d'arbitraire et de fastidieux tout en lui conservant l'essentiel qui fait tout son intérêt : comment décrit-on une opération complexe comme suite d'opérations élémentaires ?

   Si l'on revient à notre problème d'emballage, il nous reste beaucoup de questions à aborder. Nous venons de nous focaliser sur le remplissage d'une boite, problème en soi difficile. Que gagnerait-on à remplir plusieurs boîtes simultanément, prenant les objets dans l'ordre où ils se présentent et ayant à notre disposition plusieurs boîtes à divers stades de remplissage plus un nombre potentiellement illimité de boîtes vides. Nous pouvons tenter plusieurs stratégies : le « first fit » ou l'on met l'objet dans la première boite dans laquelle il veut bien rentrer, et le « best fit » où pour chaque objet l'on cherche la boite dans laquelle il rentre « au mieux » (notion à définir plus précisément) ? Comment comparer ces deux stratégies et choisir. Avant tout savant calcul (l'on peut faire beaucoup de savants calculs à ce sujet et beaucoup ont été faits et publiés) on peut procéder à des simulations, engendrer des suites aléatoires d'objets à ranger, mettre en oeuvre les deux stratégies et regarder dans l'un et l'autre cas le nombre de boîtes qui se sont révélées nécessaires. Le best fit aboutit généralement à un nombre de boîtes plus faible mais il a évidemment un coût en temps ; pour chaque objet rangé on passe du temps à rechercher la boite où il rentre le mieux. Si bien que le choix entre les deux ne peut avoir de sens que si interviennent d'autres paramètres : on devra mettre en regard le coût du rangement et le coût de l'utilisation des boîtes, que l'on peut imaginer expédiées à un certain coût unitaire.

   Mon exemple, que j'aurais pu choisir parmi cent autres, est là pour montrer qu'un problème très simple, qui se comprend de soi, qui ne nécessite que des connaissances très faibles et qui est à l'évidence lié à une activité, le rangement, aussi utile pratiquement que répandue devient grâce à l'informatique un sujet de développements nombreux aussi bien techniques que scientifiques. David Johnson, qui a consacré sa vie à ce problème comme chercheur aux Bell Laboratories, est le coauteur du livre Computers and Intractability qui a fondé en 1979 l'étude des problèmes dits NP-difficiles ou NP-complets à la résolution desquels travaillent en permanence plusieurs dizaines de milliers de chercheurs et ingénieurs à travers le monde. Beaucoup de ces problèmes, de nature discrète et combinatoire revêtent une importance cruciale pour nombre d'entreprises, que ce soit les problèmes d'emploi du temps (utilisation au mieux du temps de travail d'ouvriers et employés), de partage de ressources (utilisation optimale d'un parc de machines) ou d'ordonnancement (échelonnement dans le temps, avec des possibilités de simultanéité des tâches à accomplir pour mener à bien un chantier, par exemple dans le BTP).

   Je crois avoir montré que l'on peut sans peine amener les élèves d'une classe de seconde, jeunes de 15 ou 16 ans, à réfléchir à un tel problème et à exercer leur imagination aussi bien que leur faculté de raisonnement, ceci grâce à ce que j'appellerais la méthode incrémentale qui est très typiquement informatique ; on part d'une solution pratiquement évidente, une recherche de la solution si elle existe par exhaustion, c'est à dire examen de toutes les possibilités, et on l'affine progressivement en faisant et implémentant des remarques qui peuvent aller de remarques de simple bon sens à des remarques fort subtiles et pas du tout évidentes, pour rendre plus rapide et plus efficace la recherche de la solution. Il s'agit bien d'une démarche scientifique que n'aurait pas reniée Descartes, consistant à aller du simple vers le compliqué. Un bon enseignement de l'informatique s'attachera en particulier à préciser à chaque étape de ce processus incrémental ce que l'on gagne en temps et en efficacité tout en s'assurant que la méthode améliorée reste valide, c'est-à-dire trouve bien la solution si elle existe, ou si l'on cherche une solution approchée, fournit bien une solution assez voisine du résultat optimal.

   Je pense avoir aussi montré qu'un cours sur le « bin packing » ne ressemblera pas aux cours que l'on peut donner dans d'autres domaines des sciences qui sont plus descriptives et s'appuient sur des faits plus nombreux (physique, chimie, biologie) ou plus déductives comme les mathématiques telles qu'elles sont traditionnellement enseignées en France. L'informatique est par essence constructive : on reconnaît un but à atteindre, on dispose d'un jeu d'opérations élémentaires (au demeurant parfaitement arbitraire) et l'on cherche à atteindre ce but par une suite d'opérations élémentaires,

   L'informatique est vraiment la science de la décomposition d'opérations complexes en opérations simples.

__________________________________

   En cinquante ans d'existence, à peine, l'informatique s'est imposée comme un outil universel que tout le monde utilise mais aussi comme un facteur de progrès et d'innovation dans un très grand nombre de secteurs : par exemple c'est en les truffant de puces électroniques que les constructeurs d'automobiles améliorent aussi bien la fiabilité ou la sécurité que la consommation énergétique ou les émissions de CO₂ de nos voitures. On n'imagine plus un engin roulant, volant ou flottant dont la bonne marche ne soit en permanence surveillée par un grand nombre de capteurs reliés à un ordinateur qui signale, ou même corrige de lui-même, une anomalie dès qu'elle apparaît. Certes ce sont les ordinateurs qui permettent d'effectuer ce contrôle permanent mais c'est une réflexion systématique sur les fonctions confiées à telle ou telle partie d'un système complexe comme une auto ou un avion qui conduit à leur informatisation totale ou partielle et à une amélioration.

   Pour être honnête, ce sont de grands logiciens du début du vingtième siècle, Gödel, Church, Kleene, Markov, Turing qui ont entamé la réflexion sur l'algorithmique avant l'apparition des premières machines à calculer modernes (il y avait quand même un grand essor des machines mécanographiques, des trieuses aux caisses enregistreuses qui a joué un grand rôle dans l'avènement de l'informatique vers 1940) à l'aide de modèles abstraits. Mais cet effort de réflexion s'est généralisé dès que sont apparues les premières machines, pourtant ô combien rudimentaires par rapport aux PC actuels et c'est cette réflexion originale et neuve qui a abouti à tant d'innovations dans tant de secteurs de l'activité humaine ainsi qu'à la constitution du corps de concepts et de méthodes que l'on peut à bon droit appeler Science Informatique. Il faut bien voir que cette science n'est en rien limitée au domaine numérique mais s'étend à tous les domaines où des opérations complexes doivent être réalisées comme suite d'opérations simples : un de ces domaines dont nul ne contestera la très grande utilité est l'aide aux handicapés où l'on ne compte plus les mécanismes qui ont été mis au point pour suppléer aux fonctions que leur handicap empêche d'effectuer normalement. Et quand on lit aujourd'hui des ouvrages de neurosciences, tel celui de Stanislas Dehaene sur Les neurones de la lecture, on est surpris de constater à quel point ils ressemblent à des ouvrages d'algorithmique : car notre cerveau est une espèce de machine fort efficace mais fort complexe dont une fonction compliquée comme la lecture se décompose en une multitude de petites opérations effectuées par un très grand nombre de neurones entre la rétine qui perçoit l'image et les organes de la parole qui traduisent le signe écrit en son.

   Je ne comprends absolument pas pourquoi l'informatique n'est pas systématiquement enseignée à tous les enfants dans nos collèges et lycées. Il ne s'agit évidemment pas plus de faire de tous les enfants des informaticiens que de faire de tous les enfants des mathématiciens en leur enseignant les rudiments de maths que l'on juge nécessaire de donner à tous. Il s'agit de les faire réfléchir à des modes de pensée et d'actions qui ont désormais envahi tous les domaines de la connaissance, de les faire réfléchir à ce qui est le coeur de l'activité informatique, la décomposition d'opérations complexes en opérations simples et la description précise (peu importe le langage choisi) de telles suites d'opérations élémentaires. De leur donner une idée de ce que les ordinateurs et les logiciels dont ils sont munis sont capables de faire et de ce qu'ils ne peuvent pas faire, connaissance qui parait désormais nécessaire à tout le monde : littéraires, juristes, artistes, médecins, scientifiques, décideurs comme exécutants. Au nom de quoi priver nos jeunes d'une connaissance qui doit les accompagner toute leur vie (il semble improbable que l'informatique s'arrête !) et leur permette de mieux comprendre le monde qui les entoure donc de s'y sentir mieux et quelle que soit leur activité professionnelle future d'y être plus efficaces.

Mars 2009.

Maurice Nivat
Membre correspondant de l'Académie des Sciences

___________________
Association EPI
Mars 2009