- Lors de sa conférence de Noël 2024 à Stanford, Donald Knuth aborde les strong components et les weak components des graphes orientés, et désigne l’algorithme de Tarjan pour les strong components comme son algorithme préféré
- Si l’on contracte chaque strong component en un seul sommet, on obtient un DAG acyclique, et l’algorithme fonctionne en trouvant puis en retirant un strong component puits
- Ici, un weak component n’est pas une composante connexe obtenue en ignorant les directions, mais une partition plus générale qui regroupe de nouveau les strong components pour former un linear order
- L’algorithme de Tarjan distingue, pendant le DFS, les tree arcs, back arcs, loops, forward arcs et cross arcs, et permet d’obtenir à la fois les strong components et leur tri topologique
- L’attrait souligné par Knuth ne tient pas seulement à la procédure, mais à une structure de données profonde organisée de sorte que les informations de décision nécessaires soient accessibles au moment exact où il faut
Le point de départ de la conférence et le nouveau livre de Knuth
- Les nouvelles données au début de la conférence tournent autour de son nouveau livre, Constraint Satisfaction
- Le manuscrit interne a été envoyé à l’éditeur la veille, et les précommandes sont désormais possibles
- L’impression avant Noël pourrait être difficile, et la date de parution officielle semble être le 3 février
- Dans le livre, l’impression est indiquée comme datant de janvier, et il s’agit du principal projet de Knuth des cinq dernières années
- Des explications plus détaillées sur le thème de cette conférence, Strong Components and Weak Components, se trouvent dans le pre-fascicle 12A
- Le livre actuel est le volume 4 Fascicle 7, et les fascicules précédents ont été publiés en volumes reliés sous les noms volume 4A et 4B
- Ce contenu devrait constituer à terme le premier tiers du volume 4C
- Le sous-titre de la conférence est proche de « Which algorithm do you love the most? »
- Knuth dit qu’il n’aime généralement pas qu’on lui demande de choisir son « algorithme préféré », mais que, dans ce cas, l’algorithme de Tarjan pour les strong components est la réponse évidente
- Lorsqu’il a appris cette procédure en 1973, il a compris pour la première fois qu’une structure de données pouvait être « profonde », au même titre qu’un théorème ou qu’un algorithme
Différence entre strong component et weak component
- Un graphe orienté est composé de sommets et de flèches orientées
- Si deux sommets u et v sont mutuellement atteignables, ils appartiennent au même strong component
- Tous les sommets situés sur un cycle sont inclus dans le même strong component
- Un sommet vers lequel arrivent des chemins depuis plusieurs endroits, mais dont on ne peut pas sortir, peut constituer à lui seul un strong component
- Le weak component tel que l’emploie Knuth est différent d’une composante non orientée obtenue en ignorant les directions
- Selon lui, une composante connectée en ignorant les directions devrait être appelée « undirected component »
- Un weak component est un concept qui partitionne de nouveau le DAG obtenu en contractant les strong components, de façon à ce que l’ensemble forme un ordre linéaire
- Si l’on contracte chaque strong component en un « super-sommet », on obtient un graphe sans cycle
- On peut l’interpréter comme un ordre partiel (partial order)
- Si l’on contracte jusqu’aux weak components, on obtient un ordre total ou ordre linéaire
- Cela est aussi directement lié au tri topologique (topological sorting)
- Si un certain x précède toujours y dans tous les tris topologiques, alors ils se trouvent dans des weak components différents
- Si, dans un tri, x peut précéder y et, dans un autre, y peut précéder x, alors ils se trouvent dans le même weak component
- Knuth relie cela à la notion de mutual incomparability
Histoire des concepts et des algorithmes
- Le concept de weak component est apparu lors d’échanges épistolaires entre Knuth, Ron Graham et un professeur noté Mazkin au sujet d’un autre problème
- Dans une lettre envoyée par Mazkin à Graham le 28 février 1970, il était question d’obtenir un ordre total au moyen d’une partition
- En décembre 1970, Knuth écrit à Graham que les trois avaient prouvé un résultat plus général, chacun avec une approche différente
- Knuth a décidé d’inclure Mazkin comme coauteur, mais a appris peu après que Mazkin était subitement décédé d’une crise cardiaque
- L’article lié est paru en 1972 dans Discrete Mathematics, volume 2, numéro 1
- À l’époque, Discrete Mathematics était une revue tout juste lancée, et personne ne pouvait prévoir combien d’excellents articles y seraient publiés par la suite
- L’algorithme de Tarjan pour les strong components est paru en 1972 dans SIAM Journal on Computing, volume 1, numéro 2
- Tarjan était alors doctorant, et cet article était le sixième dans sa liste de publications
- Knuth a lu cet article en janvier 1973 et s’est pris d’affection pour l’algorithme
- L’algorithme de Tarjan est également bien présenté dans le manuel d’algorithmique d’Aho, Hopcroft et Ullman
- Pendant son congé sabbatique à Stanford, Hopcroft partageait un bureau avec Tarjan, et ils ont conçu plusieurs algorithmes
- Hopcroft avait l’idée d’un algorithme pour les composantes biconnexes des graphes non orientés, et Tarjan a appliqué une idée similaire aux strong components des graphes orientés
- Le livre de Shimon Even traite du low point de l’algorithme de Tarjan
- Tarjan a résolu une situation apparemment circulaire où il semblait falloir le low point pour trouver une composante, et connaître la composante pour calculer le low point
Trouver les strong components avec DFS
- Knuth compare l’exploration de graphes à l’exploration d’une grotte
- Chaque room est un vertex, et la liste des autres rooms accessibles depuis chaque room constitue les outgoing arcs
- L’ordinateur ne voit pas le dessin : il explore uniquement à partir de la liste des vertex et de la liste des arcs
- La méthode d’exploration de base est le depth-first search
- On suit en profondeur un outgoing arc qui n’a pas encore été vu
- S’il n’y a plus d’endroit où aller, on revient à la position précédente
- Lorsqu’on rencontre un vertex déjà visité, on détermine le type de cet arc
- Dans DFS, les arcs se divisent en cinq catégories
- tree arc : arc de l’arbre DFS créé lorsqu’on découvre un nouveau vertex pour la première fois
- back arc : arc qui revient vers un ancestor
- loop : arc qui pointe vers lui-même et n’affecte pas les strong components
- forward arc : arc dirigé vers un descendant
- cross arc : arc dirigé vers un vertex qui n’est ni un ancestor ni un descendant
- Chaque fois que l’algorithme découvre un strong component, il trouve un composant puits du graphe restant
- Un DAG fini possède toujours un puits
- La méthode consiste à retirer le strong component puits puis à recommencer sur le graphe restant
- Ce processus permet de trouver les strong components tout en obtenant aussi leur tri topologique
- Les performances sont présentées comme très rapides
- Pour M arcs et N vertex, le pire cas est de l’ordre de 5M + 17N accès mémoire
- Ce chiffre inclut des opérations comme la vérification de la fin des listes d’arcs et la mise à jour des pointeurs
Weak components, version améliorée et implémentation
- L’algorithme des weak components peut lui aussi s’exécuter en même temps que la recherche des strong components
- Il exploite le fait que les strong components sont découverts de droite à gauche, c’est-à-dire en partant des puits
- Lorsqu’un nouveau strong component s’insère à gauche, on détermine comment il se fusionne avec les weak components existants
- Pour décider des weak components, les sources et puits internes à chaque component sont importants
- Tous les puits d’un weak component doivent avoir des arcs vers toutes les sources du weak component suivant
- Cette condition est nécessaire et suffisante pour avoir des weak components
- En programmation, il est possible de faire les mises à jour en ne suivant que les sources
- En 1974, Tarjan a publié dans Information Processing Letters, volume 3, numéro 1, un article de trois pages sur un algorithme trouvant les weak components
- Knuth en présente le contenu dans son pre-fascicle 12A
- Maintenir suffisamment de structures de données pour garantir un temps linéaire dans le pire cas n’est pas simple
- Dijkstra a lui aussi traité le problème des strong components
- Le chapitre 25 du livre de Dijkstra traite de « Finding the maximal strong components in a directed graph »
- Dijkstra utilisait une structure consistant à retirer progressivement les strong components puits, mais n’est pas parvenu à la simplification par low point de Tarjan
- La solution de Dijkstra introduit quatre nouveaux tableaux pour suivre la structure
- Knuth et Tarjan ont récemment réexaminé l’algorithme existant et en ont produit de meilleures définitions ainsi qu’une version améliorée
- Ils l’ont corrigé à partir d’une idée de Kurki-Suonio des années 1970, mais l’article original contenait une erreur de raisonnement
- Ils ont réduit les accès, qui étaient d’environ 7 par arc dans l’ancienne méthode, à environ 5
- En fusionnant certains fields, ils ont obtenu une forme plus complexe mais plus rapide, qu’ils qualifient en plaisantant non pas de « premature optimization » mais de « post-mature optimization »
- L’implémentation est fournie sous forme de programme CWEB
- Les noms de programmes Tarjan strong and weak et Tarjan strong sont mentionnés
- L’entrée est un graphe au format Stanford GraphBase
- Knuth dit qu’il réorganisera les programmes de son site web pour les rendre plus faciles à trouver et corrigera le fait qu’ils n’ont pas été mis à jour depuis 2022
- Stanford GraphBase contient un exemple de graphe orienté utilisant environ 1 000 catégories du thésaurus Roget comme vertex, et des relations de synonymes ou d’antonymes comme arcs
1 commentaires
Avis sur Hacker News
En 2022, lors d’une visite à San Francisco, je me promenais sur le campus de Stanford et, au moment de sortir après avoir traversé le couloir silencieux et vide d’un bâtiment en été, je suis tombé par hasard sur le bureau de Knuth.
Il était étonnamment petit au regard de sa renommée, si bien que j’ai regardé une seconde fois, mais j’ai plutôt eu l’impression que cet espace correspondait bien à sa personnalité modeste.
https://janvandenberg.blog/wp-content/img_1813-scaled.jpg
J’ai aussi non pas un, mais deux chèques de récompense. Ce n’étaient que de petites coquilles, mais c’est vraiment génial d’avoir ces deux documents.
Personne ne va en faire un mauvais usage, mais si j’apprenais qu’une photo de mon bureau avait été mise en ligne à mon insu, je trouverais ça assez flippant.
Je lis TAOCP 4A et 4B pendant mon temps libre, et c’est vraiment excellent, je le recommande vivement.
Ce n’est pas pratique pour la plupart des programmeurs, mais la manière dont Knuth conçoit et explique les algorithmes est stupéfiante et unique.
En particulier, l’implémentation des liens dansants (Dancing Links) dans le 4B a été largement mise à jour depuis le célèbre article ; c’est une structure de données raffinée et élégante, tout en étant très rapide. Même à plus de 80 ans, il reste impressionnant.
Quand nous avons calculé le coût nécessaire à notre échelle, on arrivait à plusieurs dizaines de millions de dollars, alors que le budget total d’infrastructure de Route 53 était de l’ordre de quelques dizaines de milliers de dollars. À l’edge, nous réutilisions comme serveurs de noms des serveurs CloudFront dont le disque dur était en panne, les serveurs d’API étaient eux aussi modestes, et l’équipe comptait environ six personnes. La façon AWS de « s’accrocher coûte que coûte » consistait à dépenser très peu, à réduire le risque à la baisse et à aller vite.
Il était donc impossible de demander des dizaines de millions de dollars pour des scrubbing appliances ; leur livraison aurait aussi pris longtemps, et cela nous aurait rendus trop dépendants d’un fournisseur donné.
Au début, nous avons décidé d’exploiter les serveurs de noms Route 53 sur des plages d’IP dédiées afin d’obtenir une certaine isolation, et des liens réseau dédiés pouvaient empêcher que le reste de l’infrastructure d’Amazon soit affecté. Mais cela ne résolvait pas le problème du destin partagé entre clients de Route 53, et le plan réel se résumait plus ou moins à : « s’il y a un problème, filtrons extrêmement bien avec les outils réseau et système existants ».
Au début de l’été de cette année-là, je lisais le fascicule le plus récent lié au 4A de Knuth et j’étais plongé dans les algorithmes combinatoires. Un soir, l’idée m’est venue d’un coup : en créant beaucoup de serveurs de noms virtuels, on pouvait attribuer à chaque client une combinaison unique de quatre serveurs de noms virtuels. On pouvait aussi contrôler le degré de recouvrement, et j’ai rapidement calculé qu’avec environ 2 000 serveurs de noms, on pouvait garantir qu’aucune paire de clients n’en partagerait plus de deux. D’après nos expériences, les domaines se résolvent correctement même si deux serveurs de noms ne sont pas joignables, mais au-delà cela devient problématique ; ce nombre était donc important.
L’algorithme de recherche récursive qui attribuait les IP était directement inspiré des algorithmes du 4A, et fournissait deux dimensions d’isolation supplémentaires indépendantes du domaine client. Chaque client reçoit quatre serveurs de noms issus de quatre « stripes » indépendantes, correspondant aux différents domaines de premier niveau utilisés dans les noms de serveurs de noms (co.uk, com, net, org). Ainsi, même si l’un de ces domaines de premier niveau rencontre un problème, par exemple une erreur DNSSEC, un seul serveur de noms est affecté.
Nous les faisions aussi provenir de quatre « braids » indépendantes, ce qui permettait de garantir qu’aucune paire de serveurs de noms ne partage un chemin réseau ou du matériel physique donné. Même si je connaissais la combinatoire grâce à mes bases en statistiques et en cryptographie, je n’aurais pas pu concevoir une telle architecture sans avoir lu le 4A.
Je n’ai jamais été aussi enthousiasmé par une solution. Elle offrait en effet une isolation prouvable au niveau des IP réseau entre domaines clients, pratiquement sans coût d’infrastructure supplémentaire. C’était des mathématiques. Ce n’était pas totalement gratuit : il fallait utiliser 2 000 adresses IP anycast, et, comme de nombreux domaines de premier niveau exigent l’enregistrement des serveurs de noms et des glue records, il a aussi fallu enregistrer 512 domaines. Le processus avec les registrars a été assez amusant, mais nous y sommes finalement parvenus.
Nous avons appelé cette approche Shuffle Sharding, et c’était plus une découverte qu’une invention. De nombreux systèmes multitenant qui utilisent une répartition aléatoire obtiennent une forme de shuffle sharding, et des techniques de filtrage réseau comme Stochastic Fair Blue produisent un effet similaire via un hachage basé sur le temps. Mais je n’avais jamais vu une méthode exactement identique, avec le niveau de contrôle que nous pouvions appliquer, et nous avons même pu l’étendre à un shuffle sharding imbriqué récursif isolant davantage de niveaux, non seulement l’appelant, mais aussi l’appelant de l’appelant dans les schémas d’« appel pour le compte de ».
Quelques années plus tard, par gratitude, je suis allé voir en personne la conférence de Noël de Knuth et je me suis assis au premier rang. Comme on ne sait jamais ce qui peut inspirer, je lis encore aujourd’hui tout ce que Knuth publie. Y compris ses pièces pour orgue.
C’est pourquoi je considère que les livres de Knuth sont étonnamment pratiques pour les programmeurs. Ils élargissent la pensée et approfondissent la compréhension ; que demander de plus ?
L’article original sur Dancing Links est l’un de mes articles préférés. Quand on lit une phrase comme « ce processus fait exécuter aux variables de pointeurs de la structure de données globale une danse délicatement chorégraphiée », on voit directement l’amour de Knuth pour les algorithmes.
Je l’utilise pour générer des mots croisés, en faisant en sorte que les mots horizontaux et verticaux forment une couverture exacte (exact cover) de la grille.
Je me demande si l’algorithme mis à jour utilise moins de mémoire.
Pour ce gros problème, j’estime qu’il existe environ 100 millions de solutions, et même en en trouvant 100 par seconde, il faudrait une dizaine de jours pour finir.
Le problème sur lequel je travaille consiste à compter le nombre de configurations de « Fancy Tetris Houten Puzzel » dans lesquelles les pièces de même couleur sont toutes connectées en partageant au moins un côté.
Je réfléchis aussi à d’autres algorithmes moins sensibles à la mémoire pour résoudre ce problème de couverture exacte.
Je pose la question en tant que personne qui n’a commencé à lire de la littérature en informatique que récemment.
Quand je suis allé à San Francisco il y a quelques années, j’ai été surpris d’apprendre que Donald Knuth était non seulement encore en vie, mais qu’il continuait à donner une conférence chaque année à Stanford.
Je me souviendrai longtemps de cette soirée où j’ai trouvé le bâtiment sur le campus et où je l’ai vu parler en personne d’un sujet que j’avais presque du mal à suivre. Donald Knuth est vraiment une légende.
Un membre de l’équipe a trouvé le mois dernier une erreur dans Seminumerical Algorithms et a reçu un chèque de récompense de 1 hexadecimal dollar, accompagné de l’impression de l’e-mail original annotée à la main.
Ce qui m’inspire le plus chez Donald Knuth, c’est son dévouement et sa discipline sur plusieurs décennies.
Comme je passe sans cesse d’un projet, d’un langage ou d’une distribution à l’autre, j’ai vraiment beaucoup à apprendre de lui.
Le vêtement est très vif et éclatant, il ressemble à un costume traditionnel du monde ou folklorique qu’on portait autrefois dans un village, mais je ne sais pas trop si c’est iranien, slave, ou quelque part entre les deux
Quelqu’un saurait mieux deviner ?
Mon souvenir est flou, et cela avait peut-être aussi un lien avec sa femme. Il semble la porter souvent dans ses conférences depuis le milieu des années 2010, et il doit bien y avoir une explication quelque part
En 2012, je me suis retrouvé à côté de Knuth devant le Manchester Town Hall, alors qu’il essayait de monter sur un rebord de fenêtre pour voir arriver la flamme olympique sur la place. Je lui ai parlé, et j’ai tendu la main un instant de peur qu’il tombe par la fenêtre, mais tout s’est bien passé. Il m’a donné l’impression d’être quelqu’un de très curieux, dont les questions et l’intelligence rayonnaient, et qui paraissait plus jeune que son âge
Nous assistions tous les deux à un événement célébrant le centenaire de la naissance d’Alan Turing, et c’était saisissant de voir dans la même pièce des géants de l’informatique comme Knuth, Gary Kasparov, Fred Brooks ou Vint Cerf. À l’heure du déjeuner, la flamme olympique est arrivée sur la place à l’extérieur, et il n’a pas pu résister à l’envie d’aller voir. Il semblait être le seul à s’en enthousiasmer autant
Il a donné une conférence au dîner ce soir-là, et plus tard, quand je l’ai recroisé à Manchester au moment où le volume 4B venait de paraître, je lui ai demandé de signer mon livre et il m’a vaguement reconnu de l’événement précédent
Si je raconte cela, c’est parce que sa chemise me semble suggérer un esprit beaucoup plus éclectique et curieux. J’en ai clairement vu des preuves ailleurs aussi
Son affection pour le costume traditionnel sami vient peut-être de là
[0]: https://youtu.be/jB0aeePskBg
https://www.youtube.com/playlist?list=PLoROMvodv4rOAvKVR_dyC...
Après vérification, il a 87 ans. Donald Knuth est né le 10 janvier 1938
Waouh
Knuth est toujours aussi impressionnant
En revanche, je trouve très surprenant et décevant que personne à Stanford n’ait correctement pris en charge un enregistrement audio digne d’un tel contenu. On dirait que ça a été enregistré avec un dictaphone dans une poche
Je ne parle pas de la voix âgée de Knuth : il suffit d’écouter la mauvaise qualité du son quand il s’arrête et prend les questions du public
Ce genre de vidéo me rappelle pourquoi je suis tombé amoureux des ordinateurs au départ
C’est assez incroyable qu’il soit encore aussi vif. Malheureusement, quand j’étais étudiant en licence il y a une vingtaine d’années, il ne donnait déjà plus de cours
J’aime sa manière de traiter les questions : https://youtu.be/Hi8r_63LGyg?t=827
Il prend le temps de comprendre ce qui est demandé, puis répond très clairement