h1

Aggiornamento sulla tesi

giugno 19, 2008

Passata la prima settimana qui a Berkeley, aggiornamento sulla situazione.

Non ho ancora avuto occasione di uscire una sera, ed apprezzare la vita notturna di Berlekey (suppongo piuttosto povera in questo periodo, visto che molti studenti sono tornati a casa). La mattina alla sede di Oakland di Ask.com (bell’ufficio, non c’è che dire), e il pomeriggio in dipartimento (no, qui non c’è l’aula studenti, spiacente). Insomma, non molto diverso da Pisa, se escludiamo i 15 minuti di treno per Oakland.

Mi rimane il tardo pomeriggio, in cui vagabondo per campus e dintorni, cercando un posto nuovo dove cenare. Berkeley è un posto piacevole per passeggiare.

Finalmente la tesi ha preso una direzione positiva. O per lo meno, ha preso una direzione. Dopo le chiacchierate preliminari, e un po’ di sbattimento per preparazione iniziale su pseudocasualità, combinatoria additiva, teoremi di densità, lemmi di Szemeredi, il mio co-relatore se ne esce con un nuovo argomento che, ovviamente, non c’entra niente con quanto si era detto prima.

L’altro argomento era certamente di più ampio respiro, e probabilmente sarebbe anche piaciuto di più ai matematici puri che dovranno giudicarmi in commissione di laurea. Però non era chiaro cosa dovessi fare, e sicuramente non avrei cavato un ragno dal buco, o comunque non in tempi ragionevoli. Qui la direzione invece è stata precisa dall’inizio: implementare l’algoritmo, fare esperimenti, vedere se c’è qualcosa da dire sull’analisi teorica. Implementare? Non me lo sono fatto chiedere due volte🙂 Ora chi lo dice a mia madre che non tratto più il teorema di Green-Tao? 

Risultato, un’implementazione è pronta (insieme a quelle di un altro paio di algoritmi, di cui uno è lo stato dell’arte) e i risultati preliminari sono promettenti. Non è la prima volta che il Python mi salva la vita. Mentre sono nella Bay Area considererò un pellegrinaggio da Guido Van Rossum.

Nel cercare librerie per risparmiarmi lavoro nell’implementazione sono rimasto esterrefatto dall’ecosistema di librerie scientifiche/matematiche che si è formato attorno a Python. Sembra che abbia catturato l’entusiasmo dei ricercatori (e come biasimarli?), e grazie alla semplicità di modularizzazione e interoperabilità ne sia uscito un ambiente completo. Come Matlab, ma su un vero linguaggio di programmazione. Librerie che meritano di essere menzionate:

  • SciPy: Semplicemente impressionante. Algebra lineare numerica, funzioni statistiche, e milioni di altre cose che non ho ancora avuto il tempo di guardare. Il tutto con una interfaccia pythonica. Insieme a MatPlotLib per i grafici rende Matlab solo un brutto ricordo.
  • NetworkX: Libreria di grafi che implementa qualsiasi algoritmo vi venga in mente, e qualsiasi costruzione (grafi particolari, casuali, prodotti…). Si interfaccia con SciPy (per esempio per la costruzione del laplaciano). Programmativamente non è un granchè (il modulo principale è un blobbone di funzioni, il grafo è un dizionario di dizionari), ma fa onestamente il suo lavoro.
  • CVXOPT: Ottimizzazione convessa, l’ho usato per risolvere il primale-duale di Semidefinite Programming per l’algoritmo di Goemans-Williamson. Non ci ho guardato a fondo, ma funziona ed è abbastanza veloce, considerando che gli algoritmi sono implementati in Python (ma usando le primitive BLAS. Si può interfacciare alla libreria DSDP ma devo impostare l’SDP in un modo diverso, ci sto lavorando). Secondo l’articolo del ’95 ci volevano intorno ai 4000 secondi per risolvere un grafo di 200 nodi. Con la mia pessima implementazione ci mette intorno ai 5 secondi sul mio MacBook Pro. Sembra che sia hardware che algoritmi siano migliorati…🙂

Tornando alla tesi, qui ho conosciuto un paio di dottorandi che lavorano su problemi simili e si sono anche loro interessati al nuovo algoritmo. Chiacchierando con loro per un paio d’ore alla lavagna ho imparato di più che negli ultimi mesi (ma lo sapevate che gli autovettori del grafo di Cayley sono i caratteri della rappresentazione, e quindi nel caso abeliano la base di Fourier? La teoria delle rappresentazioni SERVE A QUALCOSA!)

Se fossi rimasto a Pisa probabilmente in questo momento sarei ancora a scambiare email (con round-trip medio di un giorno, visto il fuso orario) per capire l’argomento della tesi…

3 commenti

  1. […] Shaman81: Finalmente la tesi ha preso una direzione positiva. O per lo meno, ha preso una direzione. Dopo le chiacchierate preliminari, e un po’ di sbattimento per preparazione iniziale su pseudocasualità, combinatoria additiva, … […]


  2. Tra i figli matematici di Python ti consiglio anche di dare un’occhiata a SAGE: http://www.sagemath.org/

    Ciao,
    L.A.B.


  3. @LAB: Voglio provarlo da un po’ ma il pacchettone monolitico di centinaia di mega mi ha sempre spaventato🙂



Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: