Une parabole

Prof. Dr. Edsger W. Dijkstra
Burroughs Research Fellow


traduction par Antoine Wojdyla, depuis l'archive EWD594



(Note ajoutée au manuscrit: Récemment, j'ai retrouvé le manuscrit du texte suivant parmi de vieux papiers. Il doit avoir été écrit au milieu de l'année 1973, mais je ne pense pas qu'il ait perdu la moindre valeur [au cours des les trois années écoulées] C'est pourquoi je l'intègre aux archives EWD.)


Il y a quelques années de cela, une société de chemin de fer fut fondée, et l'un de ses administrateurs — probablement un commercial — découvrit que les investissements initiaux pourraient être réduits de manière significative si seuls cinquante pour cent des voitures étaient équipées de toilettes; il fut donc décidé qu'il en serait de la sorte.


Peu de temps après que la compagnie ait commencé son activité, des plaintes concernant les toilettes se faisaient jour. Une enquête fut menée, révélant quelque chose d'évident : malgré sa jeunesse, la société souffrait déjà de problèmes de communication en interne, et les instructions concernant les toilettes n'avaient pas été transmises au centre de répartition des rames, où toutes les voitures étaient donc considérées comme équivalentes. Par conséquent, certains trains n'étaient pourvus d'aucune toilette.

Afin de résoudre le problème, un élément (bit) d'information fut associée à chaque voiture, permettant de déterminer si c'était une voiture avec ou sans toilettes; le centre de répartition des rames fut donc chargé de composer des trains avec un nombre de voitures d'une des deux catégories aussi proche que possible. Cela rendait les choses un peu plus compliqués pour le centre répartition mais, une fois le problème résolu, les personnes responsables des assemblages étaient très fières d'avoir réussi à résoudre le problème.

Cependant, Après les nouvelles procédures d'assemblage soient mises en œuvres, les plaintes concernant les toilettes continuaient d'affluer. Une nouvelle enquête fut diligentée, suite à laquelle il apparu que, bien que dans chaque train près de la moitié des voitures comprenaient effectivement des toilettes, il arrivait que les trains fussent composés d'une première moitié entièrement composées de wagons à toilettes, et l'autre de wagons sans toilettes. Afin de remédier à cette situation, de nouvelles instructions furent édictées, promulguant que les voitures avec et sans toilettes devaient être placées en alternance. C'était une tâche un peu plus compliquée pour les gens de la répartition mais, après quelques réticences initiales, le problème fut résolu.

Les plaintes, pourtant, ne cessaient d'arriver; la raison en était que, comme les voitures avec toilettes avaient leur toilettes à l'une de leurs extrémités, la distance entre deux toilettes successives dans le train pouvait être près de trois longueurs de voiture. Pour les mères ayant des enfants avec des besoins urgents, ou lorsque les bagages étaient encombraient les couloirs, cela pouvait encore pourrait mener à des catastrophes. En conséquence, les voitures avec toilettes furent pourvues d'un autre élément (bit) d'information, leur conférant une orientation, et furent données les nouvelles instructions que dans chaque train les voitures avec toilettes devaient avoir la même orientation. Cette fois, les nouvelles instructions données au centre répartition étaient reçues sans grand enthousiasme, car le nombre machines permettant de faire tourner les voitures était à peine suffisant; pour être tout à fait honnête envers les machinistes, le nombre de machines à tourner les wagons était -à tous les égards- insuffisant, et ce n'était que grâce à leur grande ingéniosité que les machinistes parvenaient tout de même à accomplir leur tâche.

Avec toutes les toilettes équidistantes le long du train, la compagnie était convaincue que maintenant tout allait bien; Mais les passagers ne s'arrêtèrent toutefois pas de se plaindre: même si aucun passager n'était à plus d'une longueur de voiture des toilettes les plus proches, les passagers (ayant un besoin urgent) ne savaient pas dans quelle direction se diriger pour y arriver le plus rapidement. Pour résoudre ce problème, des flèches indiquant «WC» allaient équiper les couloirs de toutes les voitures, ce qui allait également imposer de faire de l'autre moitié des voitures des objets orientés, information qu'il fallait prendre en compte au centre de répartition.

Lorsque la nouvelle instruction arriva au centre de répartition, cela créa une atmosphère allant du désespoir à la révolte : il ne serait jamais possible de mettre ces procédures en œuvre! À ce moment clé, un homme, dont le nom a été oublié à jamais, fit l'observation suivante. Si chaque voiture avec une toilettes était couplée, à compter de ce jour, à son extrémité pourvue de toilettes avec une voiture sans toilettes, le centre de répartition, au lieu d'avoir à traiter avec N voitures orientées de chacun deux types, pourrait n'avoir à affaire qu'à N/2 unités identiques unités qui pourraient, qui plus est, être traitées comme identiques. Et cette observation permit de résoudre tous les problèmes de manœuvre, avec la modeste contrainte de ne pouvoir constituer des trains qu'avec un nombre pair de voitures - le coût des quelques voitures qu'il pourrait être nécessaire d'ajouter étant compensé par économies initiales proposé par le commercial - et, d'autre part, de ne pas être trop regardant sur l'égalité de l'espacement entre les toilettes. Mais, après tout, qui se soucie de quelques mètres?


Et bien qu'à l'époque à laquelle cette histoire eu lieu, l'humanité n'avait pas encore été bénie par les ordinateurs automatiques, l'anonyme qui a proposé cette solution mérite le titre de premier programmeur compétent.


*  *
*

J'ai raconté l'histoire ci-dessus à différents publics. Les programmeurs, en général, sont amusés, tandis que les manageurs invariablement s'agacent, de plus en plus à mesure que l'histoire progresse. Les vrais matheux, cependant, ne comprennent pas où je voulais en venir.