Una guida approfondita sul mondo degli algoritmi. Come viene creato un algoritmo ? Quali compiti svolgono nella vita di tutti i giorni ?
Non perderti una spiegazione sui concetti più importanti dell’informatica spiegati in maniera semplice e il loro incredibile impatto sulla nostra vista di tutti i giorni.
Prima di andare…
Non perderti il più grande cambiamento della storia.
Economia.
Business.
Lavoro.
Nulla sarà come prima.
Iscriviti all’unico canale Youtube sul futuro del business con dati e intelligenza artificiale.
Contenuti
- Che cos’è un algoritmo ?
- Origine del termine algortimo
- A cosa servono gli algoritmi
- Come fare soldi con gli algoritmi
- Come si costruisce un algoritmo
- Ricerca Binaria
- Come funziona la ricerca binaria
- Come calcolare l’efficienza di un algoritmo ?
- Big O notation O(n)
- Algoritmi di ordinamento
- Ricorsione
- Dynamic Programming
- Algoritmi Greedy
Che cos’è un algoritmo
Per definizione un algoritmo è una precisa sequenza di istruzioni per raggiungere un determinato obiettivo.
Anche una ricetta può essere un perfetto esempio di algoritmo, purché le istruzioni da seguire non siano ambigue. Cosa intendo ?
- Aggiungi un litro d’acqua
- Un po’ di sale
- Due spicchi d’aglio
Non è un algoritmo ! La lista delle informazioni da eseguire deve essere assolutamente precisa e non ambigua.
Un po’ di sale è ambiguo, per essere un algoritmo la ricetta deve contenere un esatta quantità di sale, come due spicchi d’aglio e un litro d’acqua.
Ricordiamo che gli algoritmi vengono eseguiti dalle macchine.
Sono efficienti esecutori di ordini ma completamente incapaci di creare relazioni cognitive, anche le più semplici.
Un bambino di 5 anni è perfettamente in grado di riconoscere un gatto se ne ha visti altri prima.
Per un computer è maledettamente difficile riconoscere un gatto, anche i più sofisticati sistemi di machine learning non hanno un’accuratezza del 100%.
Tuttavia le macchine sono eccellenti calcolatori. Anche il migliore dei matematici non è in grado di calcolare mentalmente la decima cifra decimale del pi greco, mentre per un normale computer richiede qualche decimo di secondo.
Origine del termine algortimo
Il termine algoritmo deriva da un matematico persiano al-Khwarizmi, che tra i suoi scritti compare un testo sulla manipolazione dei numeri in un sistema decimale.
In particolare descrisse un metodo per calcolare le quantità mancanti di una misura usando piccoli cerchi.
Il suo metodo divenne famoso e tradotto in inglese come algorism, per poi evolversi in italiano, passando per greco e latino, come algoritmo.
A cosa servono gli algoritmi
Gli algoritmi sono un argomento chiave per chi studia computer science.
Sia per capire a fondo le caratteristiche di un software sia per essere assunti nelle grandi aziende tech.
Google, Facebook e Amazon danno grande importanza a questa materia durante i colloqui di lavoro.
Internet e la tecnologia hanno fatto progressi insieme agli algoritmi. Ovunque ci giriamo possiamo vedere esempi di algoritmi intorno a noi. Basta accendere un smartphone.
Se ho bisogno di trovare la pizzeria più vicina mi basta un click su google maps.
L’algoritmo dell’applicazione calcolerà quale sia la distanza minore dalla mia posizione alla prossima pizzeria, usando la tecnologia gps per stimare le distanze.
Cercando un parola su google, l’algoritmo del motore di ricerca inizierà ad individuare quale siano i risultati più idonei alle parole chiave inserite, restituendo solamente i siti più affidabili e informativi per la mia ricerca.
L’algoritmo di google è così importante e studiato che esiste solo per lui una vera e propria disciplina nella quale ogni anno vengono spesi miliardi di dollari: la Seo (search engine optimization).
La seo si occupa di cercare di raggiungere le prime posizioni sfruttando le debolezze o le caratteristiche dell’algoritmo di google.
Più si avrà una conoscenza profonda di come funziona e più sarà facile comprendere come posizionarsi al meglio tra i milioni di competitor.
Trovarsi in prima pagina su google fa tutta la differenza del mondo per il business: quando cerchi un prodotto online hai mai guardato la seconda pagina ?
Come fare soldi con gli algoritmi
Ora che abbiamo capito cosa sia un algoritmo cerchiamo di capire come vengono usati nel business.
La cosa più spontanea per un esperto di algoritmi è farsi notare da grandi aziende tech come IBM o Microsoft che spendono ogni anno milioni di dollari per la ricerca.
Il ricercatore, a differenza di come avviene in Italia, può avere stipendi milionari oltre oceano.
Specialmente per chi si occupa di intelligenza artificiale.
Un settore sempre in espansione è l’ algorithm trading.
Sviluppare algoritmi altamente sofisticati che in automatico investono in borsa quando rilevano segnali di rialzo o ribasso del prezzo.
Questa nuova disciplina sta prendendo piede in tutte le grandi banche d’investimento.
Queste società stanno licenziando i vecchi trader sostituendoli con ingegneri software che siano in grado di elaborare sistemi d’investimento efficienti.
Scopri come funziona l’algoritmo di Fibonacci e come viene usato nel trading
La ragione di questo cambiamento è molto semplice. Gli speculatori a breve termine come i trader, basano i propri investimenti sullo studio dei grafici e del money management.
Detta così sembrerebbe molto semplice.
La vera difficoltà è quella emotiva. Ragionare lucidamente dopo aver perso o vinto milioni di dollari è assai arduo.
Anche gli algoritmi sono in grado di riconoscere i segnali su un grafico.
A differenza dei trader però non c’è pericolo che si facciano prendere dall’emozione.
Un altro modo redditizio per usare questi strumenti è l’automatizzazione di lavori manuali.
Molto spesso sentiamo che la tecnologia ci ruberà il lavoro. Che i lavori più monotoni o ripetitivi spariranno nell’arco di qualche anno.
Pensa solamente a tutti i mestieri che richiedono di analizzare un codice e interpretarlo. Come avvocati e commercialisti.
Non sto certo dicendo che dobbiamo affidare a dei robot i casi più sofisticati dove c’è il rischio di violare leggi morali.
Peccato che la maggior parte delle cause siano semplici casi assicurativi. Negli studi legali già esistono software in grado di trovare le leggi da analizzare dentro ad un intero codice.
Il passo alla sostituzione uomo macchina non è così lontano.
Infine non dobbiamo certo dimenticare il data science. Il data science è la scienza che studia i dati per ricavare informazioni utili al proprio business.
Gli algoritmi vengono usati per ordinare grandi quantità di dati e per creare modelli predittivi utili al nostro scopo.
Nuovo nel Data science ? Inizia con queste guide gratuite Numpy Pandas Plotly
Come si costruisce un algoritmo ?
Abbiamo già parlato di cosa sia un algoritmo ma può non essere chiaro come effettivamente venga creato.
Per capire come analizzarne e scriverne uno è opportuno capire quale sia la tabella di marcia da tenere sempre presente.
- What: Qual’è il problema che dobbiamo risolvere ?
- How: Quale strategia abbiamo deciso di utilizzare per risolverlo ?
- Why: Per quale motivo il nostro metodo dovrebbe funzionare ?
- How fast: è importante tenere presente le risorse richieste dal nostro algoritmo: tempo e memoria. Se google avesse un algoritmo perfetto ma restituisse i risultati in 30 min non penso che sarebbe usato da molte persone.
Facciamo un semplice esempio di algoritmo seguendo la scaletta: una conoscenza base di un linguaggio di programmazione è utile per seguire il ragionamento ma non indispensabile.
Trovare il numero più grande di una lista
What: trovare il valore più alto in un elenco di numeri
How: scansionare ogni elemento della lista partendo dal primo numero, quando trovo un numero gli verrà assegnato il nome max. Andando avanti con la scansione non appena troverò un valore maggiore di max, il nuovo numero verrà chiamato max rubando il posto a quello precedente. Alla fine della scansione saremo sicuri di avere il numero più grande.
Why: scansionando ogni singolo valore è inevitabile che prima o poi raggiungeremo il valore più grande, il nostro max.
How fast: Qualsiasi computer esegue un’operazione così semplice in pochi decimi di secondo. Se però pensiamo ad una lista con un numero di elementi molto grande il calcolo può essere piuttosto costoso da eseguire
Un buon metodo per calcolare la difficoltà computazionale di un algoritmo è contare il numero di operazioni semplici che richiede.
Ovviamente non è una soluzione accurata ma ci può dare l’idea per comprendere l’ordine di grandezza delle operazioni
Nel nostro esempio, data una lista di n elementi non ordinata, la
difficoltà computazionale non può che essere F(n).
Ovvero proporzionale al numero di elementi stessi, dato che l’unico modo per essere sicuri di avere il giusto valore di max è scansionare ogni singolo valore.
Per capire meglio l’importanza dell’efficienza ho deciso di introdurre la ricerca binaria (binary serach), tra gli algoritmi più semplici e studiati.
Spiegando la differenza che ci può essere tra due algoritmi che portano entrambe alla stessa soluzione ma con tempi diversi.
Ricerca Binaria
La ricerca binaria è un metodo efficiente per trovare un elemento in una lista ordinata di elementi. Funziona dividendo continuamente in due la lista che potrebbe contenere il nostro elemento. Così da restringere sempre più il campo di ricerca.
Uno dei metodi più comuni per usare la ricerca binaria è trovare un elemento in una lista.
Ad esempio se dovessimo cercare una persona sull’elenco telefonico che contiene 2,500,000 nomi. Ovviamente avrai bisogno di un determinato nome e sai che l’elenco è in ordine alfabetico.
Per velocizzare la ricerca decidi di usare un algoritmo che faccia il lavoro al posto tuo.
Se il tuo programma esaminasse ogni nome nell’elenco userebbe un algoritmo chiamato ricerca lineare. Il computer dovrebbe scansionare 2,500,000 elementi diversi nel caso in cui il nome da te cercato fosse l’ultimo.
Se usassimo invece la ricerca binaria, perfino nel caso peggiore il nostro computer eseguirebbe solamente 22 ricerche.
Come funziona la ricerca binaria ?
L’idea che sta a fondo della ricerca binaria è il tenere in considerazione solo il range che contiene la soluzione. Più si avanza e più il range diventa stretto aumentando le probabilità di arrivare alla soluzione.
Se ad esempio ti chiedo di pensare a un numero da 1 a 100 e cerco di indovinarlo. Tu devi solo dirmi ogni volta che cerco di indovinare, se il mio numero è maggiore o minore al numero che hai pensato.
Se ti dico 80 e mi dici che il tuo numero è minore, poi dico 20 e mi dici che il tuo numero è maggiore. Vuol dire che hai pensato ad un numero compreso tra 20 e 80.
Ad ogni turno il range di numeri viene dimezzato in due parti uguali. Se non indovino e mi dici che il numero è troppo grande o piccolo possono eliminare metà dei possibili risultati.
Dopo aver capito che ci troviamo in un intervallo 20 80 e provo con il numero 50 (80+20 / 2) che si trova esattamente a metà, così da poter eliminare metà delle soluzioni.
A questo punto mi dici che il tuo numero è più alto di 50 e ci troviamo con l’intervallo 51 80. Eliminando il suo complementare 50 20.
In questo modo qualsiasi numero tu scelga, cercando sempre la metà dell’intervallo per eliminare le soluzioni complementari, sono in grado di indovinare in al massimo 7 tentativi (in un range di 100 numeri, log(100)=7).
Tornando alla nostra ricerca dell’elenco telefonico, abbiamo visto due algoritmi che portano alla stessa soluzione ma hanno costo di esecuzione ben differente, sopratutto con grandi numeri:
- Ricerca Lineare, che scansiona nome per nome fino a che non raggiunge il risultato.
- Ricerca Binaria, che elimina sempre metà delle soluzioni fino ad un range minimo dove è facile trovare la soluzione
Il primo nel peggiore dei casi dovrà effettuare n operazioni tante quanti n nomi sull’elenco.
Mentre il secondo velocizza parecchio questo processo cercando sempre il range più adeguato.
Come calcolare l’efficienza di un algoritmo ?
L’efficienza è un argomento chiave dell’informatica. Come facciamo a calcolare i tempi di esecuzione ?
A cosa facciamo riferimento ? Ci sono diversi modi per calcolarlo ?
Possiamo distinguere tre diverse analisi per ogni algorimto
- Best Case: non molto utile ma importante per capire il concetto. Nel migliore dei casi, quante operazioni fa il nostro algoritmo ? Tornando alla ricerca lineare, immaginiamo di star cercando il sig. Rossi nell’elenco. Se siamo così fortunati di trovarlo in prima posizione ci basterà una comparazione !
- Worst case: le analisi dell’efficienza tengono sempre in considerazione il worst case. Nel caso peggiore qual’è il costo d’esecuzione ? Se il sig. rossi si trova nell’ultima posizione il costo è chiaramente n
- Average Case: il caso medio è il più complesso da calcolare. In pratica si fa uso del calcolo probabilistico per stimare una media delle esecuzioni
Best case e Average sono marginali. Il più studiato è senza dubbio il worst case. Proviamo a immedesimarci in un ingegnere software.
Pensa se i clienti che usano i suoi programmi devono fare un’operazione che sfortunatamente è la peggiore in termini d’esecuzione.
Di certo il software deve reggere lo sforzo in tempo utile anche in questo caso. Per questo è opportuno basarsi sul worst case
‘Spera nel meglio ma aspettati il peggio’
Big O notation O(n)
La big O notation è una notazione esponenziale che descrive l’ordine di grandezza del costo d’esecuzione di un algoritmo.
Non siamo interessati alle singole operazioni che richiedono tempo costante, come inizializzare una lista. Ma a quelle operazioni che crescono al crescere delle dimensioni del nostro input.
Solitamente si distinguono 7 ordini di grandezza dove rientrano quasi tutti gli algoritmi più conosciuti. Vediamoli in ordine decrescente (dal più al meno costoso )
- O(n!) per chi non ha grande esperienza di algebra il fattoriale è un’operazione data da: n*(n-1)(n-2)..(1). Ad esempio 3! = 3*2*1 = 6.
- O(2^n) le operazioni eseguite dall’algoritmo aumentano esponenzialmente con l’aumentare dell’input. In particolare l’esponente è il numero di elementi dell’input
- O(n^2) le operazioni eseguite dall’algoritmo aumentano esponenzialmente con l’aumentare dell’input. In particolare la base è il numero di elementi dell’input, l’esponente è due.
- O(n) Le operazioni eseguite sono proporzionali alla grandezza dell’input. Come nella ricerca lineare le operazioni eseguite sono un multiplo della grandezza di n
- O(nlog(n)) tipico degli algoritmi di ordinamento, che vedremo più avanti nell’articolo
- O(log(n)) Costo in scala logaritmica. Gli algoritmi che hanno questo running time dipendono ancora dalla grandezza dell’input ma, come si può vedere dal grafico, la funzione cresce lentamente. Ricordi la ricerca binaria ? Con una lista di 100 elementi bastano 7 comparazioni !
- O(1) Algoritmi con costo costante. A prescindere dalla grandezza dell’input avranno sempre lo stesso costo
A differenza di come si possa pensare, la bravura di un programmatore non è tanto quella nel risolvere un problema ma, risolverlo in maniera il più efficiente possibile !
Algoritmi di ordinamento
I sorting algorithm, in italiano algoritmi di ordinamento sono tra i più studiati e sviluppati nel mondo dell’informatica.
Quando hai una lista di n elementi. Qual’è il modo più efficiente per ordinare gli elementi in modo crescente.
Qual’è il minimo numero di comparazioni possibili ? Vediamo tre di versi algoritmi con differenti tempi di esecuzione.
- Bubble Sort: algoritmo ormai superato ma utile per avvicinarsi a questa categoria. Questo algoritmo compara due elementi adiacenti e li scambia in caso il primo sia maggiore del secondo. Percorrendo tutta la lista fino alla fine. Con un’animazione il concetto si chiarisce immediatamente. Il tempo d’esecuzione è O(n^2) nel peggiore dei casi (quando la lista è ordinata al contrario)
- Merge sort: il livello di complessità aumenta e non spiego come funziona nei dettagli. Usa la ricorsione per dividere in sottoliste la lista originale per poi ordinarla pezzo pezzo. Worst case O(nlog(n))
- Timsort: simile al merge sort è l’algoritmo standard di Python. Quando usiamo la funzione
.sort()python usa proprio questo algorimto. Tempo di esecuzione sempre O(nlog(n))
Chi ha studiato algoritmi di certo saprà che è stato dimostrato che la massima efficienza raggiungibile (lower bound) è proprio nlog(n) !
Ricorsione, Dynamic Programming e Greedy
Possiamo dividere buona parte degli algoritmi in tre categorie. Ognuna di queste rappresenta un concetto importante nell’informatica.
Non è semplice spiegare queste tre tecniche in qualche riga perché richiedono un conoscenza molto approfondita.
Il mio obiettivo è introdurre a grandi linee i concetti sperando di suscitare curiosità. Lascio alcuni link di approfondimento per chi è interessato e vuole capire più ‘a fondo’
Queste tre tecniche sono la base per costruire algoritmi efficienti e impostare una strategia di risoluzione di problemi complessi.
Partiamo con la ricorsione !
Ricorsione
La ricorsione è una tecnica algoritmica utile per risolvere problemi divisibili in sotto problemi e ricomporli alla fine
Spesso viene utilizzato il termine latino Divide et Impera.
Trova un modo per dividere il tuo problema originale in piccoli problemi e ricorri su di loro finché non ricomponi la soluzione. Termina la ricorsione quando trovi il caso base
Un esempio classico per capire il concetto è il calcolo del fattoriale di un numero. Ad esempio il fattoriale di 4! è uguale a 4*3*2*1.
Riscrivendolo in termini generali è n*(n-1)*(n-2)*(n-3)*…(1).
Il problema principale è ovviamente la serie di operazioni. E’ possibile scomporre l’operazione in sotto casi. Ogni volta si moltiplica lo stesso numero meno uno fino al caso base che è 1
Ogni volta la funzione si auto chiama diminuendo n di 1. Fino a quando a forza di diminuire n diventa 1 dove si interrompe l’esecuzione.
Dynamic Programming
La differenza tra Dynamic Programming è sottile ma fondamentale.
Entrambe cercano di dividere il problema originale in sotto problemi per poi ricomporre la soluzione.
La differenza fondamentale è che la ricorsione ricorsione ricalcola ‘cecamente’ ogni sotto problema fino al caso base.
Il dynamic programming ogni volta che esegue un calcolo archivia la soluzione.
Nel caso in cui un problema si ripresenti nuovamente anziché sprecare energie per il ricalcolo si ‘ricorda’ della soluzione.
Il modo migliore per comprendere Ricorsione e Dynamic Programming è studiare la sequenza di Fibonacci e delle sue diverse implementazioni
Algoritmo Greedy
L’algoritmo Greedy è una particolare categoria di algoritmi che sceglie la direzione più performante basandosi su informazioni ‘locali’
Cosa intendo ? Con questo esempio chiarisco subito il concetto.
Il nostro Greedy algoritmo deve calcolare quale direzione porta ad un punto più alto. Le alternative sono AC e AB.
Essendo greedy l’algoritmo baserà la decisione tenendo in considerazione le informazioni ‘locali’, senza avere una visione più ampia del problema.
Nel caso qui sopra l’algoritmo greedy sceglierà il percorso AB perché rileva una pendenza iniziale superiore rispetto al percorso AC anche se la soluzione ottimale è chiaramente AC
A seconda dei casi gli algoritmi greedy possono rivelarsi funzionanti o meno.
Un esempio pratico è il calcolo del percorso minimo nel famoso Dijsktra’s Algorithm
Conclusione
Abbiamo visto qual’è la definizione di algoritmo e come può essere usato in contesti reali. Come vengono usati per produrre denaro e come scrivere un semplice algoritmo partendo da una tabella di marcia.
Abbiamo poi fatto un excursus spiegando i principali concetti dell’informatica e quali siano le categorie di algoritmi più usati
