Cos’è un algoritmo? Eh, domanda non troppo facile ma senz’altro di fondamentale importanza. Ormai siamo nell’era digitale, dove gli algoritmi regnano sovrani. Tutti i dispositivi che utilizziamo quotidianamente sono basati su essi, direi quindi che un po’ di loro conoscenza non guasta a nessuno 😉 .

Se alla lettura preferisci vederti un video eccone uno che ho preparato a riguardo. Uno un esempio un po’ diverso ma il senso è lo stesso 😉

Introduzione ed esempi pratici

Per definire questo “oggetto”, vediamo di partire da un semplice esempio 😉 Sai preparare la pasta giusto? Bene, mentre la prepari segui un algoritmo ben preciso:

1. Metti l’acqua nella pentola
2. Accendi il fuoco e sopra ci metti la pentola
3. Aspetti 5-10 minuti che l’acqua bolla
4. Pesi la pasta su una bilancia
5. Aggiungi il sale all’acqua
6. Aggiungi la pasta nella pentola
7. Aspetti 5-10 minuti di cottura
8. Al termine la scoli e la aggiungi al sugo.
9. Quindi la servi nel piatto

Chiaramente non fissiamoci troppo sui dettagli della preparazione della pasta, magari tu hai una ricetta super segreta diversa da questa 😉 Ah, giusto per inciso ho scoperto di recente che non è necessario tenere il fuoco acceso dopo che l’acqua ha raggiunto la temperatura di ebollizione, si può buttare la pasta, spegnere la fiamma e questa si cuocerà lo stesso. Guarda questo video di Dario Bressanini se non ci credi 🙂

Comunque, mettiamo un po’ da parte la pasta, l’importante è rendersi conto che esistono delle istruzioni che vanno bene in qualsiasi momento per prepararla e funzionano sia che le metta in pratica io che tu. Inoltre il risultato è sempre lo stesso, un bel piattone di pasta 🍝🍝

Se può interessarti approfondire il tema, questo è un bel libro che ti suggerisco : https://amzn.to/3ci6Fim .

Vediamo quindi di estrarre le proprietà fondamentali di un algoritmo a partire da questo semplice esempio. Esso è una sequenza di istruzioni/azioni che vanno eseguite in un ordine specifico. Questa sequenza è inoltre finita in tempo, nel senso che sai già che riuscirai a preparare il tuo piatto di pasta in 15-20 minuti. Inoltre questa ricetta non può essere ambigua, interpretabile, ma deve funzionare chiunque sia il “cuoco”. Per concludere, le istruzioni devono essere elementari, semplici, non ulteriormente spezzabili in azioni più semplici.

Vediamo quindi un esempio più matematico prima di arrivare a definirli formalmente 😉

Algoritmo di Euclide

E’ un algoritmo che si usa per trovare il massimo comun divisore tra due numeri naturali qualsiasi. Se non sai cosa sia il massimo comun divisore (MCD), è semplicemente il numero naturale più grande in grado di dividere esattamente i numeri di partenza. Quindi si ha che esso è uguale ad 1 nel caso essi siano coprimi, ovvero privi di divisori comuni.

Ecco l’algoritmo scritto in linguaggio comune (pseudocodice):

Prendi $a,b$ due numeri naturali

Definisci una variabile naturale $r$

Finchè $b$ diverso da $0$:

>>> $r=

>>> $a=b$

>>> $b=r$

Restituisci $a$

fine

Ora non sto qui troppo a soffermarmi sul perchè questo algoritmo funzioni, proseguiamo oltre..

Ciò che importa  per il nostro obiettivo attuale è notare come le operazioni che questo algoritmo comporta sono elementari: divisioni intere e sostituzioni di variabili, niente di più.

Inoltre questo algoritmo fa al più $b$ iterazioni del ciclo, nel caso in cui essi siano coprimi e quindi termina in tempo finito 🙂 Proprio come avevamo notato prima nell’algoritmo per la pasta.

Chiaramente questo è un algoritmo ancora semplice, in fondo all’articolo ti indicherò alcuni algoritmi grossi e importanti così da farti venire voglia di approfondire l’argomento da solo 😉

Definizione più rigorosa del concetto di ALGORITMO

Si dice algoritmo una sequenza finita e ordinata di operazioni elementari e non ambigue che permettono di risolvere, in maniera deterministica, un problema in tempo finito, ovvero l’algoritmo ha un termine.

Se non hai mai sentito parlare di algoritmo in termini un po’ più formali, è molto probabile che ti sfugga l’importanza di qualcuna delle richieste che l’algoritmo deve soddisfare per essere definito tale.

Vediamo quindi un paio di esempi che sembrerebbero algoritmi ma non lo sono perchè non rispettano una o più di queste strane proprietà.

Un esempio semplice di non determinismo di una sequenza di istruzioni potrebbe essere introdotta nella procedura di preparazione della pasta. Per esempio si decide che appena si è messa l’acqua a bollire si lancia un dado e a seconda del numero che esce si salterà una delle operazioni che abbiamo elencato successivamente. Non solo questa procedura non è deterministica ma non è nemmeno detto che ci permetta di ottenere il risultato finito 🙂

Un altro “algoritmo” molto semplice ma che non può essere definito tale in quanto non termina è il seguente:

$a=2$

Finchè a è pari:

       $a=2a$

Restituisci $a$

fine

Chiramente se moltiplichiamo un numero pari per 2, esso rimarrà pari 😉 Può sembrare stupido come esempio, ma è sufficientemente chiaro per capire l’importanza di queste proprietà nella buona caratterizzazione di un algoritmo.

Per finire questa carrellata di esempi di non algoritmi, discutiamo un attimo della non ambiguità. Un esempio molto semplice, legato per sempre alla preparazione della pasta, è il seguente:

Nella ricetta invece di dire dopo 10 minuti spegni il fuoco e scola la pasta, supponi di dire di scolarla quando ti sembra cotta.

Il “sembrare cotta” non è chiaramente un parametro oggettivo. Sono d’accordo che nella realtà lo si dice, ma non è un problema dato che noi non siamo macchine ma uomini e donne pensanti, in grado di fare delle scelte in autonomia.

Però se si dicesse così ad un computer, o comunque dare queste istruzioni ad una planetaria o un robottino che cucina per te, è ovvio che lui non sarebbe in grado di decidere quando scolare la pasta (a meno di insegnarglielo, ma questo è un discorso più complicato) 😉 Ecco il perchè dell’importanza della non ambiguità delle istruzioni.

Proprio perchè queste proprietà devono appartenere ad un qualsiasi algoritmo, essi sono anche rappresentabili mediante un diagramma di flusso. Qui sotto ti allego una immagine tipo e in un altro articolo magari approfondiremo la visione grafica degli algoritmi…merita davvero più spazio che qualche riga stracciata qui.

Come anticipato in precedenza, gli algoritmi sono gli elementi fondamentali dell’informatica, sono alla base di ogni processo automatizzato ed automatizzabile. Per cui ho pensato, perchè rimanere su esempi solamente spiegati quando puoi mostrare come lavora un algoritmo matematico nella pratica? Qui di seguito trovi quindi il codice che ho scritto sia in Python che in Matlab di un algoritmo parecchio interessante, da far risalire ai babilonesi, che permette di convergere, relativamente velocemente, alla radice quadrata di un numero reale positivo.

Oltre al codice ho pensato di mostrarti riportate le iterazioni nel caso di cercare la radice del numero 17, per non fare il caso semplice di un quadrato esatto. Certo, verificare che l’algoritmo funziona per un caso particolare non ci permette di dire che esso sia corretto, ma è un buon modo per iniziare a convinrcetene.

Ah, purtroppo non sono capace di inserire codice eseguibile qui sul blog e quindi mi è toccato fare gli screen delle due schermate (Python e Matlab). Il codice è breve quindi puoi copiartelo a mano senza problemi ma mi fa schifo onestamente includerlo in delle immagini ahah 🙂 quindi se sai come inserirlo e mettere la possibilità di eseguirlo fammelo sapere con un commento. Ti lascio al codice e ai risultati. 

P.S. Come criterio di arresto dell’algoritmo ne ho usato uno stupido, ho detto: stoppa l’esecuzione dopo 15 passi. Si può fare molto meglio, il criterio più ragionevole in questa tipologia di algoritmi è di fissare una tolleranza relativa, per esempio 0.1% del numero di partenza, è poi lasciar proseguire le iterazioni fino a che il valore calcolato sarà più vicino al risultato esatto rispetto allo 0.1% di 17 in questo caso.

Prima di concludere l’articolo, ti lascio un elenco con alcuni algoritmi interessanti a cui ti consiglio di dare un’occhiata. Se c’è interesse, magari ne approfondiremo qualcuno nei prossimi articoli, in caso faccelo sapere mandando un messaggio alla Pagina Facebook, lasciando un commento qui sotto al post o mandando una mail all’indirizzo list@mathone.it 🙂

Alcuni algoritmi interessanti da approfondire

Preferisco sviluppare questa sezione in maniera molto schematica, lasciandoti una semplice lista di link che rimandano ad una pagina di approfondimento dedicata al particolare algoritmo, per parlarne sul sito ci sarà tempo in futuro 🙂

• Algoritmo di ricerca di Google
• Algoritmi di ordinamento
• Algoritmo di Dijkstra (distanza minima)
• Algoritmi di raccomandazione
• Algoritmi di compressione dati senza perdita

Ce ne sarebbero molti altri ma per ora direi che è una lista anche troppo lunga, se vuoi guardare qualcos’altro su questo sito, ecco alcuni articoli legati a queste tematiche che avevamo scritto in passato:

• Algoritmo calcolo radice quadrata
• Algoritmo moltiplicazione egizia
• Alla scoperta di algoritmi antichi e curiosi