La musica degli algoritmi

La web app che trovate in questa pagina vi permette di ascoltare il suono e osservare la danza degli algoritmi quotidiani. Sono gli stessi algoritmi che di solito lavorano in silenzio per rispondere ad un nostro click, o che noi stessi applichiamo più o meno consapevolmente nella vita di tutti i giorni. Ora li potete osservare e ascoltare per comprenderli meglio.

Come funziona

Quando lanciate l’applicazione vengono generati 100 numeri casuali, rappresentati da sinistra a destra come tante palline appese a sottili fili, tanto più lunghi quanto più grandi sono i numeri che rappresentano.

Se volete aumentare o diminuire la quantità di palline, potete usare le grandi frecce azzurre e premere il tasto centrale. Se invece volete rimescolarli potete cliccare sulle due frecce rosse incrociate.

Per cercare una pallina appesa ad una certa altezza cliccate due volte sullo schermo (in una posizione in cui non ci siano pulsanti attivi) per indicare l’intervallo di altezze entro cui effettuare la ricerca. Un algoritmo di ricerca individuerà per voi la pallina che cercate, evidenziando in rosso i tentativi di ricerca e in verde la soluzione trovata (se esiste). Se le palline non sono in ordine verrà effettuata una ricerca sequenziale, altrimenti una ricerca dicotomica.

Per mettere le palline in ordine di altezza potete cliccare su uno qualsiasi dei triangoli colorati. Corrispondono ad algoritmi di ordinamento diversi: il tasto blu è il Selection sort, il tasto verde è l’Insertion sort, il tasto giallo è il Bubble sort, il tasto rosso è il Merge sort. Sono tutti equivalenti (producono lo stesso risultato), ma hanno efficienza diversa. Metteteli alla prova.

Se volete mettere le palline in ordine crescente o decrescente di altezza potete cliccare sull’icona nera in basso a destra e rilanciare un qualsiasi algoritmo di ordinamento.

I contatori che appaiono in basso a sinistra mostrano il numero di confronti e il numero di scambi effettuati dall’algoritmo che avete scelto di utilizzare. Osservandoli potete mettere a confronto l’efficienza dei diversi algoritmi.

La danza

Durante l’esecuzione di ogni algoritmo di ricerca o di ordinamento, l’applicazione ne mostra il funzionamento evidenziando in rosso le palline prese in considerazione e aggiornando la rappresentazione ad ogni scambio.

Potete disabilitare (e riabilitare) la visualizzazione dei passaggi intermedi cliccando sull’icona dell’occhio.

Il suono

Per far suonare gli algoritmi ho preso il campionamento del suono emesso da 64 tasti di un pianoforte e li ho associati alle lunghezze dei fili, distribuendoli uniformemente dal più lungo (suono più grave) al più corto (suono più acuto).

L’app emette tutti i suoni associati alle palline prese in considerazione dall’algoritmo.

Potete disabilitare (e riabilitare) la riproduzione dei suoni cliccando sull’icona delle note musicali.

Cosa ci insegna

L’App ci aiuta a comprendere il principio di funzionamento dei 6 algoritmi che implementa e ad apprezzarne i punti di forza e di debolezza:

• Vedendoli in funzione possiamo comprendere in che ordine prendono in considerazioni gli elementi e cercare di riconoscere il comportamento ciclico della ricerca sequenziale, il comportamento ricorsivo della ricerca dicotomica e del merge sort, i due cicli nidificati del Selection sort, dell’Insertion sort e del Bubble sort
• Ascoltando l’altezza dei suoni emessi e la frequenza con cui vengono riproposte le stesse note possiamo comprendere l’alternanza dei cicli.
• Apprezzandone la durata possiamo confrontarne l’efficienza.
• Osservando i contatori possiamo misurare accuratamente il numero di passi necessari ad ottenere la soluzione.
• Rigenerando l’insieme di palline possiamo verificare la dipendenza del tempo di esecuzione dai dati del problema.

Come è fatta

L’App è stata sviluppata in diretta durante le lezioni 06.03 e 06.04 di Algoritmi quotidiani, programmando in JavaScript nell’ambiente AppLab. L’applicazione può essere utilizzata liberamente sia da computer che da smartphone e tablet. Chi vuole può guardare il codice JavaScript e provare a modifcarlo. Spostando il cursore dalla lepre alla tartaruga si può anche rallentare l’esecuzione del codice per seguirla passo-passo.

Qui trovate le video-lezioni e le slide che illustrano le fasi di sviluppo e le modalità di utilizzo:

Per saperne di più

Vi invito a seguire liberamente le lezioni online di Algoritmi quotidiani e gli aggiornamenti nel gruppo Facebook.