Alberto Apostolico è stato professore presso il College of Computing del Georgia Tech. Rimasto attivo fino alla fine, ha presentato un articolo congiunto alla conferenza RECOMB del 2015, dedicata alla Ricerca in Biologia Molecolare Computazionale. Due articoli di rivista, frutto di questo lavoro congiunto, sono stati sottomessi nello stesso mese. Un'intera sessione di quella conferenza era dedicata alla lotta contro il cancro.
Un Profilo Accademico di Rilievo
Il lavoro di Alberto Apostolico si concentrava sulla quantità di elaborazione necessaria per identificare proprietà rilevanti delle parole, intendendo parole molto lunghe come la rappresentazione testuale del genoma umano. Ha evidenziato come molti metodi "ovvi" per l'elaborazione di stringhe richiedano un'eccessiva quantità di lavoro. Una delle sue domande fondamentali era: "Come si confrontano elementi intrinsecamente troppo grandi per essere paragonati, il che significa che i vecchi metodi di calcolo non sono più fattibili, significativi o entrambi?"
La prefazione di Raffaele Giancarlo e Stefano Lonardi elenca i numerosi contributi di Alberto. Un aneddoto lo ritrae come studente universitario che, provando una certa ansia a frequentare una scuola estiva tenuta da Apostolico sull'isola di Lipari, al largo della costa settentrionale della Sicilia, fu molto rincuorato nel vederlo arrivare sulla sua barca a vela, chiamata Obliqua.
Contributi Fondamentali alla Stringologia
La stringologia è lo studio degli oggetti più basilari nell'informatica, ovvero sequenze lineari finite di lettere, ed è ricca di risultati profondi e spesso sorprendenti. Un esempio sorprendente è che una macchina di Turing multitape ordinaria, lavorando in tempo reale, può stampare un 1 ogni volta che le prime lettere lette formano un palindromo.
Prima di un altro articolo importante, Alberto Apostolico e Zvi hanno curato e contribuito a una raccolta di saggi altamente influente proveniente da un workshop in Italia sponsorizzato dall'Advanced Sciences Institute della NATO nel 1984, intitolata Combinatorial Algorithms on Words. Molti eminenti studiosi hanno partecipato e scritto per il volume, tra cui: Michael Rabin, Andy Yao, Andrew Odlyzko, Bob Sedgewick con Philippe Flajolet e Mireille Régnier, Andrei Broder, Joel Seiferas, e altri come Maxime Crochemore, Shimon Even, Guibas, Michael Main, Dominique Perrin, Wojciech Rytter e James Storer.
Un contributo di Victor Miller e Mark Wegman (noti per l'hashing universale) intitolato "Variations on a Theme by Ziv and Lempel" è seguito da uno di Lempel e Ziv. Alberto e Zvi hanno collaborato ad un altro volume nel 1997, il libro Pattern Matching Algorithms. Hanno anche scritto articoli congiunti, inclusi diversi sugli algoritmi paralleli per problemi di stringhe, persino il problema fondamentale della ricerca di palindromi. Alberto ha dimostrato molti teoremi sorprendenti durante la sua lunga carriera.
Innovazione nel "Pattern Discovery" e nella "Distanza di Edit"
Nuove prove suggeriscono che il tempo per calcolare la distanza di edit sia realmente quadratico. La distanza di edit è così fondamentale che richiede audacia immaginare che "misure alternative, basate sulla composizione di sottoparole delle sequenze", possano essere sia più veloci che utili. Il teorema principale è un algoritmo con complessità temporale lineare per una misura di distanza che sembra dipendere da un numero quadratico di coppie di sottostringhe. Questo è un vero e proprio traguardo nel sfruttare i modi in cui le parole possono combinarsi, quasi come un messaggio dallo spazio.
Alberto ha poi notato il passaggio dal pattern matching al pattern discovery, senza menzionare quanto fosse all'avanguardia in questo campo. Ha catturato il concetto di scoperta attraverso l'elemento di sorpresa, che può essere quantificato statisticamente. Uno dei suoi articoli preferiti è intitolato "Monotony of Surprise and Large-Scale Quest for Unusual Words", scritto con Mary Ellen Bock e Lonardi. Rappresenta un'altra vittoria nella battaglia perpetua di Alberto del lineare contro il quadratico.
La Monotonia della Sorpresa e la Ricerca di Parole Insolite
L'idea è la seguente: data una stringa lunga S e una sottostringa w, sia occ(w, S) il numero di occorrenze di w in S. Supponiamo che S sia nel supporto di una distribuzione casuale D in cui ogni carattere dipende solo da un numero fisso e finito di caratteri precedenti in modo indipendente da w. Sia Xw,S la variabile casuale di occ(w, S) su S estratta da questa distribuzione. zw,S è un normale z-score statistico, dove E[Xw,S] rappresenta l'aspettativa e σ[Xw,S] la deviazione standard. Se zw,S > τ per una soglia positiva elevata τ, allora w ricorre con una frequenza insolita in S ed è quindi una sottostringa sorprendente. Individuare quali sottostringhe siano sorprendenti sembra ancora scontrarsi con il fatto che esistono quadraticamente molte sottostringhe in totale.
Ma gli autori applicano un po' di "magia strutturale". Supponiamo di avere una partizione delle sottostringhe in k-molte classi tali che ciascuna abbia un membro unico più lungo e più corto. Dato j ∈ [1,k], inseriamo w in Sα(j) se w ∈ Cj e nessun'altra stringa in Cj ha uno z-score più alto, e in Sβ(j) se w ∈ Cj e nessun altro membro è più negativo. Il Teorema 1 afferma: Data una stringa S di lunghezza N e una k-partizione delle sue sottostringhe come sopra, e un qualsiasi spostamento fisso Δ, gli insiemi Sα(j) e Sβ(j) possono essere calcolati in tempo O(N).
Algoritmi e pattern risolutivi - Tree, DFS ed esercizio pratico
L'Eredità di Alberto Apostolico
Potremmo continuare a elencare i suoi successi, ma è opportuno fermarci qui e rinnovare le nostre condoglianze alla sua famiglia e ai suoi amici. Il Georgia Tech organizzerà un memoriale in suo onore. Alberto è già molto rimpianto per i suoi contributi inestimabili al campo dell'informatica.
Il Legame con l'Università di Padova: Ricerca Affine
Sebbene il testo fornito non indichi un'affiliazione diretta di Alberto Apostolico all'Università di Padova, è interessante notare la presenza di ricercatori che operano in ambiti di ricerca affini. Un esempio è la Prof.ssa Cinzia Pizzi, professoressa associata presso il Dipartimento di Ingegneria dell'Informazione dell'Università di Padova dal 2011. La sua ricerca si concentra su algoritmi e strutture dati per stringhe, bioinformatica e analisi di dati sociali. Ha conseguito il Dottorato di Ricerca in Ingegneria Elettronica e Informatica Industriale presso lo stesso dipartimento nel 2005 e ha ricoperto ruoli di ricercatrice post-dottorato presso il Baobab Team e l'Università di Helsinki.
La Dott.ssa Pizzi è membro del Centro di Ricerca interdipartimentale HIT (Human Inspired Technology) dell'Università di Padova dalla sua fondazione nel 2013. Ha partecipato a numerosi comitati di programma di conferenze internazionali, inclusa RECOMB nel 2006, e ha insegnato per diversi anni il corso di "Informatica Teorica" presso il Dipartimento di Ingegneria dell'Informazione dell'Università di Padova, supervisionando anche numerose tesi. Le aree di ricerca della Prof.ssa Pizzi evidenziano una continuità e un'importanza della stringologia e della bioinformatica anche nell'ambiente accademico patavino, in risonanza con i campi di studio pionieristici di Alberto Apostolico.
tags: #alberto #apostolico #unipd