Informatica Ricreativa

Ce n'è tanta, di matematica ricreativa. E piano piano anche il mondo degli algoritmi comincia a farsi strada nel mondo del divertissement.

Al riguardo, segue il mio contributo ;)

E gli altri video li trovate nel rispettivo canale.

A seguire, Alligator Eggs, un giochetto per bambini che ripropone niente di meno che il Lambda Calcolo.

Ed in chiusura, sentiamo come suonano...

Controlled Distance, la guerra è fatta di battaglie

L'Ultimo Protocollo, Controlled Distance, non è proprio un amore quando provi a riscriverlo da zero.
Fortuna che siamo alla fine di questa storia. Adieu! 

As Far As It Can, ne resterà uno solo

Da notare come possa essere banalmente hackerato: un messaggio viene mandato da Initialize e poi eventualmente anche dalla procedura Alive. Un semplice if statement renderebbe la cosa esclusiva, portando, nel caso di Unique Initiator, a una complessità di messaggio addirittura lineare. Nerd is better.

All the way, compagnia dell'Anello

Tutti mandano in giro tutto qua...
Un po' troppo faticoso, rispetto al prossimo...

Saturation... chi vuole un plug-in?

Questo è il capolavoro. Tutti i plugin principali (ovvero quelli visti nel Corso) radunati in un unica doppia tabella. Per il piacere della sintesi.

DFT*, hacking forever

Una cosa non immediata è spiegarne la message complexity...

DFT ok, ha 2m.
DFT+, per evitare i backedge, bussa ad ogni porta con un Visited e domanda Ack(nowledgement). Si ha dunque 4m-2(n-1).
DFT++ non chiede più gli Ack. Un upper bound dato dagli errori che ora possono presentarsi ci dà
4m-n+1.
DFT*, infine, usa il Token come un Visited. Ci fa risparmiare dunque un Visited tranne che per quei nodi che quando ricevono il Token si ritrovano già senza vicini da visitare (questo punto forse richiede un po' di riflessione...) per cui bisogna togliere n-emptyUnvisited  ottenendo una message complexity pari a
4m-2n+emptyUnvisited+1. 
Tadan.

DFT, prima non apprezzavo le staffette

Il bello di un settore è pure l'esclusività del suo gergo, o meglio jargon, per restare in tema.
I turni diventano op, le cose fatte "a mano" sono brute force, le descrizioni sommarie sono ad alto livello, etc etc.
E non ultimo, questa bellissima parola che è: token. 

Shout! Sempre più forte

Il piacere dell'ottimizzazione.
E di non dire cose superflue.
Evviva l'essenziale!
E forse col dirlo sto già sgarando...

Shout! e la Protocol Table

Questo protocollo mi è davvero davvero piaciuto quando l'abbiamo fatto.
È poi un esercizio non troppo brutto quello di arrivare alla message complexity "ragionando sugli archi", i.e. chiedendosi quanti messaggi passano su ciascun arco.

A questo punto dovrei forse spendere qualche parola sul valore di questa modalità di rappresentazione dei protocolli, che potremmo battezzare Protocol Table.
L'idea, di Alessandro, coglie appieno il fatto che non si tratta qui di algoritmi procedurali (tanto meno paralleli). Il fatto che si parli di algoritmi distribuiti richiede di ragionare... nel più incasinato dei mondi possibili, dove dietro ad ogni angolo è nascosto il più fatale dei delay, pronto a capovolgere l'ordine delle cose.
Insomma, scritti così, i protocolli si vedono "a colpo d'occhio", con tutti gli input sulle colonne e tutti gli stati sulle righe.
Funziona. Enjoy. 

Flooding & WFlood

Eccolo qui: il protocollo dei protocolli, il broadcast per eccellenza.

Notazione: M(qui c'è la message complexity), T(qui l'ideal time complexity).
Per quale motivo quello che dovrebbe essere il valore della funzione è al posto del suo argomento di entrata, con gran gioia di tutti gli smaniosi matematici, va chiesto all'autore informatico.

By the way, perdonate il puntatore nelle immagini... successivamente linkerò, scaricabile, il pdf dei protocolli postati.

Penso che sia tutto abbastanza comprensibile (per gli addetti ai lavori...). 

Algoritmi distribuiti

Passi la mia completa negligenza in queste ultime settimane di vacanza riguardo lo studio.
Non passi che questa nuova Magistrale in Informatica non l'ho ingranata bene. Oggi nell'esonero di Algoritmi Distribuiti potevo pure non scrivere certe cose... eheheh.

Di qui seguirà qualche post dedicato ad esporre il lavoro (a mio avviso) eccellente effettuato dal collega Alessandro Scarozza, programmatore puro, e me, nello studiare questa nuova disciplina.

Esiste da poco, la disciplina degli Algoritmi Distribuiti.
Il testo migliore finora pare che sia Design and Analysis of Distributed Algorithms di Nicola Santoro. E ci abbiamo trovato non pochi errori di stumpa... soprattutto nel codice dei protocolli, un po' buttato lì (che fa apparire un po' più umano l'autore, rispetto alla mole di materiale che pubblica...).

Già, gente che pubblica una tale quantità di roba da far supporre che si tratti del Bourbaki della situazione.
Prendete ad esempio Fabrizio Grandoni... che recentemente ha lasciato Tor Vergata per terre migliori...

Cercando di contenere le chiacchiere... la pagina del corso del prof. Clementi la trovate qui.

matlabbing poco professionale

Cose che succedono.
Cercare "Fun facts in Matlab" su Google e ritrovarsi a digitare nella riga di comando

>> spy
e poi
>> image
e poi
>> life
e poi
>> why
e poi
>> why(1)
e poi
>> why(2)
e poi
>> why(3)
e poi
>> why(4)
e poi
>> why(5)
e poi...

L'incubo della statistica

Qualche giorno fa vengo chiamato e mi si chiede se posso impartire ripetizioni di Statistica Sociale.

Ok, ho seguito un paio di corsi di Statistica Matematica. Che non è la stessa cosa che farsi un corso di Statistica alla facoltà di Economia. E l'una e l'altra non sono la stessa cosa della parte statistica dell'Econometria. E nessuna delle precedenti è la stessa cosa della Statistica fatta a Scienze Politiche. Nulla di tutto ciò a poi totalmente a che fare con l'esame, essenzialmente statistico, di Psicometria a Psicologia. Certo poi si capisce perché esiste(va) un intero corso di laurea in Statistica. Cmq, Statistica Sociale ancora mi mancava.

Il protagonista di questa piccola avventura, per ora, è stato l'Indice di Gini. Uno dei rari casi un cui la Wikipedia italiana è migliore dell'inglese. Certo, perché si tratta di un italiano...