Saturday, July 28, 2012

AR parte V (The End): Assegnazione di Ruoli

Nell'ultima parte si parla di Role Assignment. L'ho trovata davvero interessante. Oltre che sulla prima dispensa, il mio esame verté sull'algoritmo EcRA qui presentato, ma feci una figura tutt'altro che brillante andando in piena confusione. Mi fu di merito il fatto che, in tutta la storia del corso, sono stato l'unico a voler dare tutt'e cinque le parti in una volta sola.

AR parte IV: Clustering su reti wireless ad-hoc

Nella penultima parte, un pasto di algoritmi greedy approssimanti per trovare i dominating set in ambiente distribuito.

AR parte III: il broadcast con range assignment non omogenei

La terza parte del corso si è occupata fondamentalmente dell'algoritmo approssimante del prof. Clementi per il range assignment non omogeneo, ovvero... vedere dispensa. Molto semplice l'algoritmo, molto creativa la dimostrazione.

AR parte II: Modelli di mobilità

Della seguente dispensa non s'è fatto tutto, soprattutto si è sorvolato sulla parte iniziale in cui vengono esposte le bizzeffe di modelli di reti random date da nodi mobili tra cui esistono collegamenti in funzione della reciproca distanza, mentre sono state fatte le montagne di conti che seguono a base di integrali.

AR parte I: Grafi Random Geometrici

Il primo argomento introduce nozioni basilari alla moderna teoria delle reti casuali. Il mio esame orale iniziò da qui, e un'utile esercizio riguardo la dimostrazione del fatto che ponendo $r(n)=\gamma\sqrt{\frac{\log{n}}{n}}$ per un'opportuna gamma, si ha che il grafo risultante sarà connesso con alta probabilità, consiste nel dimostrarlo usando lo union bound.

Sessione estiva: game over (in senso neutrale)

Dato l'ultimo esame che dovevo sono stato in grado di dare, AR: Analisi di Reti. Inizia l'estate, con una magica voglia di concludere il più possibile dal punto di vista intellettuale.
Da qui in poi una serie di post allegando le dispense del corso, con qualche errore ma in generale ottime, anche perché gli argomenti erano molto molto interessanti. Cominciamo con l'introduzione.

Friday, July 13, 2012

Sage Interact... una bomba.

Permettetemi un po' di retorica.
Un software open source è open. Open a chi? In primis, alla comunità che ci vuole star dietro, e poi il resto. Quindi un software open è, in primis, la comunità che c'è dietro (e nella guerra tra le distro Linux questo è difatto uno dei fattori più pesanti: chi ce l'ha più grossa, la comunità).
Se vuoi giovare a un software open una delle migliori cose da fare è cercare di incentivarne i vari aspetti della comunità. Sage dava già l'ovvia possibilità di pubblicare i propri worksheet, ma ora... beh, è arrivato a un nuovo livello :) con http://interact.sagemath.org/recent-posts: un sito carino dove postare i propri migliori pezzi di codice (snippets) che il resto della comunità può divertirsi a riusare a gogò.
Happy code to everyone :D

Wednesday, July 11, 2012

Esame di CP: objective completed

Meno un altro. Ci ho messo un po' per prepararlo. Molto interessante, belle dispense con tanti esempi, non per nulla la professoressa è un Insegnante con la I maiuscola. 
Come di consuetudine, qui di sotto allego le ottime dispense.
Qualche minore osservazione studiando:
  • a fine pagina 105 arriva a un integrale e dice di integrarlo per parti, sicuramente per non mettere troppa carne a cuocere introducendo la densità di una Beta, infatti si fa prima a riconoscere, moltiplicando e dividendo per $n+1$, la densità di una Beta integrata su tutto il dominio;
  • a fine pagina 111 le variabili $s$ e $t$ vengono usate in senso diverso da quanto fatto poco prima nella stessa pagina, in particolare $s$ corrisponde alla $t$ di sopra;
  • la definizione dei $q_{ij}$ in un certo senso è giustificata a pagina 115, al termine della dimostrazione delle equazioni di Kolmogorov; a mio parere, la loro definizione in termini della matrice di transizione della dinamica discreta associata è meglio ricavarla come di seguito.
I parametri $q_{ij}$ in termini delle probabilità di transizione $p_{ij}$: una derivazione naturale
  1. La matrice $Q$ è definita come avente in entrata  $q_{ij}$ il parametro $\nu_i$ della legge esponenziale seguita dalla variabile aleatoria $\tau_i$ che determina il tempo di salto dallo stato $i$ allo stato $j$, inoltre (si impone che) la somma delle righe di $Q$ è zero, per cui si pone  $q_{ii}=-\sum_{i\neq j}q_{ij}$;
  2. la probabilità che il processo di Markov a tempo continuo effettivamente passi dallo stato $i$ allo stato $j$ è data dunque dalla probabilità che la prima variabile aleatoria a realizzarsi sia $\tau_j$, ovvero $$  P(X("primo salto")=j|X(0)=i)=P(\tau_j<\min(\tau_1,...,\tau_n)|X(0)=i) $$
  3. è noto che $\min(\tau_1,...,\tau_n) \sim exp(\sum_{k=1}^{n}{\nu_k})$, e che se $X\sim exp(\lambda_X)$ e $Y\sim exp(\lambda_Y)$ allora $P(X<Y)=\frac{\lambda_X}{\lambda_X+\lambda_Y}$;
  4. da quanto considerato al punto precedente segue che $$P(X("primo salto")=j|X(0)=i)=\frac{{\nu_j}}{\sum_{k=1}^{n}{\nu_k}}$$
  5. indicando con la notazione nota per le matrici di transizione per catene di Markov discrete $p_{ij}:=P(X("primo salto")=j|X(0)=i)$ e ponendo $\nu := \sum_{k=1}^{n}{\nu_k}$ per  $i\neq j$ si ha dunque  $$ p_{ij}=\frac{q_{ij}}{\nu}$$

Thursday, July 5, 2012

Perché usare Sage? - Dan Drake

Finalmente il famoso post che da lungo tempo mi proponevo di scrivere. Il proposito è quello di arguire a favore dell'uso del software Sage da parte di un qualsiasi matematico, e la combo argomentativa che mi proponevo prevedeva un attacco congiunto che partendo dalla rispettiva pagina di wikipedia (in INGLESE), passasse a sfoderare i tanti riferimenti disponibili su http://www.sagemath.org/, citando tra le varie cose il corso tenuto a Berkley dallo stesso William Stein e la sfilza di altri corsi disponibili nel rispettivo wiki.
Alla fine, avendo trovando poco tempo, economizzo con una soluzione magari assai migliore: semplicemente tradurre quanto scritto da chi ha già fatto quanto mi propongo, sul sito stesso di Sage.


A fare da apologeta è il prof. Dan Drake, un combinatorista. La traduzione è un po' più letteraria che letterale.


Perché usare Sage?

Risponde il prof. Dan Drake

Per cominciare, due parole su come io stesso uso Sage: per prima cosa lo utilizzo nella mia attività di ricerca, inoltre anche per la mia attività d'insegnamento (l'ho usato in corsi di Calcolo e di Equazioni Differenziali, e il prossimo semestre lo userò in un corso di Matematica Discreta). Principalmente lo utilizzo durante le mie lezioni per fare dimostrazioni, ma spero in futuro di poterlo integrare nei compiti che assegno.

Perché Open Source significa:

Posso installarlo dovunque voglio: nel computer del mio ufficio, sul mio laptop o il computer della sala conferenze, dovunque. Non spreco un solo istante a preoccuparmi se quel che sto facendo è permesso dalla licenza o quando uscirà la prossima versione, e così via.
Libero significa che i miei studenti possono usarlo. All'università in cui mi sono laureato, usavamo Matlab e Mathematica per i nostri corsi d'ingegneria di Calcolo. Durante la prima settimana, avrei voluto potermi aggirare nel laboratorio computer con la pretesa di non sentire chiunque dire "se vuoi usarlo a casa, basta che vai su [qualsivoglia sito/servizio popolare per il software pirata], e lo scarichi." In questo modo gli studenti che altrimenti piraterebbero del software possono trarre beneficio dal non fare qualcosa di illegale (rischiando tra l'altro di installare malware), così come ne trarrà beneficio lo studente onesto. Chiunque può scaricare e usare Sage, per cui io posso prendere una demo da una lezione, pubblicarla, e chiunque può averla a disposizione e interagirci, anziché limitarsi a guardarmi smanettarla. Certo, Mathematica ha la sua applicazione "Player", ma con Sage i miei studenti possono facilmente modificare la demo a loro piacimento, cosa non possibile col Mathematica Player.Libero significa anche che studenti che si laureano e accedono al mondo del lavoro possono continuare ad usarlo. Maplesoft può non essere interessata a querelare uno studente che s'installa Maple sul suo portatile e la cui università però a la licenza, ma se la tua compagnia sta sviluppando un prodotto e usa una copia piratata di Maple per farlo, la cosa non li farà contenti.

Perché Python significa:

Hai familiarità con uno dei migliori e più popolari linguaggi di programmazione che ci siano là fuori, disponibile per ogni piattaforma, e che è ovunque nel mondo del lavoro. Gli studenti del mio corso di matematica che però non sono studenti di matematica e che lavoreranno nel mondo dell'industria, avranno tanto di guadagnato imparando un po' di Python.

Perché Free-as-in-speech + Python significa:

Quando gli studenti incorrono in un bug, potrebbero essere in grado di correggerlo. Invece di limitarsi a restare in attesa finché qualcun'altro risolva il problema per loro, c'è una buona opportunità che un bravo studente possa essere coinvolto nella soluzione. Nell'educazione al giorno d'oggi noi incoraggiamo gli studenti ad essere "allievi attivi" e così via; si parla di "apprendimento basato sulla scoperta". Nello spirito di questa filosofia educativa rientra molto bene il fatto che uno studente incorra in bug, capisca che si tratta proprio di un bug e cerchi di risolverlo.

Perché per gli studenti di livello più alto significa:

Gli studenti di matematica più promettenti possono partecipare alla correzione di errori su più livelli significativi, poiché essi possono capire gli algoritmi che vengono usati o saperne abbastanza di programmazione da poter riparare del codice scorretto. Sage è inteso per un uso professionale e applicato, così per studenti simili lavorare al miglioramento di Sage è un'esperienza applicativa utilissima per gli studenti dopo la laurea. (Chi si vorrebbe ingaggiare? Il ragazzo che ha svolto tutti i compiti assegnati o quello che dice "ho corretto errori e aggiunto caratteristiche a un grande progetto di software usato da decine di migliaia di persone"?)
Inoltre, di questi tempi la ricerca da parte degli undergraduate è un tema importantissimo, e Sage permette agli studenti di essere aggiornati ed efficienti. Studenti che non sono ancora dei programmatori proficienti devono spendere un sacco di tempo per imparare, ad esempio, il C, perdendo un sacco di tempo a raccapezzarsi con l'aritmetica dei puntatori. Sage permette agli studenti più interessati alla matematica che a malloc() di spendere più tempo pensando ad essa che a capire perché il proprio codice restituisce segfaults.

Perché il Sage notebook server significa:

Il notebook permette trasparenza di rete, per cui mi è solo necessario ottenere che Sage lavori bene una volta sola, dopodiché mi basta usare un browser in classe. Con i computer delle sale conferenze, avere il necessario installato è una tortura, ma di sicuro si può confidare che ci sarà già installato un browser (e se ha solo IE6, non ci vuole niente a metterci Firefox). Significa anche che se ho Sage che gira su un computer veloce, traggo i benefici di quel computer quando ci accedo in remoto da qualunque altro posto.

Dan