Algoritmi di ogni sort

SortingSpesso gli algoritmi di ordinamento sono tra i primi argomenti quando si insegna programmazione.

La scelta cade sulla soluzione del problema di mettere in ordine una lista di valori perché è di semplice comprensione, il risultato è facilmente verificabile e permette di illustrare come la soluzione di un problema apparentemente semplice può avere vari gradi di complessità.

Su questa classe di algoritmi, banali solo ad un’analisi superficiale, sono stati fatti moltissimi studi e sono state scritte molte pubblicazioni. Moltissime visualizzazioni avvengono dopo aver ordinato i dati da mostrare: un algoritmo poco efficiente potrebbe costare molto tempo macchina sulla lunga distanza.

Questo sito permette di visualizzare e confrontare gli algoritmi di sort con delle animazioni che illustrano passo passo l’avanzamento dell’algoritmo. Per chi vuole approfondire, ciascun algoritmo ha un link verso Wikipedia.

Anche per il programmatore navigato, oltre che per il geek, la visualizzazione di questi algoritmi può rappresentare un passatempo interessante.

Cifratura omomorfica

Tour EiffelUn ricercatore di IBM ha pubblicato i sorgenti di HELib, una libreria di funzioni per la cifratura omomorfica.

Gli algoritmi omomorfici sono una famiglia di metodi di cifratura che, in teoria, permetterebbero di eseguire alcune operazioni sui dati cifrati ottenendo gli stessi risultati delle medesime operazioni svolte sui dati in chiaro. Ad esempio, Alice potrebbe eseguire una somma su alcuni valori registrati in maniera cifrata e Bob, e solamente lui, potrebbe decifrare il risultato.

Se si sostituisce Alice con un server online utilizzato per registrare i dati e Bob con l’utente legittimo titolare di quei dati, le implicazioni di una famiglia di algoritmi simili sono notevoli, in quanto potrebbero essere compiute delle operazioni sui dati cifrati senza che Bob debba consegnare ad Alice la chiave per decifrarli e senza che i dati di Bob debbano essere trasmessi o memorizzati in chiaro per l’elaborazione.

HELib implementa l’algoritmo omomorfico BGV (Brakerski-Gentry-Vaikuntanathan, PDF) con varie ottimizzazioni per renderlo più veloce ed è distribuita con la licenza GNU GPL. Per ora sull’account GitHub di Shai Halevi si trovano i sorgenti C++ della libreria e  qualche programmino di test, nulla più; non siamo ancora al livello di un’applicazione funzionante di cui si possono verificare caratteristiche e limiti.