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):

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.

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

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).

' 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.'

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é.

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. "

En marchant tout à l'heure dans la rue, me vient aux lèvres, sans prévenir, ce petit bout de 'l'Aventurier':

'... Avec l'ami Bill Balantine Sauvé de justesse des crocodiles'

Dans toutes ces histoires de super-héros, voilà bien ce qui au fond n'est pas tolérable: ce 'de justesse'.

Les super-héros sont systématiquement sauvés de justesse. A force de tant défier les lois de la probabilité, cela en devient vraiment déprimant, comme une insulte persistante à l'intelligence.

Je ne peux éprouver ni tendresse véritable ni sympathie pour ce genre de robots toujours artificiellement sauvés de justesse. Des robots? Pas des hommes en tout cas.

Du coup - du coup, mais allez vraiment savoir pourquoi - je me rappelle une phrase de C. qui m'avait, à l'époque où il l'avait prononcée, extraordinairement troublé.

Nous avions vingt ans, et, la soirée s'imprégnant d'un soupçon de nostalgie, nous en étions arrivés à ce point où défilait devant ...

Si on décide par exemple de dénombrer les matrices carrées de taille n comportant exactement deux '1' dans chaque ligne et dans chaque colonne ( avec partout ailleurs des zéros), c'est pour moi un problème neuf. Je n'y ai jamais réfléchi et peut-être même que personne avant moi n'y a réfléchi. Pourtant, on sent qu'il y a des relations à découvrir, on sent qu'il existe des liens originels. Je n'ai pas d'inquiétude: il existe forcément des choses à voir, à remarquer, à prouver. Les relations, les propriétés, les théorèmes concernant ce problème sont là depuis toute éternité comme la momie d'un pharaon dans une tombe restée inviolée: ils nous attendent, ils ne demandent qu'à être cueillis, ils ont été installés pour ainsi dire à l'aplomb de ce sujet avant même la venue sur terre du premier homme. Tout est là depuis toujours, des choses nous attendent dans l'ombre, il suffit de les découvrir. Les mathématiques ne sont pas un grand livre à f...

Je remercie Franck Antunes qui se trouve de fait à l'origine de cet article.

J'ai découvert, ce matin, la page de Franck à la faveur d'un billet qu'il a publié sur Le Club de La Cause Littéraire au sujet de sa lecture de 'John Barleycorn' de Jack London (1913).

Parcourant son mur, je découvre qu'il est fan de Bruce Springsteen, ce qui nous fait un point commun. Voulant me manifester auprès de lui, autrement que par un simple 'j'aime', j'ai écrit la première chose qui m'est passé par l'esprit, à savoir que je lui recommandais la lecture de 'Born To Run' l'autobiographie du Boss. Ce conseil - assez inutile car Franck a l'air d'être un vrai fan - m'a immédiatement fait repenser au grand hêtre pourpre.

Voilà ce que Springsteen en écrit vers la la fin de 'Born To Run', presqu'en guise de conclusion :

' Un soir de novembre, dans la période où j'écrivais ce livre, j'ai pris une fois de plus la voiture ...