John Hopcroft: O livro didático que formou um campo

Milhões de estudantes de ciência da computação nunca leram uma palavra escrita por John Hopcroft em um periódico de pesquisa, no entanto, quase todos aprenderam com ele — através dos livros didáticos de teoria de autômatos e algoritmos que levam seu nome ao lado de Jeffrey Ullman e Alfred Aho, livros tão amplamente adotados como currículo padrão que moldaram a forma como a disciplina se ensina.

Do filho de um zelador a Stanford

John Edward Hopcroft nasceu em 7 de outubro de 1939, em Seattle, Washington, em uma família de classe trabalhadora; seu pai, um veterano britânico da Primeira Guerra Mundial, trabalhava como zelador, e nenhum dos pais havia concluído o ensino médio. Ele também era neto de Jacob Nist, fundador da Seattle-Tacoma Box Company. Apesar de sua escolaridade limitada, seus pais incentivaram sua curiosidade intelectual, e ele obteve um bacharelado em engenharia elétrica na Universidade de Seattle em 1961, seguido por um mestrado em 1962 e um doutorado em 1964, ambos em engenharia elétrica, na Universidade de Stanford. Esse treinamento em engenharia, em vez de uma formação em matemática pura ou ciência da computação, moldou seu instinto posterior para algoritmos que não eram apenas teoricamente elegantes, mas genuinamente eficientes de executar.

Construindo os livros didáticos da disciplina

Hopcroft começou sua carreira acadêmica na Universidade de Princeton como professor assistente antes de se mudar para a Universidade Cornell, onde passaria a maior parte de sua carreira, eventualmente ocupando o título de Professor IBM de Engenharia e Matemática Aplicada e servindo em cargos de liderança, incluindo chefe de departamento e reitor de engenharia. Foi em Cornell que ele foi coautor, com Jeffrey Ullman e mais tarde Alfred Aho, de uma série de livros didáticos sobre linguagens formais, teoria de autômatos e design de algoritmos que se tornaram os textos de ensino padrão para gerações de estudantes de ciência da computação em todo o mundo. Esses livros fizeram mais do que resumir o conhecimento existente — eles codificaram a análise de complexidade assintótica e a teoria de linguagens formais na forma que ainda é ensinada em cursos introdutórios de teoria hoje, dando ao campo um vocabulário compartilhado antes que esse vocabulário existisse plenamente em outros lugares.

Algoritmos que ainda rodam hoje

Além dos livros didáticos, a própria pesquisa de Hopcroft produziu ferramentas ainda em uso ativo. O algoritmo de Hopcroft-Karp, desenvolvido com Richard Karp, encontra correspondências máximas em grafos bipartidos mais rápido do que qualquer método que o precedeu, e permanece uma técnica padrão em problemas de fluxo de rede e atribuição. Ele também desenvolveu um algoritmo eficiente para minimizar autômatos finitos determinísticos, uma ferramenta fundamental no design de compiladores e verificação formal. Seu resultado mais célebre, no entanto, foi um trabalho conjunto com Robert Tarjan: o primeiro algoritmo de tempo linear para testar se um grafo é planar — se ele pode ser desenhado em uma superfície plana sem que as arestas se cruzem — publicado em 1974. Os dois construíram o algoritmo em torno de um uso sistemático de busca em profundidade, transformando o que havia sido um problema lento e ad hoc em um problema solucionável em tempo proporcional ao tamanho do próprio grafo.

O Prêmio Turing e sua natureza compartilhada

Em 1986, Hopcroft e Tarjan receberam conjuntamente o Prêmio ACM A.M. Turing, a maior honraria da computação, "por conquistas fundamentais no design e análise de algoritmos e estruturas de dados". A citação nomeia ambos os homens juntos e credita um corpo de trabalho colaborativo e paralelo em vez de um único avanço individual — o algoritmo de planaridade é o principal das conquistas que a citação tinha em mente, ao lado das contribuições independentes de cada homem para o campo mais amplo do design de algoritmos.

Uma segunda carreira na China

Nas décadas após seu Prêmio Turing, Hopcroft redirecionou grande parte de sua energia para fortalecer a educação em ciência da computação fora dos Estados Unidos, particularmente na China. Ele se tornou codiretor do Centro de Fronteiras de Estudos de Computação na Universidade de Pequim e lidera centros que levam seu nome na Universidade Jiao Tong de Xangai e na Universidade de Ciência e Tecnologia de Huazhong, orientando estudantes e ajudando a construir programas de pesquisa em algoritmos e, mais recentemente, em aprendizado profundo. A China concedeu-lhe seu Prêmio da Amizade em 2016, um reconhecimento reservado para especialistas estrangeiros que fizeram contribuições notáveis para o desenvolvimento do país — um segundo ato incomum para um laureado com o Turing que já estava décadas além do trabalho que lhe rendeu o prêmio.

Reconhecimento

Hopcroft foi eleito para a Academia Nacional de Engenharia em 1989, tornou-se membro da ACM em 1994 e recebeu a Medalha IEEE John von Neumann em 2010 por conquistas notáveis em ciência da computação e engenharia, além do Prêmio Turing de 1986 e do Prêmio da Amizade chinês de 2016.

Por que John é chamado de gênio

O caso para o gênio de Hopcroft não repousa em uma única prova deslumbrante, mas em uma combinação mais rara: contribuições de pesquisa substanciais o suficiente para ganhar o prêmio máximo do campo, combinadas com um dom inigualável para destilar os fundamentos desse campo em uma forma ensinável. O algoritmo de planaridade e o algoritmo de correspondência de Hopcroft-Karp são o tipo de resultados que os cientistas da computação teóricos apontam como genuinamente inteligentes — reduzindo problemas que pareciam exigir busca de força bruta para tempo linear ou quase linear através de percepção estrutural. Mas a estrutura honesta, que a própria citação do Prêmio Turing torna explícita, é que seu resultado mais famoso pertence conjuntamente a ele e a Robert Tarjan; a citação de nenhum dos dois homens se sustenta sozinha, e o prêmio foi por um corpo compartilhado de conquistas, não por um avanço solo. O que é menos compartilhado, e menos frequentemente celebrado como "gênio", é seu segundo talento: três livros didáticos separados em coautoria tão bem construídos que se tornaram a maneira padrão pela qual toda uma disciplina ensina a si mesma seus próprios fundamentos, uma forma de contribuição intelectual mais próxima do ensino magistral do que da invenção individual.

Legado

O legado de Hopcroft segue dois caminhos paralelos que raramente coincidem em uma carreira — um histórico de pesquisa vencedor do Prêmio Turing em algoritmos e um segundo ato de décadas construindo infraestrutura de educação em ciência da computação na China. Poucas figuras na história do campo moldaram como ele é ensinado tão diretamente, ou por tanto tempo, quanto o autor de seus livros didáticos mais amplamente designados. Que o homem que ajudou a formalizar a teoria da computação nas décadas de 1960 e 1970 estivesse, na década de 2010, orientando estudantes em aprendizado profundo na Universidade de Pequim diz algo sobre a duração e o alcance incomuns de sua vida profissional: uma carreira que começou na era da engenharia elétrica adjacente a tubos de vácuo e continuou na era das redes neurais, sem nunca perder seu fio condutor de ensinar à próxima geração a estrutura subjacente do campo.