Le paysan russe, l’ordinateur, le télescope et l’informatique en tant que science fondamentale.

« L'informatique n'est pas plus la science des ordinateurs que l'astronomie n'est celle des télescopes. »

Chaque fois que je me le répète, je suis stupéfait par la puissance de cet aphorisme attribué au grand informaticien et mathématicien Edsger Dijkstra (né à Rotterdam le 11 mai 1930 et mort à Nuenen le 6 août 2002):

Edsger Dijkstra ( 1930-2002)

En général, je commence mon cours d'informatique en insistant particulièrement sur cette phrase.

D'abord pour marquer à quel point je compte inscrire mes considérations aussi loin que possible de tout bidouillage bureautico-logicielo-mercantile de type 'heures facturées SSII'.

Et surtout pour bien les convaincre  - dans la logique de la phrase de Djikstra - que l'informatique théorique a existé bien avant la fabrication du premier ordinateur.

L’informatique fondamentale est une branche particulière des mathématiques discrètes visant particulièrement à l’étude des processus itératifs. Et comme les autres théories mathématiques, elle forme un pays présent de toute éternité, un continent platonicien à l'intérieur duquel nous apprenons à nous balader, et que, peu à peu, nous cartographions de plus en plus précisément. Il s'agit, au sein de cette immensité, d'en mettre à jour les merveilles, les sites exceptionnels...

Je tente aussi de bien leur faire comprendre qu'à l'aune de la connaissance de ce continent, nous vivons une époque formidable, puisque la technique nous permet de regarder dedans, de le scruter comme jamais personne auparavant. Oui, aujourd'hui, nous disposons de puissants télescopes - il faut s'en réjouir, et les utiliser au maximum de leurs possibilités. Comme de fins instruments de musique à deux, quatre, seize, voire à trente-deux coeurs -  de superbes Stadivarius Intel Penthium 12- sur lesquels faire jouer au mieux la partition de chaque algorithme écrit au préalable au tableau.
Sans oublier pour autant que ses premiers explorateurs ont fait avec les moyens du bord.

C'est pourquoi, en introduction à mon chapitre sur la récursivité, j'explique aux étudiants la méthode de multiplication du paysan russe.

Pendant des millénaires - au gré de leurs besoins dans la vie quotidienne - les hommes ont multiplié les nombres en utilisant cet algorithme dont voici, brièvement le principe.

Slide emprunté à Richard Terrat ( faculté d'Assas)

Et voilà son fonctionnement appliqué au calcul de 35 par 19

Slide emprunté à Richard Terrat ( faculté d'Assas)

Cette technique récursive est notamment connue grâce au papyrus Rhind, papyrus hiératique écrit au xviie siècle av. J.-C. (env. -1650).

Papyrus Rhind, écrit au XVIIième siècle avant J.C. ( British Museum)

'Le papyrus Rhind est un célèbre papyrus de la Deuxième Période intermédiaire écrit par le scribe Ahmès. Son nom vient de l'Écossais Alexander Henry Rhind qui l'acheta en 1858 à Louxor, mais il aurait été découvert sur le site de la ville de Thèbes. Depuis 1865 il est conservé au British Museum. Avec le papyrus de Moscou, il constitue l'une des plus importantes  sources pour la connaissance des mathématiques dans l'Égypte antique.

Ahmès indique que son papyrus est, en partie, une copie de résultats plus anciens remontant au Moyen Empire (vers -2000). Le papyrus Rhind contient 87 problèmes résolus d'arithmétique, d'algèbre, de géométrie et d'arpentage, sur plus de cinq mètres de longueur et trente-deux centimètres de large. Il est rédigé en écriture hiératique.'

L'algorithme du paysan russe fut utilisé en Europe jusqu'à l'introduction des chiffres arabes.
Son intérêt réside dans le fait que son application dans le calcul de x par y  conduit en général à O(log x) additions alors que la méthode naïve est en O(x).

Je dois quand même apporter une précision à la fin de cet article: si l’on se fie à Wikipedia, la fameuse phrase attribuée à Dijkstra, est en fait l’oeuvre de Michael R. Fellows et Ian Parberry dans un article du journal Computing Research News.

Ce qui me gène.

Car j'aurais préféré qu'elle soit effectivement du grand Dijkstra, lauréat du prix Turing en 1972

J'aime à penser que c'est à lui, plus qu'à quiconque, lui Edsger Dijkstra, lui le lauréat du prix Turing de 1972, qu'il seyait de prononcer cette phrase. Oui si le monde était bien fait, c'est Djikstra qui aurait dû la sortir du néant, cette phrase, et, la portant à bout de bras, la montrer à l'univers tout entier.

Ce qui nous ramène inévitablement au dénouement d'un de mes films préférés: ‘L’homme qui tua Liberty Valance’: 

'Ici dans l'Ouest, quand la légende surpasse la réalité, on imprime la légende.'

 'L'Homme qui tua Liberty Valance', John  Ford, 1962

On a beau dire, on a beau écrire, tout le monde continue à l'attribuer à Djikstra , cette phrase - comme si on ne pouvait pas s'en empêcher, tant nous autres humains sommes des chercheurs de cohérence, des amoureux fous de ce qui porte sens.

Quand on y réfléchit, c'est une grande part de l'activité humaine que d'avoir, toujours et partout, essayé - à la force du poignet bien souvent, et il ne faut pas être trop regardant - de plaquer sur le monde une cohérence qui n'existe pas ailleurs que dans nos cerveaux.

Alors  finalement, moi aussi je fais comme le journaliste dans le western, j'imprime la légende en continuant invariablement à dire à mes étudiants que la phrase est de Djikstra, de celui qui a inventé le fameux algorithme capable de vous fournir, en O(n^2), le plus court chemin d'un point origine à n'importe quel autre point d'un graphe pondéré.

Lee Marvin, James Stewart et John Wayne dans 'L'Homme qui tua Liberty Valance' de John  Ford ( 1962)

Donc la phrase est bien de Djikstra et je termine en la recopiant une fois encore - car je ne me lasse pas de la répéter, comme une bienveillante litanie:

« L'informatique n'est pas plus la science des ordinateurs que l'astronomie n'est celle des télescopes. »