Pensieri in codice

È facile dire che le cose vano fatte in modo semplice, ma cosa vuol dire esattamente? Io non ho la risposta ma almeno posso provare a pormi la domanda.

Link affiliati: il costo per te non cambia, ma una piccola parte del ricavato sostiene il podcast.

Fino ad oggi, questo è forse il progetto più ambizioso di Pensieri in codice: una monografica in 3 episodi su Ada Lovelace e la sua opera.

Voci amiche:

Martina Costanza Vitale -

nella parte di Miss Chaloner da Jennifer Chiaverini - L’Incantatrice di numeri (Ada Byron Lovelace).

Maria Chiara Virgili di Dannati Architetti -

nella parte di Ada Lovelace da Jennifer Chiaverini - L’Incantatrice di numeri (Ada Byron Lovelace).

Simona di Gli scimmioni non leggono Nietzsche -

nella parte di Sophia Frend da da Ada, the Enchantress of Numbers.

Link affiliati: il costo per te non cambia, ma una piccola parte del ricavato sostiene il podcast.

Oggi parliamo di un’applicazione reale di un algoritmo di ricerca dell’ottimo con il quale alcuni ricercatori hanno decifrato le lettere cifrate scritte da Maria Stuart, Regina di Scozia.

Link affiliati: il costo per te non cambia, ma una piccola parte del ricavato sostiene il podcast.

Esistono varie forme di machine learning e quella di cui parliamo oggi ha dimostrato di avere enormi potenzialità e ricadute nel mondo reale.

Pensieri in codice

Link affiliati: il costo per te non cambia, ma una piccola parte del ricavato sostiene il podcast.

Fino ad ora ho preferito evitare l’argomento ChatGPT perché sentivo di non avere granché da aggiungere al fiume di parole già spese. Ora però credo di aver riflettuto a sufficienza e spero di aver messo insieme un po’ di idee interessanti.

Pensieri in codice

Link affiliati: il costo per te non cambia, ma una piccola parte del ricavato sostiene il podcast.

Di ritorno dall’Open Source Day 2023 ho avuto modo di riflettere su quello che ho sempre avuto ben chiaro un mente sull’Open Source e su quello che invece ho sempre relegato un po’ in secondo piano. Come al solito, voglio condividere le mie rilessioni con te.

Pensieri in codice

Link affiliati: il costo per te non cambia, ma una piccola parte del ricavato sostiene il podcast.

Oggi ti racconto di qualcosa che ho scoperto e che mi sta entusiasmando molto. Si tratta di un metodo di organizzazione della conoscenza personale chiamato Second brain.

Pensieri in codice

Link affiliati: il costo per te non cambia, ma una piccola parte del ricavato sostiene il podcast.

Oggi proseguiamo il discorso sul Problema del Commesso Viaggiatore approfondendo il concetto di Ottimizzazione e correggendo alcune imprecisioni dello scorso episodio.

Pensieri in codice

Autori dell’episodio:

Link affiliati: il costo per te non cambia, ma una piccola parte del ricavato sostiene il podcast.

Oggi parliamo del Problema del Commesso Viaggiatore che affascina da anni matematici ed informatici.

Il problema del commesso viaggiatore (anche noto come TSP, dall’inglese “Traveling Salesman Problem”) consiste nell’individuare il percorso più breve che un ipotetico commesso viaggiatore dovrebbe compiere per visitare un certo numero di città, e tornare poi al punto di partenza, senza mai passare due volte per la stessa città.

Si tratta di un problema matematico di ottimizzazione, cioè un problema la cui soluzione consiste nel trovare il valore ottimo di una determinata funzione obiettivo, tenendo in conto specifiche limitazioni, note anche come vincoli.

Lungi dall’essere un semplice artificio matematico, il TSP ha moltissime applicazioni pratiche: una fra tutte è ovviamente la logistica, la pianificazione di percorsi ed itinerari, che migliora notevolmente fattori come il traffico o l’efficienza nella consegna e distribuzione delle merci.

Oltre a questa poi, altri esempi di applicazioni forse un po’ meno intuitivi sono la pianificazione di risorse, la realizzazione di microchip, l’apprendimento di algoritmi di Intelligenza Artificiale, perfino il sequenziamento del DNA.

L’origine del TSP non è chiarissima. Se ne parla addirittura in un libretto di appunti per commessi viaggiatori del 1832, con tanto descrizione del problema ed esempi di tragitti che attraversavano la Germania e la Svizzera. Anche se l’intenzione di tali appunti era chiaramente di risoluzione pratica, non di studio teorico, vista la completa assenza di dettagli matematici.

Sempre nel diciannovesimo secolo, però, il matematico, fisico e astronomo irlandese William Hamilton, inventò un gioco, the icosian game, che consisteva nell’unire tutti i vertici di un dodecaedro con un unica linea continua chiusa. E, guarda caso, la soluzione di tale gioco era proprio la soluzione al problema del commesso viaggiatore prendendo in considerazione 20 città.

Ad ogni modo, i primi studi veri e propri sul TSP iniziarono negli anni ‘30 del secolo scorso e fu subito chiaro che il problema in questione fosse di tipo cosiddetto NP-completo: cioè, in primo luogo, si tratta di un è problema che non può essere risolto in modo efficiente; e, oltre a ciò, ha la caratteristica che qualsiasi altro problema NP può essere può essere matematicamente trasformato in un’istanza del TSP.

Queste sue caratteristiche lo resero immediatamente abbastanza famoso nei circoli matematici e la sua fama crebbe ancora, quando, negli anni ‘50 e ‘60 iniziarono ad essere offerti premi in denaro a chi fosse riuscito a risolverlo in maniera efficiente.

Nonostante tali incentivi, però, ad oggi il TSP è ancora un problema privo di una soluzione efficiente: l’unico modo per ottenere la soluzione esatta, infatti, è tracciare tutti i possibili percorsi e valutarne il migliore, ma è chiaro che se parliamo di 3 o 4 città è un conto, mentre consideriamo, ad esempio, 150 città, il carico di lavoro diventa praticamente ingestibile.

Il risultato di ciò è che, attualmente, per la risoluzione del TSP per quantità importanti di nodi vengono utilizzati degli algoritmi euristici, cioè algoritmi la cui soluzione è solo probabilmente esatta: cioè che non assicurano che essa sia quella ottima.

Negli ultimi anni, il problema del commesso viaggiatore ha iniziato ad attirare attenzione anche al di fuori della comunità matematica ed informatica. In particolare sono stati condotti studi su esseri viventi per determinare la loro capacità di trovare la soluzione ottima.

Gli esseri umani, ad esempio, sono risultati particolarmente adatti, riuscendo ad individuare rapidamente, a colpo d’occhio, soluzioni molto vicine a quella ottima, con una perdita di efficienza di circa l'1% in caso di 10 o 20 nodi e che saliva fino all'11% in caso di 120 nodi.

Anche studi condotti sui piccioni, hanno mostrato come essi siano in grado di pianificare itinerari complessi e quasi ottimali per visitare in modo efficiente una serie di mangiatoie. Dimostrando come anche tali animali vantino abilità naturali nell’avvicinarsi alla soluzione ottima del TSP.

Negli anni ‘10 la fama del problema del commesso viaggiatore raggiunse perfino le grandi masse. La stampa generalista diffuse infatti la notizia che gli esemplari di alcune specie di api fossero in grado istintivamente di risolvere il problema del commesso viaggiatore, con titoli del calibro di “Il piccolo cervello delle api batte i computer”.

Sarebbe stato bello, ma in effetti si trattò semplicemente di una cattiva interpretazione del paper di una ricerca scientifica.

Le api, infatti, si sono dimostrate abili nello spostarsi da un fiore all’altro scegliendo il percorso più breve, questo è vero, ma ciò è ben lontano dall’essere in grado di risolvere il problema del commesso viaggiatore. In più, non essendo noi stessi in grado di calcolare l’ottimo percorso tra centinaia o addirittura migliaia di fiori utilizzando un computer, come potremmo giudicare se quello effettuato da un ape sia effettivamente l’ottimo o meno?

Link affiliati: il costo per te non cambia, ma una piccola parte del ricavato sostiene il podcast.

Oggi torniamo a parlare di algoritmi ed in particolare di tit-for-tat, un algoritmo particolarmente utilizzato nei protocolli di scambio di file come BitTorrent.

Link affiliati: il costo per te non cambia, ma una piccola parte del ricavato sostiene il podcast.