Robert Tarjan: La grammatica degli algoritmi efficienti

Chiedete a qualsiasi studente di informatica di tracciare un grafo con la ricerca in profondità e, che lo sappia o meno, sta eseguendo una tecnica che Robert Tarjan ha trasformato da curiosità in disciplina. Il suo articolo del 1972 "Depth-first search and linear graph algorithms" si legge oggi come un testo di grammatica fondamentale: il tipo di lavoro così profondamente assorbito dal campo che il nome del suo autore è quasi scomparso dal modo in cui le persone ne parlano, anche se il suo nome è legato a una mezza dozzina di strutture che usano ogni giorno.

Il percorso di un matematico verso le macchine

Robert Endre Tarjan è nato il 30 aprile 1948 a Pomona, in California, da George Tarjan, uno psichiatra infantile specializzato in disabilità intellettive; suo fratello minore James è diventato un grande maestro di scacchi. Tarjan voleva fare l'astronomo da ragazzo, finché le rubriche di enigmi di Martin Gardner su Scientific American e un insegnante stimolante di terza media non lo hanno spinto verso la matematica. Ha conseguito una laurea in matematica al Caltech nel 1969, poi è andato a Stanford per un master in informatica nel 1971 e un dottorato nel 1972, con una tesi sugli algoritmi di planarità supervisionata da Robert Floyd e Donald Knuth. In seguito avrebbe descritto la sua scelta di campo in modo semplice: l'informatica era un modo di fare matematica che poteva avere un impatto pratico, una frase che funge anche da descrizione dell'intera sua opera.

Costruire il toolkit

La carriera di Tarjan, che ha attraversato Cornell, UC Berkeley, Stanford, AT&T Bell Labs, NYU, NEC Research Institute, Microsoft Research, Compaq, Hewlett Packard e Intertrust Technologies prima di stabilirsi a Princeton nel 1985 come James S. McDonnell Distinguished University Professor, ha prodotto un corpo di algoritmi e strutture dati insolito per il numero di essi che sono diventati infrastrutture portanti piuttosto che curiosità teoriche. Il suo nome è legato all'algoritmo di Tarjan per trovare componenti fortemente connesse in un grafo, un algoritmo offline per calcolare gli antenati comuni minimi e un algoritmo a tempo lineare per trovare i ponti: tutte tecniche basate sul framework di ricerca in profondità che ha formalizzato. Nel 1975 ha fornito la prima analisi esatta della struttura dati union-find combinata con la compressione del percorso, dimostrando il suo tempo di esecuzione ammortizzato quasi costante utilizzando la funzione di Ackermann inversa, un risultato così strettamente legato alle prestazioni nel mondo reale che ora è alla base di tutto, dall'algoritmo dell'albero ricoprente minimo di Kruskal alle ottimizzazioni dei compilatori. Con Daniel Sleator ai Bell Labs ha co-inventato gli splay tree, alberi di ricerca binari auto-regolanti che si riequilibrano attraverso l'uso invece di trasportare metadati di bilanciamento espliciti, e con essi ha aperto la strada all'analisi competitiva, un framework per giudicare gli algoritmi online contro un avversario onnisciente. Con Michael Fredman ha sviluppato gli heap di Fibonacci nel 1985, una struttura di coda di priorità che ha reso l'algoritmo del percorso più breve di Dijkstra e gli algoritmi di ottimizzazione di rete asintoticamente più veloci di qualsiasi cosa esistesse prima. Il suo libro di testo, Data Structures and Network Algorithms, ha vinto il premio Frederick W. Lancaster ed è diventato una lettura standard nel campo.

La svolta della planarità con Hopcroft

Il singolo risultato più esplicitamente accreditato nella sua citazione del Premio Turing è il lavoro congiunto con John Hopcroft: il primo algoritmo a tempo lineare per testare se un grafo può essere disegnato su un piano senza che i bordi si incrocino, pubblicato nel 1974. Il test di planarità era un problema lento e difficile prima che il loro algoritmo lo riducesse a una questione di attenta traversata in profondità: una tecnica così centrale per la loro soluzione che la precedente formalizzazione della ricerca in profondità di Tarjan divenne, in retrospettiva, lo strumento che rese possibile il risultato di Hopcroft-Tarjan. I due hanno condiviso il premio ACM Turing del 1986 "per i risultati fondamentali nella progettazione e nell'analisi di algoritmi e strutture dati", una citazione che accredita un corpo di lavoro congiunto e parallelo piuttosto che un singolo articolo.

Riconoscimento in quattro decenni

Tarjan è stato il primo vincitore del premio Nevanlinna in Scienze dell'Informazione nel 1983, onorando contributi eccezionali agli aspetti matematici dell'informatica. Ha vinto il premio Turing nel 1986, è stato eletto all'American Academy of Arts and Sciences nel 1985, alla National Academy of Sciences nel 1987 e alla National Academy of Engineering nel 1988. Ha ricevuto il premio Paris Kanellakis in Teoria e Pratica nel 1999 e il premio Distinguished Alumni del Caltech nel 2010. Il suo record di pubblicazioni supera i 250 articoli con decine di migliaia di citazioni, e detiene più di una dozzina di brevetti statunitensi in strutture dati e sicurezza, riflettendo una carriera che si è mossa fluidamente tra la teoria accademica a Princeton e la ricerca applicata in laboratori industriali come Bell Labs, NEC e Microsoft.

Perché Robert è chiamato un genio

Il caso di Tarjan per la parola si basa su qualcosa di specifico: non ha solo risolto singoli problemi difficili, ha identificato il meccanismo combinatorio sottostante (ricerca in profondità, analisi ammortizzata, auto-regolazione) che ha reso veloci intere classi di algoritmi precedentemente lenti, e lo ha fatto ripetutamente in quattro decenni piuttosto che una volta sola. L'analisi union-find e l'algoritmo di planarità di Hopcroft-Tarjan rimangono materiale da libro di testo proprio perché non sono trucchi intelligenti ma tecniche generali che altri ricercatori potrebbero riutilizzare; quella riutilizzabilità, più di ogni singolo risultato, è ciò che i comitati del premio Nevanlinna e del premio Turing stavano premiando. La complicazione onesta è che il suo risultato più celebre, l'algoritmo di planarità a tempo lineare, è esplicitamente un lavoro congiunto con John Hopcroft, e la citazione del premio Turing accredita entrambi gli uomini congiuntamente piuttosto che incoronare l'uno o l'altro come un genio solitario: il premio stesso è la prova che il campo considera questo come un risultato collaborativo, non un'invenzione singolare. Gli altri risultati storici di Tarjan sono stati costruiti allo stesso modo con coautori nominati: splay tree con Daniel Sleator, heap di Fibonacci con Michael Fredman. Ciò che è incontestato è la pura densità di risultati fondamentali, ancora insegnati, che portano il suo nome, un record che pochi nel campo hanno eguagliato.

Eredità

Ogni studente di informatica che impara la ricerca in profondità, l'union-find, gli splay tree o gli heap di Fibonacci viene, in effetti, ancora istruito dagli articoli di Tarjan, decenni dopo che sono stati scritti. Il suo lavoro si trova sotto i compilatori, il routing di rete e i sistemi di informazione geografica senza che la maggior parte dei suoi utenti conosca il suo nome: il destino silenzioso della matematica a livello di infrastruttura che ha avuto pieno successo. Ha continuato a produrre nuovi risultati fino ai settant'anni, muovendosi tra la facoltà di Princeton e ruoli come scienziato capo presso Intertrust Technologies e ricercatore presso Microsoft e Hewlett Packard, una forma di carriera che di per sé argomenta contro il trattarlo come una figura puramente accademica: gran parte del suo lavoro più citato è stato svolto, testato e applicato all'interno di laboratori di ricerca industriale piuttosto che in un vuoto universitario. Questa doppia vita, pubblicare matematica rigorosa pur brevettando sistemi pratici, è parte di ciò che separa il suo record dai teorici le cui idee sono rimaste confinate alle riviste.