MATHÉMATIQUES ET ALGORITHMIQUE EXEMPLES D'INTERACTIONS

Denis Monasse

Sujets

• Sciences formelles
• Algorithmes

Informations

• Publié par: Rue des écoles
• Date de parution: 01 janvier 2023
• Nombre de lectures: 40
• EAN13: 9782820806284
• Langue: Français

Extrait

MATHÉMATIQUES T ALGORITHMIQUE E E X E M P L E S D ' I N T E R A C T I O N S

Denis Monasse

© 2017, Epistemon ISBN : 9782820806284 Achevé d’imprimer en France par Dupli-Print (95) en janvier 2017 Dépôt légal : février 2017

Préface

L’informatique peutelle et doitelle s’enseigner ? Un enseignement d’informatique doitil entrer en compétition avec un enseignement de mathématiques ? Ces deux questions peuvent sembler aujourd’hui un peu saugrenues, et pourtant...

La réponse à la première ne fait plus débat, ou presque. L’informatique doit s’enseigner, pour de nombreuses et sérieuses raisons que l’on peut, schématiquement et donc un peu abusivement, synthétiser en un slogan « Programmer ou être programmé, il faut choisir ». A part quelques pseudointellectuels sur le retour qui croient pertinent d’opposer science et littérature, ou simplement codage et lecture, personne ne peut raisonnablement contester que l’enseignement des humanités et l’enseignement des sciences et des techniques se complètent et se confortent, et ne sont en rien antagonistes. Pour être tout à fait honnête, il n’est pas exclu qu’il reste encore quelques dinosaures dans d’obscurs bureaux de l’Education Nationale qui n’aient pas non plus compris la révolution informatique actuelle et ses conséquences. Cette cécité est en particulier liée à une incapacité à regarder autre chose que leur nombril et donc ce qui se passe dans beaucoup de pays du monde où l’enseignement des bases de l’informatique se fait de plus en plus tôt. Mais, heureusement, ces dinosaures sont, comme les animaux dont ils ont hérité du nom, en voie de disparition.

La réponse à la seconde question est quant à elle négative. Aucun argument rationnel n’op pose les mathématiques et l’informatique. Les activités menées à travers le monde, dans les laboratoires de recherche, publics ou privés, témoignent que leur conjonction est source d’in novation et de progrès. Elle permet le traitement de nombreux problèmes de modélisation et de simulation avec des conséquences extraordinaires dans la plupart des domaines, scienti fiques comme industriels. Ce sont aussi via des approches croisées, réunissant mathémati ciens, informaticiens ou biculturels que sont abordés aujourd’hui de nombreux sujets d’ac tualité. Le traitement d’images, la cybersécurité ou encore les fameuses « Big Data » en sont quelques exemples notoires. Mais, au delà de la formation de spécialistes capables de traiter ces sujets, la société numérique dans laquelle nous vivons impose de fournir à tout un cha cun, future citoyenne ou futur citoyen, les principales clés pour comprendre le monde qui l’entoure. Pour cela, un enseignement des bases de l’informatique et un enseignement des bases des mathématiques sont autant nécessaires l’un que l’autre.

Ces deux « évidences » (cela écrit avec un peu d’optimisme) sont pourtant assez récentes. Il y a une vingtaine d’années, au siècle dernier et même au millénaire dernier donc, les certitudes étaient souvent tout autre. Ainsi, un haut responsable de l’Education Nationale expliquait avec emphase, et une certaine condescendance, qu’on n’allait quand même pas créer une Agréga tion d’Informatique puisque l’on venait de refuser la création d’une Agrégation d’Hôtellerie (sic). Quel visionnaire ! Par ailleurs, de façon un peu corporatiste, un nombre non négligeable

4

de mathématiciens ne voyait pas, on peut le dire aujourd’hui car il y a prescription, l’arrivée d’un enseignement d’informatique d’un très bon œil, de peur qu’il conduise à réduire encore le volume des enseignements de mathématiques. Et pourtant, les informaticiens étaient les premiers à reconnaître que ce volume était trop faible et qu’un enseignement d’informatique devait aussi s’appuyer sur des bases solides en mathématiques.

L’évolution majeure des esprits en une vingtaine d’années repose sur beaucoup de facteurs complémentaires. La science informatique s’est développée à travers le monde, et fait mainte nant l’objet d’enseignements et de recherche dans toutes les universités et écoles scientifiques à travers le monde. Elle joue aussi un rôle essentiel dans de nombreux champs thématiques et permet de conduire des études pluridisciplinaires s’attaquant à des verrous, jugés jusqu’alors incassables. La numérisation de la société, déjà évoquée, a également largement contribué à faire bouger les mentalités. Mais cette évolution doit énormément aux pionniers, à ceux qui ont su lever le doigt, prendre des risques, tirer les sonnettes d’alarme et «mouiller le maillot» pour prêcher par l’exemple. Denis Monasse occupe une place de choix au Panthéon de ces pionniers. Déjà professeur renommé de mathématiques de classes préparatoires dans un des lycées les plus réputés, il aurait pu se satisfaire de continuer à former de brillants élèves dont quelques futurs mathématiciens illustres (clin d’œil du calendrier, il a été le professeur de Claire Voisin, membre de l’Académie des Sciences, et récompensée récemment en 2016 par la très prestigieuse médaille d’or du CNRS).

Denis Monasse a au contraire fait le choix, courageux et risqué, de se mettre en danger en choisissant d’enseigner dès la fin des années 1990 la toute nouvelle option informatique en fin introduite en classes préparatoires. Il a ainsi acquis « sur le tas » en quelques années une culture solide en informatique complétant à merveille celle qu’il avait déjà en mathéma tiques. Il a aussi eu la générosité, et aussi l’humilité, d’organiser chaque année un séminaire d’une semaine au CIRM (Centre International de Recherche en Mathématiques) à Luminy, destiné aux professeurs de classes préparatoires en charge de ces nouveaux enseignements d’informatique. Ce séminaire avait un double objectif et les a toujours car, si Denis Monasse a passé la main, ce séminaire continue son chemin. Se sont ainsi rencontrés des professeurs qui ont partagé leurs expériences, leurs découvertes et aussi leurs difficultés. Ce séminaire était aussi l’occasion de coursconférences de chercheurs en informatique venant compléter la formation et enrichir la culture de ces pionniers. La qualité des échanges entre les uns et les autres a produit d’excellentes et très fécondes relations professionnelles (et parfois aussi personnelles), elles demeurent souvent encore actives aujourd’hui. C’est dans ce cadre que j’ai connu Denis Monasse. J’ai eu le grand plaisir d’y faire d’abord moimême plusieurs coursconférences puis, plus modestement, de proposer de nouveaux intervenants.

Dans ces séminaires, Denis Monasse occupait plusieurs rôles, tous clés. Pionnier en chef, organisateur numéro 1 et conférencier multirécidiviste. Une de ses grandes spécialités a tou jours été de faire le pont entre ses deux grandes disciplines de cœur, les mathématiques dans lesquelles il était tombé tout petit et l’informatique qu’il avait apprivoisée un peu plus tard, mais avec autant de passion et de talent. En particulier, il faisait régulièrement des exposés dans lesquels il rendait les mathématiques effectives grâce à un traitement algorithmique à la fois rigoureux et élégant. Et cette effectivité rendait les mathématiques encore plus belles, illustrant à merveille leur complémentarité avec l’informatique, que j’ai déjà soulignée.

5

Aujourd’hui, Denis Monasse présente un ouvrage dont il m’a fait l’amitié de me proposer d’en écrire l’introduction, j’en tire une grande fierté. On y trouve plusieurs de ses confé rences qui sont ainsi mises à disposition du plus grand nombre. Je suis convaincu que tous les lecteurs potentiels, élèves de classes préparatoires ou de premiers cycles universitaires et, bien sûr, leurs professeurs mais également tout curieux de sciences (possesseur cependant d’une certaine culture mathématique et informatique), seront captivés par cet ouvrage comme l’étaient les auditeurs des conférences de Luminy. Et, parce que les sciences décrites dans les pages qui suivent, sont pratiques et effectives, j’invite toutes les lectrices (nous avons un cruel manque de femmes mathématiciennes et informaticiennes !) et tous les lecteurs à prendre leur clavier, à écrire les algorithmes, à les tester et même à les améliorer, les interactions mises en lumière par Denis Monasse constituent une activité vivante !

Et pour boucler la boucle, je ne résiste pas à appeler votre attention sur le fait que Denis Monasse fait un grand usage de Caml, un langage de programmation généraliste inventé par les chercheurs d’Inria, un organisme de recherche français parmi les plus performants sur la scène internationale et dont les deux domaines de spécialité sont précisément l’informatique et les mathématiques (appliquées) ! Denis Monasse en a été un parfait ambassadeur, c’est avec grand plaisir que je l’en remercie ici.

Fait à Paris le 19 octobre 2016

Antoine Petit Professeur des Universités en Informatique à l’Ecole Normale Supérieure ParisSaclay Président – Directeur général d’Inria

Introduction

1. Le séminaire Algorithmique et Programmation Le séminaire Algorithmique et Programmation a vu le jour en 1985 sous l’impulsion de Robert Rolland et Hervé Lehning. En 1987, Hervé désirant passer la main, j’en repris l’or ganisation en tant que responsable d’une informatique encore balbutiante au sein de l’Union des Professeurs de Spéciales (UPS). De 1987 à 2012, chaque année au mois de mai, je me suis occupé de l’organisation pédagogique et matérielle de ce séminaire. Il se déroula presque toujours au Centre International de Rencontres Mathématiques (à l’exception d’un épisode à Sup’Aero et d’un épisode aux Mines d’Alès) grâce à la bienveillance des directeurs suc 1 2 cessifs de cette belle maison et au soutien affirmé de la Société Mathématique de France , du Centre National de la Recherche Scientifique et de l’Institut National de Recherches en 3 Informatique et Automatique . Depuis 2013, le séminaire se perpétue grâce au dévouement de Francis Dorra. Au cours des années, les thèmes rencontrés ont fluctué suivant l’évolution de l’informatique en classes préparatoires aux grandes écoles. Au départ, le séminaire était plus axé sur l’ana lyse numérique et la programmation en Pascal, puis à partir de 94, le calcul formel (Maple, Mathematica) et la programmation fonctionnelle (Caml) ont régné en maîtres. Depuis le dé but des années 2000, le but de départ qui était de donner une formation initiale aux futurs enseignants d’informatique en classes préparatoires ayant été atteint, le séminaire s’est large ment ouvert à des universitaires et des chercheurs, cherchant à montrer tout l’éventail de la recherche en informatique à un public varié, ayant déjà une compétence certaine en program mation et en algorithmique. Il faut souligner que ce séminaire a été pratiquement le seul endroit où ont été formés dans les années 1990 les futurs enseignants de l’option informatique en classes préparatoires, l’édu cation nationale n’ayant en aucune façon contribué à cette formation pourtant indispensable. Remarquons encore qu’à cette époque, beaucoup de conférences étaient données par les par ticipants euxmêmes ; il s’agissait donc plutôt d’une autoformation, chacun travaillant un domaine particulier et communiquant à ses collègues et amis ce qu’il avait assimilé.

2. Le contenu de cet ouvrage Tout au long des 25 années que j’ai passées dans ces rencontres Algorithmique et Program mation, je me suis astreint à donner, pratiquement à chaque session, au moins une conférence 1. En particulier mes amis Gilles Lachaud et JeanPierre Labesse 2. Merci en particulier à Daniel Barlet et Gilles Godefroy 3. Un merci tout particulier à Antoine Petit et Pierre Weis

8

sur des sujets variés. Certaines d’entre elles, qui avaient un simple objectif d’exposition d’un langage de programmation ou d’un algorithme en vue de l’enseignement en prépas, ne pré senteraient plus aucun intérêt actuellement. D’autres m’avaient demandé un gros travail de préparation et m’avaient tout particulièrement motivé et intéressé, me faisant découvrir des domaines de l’informatique que je connaissais peu a priori. Beaucoup de ces exposés avaient un rapport avec les mathématiques (par l’intermédiaire du calcul formel ou de LaTeX) ou avec un formalisme et une structuration proches des mathé matiques (comme XML ou la programmation objet). J’ai pensé qu’il aurait été dommage de ne pas réunir ces conférences dans un ouvrage dans la mesure où les sujets abordés pour raient intéresser des enseignants scientifiques ou des étudiants, qu’ils soient en Master, qu’ils préparent l’agrégation ou soient simplement intéressés par un complément de culture mathé matique et informatique. Les chapitres de cet ouvrage sont variés ; certains s’intéressent essentiellement au calcul for mel à travers les algorithmes de sommation, de primitivation, de simplification ou de géné ration de groupes finis ; un chapitre s’intéresse à la calculabilité et la complexité algébriques dans le cadre inhabituel des nombres réels ; d’autres chapitres concernent plus particulière ment l’informatique à travers XML, les types de données, le Web dynamique ou la transfor mation de LaTeX en HTML. Ils ont tous en commun de faire appel à une formalisation et une structuration qui sont chères à mon cœur de mathématicien. 4 J’espère que cet ouvrage, où chaque chapitre peutêtre lu indépendamment de tous les autres , permettra aux lecteurs de m’accompagner dans la découverte de ces divers domaines. Bien entendu, l’ouvrage ne contient rien d’original à part le regard que j’ai apporté sur les différents sujets abordés et l’effort de pédagogie déployé pour mettre à la disposition du lecteur un outil d’approfondissement des liens divers entre l’informatique et les mathématiques. Je voudrais remercier tout particulièrement les amis et collègues qui m’ont accompagné au CIRM pratiquement chaque année, en particulier Denis Cazor, Laurent Chéno, Luc Albert, Francis Dorra et Bruno Pettazzoni, tous les chercheurs qui ont sacrifié une partie de leur temps si précieux pour nous faire découvrir leurs domaines d’étude, tous les membres du personnel du CIRM qui nous ont toujours accueillis avec une gentillesse incroyable en nous permettant de travailler dans une ambiance exceptionnelle et bien entendu Antoine Petit sans lequel ce séminaire n’aurait pas pu se poursuivre au long de ces années.

4. Le lecteur attentif pourra détecter certaines redites (en particulier sur l’algorithme de Gosper).It’s not a bug, it’s a featurecomme disent les informaticiens : cela permet à chaque chapitre d’êtreauto suffisant.

Sommation et intégration formelles

Les logiciels de calcul formel, que ce soient Derive, Mathematica et Maple, ont fait leur apparition dans l’enseignement des mathématiques en France il y a une vingtaine d’années. Certains d’entre eux tournent sur des ordinateurs de poche et même sur des calculatrices dont les élèves peuvent disposer aux examens et concours ; leur usage progresse même si la pédagogie à mettre en œuvre pour une utilisation intelligente de ces outils merveilleux est encore balbutiante. En dehors des problèmes purement pédagogiques que cela peut poser, il convient pour un scientifique d’essayer de comprendre le fonctionnement de ces outils et d’en connaître le do maine de validité. Les algorithmes de calcul formel ont connu un développement parallèle à celui des matériels capables de les faire fonctionner et, bien que ce soit encore un domaine de recherche en pleine activité, les plus fondamentaux d’entre eux ont vu le jour entre 1960 et 1980, que ce soient les premiers essais de manipulation d’expressions algébriques et de dé rivation ou des algorithmes complets d’intégration (algorithme de Risch), de factorisation de polynômes à coefficients dans un corps fini et par suite à coefficients rationnels (Berlekamp) et de sommation de séries (Gosper). Nous commencerons par décrire ce dernier algorithme, avec une démonstration complète de sa validité et des exemples d’applications. Nous es sayerons ensuite de fournir des idées sur les techniques d’intégration formelle en donnant un algorithme de calcul de primitives de fractions rationnelles qui fournit une introduction à l’algorithme de Risch.

1. L’algorithme de Gosper X Donnons nous une sériea n à terme général réel ou complexe connu. On appelleS n = n n X a k la somme partielle d’indicende la série. L’algorithme de Gosper permet de détecter k=0 le fait queS n admet une expression en fonction dentelle que le rapport S n S n−1 soit une fraction rationnelle enn(ce qui couvre beaucoup de cas d’expressions deS n en termes de fractions rationnelles, de factorielles et d’exponentielles) et d’en déterminer ex plicitement une telle expression. C’est donc un algorithme complet dans le sens où soit il aboutit à une expression explicite deS n en fonction den, soit il échoue, et on a dans ce cas une preuve qu’il n’existe pas d’expression répondant à notre condition de rationalité du rapport S n . S n−1

10

En réalité, le fait de démarrer àk= 0n’a aucune importance en ce qui concerne le calcul des sommes partielles de la série (mais il peut en avoir sur la rationalité du rapportS n /S n−1 comme le montre l’exemple d’une série géométrique) et nous allons remplacer notre pro blème initial par celui plus général de rechercher une suite(S n ) n∈N vérifiant les deux condi tions (i)a n =S n −S n−1 (ii)S n /S n−1 est une fraction rationnelle enn. On aura alors n X a k =S n −S n 0 −1 . k=n 0

Proposition 1.Le rapportS n /S n−1 est une fraction rationnelle ennsi et seulement si il existe des fractions rationnellesR(X)etα(X)(à coefficients rationnels, réels ou complexes suivant le cas), telles que a n ∀n∈N=R(n) (1) a n−1 ∀n∈NS n =α(n)a n (2)

Demonstration : la condition est bien évidemment suffisante puisque si (1) et (2) sont véri fiées, on a S n α(n)a n α(n) = =R(n). S n−1 α(n−1)a n−1 α(n−1) La réciproque provient des formules évidentes

S n −1 a n S n −S n−1 S n−1 σ(n)−1 = = = S n−2 1 a n−1 S n−1 −S n−2 1− 1− σ(n−1) S n−1

(en posantS n /S n−1 =σ(n)) et 1 a n =S n −S n−1 =S n (1−) σ(n) soit σ(n) S n =a n . σ(n)−1 La fraction rationnelleRétant supposée connue, l’algorithme de Gosper va permettre soit de calculer la fraction rationnelleα(X)quand celleci existe, soit d’assurer qu’elle n’existe pas et que le rapportS n /S n−1 n’est donc pas une fraction rationnelle enn. Proposition 2.Il existe des polynômesp(X),q(X)etr(X)vérifiant les deux conditions

p(X)q(X) R(X) = p(X−1)r(X)

∀k∈N

q(X)∧r(X+k) = 1

(3)

(4).