Interstices


  Lire et voir

Informatique et mathématiques

Entre les mathématiques et l'informatique, des liens de filiation, des interactions, des frontières pas toujours faciles à tracer... dont ces quelques références vous donneront une idée.

Géométrie algorithmique : des données géométriques à la géométrie des données

Jean-Daniel Boissonnat, leçon inaugurale au Collège de France (mars 2017).

Accéder à la vidéo.

jd-boissonnat230

© Inria / Photo G. Scagnelli
Jean-Daniel Boissonnat, nouveau titulaire de la chaire « Informatique et sciences numériques » au Collège de France, a donné sa leçon inaugurale le 23 mars 2017 dernier. L’occasion, en une heure, de présenter les principales facettes de plusieurs décennies de travail sur un sujet qui a émergé dans le dernier tiers du 20e siècle : la géométrie algorithmique.
Aider à passer des maquettes à la réalité virtuelle, ou de la photo à l’impression 3D, pour ne citer que quelques incidences, Jean-Daniel Boissonnat nous rappelle que cette matière a occupé nombre de scientifiques issus de divers corps de métiers. Beaucoup nous sont contemporains, portant une école française dont la présence ne fléchit pas depuis Pierre Bézier ou encore Paul de Faget De Casteljau.
Dans cette leçon inaugurale, on découvre que ce domaine doit certainement son succès à la diversité des résultats de recherche auxquels il fait appel. Jean-Daniel Boissonnat y parle aussi bien d’outils connus en analyse numérique (maillages) que de mathématiques fondamentales (topologie) ou de domaines plus récents dans les sciences du numérique (analyse d’algorithmes). 
La décomposition ou l’approximation des surfaces en éléments plus simples représente une partie importante de la modélisation. On passe ainsi en particulier d'un monde continu fait de « formes » à un monde discret fait d’assemblages de points, de droites, de triangles, de tétraèdres, parfois de courbes ou de surfaces « simples ».
Pour reprendre l’analogie pâtissière utilisée par les prix Nobel de physique 2016 pour décrire leur utilisation de la topologie, si on considère un donut, la surface qu’il définit peut être découpée en simplexes (3 points reliés par des courbes) eux-mêmes approchés par des triangles en préservant le nombre de trous qu’il possède. Ceci rend compte du fait qu’une transformation « simple » permet de passer d’une de ses représentations/approximations à une autre, sans influer sur l’allure générale de l’objet ou simplement sans changer certaines de ses caractéristiques. L’étude de la topologie des surfaces et/ou de leurs approximations/modélisations permet une classification en fonction des propriétés que l’on veut préserver.  
On comprend qu'il est alors plus facile de voir le nombre de trous formés par un donut que par une tasse, même si topologiquement ce sont les mêmes objets.
donut-tasse
D'après Stephen Barr, Experiments in Topology (New York, Dover Publications Inc, 1964).

Ensuite, il est en général plus facile de faire calculer par une machine le nombre de trous formés par un « complexe simplicial » (une structure discrète, par exemple un recollement de triangles) que  par une structure continue comme un donut ou une tasse.
Comme souvent, la notion de « simple » est toute relative et l’accumulation de transformations « simples » se traduit invariablement par une accumulation d’objets « simples », reportant alors la complexité du problème initial sur celle des algorithmes gérant, manipulant, simplifiant ces nouvelles structures. C’est l’étude des complexités combinatoires et/ou algorithmiques qui rend alors compte de la faisabilité d’un calcul,  savant mélange entre une stratégie de modélisation, son adaptation au problème posé et les algorithmes mis en œuvre.

La sanction absolue est l’implantation, le moment où l’on met tout bout à bout et où l’expérience validera (ou non) l’accumulation de choix. La présentation du logiciel CGAL est au cœur de la leçon inaugurale, montrant sans ambiguïté l’effort fourni sur un peu plus de vingt ans pour rendre exploitables en pratique les objets, les algorithmes qui seront présentés en détail dans les leçons suivantes.

Fabrice Rouillier

Mathématiques et langages - Panorama du thème

Livret édité par la Commission française pour l'enseignement des mathématiques (CFEM).panorama maths-langages

Les questions de langage, au sens large, sont omniprésentes en mathématiques. Comment modéliser et calculer des propriétés de langages formels ? Quelles notations prendre pour un article de recherche ? Comment enseigner à une classe multilingue ?

Ce livret de 86 pages, réalisé à l'occasion du Forum Mathématiques Vivantes 2017, est composé d'une trentaine de textes courts rédigés par des scientifiques (mathématiciens, informaticiens, didacticiens, linguistes et historiens). On y découvre comment utiliser l'analyse mathématique et statistique pour étudier le langage d'œuvres littéraires et de morceaux de musique, l'histoire d'amour-haine des mathématiciens envers leurs notations et systèmes de typographie, ou encore les défis de la transmission du langage mathématique dans l'enseignement.

La plupart des textes sont accessibles à un large public, même si certains sont plus spécialisés. Ils donnent un aperçu de quelques problématiques actuelles en recherche et enseignement.

Ce document distribué gratuitement sous licence Creative Commons CC0 1.0 est téléchargeable en version pleine définition (PDF 17,5 Mo) et version allégée (PDF 4,4 Mo).

Antoine Levitt

Accromath

Revue produite par l'Institut des sciences mathématiques et le Centre de recherches mathématiques (Québec).

Accromath est à la fois une revue et un site tous deux consacrés aux mathématiques et leurs applications, à destination plus particulièrement des élèves de l’enseignement secondaire au Québec et de leurs enseignants. À raison de deux numéros par an depuis 2006, publiés simultanément sous forme papier et numérique, ce sont douze numéros qui sont désormais accessibles en ligne.

Le numéro paru début 2012 consacre un de ses articles, « Des coquillages aux pelages », à la morphogenèse dont un cas particulier est celui de la formation des taches sur le pelage des félins ou de motifs récurrents sur certains coquillages. À partir d’un algorithme simple de production de triangles de Sierpinski, le mécanisme de réaction-diffusion est présenté de façon très pédagogique, jusqu’à l’introduction des équations aux dérivées partielles correspondantes. L'article cite les travaux d’Alan Turing, qui a proposé en 1952 des mécanismes pour expliquer la morphogenèse. Un article d’actualité donc, en cette année qui voit célébrer le centenaire de la naissance de ce fondateur de l’informatique.

La revue Accromath est l'un des principaux partenaires de l'initiative internationale Mathématiques de la planète Terre 2013. Elle publiera en 2013 un numéro spécial sur ce thème.

Excellence et pédagogie des textes, pertinence des thèmes, qualité de la présentation : tout concourt à recommander cette revue francophone à tout curieux de mathématiques et de leurs applications.

 

Mathématiques, espionnage et piratage informatique - Codage et cryptographie

Joan Gómez (Collection « Le monde est mathématique », RBA Coleccionables S.A., Barcelone, 2011)

Traduit de l'espagnol.
Des codes de César et de Vigenère à l’algorithme RSA et aux perspectives de l’ordinateur quantique, en passant par les machines Enigma, un exposé des méthodes de codage et de cryptographie, parsemé d’anecdotes historiques et assez joliment illustré. Un de plus ? Peut-être, mais cet ouvrage se distingue par une présentation des fondements mathématiques et informatiques, plutôt rare et bienvenue au sein d’une collection qui, à travers la vente en kiosque, vise un large public. Le lecteur se verra par exemple proposer une introduction à l’arithmétique modulaire, ou plus poétiquement une « touche d’algèbre linéaire » lors de la présentation très pédagogique du chiffre de Hill. Les quelques rares passages inintelligibles sont probablement à mettre sur le compte de la traduction ; sinon, comment expliquer que la machine de Babbage ait pu servir pour « travailler également avec des tables astrologiques » ?

 

À la recherche de la preuve en mathématiques

Hervé Lehning (Éditions Belin – Pour la science 2009)

« L’idée de prouver un algorithme peut sembler étrange. Certains croient que l’informatique est le domaine du système D et de la "bidouille". Ils se trompent […] ». Voilà une déclaration à laquelle nous souscrivons évidemment sans retenue. Et l’auteur de ce livre de poursuivre, dans ce chapitre intitulé Induction et récurrence, par la présentation de l'exemple de la preuve d’un algorithme de tri par insertion. Simple, mais démonstratif !

Au long de ce petit ouvrage, tout en livrant avec bonheur quelques heuristiques propres à guider le lecteur sur le chemin de la preuve en mathématiques, Hervé Lehning effectue plusieurs autres incursions très pertinentes dans le domaine de l’algorithmique. Il souligne de ce fait la forte connexité de ce domaine et des mathématiques, plus particulièrement des mathématiques discrètes qui s’occupent de graphes, de dénombrements et d’optimisation combinatoire. Le lecteur appréciera ainsi l’explication des « cryptarithmes », des algorithmes gloutons, du théorème des quatre couleurs, ou encore des jeux de Nim. Une lecture distrayante… qui mobilise les neurones.
 

Le pouvoir des mathématiques

Les dossiers de La Recherche (novembre 2009)

Loin de se limiter à s’interroger sur l'utilité des mathématiques, comme son sous-titre, « Pourquoi elles sont encore indispensables », pourrait le laisser entendre, ce dossier du mensuel La Recherche illustre magistralement les liens fructueux que continuent de tisser les mathématiques avec les autres sciences. Au-delà de la physique, ce sont la biologie et l’informatique qui, à des titres différents, bénéficient maintenant des avancées mathématiques, et simultanément les sollicitent. Il est ainsi tout-à-fait significatif de relever dans les articles de ce dossier de nombreuses références à la complexité algorithmique, une des notions fondamentales de l’informatique. Parallèlement, l’ordinateur émerge comme un instrument au service de la preuve mathématique, non sans réactions des mathématiciens concernés. Ce dossier de La Recherche dresse ainsi un portrait très vivant, souvent étonnant, des mathématiques du XXIe siècle.
 

Les Métamorphoses du calcul

Gilles Dowek (Le Pommier 2007)

couverture

Socle des mathématiques, la notion de démonstration s'est profondément transformée dans les trente dernières années. Le calcul, longtemps éclipsé par le raisonnement, retrouve aujourd'hui sa place dans les démonstrations. L'ouvrage retrace les avancées mathématiques qui sont à l'origine de ces transformations. Il nous amène en particulier à réfléchir sur les liens entre les mathématiques et l'informatique, notamment la possibilité maintenant offerte de dépasser les limites en taille des démonstrations mathématiques.

Un livre à la frontière des mathématiques, de l'informatique et de la philosophie, qui fait réfléchir sur les évolutions des mathématiques.
 

Petite introduction à l'algorithmique - À la découverte des mathématiques du pas à pas

Pierre Damphousse (Ellipses 2005)

couverture

« Petit » par la taille, cet ouvrage donne une vision rigoureuse et concise des concepts centraux de l'algorithmique, en les illustrant par des exemples et en les mettant en perspective par de nombreuses références historiques.
En résumé, un ouvrage d'informatique mathématique à la fois fluide et rigoureux, destiné à un lectorat étendu mais averti, qui évite tout jargon informatique et ne nécessite aucune connaissance d'un langage de programmation.
 

À la racine des nombres - Une histoire du calcul numérique des origines à nos jours

Philippe A. Doisy (Ellipses 2006)

couverture

Le calcul de la racine carrée d’un nombre, tel est le fil rouge de cet ouvrage. Pas moins d’une vingtaine de méthodes de calcul sont exposées, dont les plus anciennes remontent à l’époque babylonienne.

Leur justification mathématique est entrelacée de repères historiques, tant sur les techniques numériques et les mathématiciens qui les inventèrent que sur les outils de calcul disponibles pour les mettre en œuvre. L'auteur présente ainsi calculi et tables à calcul, abaques, bouliers, tables de logarithmes, compas de proportion, règle à calcul… jusqu’aux calculettes modernes, où la détermination d’une racine carrée s’obtient d’une simple pression sur la touche appropriée. Même aujourd'hui cachés, les algorithmes utilisés s’inscrivent en filiation directe de leurs antiques prédécesseurs.

Sans doute pas une histoire exhaustive du calcul numérique, mais un fascinant cocktail pédagogique de science et d’histoire(s).
 

Origines des nombres et du calcul

Cahiers de Science et Vie n°112, août-septembre 2009

couverture

Le calcul a une histoire passionnante et riche en surprises, jusqu'à ses formes actuelles impossibles à prévoir il y a cinquante ans. L'invention des systèmes de numération et la découverte (ou l'invention ?) du zéro sont moins simples qu'on l'imagine souvent. Les outils élémentaires de calcul (bouliers, cordelettes, abaques, etc.) ont suivi une lente progression qui nous étonne aujourd'hui. Les algorithmes sont une création aussi ancienne que l'irrationalité du nombre racine de 2. Tous ces thèmes et bien d'autres, concernant l'informatique, le cerveau calculateur ou la nature mentale des nombres, sont abordés dans ce cahier richement illustré qu'on lit avec plaisir. À conseiller à tous.
 

Mathématiques concrètes - Fondations pour l'informatique

Ronald L. Graham, Donald E. Knuth et Oren Patashnik (Vuibert 2003)

couverture

Traduction de Concrete Mathematics (Addison-Wesley Company 1988).
Un type particulier de mathématiques (basées sur le discret plus que sur le continu) constitue la base de l'informatique. Ce type de mathématiques devrait avoir plus de place par rapport à celui tourné vers les sciences pour l'ingénieur telles qu'elles existaient il y a cinquante ans (et qui est encore dominant dans l'enseignement en France). Problèmes récurrents, sommes, théorie élémentaire des nombres, probabilités discrètes, calcul asymptotique sont quelques-uns des thèmes de ce livre pour étudiant en informatique (niveau bac ou plus) souhaitant apprendre les mathématiques qui auront le plus de chances de lui être utiles.
Un livre qui ose attaquer des problèmes un peu ardus, mais à la portée de tous les étudiants en science ou technique.
 

Lorsque l’ordinateur joue aux dés…

Philippe Flajolet

conférencier

Conférence donnée au Laboratoire d'Informatique de Grenoble le 6 janvier 2011.
Voir la vidéo.

Dans un exposé brillant et riche, Philippe Flajolet montre l'intérêt d'une introduction volontaire de l'aléatoire dans le calcul, dans de nombreuses branches de l’informatique (cryptographie, algorithmique géométrique, optimisation combinatoire, fouille de données, etc.). Il explique la genèse et les fondements de la « combinatoire analytique », dont il est l'inventeur, et qui démontre la fécondité d’une alliance entre méthodes mathématiques adaptées, informatique fondamentale, et la quête d’algorithmes de haute performance.
 

Entre mathématiques et informatique : l'analyse des algorithmes

Philippe Flajolet

conférencier

Conférence donnée dans le cadre du Colloquium Jacques Morgenstern à Sophia Antipolis.
Présentation et transparents.

Jusqu'au dix-neuvième siècle, les mathématiques sont de nature largement algorithmique, mais les problèmes de complexité, s'ils sont présents, restent souvent subliminaux. L'avènement de l'informatique pose, dès les années cinquante, de nombreuses questions, dès lors que l'on cherche à comprendre, prédire, et quantifier les performances des algorithmes. Le nouveau domaine de l'analyse d'algorithmes est fondé par Donald Knuth au début des années soixante. Au fil de quelques exemples, cette conférence retrace l'évolution des idées depuis la période des pionniers jusqu'à maintenant. On voit ainsi surgir des domaines mathématiques extraordinaires issus des recherches en informatique. Tous ces domaines illustrent, selon le mot du physicien Eugene Wigner, la « déraisonnable efficacité des mathématiques » dans les sciences, ici, l'informatique.

 

La déraisonnable efficacité des mathématiques

Gilles Dowek

conférencier

Conférence donnée dans le cadre du Colloquium Jacques Morgenstern à Sophia Antipolis.
Présentation et vidéo.

Depuis le XVIIe siècle, on s'interroge sur les raisons de l'efficacité des mathématiques comme outil de description de la nature, ou, pour reprendre les mots de Galilée, sur les raisons pour lesquelles « Le Grand Livre de la nature est écrit en langage mathématique ». Beaucoup d'idées reçues sur le sujet sont, au passage, à démythifier.

L'informatique est une science qui offre une nouvelle manière d'aborder cette question en se demandant ce qui est calculable dans un temps fini. C'est un des piliers de l'informatique théorique, la notion de fonction calculable (liée à ce qu'on appelle la « thèse de Church ») qui permet à Gilles Dowek de proposer une réponse possible, finalement époustouflante de simplicité à ce problème philosophique... qui est... ah non, nous préférons vous laisser le découvrir !

C'est aussi un bel exemple de ce que l'informatique, en tant que science, bien au-delà des ordinateurs, permet de comprendre du monde.
 

Les mathématiques

Benoît Rittaud (Le cavalier bleu, 2008 - collection Idées reçues)

couverture

Sur Interstices, nous aimons bien affronter et rectifier les idées reçues. C’est donc avec beaucoup de sympathie que nous avons accueilli l’ouvrage de notre collègue Benoît Rittaud, maître de conférences à l’université Paris 13. D’autant que, parmi la vingtaine d’idées reçues qu’il aborde, plusieurs touchent le domaine des STIC, reflet du rapprochement des notions de preuve et de calcul. Si le chapitre « Avec l’ordinateur, on n’a plus besoin des mathématiciens » a ainsi plus spécifiquement retenu notre attention, l’ensemble des idées, très agréables à lire et accessibles sans aucune connaissance préalable, contribue à faire comprendre l’activité des mathématiciens et leurs motivations. Une mention particulière, peut-être, pour le dernier chapitre. Intitulé « Pour intéresser le public, il faut parler des applications », il invite à une réflexion très actuelle sur une « stratégie de communication » sur les mathématiques, qui pourrait bien concerner d’autres domaines de la recherche scientifique.

François Rechenmann

Tags