Informatique

L'informatique théorique...
...est un domaine en ébullition : les applications sont innombrables et
des questions fondamentales sur les limites du calcul restent en
suspens.

Jean-Paul Delahaye
01 octobre 2002 | POUR LA SCIENCE N° 300 | Temps de lecture : 11 mn

Article réservé aux abonnés numériques

Plus que toute autre discipline, l'informatique a connu en 25 ans une

évolution rapide qui a suscité une réflexion théorique d'une extrême
richesse. Comme toujours en pareilles circonstances, on s'est aperçu
que les mathématiques dont on disposait non seulement ne
répondaient pas à toutes les questions qui se posaient, mais que de
nouveaux domaines devaient être définis et explorés. Un foisonnement
remarquable d'idées en a résulté.

En fait, c'est une nouvelle sensibilité mathématique qui est née de

l'usage des ordinateurs et des problèmes qu'ils posent à l'esprit
théoricien : si tout remonte à la décennie 1930 avec les travaux de Alan
Turing, Kurt Gödel et Alonso Church sur la calculabilité, dans les 25
dernières années, l'essor de cette nouvelle sensibilité mathématique a
été considérable. à côté des mathématiques du continu, ces
mathématiques du discret, du calcul et de l'information se sont
épanouies et on est très loin d'avoir parcouru ne serait-ce que les allées
principales de ce jardin foisonnant qui croît sur le terreau des circuits
électroniques. Tout bouillonne dans cet univers que les mathématiques
pures observent maintenant avec grand intérêt.

Calcul à grande vitesse

Donner des ordres précis aux ordinateurs de façon à ce qu'ils fassent ce
qu'on attend d'eux s'appelle «écrire des algorithmes». Les
mathématiciens depuis toujours conçoivent de telles procédures de
calcul (l'algorithme d'Euclide qui détermine le plus grand commun
diviseur de deux nombres est né avec les mathématiques il y a plus de 2
000 ans), mais en pratique la règle implicite était qu'on utilise les
algorithmes en effectuant à la main quelques dizaines ou au plus
quelques centaines d'opérations élémentaires. Lorsqu'on disposa de
machines capables de réaliser des millions, puis des milliards de calculs
sans erreur, on découvrit qu'une nouvelle science d'essence
mathématique, l'algorithmique, devait être développée.

Commander des calculateurs automatiques n'est ni simple ni évident,

et des méthodes au premier regard satisfaisantes peuvent être
totalement vaines dans l'univers des ordinateurs. Par exemple, les
formules de Cramer, qui expriment les solutions d'un système
d'équations linéaires, sont trop lentes pour traiter des systèmes de plus
de 20 équations, alors que d'autres méthodes vont bien au-delà. Le bon
usage d'un ordinateur consiste à lui faire exécuter des algorithmes qui
réalisent une tâche donnée en un minimum de temps. Contrairement à
ce que pense le débutant en programmation, la puissance de la machine
ne peut pas suppléer au manque d'analyse préalable. La règle véritable
est donc que plus une machine est puissante, plus il y a de travail
(mathématique) à mener pour la faire fonctionner correctement.

Un problème aussi simple que la multiplication des nombres entiers a

conduit au développement de méthodes complexes et délicates pour
manipuler des nombres possédant plusieurs milliers ou millions de
chiffres. Dans les années 1970, on a ainsi élaboré des techniques
permettant de multiplier deux nombres de n chiffres en un temps
proportionnel à n ln(n) ln(ln(n)). En pratique, ce temps de calcul est
quasiment proportionnel à n, c'est-à-dire qu'il est bien plus court que
celui des méthodes classiques, inspirées des procédures pratiquées à la
main depuis des millénaires, pour lesquelles le temps de travail est
proportionnel à n2.

L'un des terrains d'applications de l'algorithmique est le calcul des

constantes mathématiques, telles que π, e, √2, le nombre d'or… Grâce
aux progrès en algorithmique, on connaît maintenant plusieurs
milliards de décimales des principales d'entre elles. La recherche de ces
décimales s'est parfois accompagnée de surprises, comme la découverte
d'une nouvelle formule pour calculer π. Le nombre π était jusqu'alors
un livre lu page après page : on ne déterminait l'un de ses chiffres qu'à
condition de connaître les précédents. En 1995, une équipe canadienne
contourna cette impossibilité pratique – et théorique, pensait-on – en
découvrant une formule permettant de calculer les chiffres binaires de
π indépendamment les uns des autres. Grâce à cette formule, Colin
Percival obtint cinq ans plus tard une petite tranche de chiffres binaires
de π autour de son 1015-ème chiffre binaire, performance qui semblait
hors de portée pour des siècles.

Une autre conséquence de cette maîtrise algorithmique des calculs

arithmétiques avec des nombres de grande taille est la découverte de
nombres premiers records : un nombre premier de deux millions de
chiffres en 1999 et un autre de quatre millions de chiffres en 2001. Là
encore la découverte, dans les années 1970, des tests probabilistes de
primalité (qui indiquent sans certitude absolue, mais avec un risque
d'erreur infinitésimal qu'un nombre entier est premier) fut une surprise
théorique, par ailleurs d'une grande utilité en cryptographie.

Depuis 25 ans et au-delà des exploits informatiques parfois

anecdotiques, c'est toute une science de l'organisation des calculs qui a
connu des progrès considérables et a atteint la maturité, tissant ainsi
des liens profonds avec les mathématiques et changeant parfois
radicalement nos points de vue. Des livres d'arithmétique d'un nouveau
genre sont apparus dans les rayons des bibliothèques, dans lesquels les
concepts introduits sont systématiquement associés à des outils
algorithmiques permettant de les manipuler réellement et efficacement
avec un ordinateur. Les mathématiques sont nécessaires afin de
maîtriser les ordinateurs, mais, en retour, les ordinateurs conduisent à
pratiquer différemment les mathématiques et offrent une vue nouvelle
des objets abstraits que la machine (pourvu qu'on l'instruise pour cela)
manipule mieux que l'esprit humain, en tout cas avec une précision et
une sûreté sans égales.

Ce n'est pas seulement l'arithmétique, mais une partie importante des

mathématiques qui est concernée par les progrès de l'algorithmique. Le
calcul formel (domaine où l'on demande à l'ordinateur de calculer non
plus seulement avec des nombres, mais aussi avec des symboles, des
fonctions, des équations, des matrices, etc.) s'est considérablement
développé depuis 25 ans, et a désormais sa place dans les lycées et sur
le bureau des ingénieurs à travers les calculatrices et les logiciels de
calcul symbolique. Là encore, c'est une nouvelle pratique
mathématique qu'engendre l'irruption de l'ordinateur dans le monde
des objets abstraits.

En même temps que ces anciens domaines de recherche se

renouvelaient, de nouveaux champs d'applications de l'algorithmique
naissaient. À titre d'exemple, citons la phylogénie, l'art de reconstituer
les arbres généalogiques des espèces vivantes. On traitait autrefois les
données morphologiques ou moléculaires à la main par des méthodes
nécessairement limitées en complexité. Depuis une trentaine d'années,
l'utilisation des ordinateurs a non seulement permis d'envisager des
ensembles de données plus volumineux, mais a aussi autorisé
l'utilisation de méthodes bien plus complexes et performantes. Ces
méthodes empruntent à différents domaines de l'informatique et des
mathématiques, tels que l'algorithmique, la théorie des graphes (l'étude
des réseaux de nœuds reliés) et des arbres et la statistique. Plus
généralement, le traitement des données de la biologie moléculaire a
engendré des développements théoriques et algorithmiques nombreux,
donnant naissance à un domaine scientifique mi-théorique mi-
pratique, la bio­informatique, qui prend de plus en plus d'importance et
qui contribuera peut-être à une mathématisation de la biologie
analogue à celle que connaît depuis longtemps la physique.

La logique, mère de l'informatique

Dans ce territoire si foisonnant qu'est l'algorithmique, un domaine de
recherche mérite qu'on s'y attarde, car il a bouleversé notre regard sur
la programmation : la logique mathématique. L'idée de la
programmation déclarative a été formulée au début des années 1970 ;
afin de faciliter le travail du programmeur, on doit seulement lui
demander de décrire son problème, la machine se chargera ensuite
seule de le résoudre. Bien entendu, cette idée relève de l'utopie et
montre rapidement ses limites : dans le cas où plusieurs algorithmes
existent pour un problème donné, comment la machine choisit-elle?
Cependant le langage Prolog, inventé à Marseille par A. Colmerauer et
ses collaborateurs en 1973, s'approche de ce rêve. Prolog, qui se fonde
sur des techniques de démonstration automatique (la machine déduit
seule les conséquences de formules prises comme des axiomes), a
réussi un compromis entre simplicité et efficacité. Les idées
développées pour ce langage ont été généralisées et jouent un rôle
important dans le domaine de l'intelligence artificielle et des systèmes
experts.

Toujours dans le cadre des applications des concepts de la logique

mathématique, une autre voie appelée programmation par les preuves se
propose de concevoir la programmation comme un exercice d'écriture
de démonstrations : le programmeur écrit dans un langage utilisant des
symboles logiques la démonstration d'une certaine propriété (par
exemple que pour toute suite de nombres T, il existe une suite S qui
possède les mêmes éléments classés par ordre croissant), et à partir de
cette preuve la machine engendre un programme dont on peut être
certain qu'il ne comportera aucune erreur (ce programme dans notre
exemple classera les éléments d'une suite T par ordre croissant, ce qui
donnera S). Cette approche prometteuse pour la mise au point de
logiciels sans erreur a déjà à son actif plusieurs réussites dans le
domaine de la certification des programmes et des circuits.
La logique joue également aujourd'hui un rôle important en
intelligence artificielle où de nombreuses études ont été menées sur ce
qu'on appelle les logiques non classiques, dont le but est de suivre au
plus près le raisonnement humain, plus complexe que le raisonnement
mathématique pur. Parmi les logiques non classiques, on trouve
notamment les logiques paraconsistantes, qui permettent de traiter des
données comportant des contradictions ; les logiques non monotones,
qui considèrent que ce qui est déduit peut être invalidé lorsque des
informations nouvelles surviennent ; les logiques floues, partielles,
multivaluées, modales, qui refusent l'idée classique que tout est soit
vrai, soit faux, etc.

La leçon de ces approches tirées de la logique mathématique est que la

programmation des ordinateurs doit être abordée sous tous les angles
possibles et qu'un bon algorithme est d'abord une idée, mieux une
vision. Toute théorie mathématique, y compris la plus abstraite, peut
conduire au développement d'algorithmes utiles.

Le déferlement de la cryptographie
Plus que tout autre domaine de l'informatique, la cryptographie connaît
depuis 25 ans une authentique révolution. Auparavant aux mains des
militaires, elle est devenue une discipline civile réunissant chaque
année, lors de congrès qui lui sont spécialement consacrés, une
communauté scientifique importante.

L'élément déclencheur de cette révolution a été la découverte, au début

des années 1970, de la cryptographie à double clef, ou cryptographie à
clef publique. Il s'agit de proposer des méthodes où la transformation
du message clair en message chiffré se fait à l'aide d'une clef mise à la
disposition de tout le monde (la clef publique) ; la transformation
inverse permettant de retrouver le message clair à partir du message
chiffré nécessite en revanche la connaissance d'une clef qui reste
secrète (cette clef privée est associée à la clef publique, mais aucun
moyen simple ne permet de la déduire de la clef publique).

Avec cette invention remarquable, dont le protocole RSA (attribué à

Rivest, Shamir et Adleman, mais en fait découvert dès 1973 par Clifford
Cocks) est la version la plus aboutie et la mieux maîtrisée, on
communique secrètement avec un interlocuteur sans avoir à échanger
préalablement de clefs secrètes. Grâce à ces méthodes, on peut
également signer des messages, ou programmer des systèmes
d'authentification. D'autres recherches en cryptographie ont conduit à
la mise au point de générateurs pseudo-aléatoires efficaces et sûrs et
permettent une maîtrise améliorée des protocoles à simple clef (la clef
de chiffrage est la même que la clef de déchiffrage).

Ces découvertes mathématiques fondamentales et réellement

importantes sur le plan pratique sont merveilleuses. Elles montrent à
quel point la maîtrise des concepts de l'arithmétique (qui a longtemps
eu la réputation d'être

une science inutile) et de la théorie de l'information est importante

pour le développement de l'informatique. L'informatique théorique
n'est pas une danseuse coûteuse et inutile destinée à procurer des
satisfactions intellectuelles, mais une science fondamentale dont on
attend les avancées avec impatience et sans laquelle notre monde ne
serait pas ce qu'il est ; notre carte à puce bancaire ou nos paiements par
Internet mettent en jeu des mathématiques de haut niveau.

Pourtant, quelles que soient les découvertes faites, il se trouve que

certaines questions restent mal résolues. La sûreté de nombreux
algorithmes de cryptographie repose sur l'affirmation qu'un certain
problème est intrinsèquement difficile à résoudre (nous définirons par la
suite ce que les mathématiciens entendent précisément par là). Par
exemple, la sûreté du RSA s'appuie sur le problème de la factorisation
des grands nombres. Or, même si elle n'est guère mise en doute, la
preuve que la factorisation des grands nombres est intrinsèquement
difficile n'a pour l'instant pas été apportée. Par conséquent,
contrairement à ce qu'on présente souvent au public pour simplifier les
exposés, la sûreté de nombreuses méthodes de cryptographie reste
suspendue à des résultats mathématiques manquants.

Les questions posées par la cryptographie font partie d'un plus vaste
ensemble d'interrogations qui forment le cœur de l'informatique
théorique : la théorie du calcul (ou théorie de la calculabilité). Née dans
les années 1930, la théorie du calcul énonce des résultats négatifs du
type : il est impossible d'écrire un programme qui repérerait, parmi
plusieurs programmes, ceux qui calculent la même fonction. Ces
preuves d'impossibilité sont importantes d'un point de vue général, et
une multitude de nouveaux résultats de ce type ont été démontrés
depuis 25 ans qui précisent la frontière entre l'algorithmiquement
faisable et l'impossible du calcul.

Ce domaine ancien sans cesse complété a ouvert la voie depuis 30 ans à

une analyse d'un niveau plus fin encore où l'on se pose par exemple la
question : peut-on décomposer en facteurs premiers un nombre de n
chiffres en utilisant un temps de calcul proportionnel à un polynôme
en n (on parle de temps polynomial)? Les problèmes qu'on peut
résoudre en temps polynomial constituent la classe de complexité P.
On considère qu'un problème dans la classe P est non seulement
algorithmiquement

traitable, mais efficacement traitable ; dans le cas contraire, on

considère que le problème est intrinsèquement difficile.

Une autre classe de complexité est apparue lorsqu'on s'est posé la

question : connaissant une éventuelle décomposition d'un nombre de n
chiffres en facteurs premiers, peut-on vérifier (sans avoir à la trouver)
en temps polynomial qu'elle est correcte? Les problèmes dont on peut
ainsi vérifier les solutions en temps polynomial constituent la classe NP
(voir l'encadré ci-dessus). On sait aujourd'hui que le problème de la
factorisation est dans la classe NP. En revanche, on pense qu'il
n'appartient pas à la classe P, sans en avoir la preuve.

Cette absence de certitude est franchement gênante, car elle concerne

un point central de la théorie de la complexité : tant que cette question
ne sera pas réglée, les recherches en théorie des classes de complexité
seront entravées, et aucun des résultats nécessaires en cryptographie
pour prouver de manière absolue la sûreté des méthodes les plus
utilisées ne sera établi.

Le travail réalisé pendant les 25 dernières années dans la théorie des

classes de complexité n'a cependant pas été vain, et un grand nombre
de classes nouvelles ont été identifiées, qui composent un panorama
détaillé des échelles de difficulté algorithmique, panorama dont on
espère qu'il nous achemine vers le déblocage tant attendu.

La naissance de l'informatique quantique

L'idée de l'informatique quantique part du principe que la vraie théorie
de notre monde physique est la mécanique quantique (et non pas la
mécanique classique), et que nous serons un jour capables de
manipuler un à un de nombreux états quantiques ainsi que de les faire
interagir sans qu'ils perdent leur caractère quantique. Nous aurons
alors construit un ordinateur quantique, où les données élémentaires
ne se trouvent pas soit dans l'état 0 ou dans l'état 1 comme dans
l'ordinateur classique, mais dans une superposition des deux états en
même temps, propriété purement quantique. Auparavant, l'hypothèse
implicite de toute l'informatique théorique était celle d'un monde
newtonien. Cette hypothèse est moins bénigne qu'on le croyait et il a
fallu admettre que de nombreux problèmes fondamentaux doivent être
reformulés dans un monde quantique. Citons deux résultats importants
obtenus dans cette direction.

Le premier concerne encore la cryptographie où l'intrusion de la

mécanique quantique a permis de définir des protocoles d'échanges
secrets dont la sûreté ne repose plus sur des conjectures
mathématiques indémontrées, mais simplement sur l'hypothèse de la
validité des lois quantiques. Ces protocoles qui utilisent des photons
polarisés ont été concrètement mis en place ces dernières années.

Le second résultat, découvert en 1994 par Peter Shor, est la preuve

qu'un ordinateur quantique peut réaliser la factorisation des entiers en
temps polynomial (ce que, comme nous le disions, un ordinateur
classique ne peut vraisemblablement pas faire). Cette preuve a deux
conséquences. D'abord elle montre que l'introduction des modèles
quantiques de calcul change profondément la situation, rendant
possibles des traitements qui ne le sont pas dans le monde classique
(de nouvelles classes de complexité quantiques sont donc venues
compléter la famille commencée avec P et NP). Ensuite, cette preuve
établit que la mise au point de calculateurs quantiques, dont on ne sait
pas aujourd'hui si elle aboutira, entraînerait des bouleversements
graves en cryptographie.

En fait, c'est une nouvelle conception de l'information et du calcul que

suggère la mécanique quantique, et une remise en cause profonde des
modèles jusqu'ici considérés comme absolus. Nous devons revoir le
modèle de la machine de Turing classique – sur lequel reposent les
ordinateurs actuels –, capable d'effectuer tous les types de calculs
possibles, mais uniquement sur des bits classiques. La machine de
Turing classique doit laisser la place à la machine de Turing quantique.
 À la Une

Archéologie 3mn Archéologie 12mn Biologie animale 3mn

Un voilier du haut Fallait-il inventer La dopamine

Moyen Âge l’agriculture ? éveille l’appétit des
découvert près de abeilles
Bordeaux

Auteur
 Jean-Paul Delahaye
Jean-Paul Delahaye est professeur émérite à l'Université de Lille et chercheur au
centre de recherche en informatique, signal et automatique de Lille (CRISTAL). Il est
l'auteur de la rubrique Logique et calcul dans Pour la Science et du blog
Complexités.

Science & fiction

Le paradoxe de Fermi : réflexions sur la vie ailleurs… et sur Terre

Logique & calcul

Mathématiques des engrenages

Logique & calcul

Des cryptomonnaies sobres en énergie ?

Logique & calcul

Bouger vite... jusqu’à l’ubiquité ?

En kiosque
 Tous nos magazines

Hors-série Pour la Science Thema N°32 ssss

N°116

Tous les numéros Tous les numéros

Soutenez l’information
scientifique de qualité
Découvrez les avancées de la recherche expliquées par les
meilleurs spécialistes dans chaque domaine.

Explorez les archives de Pour la Science depuis 1996.

Accédez à tous les articles réservés aux abonnés sur le site

www.pourlascience.fr

Je m'abonne