Robert Tarjan: A gramática dos algoritmos eficientes

Peça a qualquer estudante de ciência da computação para rastrear um grafo com busca em profundidade e eles estarão, quer saibam ou não, executando uma técnica que Robert Tarjan transformou de uma curiosidade em uma disciplina. Seu artigo de 1972 "Depth-first search and linear graph algorithms" é lido hoje como um texto de gramática fundamental — o tipo de trabalho tão profundamente absorvido pelo campo que o nome de seu autor quase desapareceu da maneira como as pessoas falam sobre ele, mesmo quando seu nome está ligado a meia dúzia de estruturas que eles usam todos os dias.

O caminho de um matemático para as máquinas

Robert Endre Tarjan nasceu em 30 de abril de 1948, em Pomona, Califórnia, filho de George Tarjan, um psiquiatra infantil especializado em deficiência intelectual; seu irmão mais novo, James, tornou-se grande mestre de xadrez. Tarjan queria ser astrônomo quando menino, até que as colunas de quebra-cabeças de Martin Gardner na Scientific American e um professor inspirador da oitava série o levaram para a matemática. Ele obteve um bacharelado em matemática no Caltech em 1969, depois foi para Stanford para um mestrado em ciência da computação em 1971 e um doutorado em 1972, com uma dissertação sobre algoritmos de planaridade supervisionada por Robert Floyd e Donald Knuth. Mais tarde, ele descreveria sua escolha de campo de forma simples: a ciência da computação era uma maneira de fazer matemática que poderia ter impacto prático — uma frase que também serve como uma descrição de todo o seu trabalho.

Construindo o kit de ferramentas

A carreira de Tarjan, que abrangeu Cornell, UC Berkeley, Stanford, AT&T Bell Labs, NYU, NEC Research Institute, Microsoft Research, Compaq, Hewlett Packard e Intertrust Technologies antes de se estabelecer em Princeton em 1985 como professor universitário distinto James S. McDonnell, produziu um corpo de algoritmos e estruturas de dados incomum pela quantidade deles que se tornaram infraestrutura de suporte em vez de curiosidades teóricas. Seu nome está ligado ao algoritmo de Tarjan para encontrar componentes fortemente conectados em um grafo, um algoritmo off-line para calcular ancestrais comuns mínimos e um algoritmo de tempo linear para encontrar pontes — todas técnicas construídas sobre a estrutura de busca em profundidade que ele formalizou. Em 1975, ele deu a primeira análise exata da estrutura de dados union-find combinada com compressão de caminho, provando seu tempo de execução amortizado quase constante usando a função de Ackermann inversa, um resultado tão intimamente ligado ao desempenho no mundo real que agora sustenta tudo, desde o algoritmo de árvore geradora mínima de Kruskal até otimizações de compiladores. Com Daniel Sleator nos Bell Labs, ele co-inventou splay trees, árvores de busca binária autoajustáveis que se reequilibram através do uso em vez de carregar metadados de equilíbrio explícitos, e com elas foi pioneiro na análise competitiva, uma estrutura para julgar algoritmos on-line contra um adversário onisciente. Com Michael Fredman, ele desenvolveu heaps de Fibonacci em 1985, uma estrutura de fila de prioridade que tornou o algoritmo de caminho mais curto de Dijkstra e algoritmos de otimização de rede assintoticamente mais rápidos do que qualquer coisa que existia antes. Seu livro didático, Data Structures and Network Algorithms, ganhou o Prêmio Frederick W. Lancaster e tornou-se leitura padrão na área.

O avanço da planaridade com Hopcroft

A única conquista mais explicitamente creditada em sua citação do Prêmio Turing é o trabalho conjunto com John Hopcroft: o primeiro algoritmo de tempo linear para testar se um grafo pode ser desenhado em um plano sem que nenhuma aresta se cruze, publicado em 1974. O teste de planaridade era um problema lento e difícil antes que o algoritmo deles o reduzisse a uma questão de travessia cuidadosa em profundidade — uma técnica tão central para a solução deles que a formalização anterior de Tarjan da busca em profundidade tornou-se, em retrospectiva, a ferramenta que tornou possível o resultado de Hopcroft-Tarjan. Os dois compartilharam o Prêmio ACM Turing de 1986 "por conquistas fundamentais no projeto e análise de algoritmos e estruturas de dados", uma citação que credita um corpo de trabalho conjunto e paralelo em vez de qualquer artigo único.

Reconhecimento ao longo de quatro décadas

Tarjan foi o primeiro ganhador do Prêmio Nevanlinna em Ciência da Informação em 1983, homenageando contribuições notáveis para aspectos matemáticos da ciência da computação. Ele ganhou o Prêmio Turing em 1986, foi eleito para a Academia Americana de Artes e Ciências em 1985, para a Academia Nacional de Ciências em 1987 e para a Academia Nacional de Engenharia em 1988. Ele recebeu o Prêmio Paris Kanellakis em Teoria e Prática em 1999 e o Prêmio de Ex-Alunos Distintos do Caltech em 2010. Seu histórico de publicações ultrapassa 250 artigos com dezenas de milhares de citações, e ele possui mais de uma dúzia de patentes nos EUA em estruturas de dados e segurança, refletindo uma carreira que se moveu fluidamente entre a teoria acadêmica em Princeton e a pesquisa aplicada em laboratórios industriais como Bell Labs, NEC e Microsoft.

Por que Robert é chamado de gênio

O caso de Tarjan para a palavra baseia-se em algo específico: ele não apenas resolveu problemas difíceis individuais, ele identificou a maquinaria combinatória subjacente — busca em profundidade, análise amortizada, autoajuste — que tornou rápidas classes inteiras de algoritmos anteriormente lentos, e ele fez isso repetidamente ao longo de quatro décadas em vez de apenas uma vez. A análise union-find e o algoritmo de planaridade Hopcroft-Tarjan permanecem material de livro didático precisamente porque não são truques inteligentes, mas técnicas gerais que outros pesquisadores poderiam reutilizar; essa reutilização, mais do que qualquer resultado único, é o que os comitês do Prêmio Nevanlinna e do Prêmio Turing estavam recompensando. A complicação honesta é que seu resultado mais célebre, o algoritmo de planaridade de tempo linear, é explicitamente um trabalho conjunto com John Hopcroft, e a citação do Prêmio Turing credita ambos os homens conjuntamente em vez de coroar qualquer um como um gênio solo — o prêmio em si é a prova de que o campo considera isso como uma conquista colaborativa, não uma invenção singular. Outros resultados marcantes de Tarjan foram construídos da mesma forma com coautores nomeados: splay trees com Daniel Sleator, heaps de Fibonacci com Michael Fredman. O que é incontestável é a pura densidade de resultados fundamentais, ainda ensinados, que carregam seu nome, um recorde que poucos na área igualaram.

Legado

Todo estudante de ciência da computação que aprende busca em profundidade, union-find, splay trees ou heaps de Fibonacci está, na verdade, ainda sendo ensinado pelos artigos de Tarjan, décadas depois de terem sido escritos. Seu trabalho fica abaixo de compiladores, roteamento de rede e sistemas de informação geográfica sem que a maioria de seus usuários saiba seu nome — o destino silencioso da matemática de nível de infraestrutura que teve sucesso total. Ele continuou produzindo novos resultados até bem depois dos setenta anos, movendo-se entre o corpo docente de Princeton e cargos como cientista-chefe na Intertrust Technologies e pesquisador na Microsoft e Hewlett Packard, uma forma de carreira que argumenta contra tratá-lo como uma figura puramente acadêmica: grande parte de seu trabalho mais citado foi feito, testado e aplicado dentro de laboratórios de pesquisa industrial em vez de em um vácuo universitário. Essa vida dupla, publicando matemática rigorosa enquanto também patenteia sistemas práticos, é parte do que separa seu histórico dos teóricos cujas ideias permaneceram confinadas a periódicos.