MATHÉMATIQUES
Un ordinateur pourra-t-il répondre à cette question ?

mathématiques - par Propos recueillis par Philippe Pajot dans mensuel n°449 daté février 2011 à la page 18 (632 mots) | Gratuit
Pour vérifier que des systèmes informatiques fonctionneront comme prévu, on ne peut pas tester leur nombre infini de configurations. Les informaticiens ont alors recours à la logique.

Pourquoi utilise-t-on la logique en informatique théorique ?

T.C. Il existe des questions auxquelles aucun ordinateur ne peut répondre, quelle que soit la manière dont il est programmé ou sa puissance. Partant de ce résultat fondamental, une partie de l'informatique théorique tente de déterminer quelles sont les questions que l'on peut résoudre, ce que l'on qualifie de décidable. La logique permet d'aborder ce problème. On se place dans un cadre d'un formalisme logique : un ensemble d'énoncés - des phrases mathématiques - qui peuvent être vrais ou non, et on cherche à programmer un ordinateur pour répondre aux énoncés.

Comment choisit-on ce formalisme logique ?

T.C. Il en existe beaucoup, élaborés dans le cadre d'autres questions mathématiques, mais la plupart de ces formalismes sont indécidables : aucun ordinateur ne peut dire si un énoncé donné du formalisme est vrai ou non. Cela oblige à utiliser des formalismes logiques assez simples. Je m'intéresse en particulier à la « logique monadique du second ordre », et ce qu'elle peut exprimer sur les suites de symboles par exemple des lettres, éventuellement de longueur infinie, ce que les informaticiens nomment des « mots », et possédant parfois des embranchements, les « arbres ».

Que peut-on montrer sur la logique monadique ?

T.C. Le résultat fondamental, établi en 1969, est que ce formalisme logique est décidable sur les mots et sur les arbres infinis. Cela signifie que, si on a un énoncé exprimé dans ce formalisme, un ordinateur est capable de dire s'il existe une séquence infinie de symboles pour laquelle l'énoncé est vrai. Par exemple, l'énoncé : un mot contient une infinité de lettres « a », une infinité de lettres « b », et entre deux lettres « a », il y a un nombre pair de lettres « b », est vrai sur le mot infini « abbabbabb »... De même, on saura dire s'il existe un arbre infini pour lequel un énoncé est vrai. Ce résultat a été démontré en établissant une équivalence entre logique et automates finis, des objets mathématiques conçus pour effectuer des calculs simples sur les mots ou sur les arbres. Il s'agit de machines abstraites dotées d'un nombre fini d'états. Un automate va commencer au début d'un mot, puis, lettre par lettre, va lire ce mot, son état évoluant à chaque étape. À la fin, l'automate répondra vrai ou faux. Sur les mots infinis, un automate pourra par exemple détecter l'apparition d'une infinité de lettres « a ». C'est en traduisant la logique monadique en automates équivalents que le résultat de décidabilité a été démontré.

Comment avez-vous étendu ce résultat ?

T.C. Ces questions sont à la frontière de ce qui est décidable. Ainsi, si on s'autorise une extension a priori mineure à la logique, on sort en général du domaine décidable : toute la théorie s'effondre. J'ai tenté d'étendre cette logique à un formalisme quantitatif. Au lieu de dire si un énoncé est vrai ou faux, ce formalisme permet de dire s'il est plus ou moins vrai. Cette logique permet de mesurer des choses, de compter. En montrant son équivalence avec de nouvelles formes d'automates, nous avons généralisé le résultat fondamental à cette nouvelle logique, sur les mots et sur les arbres les arbres finis pour l'instant [1] . Un aspect intéressant du cas des arbres finis est que sa démonstration utilise la théorie des jeux, une technique essentielle pour la démonstration du résultat de 1969 sur les arbres infinis voir encadré. Les jeux permettent de voir la vérité d'un énoncé logique comme un jeu au cours duquel l'un des joueurs va tenter de montrer que l'énoncé est vrai quand l'autre va essayer de le réfuter.

Par Propos recueillis par Philippe Pajot

DOCUMENT      larecherche.fr     LIEN

MATHÉMATIQUES
Pourquoi les plasmas sont stables

mathématiques - par Propos recueillis par Philippe Pajot dans mensuel n°448 daté janvier 2011 à la page 20 (564 mots) | Gratuit
En 1946, le physicien russe Lev Landau avait prédit qu'un gaz complètement ionisé évolue spontanément vers un état d'équilibre. Cette hypothèse, fondamentale en physique, vient d'être complètement prouvée mathématiquement.

Vous venez de démontrer l'existence de l'« amortissement Landau ». De quoi s'agit-il ?

C.M. C'est un phénomène physique qui se produit dans les plasmas, des gaz dans lesquels les électrons sont séparés des noyaux des atomes. Localement, il n'y a pas le même nombre de charges positives et négatives, de sorte qu'il se crée un champ électrique. À son tour, ce champ électrique agit sur les charges, qui le modifient en retour, et ainsi de suite. C'est ce que les mathématiciens appellent un système non linéaire : une boucle de rétroaction infinie. En raison de ce couplage, il se crée dans les plasmas une grande variété d'ondes. En 1946, le physicien soviétique Lev Landau a fait un calcul simplifié montrant que les charges électriques s'homogénéisent au cours du temps [1] . Ce phénomène a été qualifié d'amortissement du champ électrique, ou amortissement Landau.

Pourquoi y avait-il un questionnement sur cet amortissement ?

C.M. Les physiciens l'observaient depuis une cinquantaine d'années, mais il suscitait des controverses parce que l'équation de Vlasov-Poisson, qui décrit l'évolution des plasmas, est réversible. Si l'on passe le film des événements à l'envers, on a une solution acceptable pour l'équation. Comment une équation réversible peut-elle engendrer un amortissement, phénomène physique irréversible, qui va dans un seul sens ? L'abondante littérature de la physique des plasmas faisant référence à l'amortissement Landau illustre l'importance de cet effet. Du côté des mathématiques, le domaine était presque vierge : moins de dix articles traitaient de l'amortissement Landau.

Quelles difficultés avez-vous rencontrées ?

C.M. Les solutions que l'on recherche dans ce type d'équation de transport sont des fonctions de distribution des électrons. Dans le cas non linéaire, ces solutions ont des oscillations qui croissent au cours du temps. L'outil de mesure avec lequel les mathématiciens regardent les solutions d'une telle équation s'appelle une norme. Or, en prenant des outils de mesure de plus en plus précis des normes de plus en plus régulières, nous avons constaté que les oscillations augmentaient. Cela est dû au fait que les plasmas ont tendance à former des filaments qui s'enroulent et se ramifient, comme ce qu'on peut voir dans les éruptions solaires.

Comment vous-êtes vous sortis de cette impasse ?

C.M. Nous sommes partis du mécanisme de mélange de phase, bien connu dans le domaine des systèmes dynamiques lire l'encadré. Or le mélange de phase, qui est la traduction mathématique du mécanisme de filamentation et qui semblait être un problème pour analyser les solutions, s'est révélé responsable de l'amortissement. Pour analyser les solutions, nous avons dû mettre au point des outils de mesure qui s'adaptaient dans le temps et suivaient la filamentation. Finalement, l'amortissement Landau est bien là [2] .

Ces résultats peuvent-ils

s'étendre à d'autres domaines ?

C.M. Notre théorème confirme aussi que l'amortissement existe lorsqu'on remplace les électrons par des étoiles et le champ électrique par le champ gravitationnel. Autrement dit, cet amortissement joue un rôle pour expliquer la stabilité des galaxies. Un phénomène analogue baptisé amortissement non visqueux résulterait des équations d'Euler de la mécanique des fluides. Ce type d'amortissement, pas encore confirmé mathématiquement, serait responsable par exemple de la stabilité de la grande tache rouge de Jupiter, un gigantesque anticyclone de l'atmosphère jovienne observée depuis plus de trois cents ans.

Par Propos recueillis par Philippe Pajot

DOCUMENT      larecherche.fr     LIEN

MATHÉMATIQUES
Vérifier une démonstration en un coup d'oeil

mathématiques - par Propos recueillis par Philippe Pajot dans mensuel n°447 daté décembre 2010 à la page 20 (611 mots) | Gratuit
Une méthode probabiliste de vérification de théorèmes permet de valider une démonstration en vérifiant seulement une petite partie. Irit Dinur, qui a produit une nouvelle démonstration de ce résultat, nous explique cette percée de l'informatique théorique.

Comment peut-on vérifier une preuve de manière probabiliste ?

I.D. D'habitude, pour vérifier une démonstration, il faut la lire entièrement. Mais grâce au théorème PCP pour Probabilistically Checkable Proof, soit « preuve vérifiable de manière probabiliste », on peut faire autrement. Dans un premier temps, il faut mettre la démonstration au format PCP à l'aide de graphes mathématiques. On aboutit à une preuve qui est une suite de bits. Ensuite, il suffit de vérifier au hasard quelques bits de cette démonstration. Si vous ne trouvez pas d'erreur dans ces quelques bits, vous êtes assuré que la démonstration initiale est juste avec une probabilité d'erreur de 1 sur un milliard par exemple. L'aspect le plus étonnant de cette méthode, c'est que la probabilité est indépendante de la longueur de la démonstration.

Quelle est l'astuce ?

I.D. Prenons une image. La preuve est comme un morceau de pain sur lequel il peut y avoir un peu de confiture localisée, qui représente les erreurs. Pour savoir s'il y a ou non de la confiture sur cette tartine, vous devez explorer toute la tartine, ce qui peut être long si la tartine est grande. Avec la méthode PCP, c'est inutile. C'est comme si vous étaliez d'abord votre confiture, s'il y a de la confiture. Puis, sur cette tartine la nouvelle preuve, il vous suffit de regarder au hasard à quelques endroits. Si vous n'y trouvez pas de confiture, vous pouvez être assuré qu'il n'y en avait pas sur la tartine au départ, et donc que la preuve initiale est correcte. Le théorème PCP vous garantit qu'il existe toujours une autre tartine sur laquelle la confiture va s'étaler, c'est-à-dire transformer la preuve en une preuve où les éventuelles erreurs auront « diffusé » [1] . C'est la clé de la méthode : faire diffuser les erreurs dans toute la démonstration voir encadré.

Quels types de problème peuvent être analysés par cette méthode probabiliste ?

I.D. La méthode PCP concerne les problèmes qui peuvent être vérifiés de manière efficace par un algorithme. Ce sont les problèmes de la classe NP non déterministes polynomiaux. Intuitivement, cette classe de complexité correspond à des problèmes « raisonnables » : si je vous pose une question et que vous me donnez une réponse, il faut que je sois capable de vérifier que cette réponse est correcte. De plus, elle s'applique uniquement aux preuves formelles, c'est-à-dire à celles qui peuvent être mises sous forme compréhensible par un ordinateur. En pratique, c'est plus facile dans le cas de problèmes qui mettent en jeu des graphes et de la combinatoire. Ses domaines d'application privilégiés sont les problèmes d'approximation dans les équations linéaires, un domaine actif où il reste de nombreuses questions ouvertes.

Est-ce applicable à toutes les démonstrations ?

I.D. Uniquement aux preuves formelles. Dans d'autres domaines que les approximations linéaires, des formalisations de preuve ont été effectuées. Ainsi, Georges Gonthier, des laboratoires Microsoft, s'est attaqué à la démonstration par cette approche du théorème des 4 couleurs - le fait qu'il est possible de colorier une carte avec uniquement 4 couleurs sans que deux couleurs identiques se touchent. Il a déjà fait un énorme travail pour formaliser la preuve et la faire vérifier par un ordinateur, sans toutefois utiliser la méthode PCP [2] . Là encore, cette preuve ne fait intervenir que la combinatoire de graphes. Pour formaliser d'autres démonstrations, il faudrait formaliser des concepts non triviaux de topologie, d'algèbre et de géométrie différentielle par exemple. Cela reste hors de notre portée.

Par Propos recueillis par Philippe Pajot

DOCUMENT      larecherche.fr     LIEN

MATHÉMATIQUES
Un manuscrit mathématique de la main de Pascal

mathématiques - par Propos recueillis par Philippe Pajot dans mensuel n°446 daté novembre 2010 à la page 18 (600 mots) | Gratuit
Un théorème écrit de la main de Blaise Pascal témoigne de la manière dont ce penseur a vécu l'arrivée du symbolisme dans l'écriture mathématique.

Dans quelles circonstances avez-vous découvert un manuscrit inédit de Pascal ?

D.D. J'ai repéré ce manuscrit parmi les clichés du manuscrit des Pensées que le centre international Blaise-Pascal était en train de faire numériser. Sur le verso de ce manuscrit des Pensées, j'ai vu un texte mathématique partiellement effacé et raturé. Cette page mathématique était sous les yeux de tous depuis des années dans les fonds de la Bibliothèque nationale de France, mais personne n'y avait prêté attention. Les chercheurs qui ont établi des éditions des Pensées de Pascal l'ont fait soit dans le cadre d'éditions de textes religieux, soit dans celui d'études littéraires. Du coup, ils ne se sont jamais arrêtés sur cet écrit. Il faut dire que cette page était très abîmée : une grande partie est effacée et une autre coupée. Pour leur part, les historiens des mathématiques se sont intéressés aux textes publiés dans des ouvrages, tel le Traité du triangle arithmétique, publié en 1654, et n'avaient jamais pensé à examiner un papier qui était inséré dans un manuscrit connu pour être un texte religieux. Au fond, si l'on a découvert cet écrit si tard, c'est en raison du cloisonnement des disciplines.

Quel est le contenu mathématique de cette page ?

D.D. Bien qu'il soit partiel et très abîmé, il y a plusieurs choses que l'on peut établir. Il s'agit d'un théorème relatif à ce que Pascal appelle les indivisibles, qui annoncent, à échéance, le calcul intégral [1] . Ce texte traite de géométrie, puisqu'on distingue une figure en haut à gauche. En analysant cet écrit, j'ai pu établir que ce théorème relève de préoccupations de Pascal sur les solides de révolution et sur ce qu'il nomme les « onglets », des constructions en trois dimensions qu'on obtient en ajoutant des formes élémentaires.

Ce théorème a-t-il été publié ?

D.D. Le principal texte de Pascal sur la géométrie des indivisibles est son Traité sur la roulette publié en 1659. Or ce théorème, que l'on a pu dater de 1657 ou 1658, n'a pas été utilisé dans ce traité. En dehors des textes mathématiques qu'il a publiés - et qui n'étaient pas très nombreux -, Pascal disposait donc de matériel mathématique qu'il a gardé pour lui.

Que nous apprend ce manuscrit sur la manière de faire des mathématiques à cette époque ?

D.D. Ce théorème est un témoignage unique de la manière de travailler de Pascal. Les manuscrits originaux des oeuvres de Pascal ont tous été détruits après publication. Il ne restait que quelques correspondances avec Fermat, Sluse et Huygens. Ce manuscrit est riche d'enseignements sur la manière dont Pascal élaborait un théorème avant de le mettre au point sous la forme d'un texte définitif. Alors que les textes publiés de Pascal sont presque exclusivement rhétoriques, sans symbole, ni équation, on trouve ici un symbolisme propre. Il ne s'agissait pas du symbolisme algébrique de Descartes voir encadré, mais d'un symbolisme préalable à la rédaction. Cette conception du symbolisme résultait de l'idée de Pascal que les mathématiques de pointe pour l'époque ne devaient pas être écrites dans un style purement symbolique et inaccessible. C'est une des dernières périodes où l'on pouvait encore associer un public cultivé, pas nécessairement mathématicien, à des découvertes géométriques élaborées. En cela, les écrits mathématiques de Pascal, et ce manuscrit en particulier, témoignent de la fin de cette époque où les mathématiques étaient encore « littéraires ». Avec Leibniz, une vingtaine d'années plus tard, le symbolisme algébrique prendra définitivement le pas [2] .

Par Propos recueillis par Philippe Pajot

DOCUMENT      larecherche.fr     LIEN