sabato, giugno 28, 2014

Visualizzazione di algoritmi

Bellissimo il post Visualizing Algorithms di Mike Bostock, che introduce con degli ottimi esempi l'importanza della visualizzazione dei risultati di un algoritmo, del grado di correttezza dello stesso o, semplicemente, dei passi che sono stati necessari per ottenere un determinato risultato.

Nella prima parte, dedicata alle tecniche di campionamento, Mike illustra tre diversi algoritmi per la generazione casuale di punti all'interno di un rettangolo, che si desiderano distribuiti in maniera da evitare pattern riconoscibili. Oltre a visualizzare il risultato, si può visualizzare a colpo d'occhio la bontà del risultato raggiunto. Si confrontino ad esempio queste due immagini

 

nelle quali le macchie più scure rappresentano le aree sottocampionate, e quelle più chiare le aree sovracampionate. Ci si rende conto facilmente che l'algoritmo alla base della seconda immagine è migliore.

Nella seconda parte, un'immagine mostra meglio di mille parole quale problema può nascere dall'utilizzo di un algoritmo usato per un mescolamento casuale di un mazzo di carte (o di qualsiasi altra cosa):

Se l'obiettivo è di avere una distribuzione equiprobabile delle carte, ci possiamo rendere conto, semplicemente visualizzando con diversi colori la distanza dall'obiettivo, quanto siamo lontani da un'implementazione corretta.

Nella terza parte Mark mostra come si possa visualizzare l'esecuzione "passo passo" di un algoritmo, tracciando un grafico che rappresenta la serie di scambi di un quick sort.

Nella quarta parte, forse la più divertente da vedere, sono poi presentati diversi algoritmi per la generazione di labirinti, con una rappresentazione di alberi e della lunghezza dei singoli percorsi basata su una scala di colori.

Come dice Mark, la visualizzazione degli algoritmi può essere un valido ausilio per l'intrattenimento (è divertente vedere gli algoritmi all'opera), per l'insegnamento, per il debugging e per la costruzione di un'interfaccia utente per l'input di dati che sono collegati reciprocamente tra di loro, come nel caso della scelta tra acquisto di una casa o affitto della stessa. Come dargli torto?