John Hopcroft: Il libro di testo che ha formato un campo

Milioni di studenti di informatica non hanno mai letto una parola scritta da John Hopcroft in una rivista di ricerca, eppure quasi tutti hanno imparato da lui — attraverso i libri di testo sulla teoria degli automi e sugli algoritmi che portano il suo nome insieme a quelli di Jeffrey Ullman e Alfred Aho, libri così ampiamente adottati come curriculum standard da aver plasmato il modo in cui la disciplina insegna se stessa.

Da figlio di un custode a Stanford

John Edward Hopcroft è nato il 7 ottobre 1939 a Seattle, Washington, in una famiglia della classe operaia; suo padre, un veterano britannico della Prima Guerra Mondiale, lavorava come custode e nessuno dei due genitori aveva completato la scuola superiore. Era anche il nipote di Jacob Nist, fondatore della Seattle-Tacoma Box Company. Nonostante la loro istruzione limitata, i suoi genitori incoraggiarono la sua curiosità intellettuale, e lui ottenne una laurea in ingegneria elettrica presso l'Università di Seattle nel 1961, seguita da un master nel 1962 e un dottorato nel 1964, entrambi in ingegneria elettrica, presso l'Università di Stanford. Quella formazione ingegneristica, piuttosto che un background in matematica pura o informatica, ha plasmato il suo istinto successivo per algoritmi che non fossero solo teoricamente eleganti, ma genuinamente efficienti da eseguire.

Costruire i libri di testo della disciplina

Hopcroft ha iniziato la sua carriera accademica all'Università di Princeton come assistente professore prima di trasferirsi all'Università Cornell, dove avrebbe trascorso la maggior parte della sua carriera, ricoprendo infine il titolo di IBM Professor of Engineering and Applied Mathematics e ricoprendo ruoli di leadership, tra cui capo dipartimento e preside di ingegneria. È stato alla Cornell che ha co-scritto, con Jeffrey Ullman e più tardi Alfred Aho, una serie di libri di testo su linguaggi formali, teoria degli automi e progettazione di algoritmi che sono diventati i testi di insegnamento predefiniti per generazioni di studenti di informatica in tutto il mondo. Questi libri hanno fatto più che riassumere le conoscenze esistenti: hanno codificato l'analisi della complessità asintotica e la teoria dei linguaggi formali nella forma ancora insegnata oggi nei corsi teorici introduttivi, dando al campo un vocabolario condiviso prima ancora che tale vocabolario esistesse pienamente altrove.

Algoritmi che girano ancora oggi

Oltre ai libri di testo, la ricerca di Hopcroft ha prodotto strumenti ancora in uso attivo. L'algoritmo di Hopcroft-Karp, sviluppato con Richard Karp, trova i matching massimi nei grafi bipartiti più velocemente di qualsiasi metodo precedente e rimane una tecnica standard nei problemi di flusso di rete e assegnazione. Ha anche sviluppato un algoritmo efficiente per minimizzare gli automi a stati finiti deterministici, uno strumento fondamentale nella progettazione di compilatori e nella verifica formale. Il suo risultato più celebre, tuttavia, è stato un lavoro congiunto con Robert Tarjan: il primo algoritmo in tempo lineare per testare se un grafo è planare — se può essere disegnato su una superficie piana senza che gli archi si incrocino — pubblicato nel 1974. I due hanno costruito l'algoritmo attorno a un uso sistematico della ricerca in profondità, trasformando quello che era stato un problema lento e ad hoc in uno risolvibile in un tempo proporzionale alla dimensione del grafo stesso.

Il Premio Turing e la sua natura condivisa

Nel 1986, Hopcroft e Tarjan hanno ricevuto congiuntamente il premio ACM A.M. Turing, il più alto riconoscimento dell'informatica, "per i risultati fondamentali nella progettazione e nell'analisi di algoritmi e strutture dati". La citazione nomina entrambi gli uomini insieme e accredita un corpo di lavoro collaborativo e parallelo piuttosto che un singolo successo individuale — l'algoritmo di planarità è il principale dei risultati che la citazione aveva in mente, insieme ai contributi indipendenti di ciascun uomo al campo più ampio della progettazione di algoritmi.

Una seconda carriera in Cina

Nei decenni successivi al suo Premio Turing, Hopcroft ha reindirizzato gran parte della sua energia verso il rafforzamento dell'istruzione informatica al di fuori degli Stati Uniti, in particolare in Cina. È diventato co-direttore del Center on Frontiers of Computing Studies presso l'Università di Pechino e dirige centri che portano il suo nome presso l'Università Jiao Tong di Shanghai e l'Università di Scienza e Tecnologia di Huazhong, facendo da mentore agli studenti e aiutando a costruire programmi di ricerca in algoritmi e, più recentemente, nel deep learning. La Cina gli ha conferito il suo Friendship Award nel 2016, un riconoscimento riservato agli esperti stranieri che hanno dato contributi eccezionali allo sviluppo del paese — un secondo atto insolito per un premio Turing già lontano decenni dal lavoro che gli era valso il premio.

Riconoscimento

Hopcroft è stato eletto alla National Academy of Engineering nel 1989, è diventato ACM Fellow nel 1994 e ha ricevuto la medaglia IEEE John von Neumann nel 2010 per i risultati eccezionali nell'informatica e nell'ingegneria, oltre al Premio Turing del 1986 e al Friendship Award cinese del 2016.

Perché John è chiamato un genio

Il caso per il genio di Hopcroft non poggia su una singola prova sbalorditiva, ma su una combinazione più rara: contributi di ricerca abbastanza sostanziali da vincere il premio più importante del campo, abbinati a un dono impareggiabile per distillare le fondamenta di quel campo in una forma insegnabile. L'algoritmo di planarità e l'algoritmo di matching di Hopcroft-Karp sono il tipo di risultati che gli informatici teorici indicano come genuinamente intelligenti — riducendo problemi che sembravano richiedere una ricerca a forza bruta in un tempo lineare o quasi lineare attraverso l'intuizione strutturale. Ma l'inquadramento onesto, che la citazione stessa del Premio Turing rende esplicito, è che il suo risultato più famoso appartiene congiuntamente a lui e a Robert Tarjan; la citazione di nessuno dei due uomini sta da sola, e il premio è stato per un corpo condiviso di risultati, non per una svolta da solista. Ciò che è meno condiviso, e meno spesso celebrato come "genio", è il suo secondo talento: tre libri di testo separati in co-autorialità così ben costruiti da essere diventati il modo predefinito in cui un'intera disciplina insegna a se stessa le proprie fondamenta, una forma di contributo intellettuale più vicina all'insegnamento magistrale che all'invenzione individuale.

Eredità

L'eredità di Hopcroft corre su due binari paralleli che raramente coincidono in una carriera — un record di ricerca vincitore del Premio Turing negli algoritmi e un secondo atto lungo decenni nel costruire l'infrastruttura per l'istruzione informatica in Cina. Poche figure nella storia del campo hanno plasmato il modo in cui viene insegnato così direttamente, o per così tanto tempo, come l'autore dei suoi libri di testo più ampiamente assegnati. Che l'uomo che ha contribuito a formalizzare la teoria della computazione negli anni '60 e '70 stesse, negli anni 2010, facendo da mentore agli studenti di deep learning all'Università di Pechino dice qualcosa sulla durata e la portata insolite della sua vita lavorativa: una carriera iniziata nell'era dell'ingegneria elettrica adiacente ai tubi a vuoto e continuata nell'era delle reti neurali, senza mai perdere il suo filo conduttore di insegnare alla prossima generazione la struttura sottostante del campo.