- Donald Knuth tratou de strong components e weak components em sua palestra de Natal de 2024 em Stanford, e apontou o algoritmo de componentes fortes de Tarjan como seu algoritmo favorito
- Ao contrair cada strong component em um único vértice, o resultado é um DAG sem ciclos, e o algoritmo funciona encontrando e removendo componentes fortes sumidouro
- Aqui, weak component não significa um componente conexo com a direção ignorada, mas uma partição mais geral que volta a agrupar os strong components de modo a formar uma linear order
- O algoritmo de Tarjan distingue, durante o DFS, tree arc, back arc, loop, forward arc e cross arc, obtendo ao mesmo tempo os strong components e sua ordenação topológica
- O aspecto que Knuth destaca não é só o procedimento, mas a estrutura de dados profunda organizada para que a informação necessária para cada decisão esteja acessível exatamente no momento certo
O ponto de partida da palestra e o novo livro de Knuth
- A atualização inicial da palestra foi centrada no novo livro Constraint Satisfaction
- O manuscrito interno foi enviado à editora no dia anterior, e a pré-venda também passou a estar disponível
- A impressão antes do Natal pode ser difícil, e a data oficial de lançamento parece ser 3 de fevereiro
- No livro, consta janeiro como mês de impressão, e esse foi o principal projeto de Knuth nos últimos 5 anos
- Mais detalhes sobre o tema desta palestra, Strong Components and Weak Components, estão no pre-fascicle 12A
- Atualmente, o livro está no volume 4 Fascicle 7, e os fascicles anteriores foram publicados em capa dura como volume 4A e 4B
- Esse conteúdo deverá formar futuramente o primeiro terço do volume 4C
- O subtítulo da palestra fica próximo de “Which algorithm do you love the most?”
- Knuth normalmente não gosta da pergunta sobre “algoritmo favorito”, mas disse que, neste caso, a resposta é claramente o algoritmo de componentes fortes de Tarjan
- Quando aprendeu esse procedimento em 1973, foi a primeira vez que entendeu que uma estrutura de dados podia ser “profunda” tanto quanto um teorema ou um algoritmo
A diferença entre strong component e weak component
- Um grafo direcionado é composto de vértices e setas com direção
- Se dois vértices
uevsão mutuamente alcançáveis, pertencem ao mesmo strong component - Todos os vértices em um ciclo pertencem ao mesmo strong component
- Mesmo que existam caminhos entrando por vários lugares, um vértice do qual não se pode sair pode formar sozinho um strong component
- Se dois vértices
- O termo weak component usado por Knuth é diferente de um componente não direcionado obtido ao ignorar a direção
- A posição dele é que os componentes conectados ao ignorar a direção deveriam ser chamados de “undirected component”
- Weak component é o conceito de particionar novamente o DAG obtido ao contrair os strong components, de modo que o conjunto inteiro se torne uma ordem linear
- Ao contrair cada strong component em um “supervértice”, obtém-se um grafo sem ciclos
- Isso pode ser visto como uma ordem parcial
- Ao contrair também os weak components, obtém-se uma ordem total, ou linear order
- Isso também se conecta diretamente à ordenação topológica
- Se algum
xsempre aparece antes deyem toda ordenação topológica possível, eles estão em weak components diferentes - Se em uma ordenação
xvem antes dey, mas em outraypode vir antes dex, então ambos pertencem ao mesmo weak component - Knuth relaciona isso à mutual incomparability
- Se algum
A história dos conceitos e dos algoritmos
- O conceito de weak component surgiu durante a troca de cartas entre Knuth, Ron Graham e um professor identificado como Mazkin, a respeito de outro problema
- Em uma carta de 28 de fevereiro de 1970, Mazkin escreveu a Graham sobre obter uma ordem total por meio de uma partição
- Em dezembro de 1970, Knuth escreveu a Graham dizendo que os três haviam provado um resultado mais geral, cada um por uma abordagem diferente
- Knuth decidiu incluir Mazkin como coautor, mas logo depois recebeu a notícia de que Mazkin havia morrido subitamente de ataque cardíaco
- O artigo relacionado foi publicado em 1972 na Discrete Mathematics volume 2 número 1
- Na época, Discrete Mathematics era uma revista recém-lançada, e ninguém imaginava quantos excelentes artigos seriam publicados ali depois
- O algoritmo de componentes fortes de Tarjan foi publicado em 1972 no SIAM Journal on Computing volume 1 número 2
- Tarjan ainda era estudante de pós-graduação, e esse artigo era o sexto de sua lista de publicações
- Knuth leu esse artigo em janeiro de 1973 e passou a gostar do algoritmo
- O livro de algoritmos de Aho, Hopcroft e Ullman também apresenta bem o algoritmo de Tarjan
- Durante um período sabático em Stanford, Hopcroft dividiu escritório com Tarjan e idealizou vários algoritmos com ele
- Hopcroft tinha a ideia de um algoritmo para componentes biconexos em grafos não direcionados, e Tarjan aplicou uma ideia semelhante aos componentes fortes em grafos direcionados
- O livro de Shimon Even trata do low point do algoritmo de Tarjan
- Parecia haver uma situação circular em que, para encontrar os componentes, seria preciso o low point, mas para calcular o low point seria preciso conhecer os componentes; Tarjan resolveu esse impasse
Como encontrar strong components com DFS
- Knuth compara a exploração de grafos à exploração de uma caverna
- Cada sala é um vértice, e a lista de outras salas acessíveis a partir dela corresponde aos arcos de saída
- O computador faz a exploração olhando apenas para a lista de vértices e a lista de arcos, sem ver o desenho do grafo
- O método básico de exploração é o depth-first search
- Segue-se em profundidade por um arco de saída ainda não visto
- Quando não há mais para onde ir, volta-se à posição anterior
- Ao encontrar um vértice já visitado, determina-se o tipo daquele arco
- No DFS, os arcos se dividem em cinco tipos
- tree arc: arco da árvore DFS criado ao descobrir um novo vértice pela primeira vez
- back arc: arco que retorna a um ancestral
- loop: arco que vai para o próprio vértice e não afeta os strong components
- forward arc: arco que aponta para um descendente
- cross arc: arco que aponta para um vértice que não é nem ancestral nem descendente
- Sempre que o algoritmo descobre um strong component, ele encontra o sink component do grafo que ainda resta
- Todo DAG finito sempre tem um sink
- O processo avança removendo esse sink strong component e repetindo a busca no grafo restante
- Com isso, o algoritmo encontra os strong components e ao mesmo tempo obtém sua ordenação topológica
- O desempenho apresentado é muito rápido
- Para
Marcos eNvértices, no pior caso o número de acessos à memória fica em torno de5M + 17N - Isso inclui operações como verificar o fim da lista de arcos e atualizar ponteiros
- Para
Weak components, versão melhorada e implementação
- O algoritmo de weak components também pode ser executado junto com a busca dos strong components
- Isso aproveita o fato de que os strong components são descobertos da direita para a esquerda, isto é, começando pelos sinks
- Quando um novo strong component entra à esquerda, decide-se como ele deve ser combinado com os weak components já existentes
- Para determinar weak components, os sources e sinks dentro de cada componente são importantes
- Todos os sinks de um weak component precisam ter arcos para todos os sources do weak component seguinte
- Essa condição é necessária e suficiente para que existam weak components
- Na implementação, basta rastrear apenas os sources para fazer as atualizações
- Em 1974, Tarjan publicou um artigo de 3 páginas sobre um algoritmo para encontrar weak components na Information Processing Letters volume 3 número 1
- Knuth resume esse conteúdo em seu pre-fascicle 12A
- Manter uma estrutura de dados suficiente para garantir tempo linear no pior caso não é algo simples
- Dijkstra também tratou do problema dos strong components
- O capítulo 25 de seu livro aborda “Finding the maximal strong components in a directed graph”
- Dijkstra também usava a estrutura de remover sink strong components, mas não chegou à simplificação do low point de Tarjan
- A solução de Dijkstra introduz quatro novos arrays para acompanhar a estrutura
- Knuth e Tarjan revisitaram recentemente os algoritmos existentes e produziram definições melhores e uma versão aperfeiçoada
- Eles a reformularam com base em uma ideia dos anos 1970 de Kurki-Suonio, mas o artigo original continha uma falácia
- Reduziram o número de acessos por arco de cerca de 7 para cerca de 5
- Unificaram alguns campos para obter uma forma mais complexa, porém mais rápida, brincando que isso não é “premature optimization”, mas “post-mature optimization”
- A implementação é fornecida como um programa CWEB
- São mencionados os nomes de programa Tarjan strong and weak e Tarjan strong
- A entrada é um grafo no formato Stanford GraphBase
- Knuth disse que vai reorganizar os programas de seu site para facilitar a busca e corrigir o fato de eles não serem atualizados desde 2022
- O Stanford GraphBase inclui um exemplo de grafo direcionado com cerca de 1.000 categorias do tesauro de Roget como vértices e relações de sinônimo ou antônimo como arcos
1 comentários
Comentários do Hacker News
Em 2022, quando visitei San Francisco, eu estava passeando pelo campus de Stanford e, no momento em que ia sair por um corredor silencioso e vazio de um prédio durante o verão, acabei encontrando por acaso o escritório de Knuth
Em comparação com sua fama, era surpreendentemente pequeno, então olhei de novo, mas, no fim, pareceu um espaço que combinava bem com sua personalidade modesta
https://janvandenberg.blog/wp-content/img_1813-scaled.jpg
Também tenho não um, mas dois cheques de recompensa. Eram pequenos erros de digitação, mas é muito legal ter esses dois documentos
Ninguém vai usar isso para o mal, mas eu acharia bem assustador descobrir que uma foto do meu escritório foi publicada sem eu saber
No tempo livre, estou lendo TAOCP 4A e 4B, e é realmente excelente; recomendo muito.
Não é prático para a maioria dos programadores, mas a forma como Knuth projeta e explica algoritmos é surpreendente e única.
Em especial, a implementação de Dancing Links no 4B foi bastante atualizada desde o artigo famoso; é uma estrutura de dados sofisticada e bonita, além de ser muito rápida. Mesmo na casa dos 80, ele continua incrível.
Quando calculamos o custo necessário para a nossa escala, deu dezenas de milhões de dólares, mas o orçamento total de infraestrutura do Route 53 era da ordem de dezenas de milhares de dólares. Na borda, reutilizávamos como nameservers servidores do CloudFront com discos rígidos quebrados; os servidores de API também eram modestos, e a equipe tinha cerca de 6 pessoas. O jeito AWS de “fazer na raça” era gastar quase nada, reduzir o risco de queda e entregar rápido.
Por isso, não dava para pedir dezenas de milhões de dólares para packet scrubbers; eles também demorariam a chegar e poderiam nos deixar dependentes demais de um fornecedor específico.
No início, decidimos operar os nameservers do Route 53 em faixas de IP dedicadas para obter algum isolamento, e com links de rede dedicados dava para impedir que outras infraestruturas da Amazon fossem afetadas. Mas isso não resolvia o problema de os clientes do Route 53 compartilharem o mesmo destino; o plano real era algo como “se der problema, vamos filtrar muito bem com as ferramentas de rede e sistema existentes”.
No começo daquele verão, eu estava mergulhado em algoritmos combinatórios enquanto lia os fascículos mais recentes relacionados ao 4A de Knuth, quando, certa noite, a ideia “clicou”: se criássemos muitos nameservers virtuais, poderíamos atribuir a cada cliente uma combinação única de quatro nameservers virtuais. Também era possível controlar o grau de sobreposição, e calculei rapidamente que, com cerca de 2.000 nameservers, dava para garantir que quaisquer dois clientes não compartilhassem mais de dois. Em testes, um domínio continuava resolvendo bem mesmo que dois nameservers não fossem alcançáveis, mas a partir daí começava a dar problema; por isso esse número era importante.
O algoritmo de busca recursiva para atribuir IPs foi diretamente inspirado em algoritmos do 4A, e fornecia mais duas dimensões de isolamento independentes do domínio do cliente. O cliente recebia quatro nameservers em quatro “stripes” independentes, correspondentes aos diferentes domínios de topo usados nos nomes dos nameservers (co.uk, com, net, org). Assim, mesmo que um desses domínios de topo tivesse algum problema, como um erro de DNSSEC, apenas um nameserver seria afetado.
Também fizemos com que eles viessem de quatro “braids” independentes, para garantir que quaisquer dois nameservers não compartilhassem um caminho de rede específico nem hardware físico. Mesmo conhecendo combinatória por causa da minha formação em estatística e criptografia, eu não teria conseguido fazer esse projeto se não tivesse lido o 4A.
Nunca fiquei tão empolgado com uma solução. Ela fornecia, praticamente sem custo adicional de infraestrutura, um isolamento comprovável em nível de IP de rede entre domínios de clientes. Era matemática. Não era totalmente grátis: precisávamos usar 2.000 endereços IP anycast, e também registrar 512 domínios por causa da forma como muitos domínios de topo exigem registro de nameservers e registros glue. O processo com os registradores foi bem divertido, mas no fim conseguimos.
Chamamos essa abordagem de Shuffle Sharding, e ela está mais para descoberta do que para invenção. Muitos sistemas multitenant que usam alocação aleatória acabam obtendo algum tipo de shuffle sharding, e técnicas de filtragem de rede como Stochastic Fair Blue produzem efeito semelhante com hashing baseado em tempo. Mas eu nunca tinha visto exatamente esse método com o nível de controle que conseguimos aplicar, e ele podia ser estendido para shuffle sharding recursivo e aninhado, isolando em mais níveis não só o chamador, mas também o chamador do chamador em padrões de “chamar em nome de”.
Alguns anos depois, em agradecimento, fui pessoalmente assistir à palestra de Natal de Knuth e sentei na primeira fila. Como nunca se sabe o que vai inspirar você, ainda leio tudo que Knuth publica. Incluindo até as peças para órgão.
Por isso considero os livros de Knuth surpreendentemente práticos para programadores. Eles ampliam o pensamento e aprofundam a compreensão; o que mais alguém poderia querer?
O artigo original de Dancing Links é um dos meus artigos favoritos. Em frases como “esse processo faz as variáveis de ponteiro na estrutura de dados global executarem uma dança cuidadosamente coreografada”, dá para ver claramente o amor de Knuth por algoritmos.
Estou usando isso para gerar palavras cruzadas, fazendo com que as palavras horizontais e verticais formem uma cobertura exata (exact cover) da grade.
Fico curioso para saber se o algoritmo atualizado usa menos memória.
Estimo que esse problema grande tenha cerca de 100 milhões de soluções; mesmo encontrando 100 por segundo, levaria uns dez dias para terminar.
O problema em que estou trabalhando é contar o número de casos em que, no ‘Fancy Tetris Houten Puzzel’, peças da mesma cor ficam todas conectadas por pelo menos um lado em comum.
Também estou pensando em outros algoritmos menos sensíveis a memória para resolver esse problema de cobertura exata.
Pergunto como alguém que só recentemente começou a ler literatura relacionada à ciência da computação.
Alguns anos atrás, quando fui a San Francisco, fiquei surpreso ao descobrir que Donald Knuth não só ainda estava vivo, como continuava dando palestras todos os anos em Stanford.
A noite em que fui procurar o prédio no campus e o vi falar pessoalmente sobre um tema que eu quase não conseguia acompanhar ficou marcada por muito tempo. Donald Knuth é realmente uma lenda.
Um colega de equipe encontrou no mês passado um erro em Seminumerical Algorithms e recebeu um cheque de recompensa de 1 hexadecimal dollar; ele veio junto com a impressão do e-mail original, com anotações manuscritas.
O que mais me inspira em Donald Knuth é sua dedicação e disciplina ao longo de décadas.
Como alguém que vive trocando de projeto, linguagem e distribuição, tenho muito a aprender com ele.
A roupa é muito vívida e cheia de vida, parece aqueles trajes tradicionais/folclóricos usados em vilarejos antigos, mas não sei bem se é iraniana, eslava ou algo entre os dois
Alguém consegue chutar melhor?
Minha lembrança é vaga, e talvez também tivesse relação com a esposa dele. Parece que ele a usa com frequência em palestras desde meados da década de 2010, e deve haver uma explicação em algum lugar
Certa vez, em 2012, eu estava ao lado de Knuth quando ele tentava subir no parapeito de uma janela para ver a tocha olímpica chegando à praça em frente ao Manchester Town Hall. Falei com ele e, por um instante, estendi a mão com medo de que ele caísse pela janela, mas ficou tudo bem. Ele me pareceu uma pessoa muito curiosa, com perguntas e inteligência brilhantes, e mais jovem do que a idade
Nós dois estávamos participando de um evento em comemoração ao centenário de nascimento de Alan Turing, e foi surpreendente estar na mesma sala que gigantes da ciência da computação como Knuth, Gary Kasparov, Fred Brooks, Vint Cerf e outros. Na hora do almoço, a tocha olímpica chegou à praça do lado de fora, e ele não conseguiu resistir e foi ver. Parecia que ele era o único empolgado com aquilo
Ele palestrou no jantar daquela noite e, mais tarde, quando o encontrei novamente em Manchester logo depois da publicação do 4B, pedi que autografasse o livro, e ele pareceu me reconhecer vagamente do evento anterior
Conto essa história porque acho que a camisa dele sugere uma mente muito mais eclética e curiosa. Definitivamente vi sinais disso em outros lugares também
Então talvez venha daí o carinho dele pelos trajes tradicionais Sami
[0]: https://youtu.be/jB0aeePskBg
https://www.youtube.com/playlist?list=PLoROMvodv4rOAvKVR_dyC...
Fui conferir e ele tem 87 anos. Donald Knuth nasceu em 10 de janeiro de 1938
Uau
Knuth continua impressionante
Mas é bem surpreendente e decepcionante que ninguém em Stanford tenha cuidado direito de uma gravação de áudio à altura desse material. Parece que foi gravado com um gravador no bolso de alguém
Não estou falando da voz envelhecida de Knuth; basta ouvir como a qualidade do áudio fica ruim quando ele para e recebe perguntas da plateia
Vídeos assim me lembram por que eu me apaixonei por computadores em primeiro lugar
É bastante impressionante que ele ainda esteja tão afiado. Infelizmente, quando eu era aluno de graduação, há mais de 20 anos, ele já não dava mais aulas
Gosto da forma como ele lida com perguntas: https://youtu.be/Hi8r_63LGyg?t=827
Ele dedica tempo para entender o que está sendo perguntado e responde com muita clareza