Algoritmo: la guida definitiva

Ai giorni d’oggi, con l’avvento di internet e dei computer, si sente sempre più parlare del termine algoritmo. Ormai lo troviamo ovunque. Persino quando si parla dei social network e dei motori di ricerca, spesso si sente dire che è cambiato l’algoritmo per la visualizzazione dei post e del posizionamento nei motori di ricerca.

Insomma, l’algoritmo è entrato a far parte della nostra vita. Pochi lo sanno, ma in ogni azione che noi compiamo, sia che essa sia tecnologica come connetterci a internet con il cellulare, sia che l’azione sia prepararci una tazzina di caffè, è presente un algoritmo.

Ma dove è nato questo termine e cosa significa algoritmo? Forse ci siamo fatti un’idea di cosa può significare, ma se sei finito in questo articolo sono sicuro che finalmente ti sei preso la briga di andarlo a cercare e di informarti più a fondo sul suo funzionamento e significato.

Come fare un algoritmo?

Qual è un esempio di algoritmo?

In questo articolo risponderemo a domande come questa e lo faremo in maniera semplice ma approfondita, in modo tale che alla fine della lettura, tu sia in grado di implementare un algoritmo e capire i meccanismi che ci stanno dietro. Alla semplicità non verrà meno il rigore matematico, che non rende sempre le cose difficili ma spesso aiuta a spiegarle bene. Iniziamo.

Algoritmo: cos’è

algoritmo

L’algoritmo è l’insieme delle operazioni utili a risolvere un determinato problema, è dunque l’insieme delle operazioni che ci consente di passare dai dati iniziali ai dati finali.

Come sono queste operazioni?

Le operazioni sono deterministiche, cioè ben definite. Ciò significa che non variano nel tempo e seguono una certa struttura logica.

Quindi, per esempio, un problema potrebbe essere risolto in vari modi. Il problema rimarrà lo stesso e anche la soluzione. Quello che potrebbe cambiare sarà l’algoritmo per risolverlo, questo perché potrebbero esserci più algoritmi atti a risolvere un determinato problema. Ognuno di questi algoritmi risolverà quel problema, usando passi diversi, quindi gli algoritmi saranno differenti. In pratica diversi algoritmi useranno modi diversi di risolvere il problema, ma la soluzione finale sarà la stessa.

Algoritmo esempio

Forse non sai che l’algoritmo non deve essere per forza un algoritmo matematico ma possiamo implementare un algoritmo per descrivere i passi di cose che facciamo tutti i giorni, per esempio: andare a scuola, prepararsi una tazzina di caffè, rifarsi il letto, fare una valigia prima di partire, prendere un aereo o un treno. Insomma, le possibilità possono essere infinite, e in questo paragrafo faremo un esempio sul semplice algoritmo che esegue chi va a scuola. Per questo “problema” ne abbiamo implementato due, e adesso vediamo il perché.

L’algoritmo per andare a scuola 1

  1. Svegliarsi
  2. Spegnere la sveglia
  3. Alzarsi dal letto
  4. Fare colazione
  5. Lavarsi
  6. Vestirsi
  7. Recarsi alla fermata dell’autobus
  8. Prendere l’autobus
  9. Scendere dall’autobus
  10. Fare a piedi l’ultimo pezzo di strada prima di entrare scuola

Ecco il suo diagramma a blocchi

L’algoritmo per andare a scuola 2

  1. Svegliarsi
  2. Spegnere la sveglia
  3. Alzarsi dal letto
  4. Fare colazione
  5. Lavarsi
  6. Vestirsi
  7. Prendere la macchina
  8. Scendere dalla macchina
  9. Fare a piedi l’ultimo pezzo di strada prima di andare a scuola

Il suo diagramma a blocchi

Analisi degli algoritmi

Come vedi gli algoritmi implementati sono simili ma non uguali. Questo perché differiscono nel punto 7 e 8. Infatti nel primo, lo studente prenderà l’autobus per andare a scuola e per far questo si recherà alla fermata dell’autobus, nel secondo, invece, lo studente per andare a scuola prenderà la macchina, ipotizzando che sia uno studente maggiorenne.

Dunque, come premesso nel precedente paragrafo, i due algoritmi risolvono lo stesso problema (come andare a scuola) e ottengono la stessa soluzione (arrivare a scuola), ma lo fanno in maniera differente, cioè usando passi diversi.

Ti faccio riflettere su una cosa.

Chi arriverà prima a scuola? Lo studente che prenderà la macchina o quello che prenderà l’autobus? Detta in termini scientifici: quale algoritmo sarà computazionalmente più efficiente, il primo o il secondo?

Si presuppone che la risposta sia: lo studente che prenderà la macchina. Bene hai appena scoperto uno degli argomenti più affascinanti dell’analisi degli algoritmi: il calcolo della complessità computazionale. Ne parleremo più avanti.

Un algoritmo matematico

Gli algoritmi vengono utilizzati in matematica e soprattutto in informatica, quindi i nostri esempi calzano a pennello qualora lo scopo per cui si interpellano sia didattico, ma nel campo pratico assumono poca utilità, ecco perché conviene passare agli algoritmi matematici nella nostra trattazione.

Per questo vorrei introdurre una struttura dati molto presente quanto si parla di algoritmi; gli array.

Gli array

Gli array sono insiemi di variabili disposti in maniera contigua nella memoria, questo vale a dire che sono disposti uno dietro l’altro. Le variabili, invece, sono aree di memoria che vengono dichiarate per contenere dei valori numerici che possono cambiare nel tempo.

Per esempio, in linguaggio C, la variabile a=10 viene istanziata nella seguente maniera.

int a = 10;

In pratica stiamo dicendo al linguaggio C di creare un’area di memoria per contenere il numero 10.

Ora vogliamo creare un’area di memoria con tanti numeri contigui, posti in maniera casuale: creeremo dunque un array di numeri interi.

int a[] = {5, 1, 7, 3, 10, 13, 11, 1, 0, 5};

Bene, abbiamo creato un vettore di elementi non ordinati, adesso vogliamo posizionarli in maniera crescente. Dunque, creeremo un algoritmo di ordinamento, cioè un algoritmo che ordina gli elementi in un array.

algoritmo ordinamento

Tra i tanti algoritmi di ordinamento, il più comune, ma non il migliore è l’algoritmo Bubble sort.

L’algoritmo Bubble sort esegui i confronti dei numeri a due a due e li inverte di posizione se l’ordine e sbagliato. L’algoritmo reitera questo procedimento per tutta la lista di numeri finché non vengono eseguiti più scambi. Ciò indicherà che la lista sarà ordinata.

Tra i tanti algoritmi di ordinamento, ovviamente questo non è il migliore perché è il più lento. Ci sono molti algoritmi per ordinare una lista di numeri e, anche se raggiungono lo stesso risultato, ciò che li distingue è proprio quello di cui parlavamo poco fa: la complessità computazionale, cioè la velocità di esecuzione di quel problema.

Complessità computazionale di un algoritmo

La complessità computazionale misura quanto un algoritmo è efficiente. Detto in termini più comuni, misura quanto un algoritmo è veloce.

Come avevo introdotto precedentemente, avere un algoritmo funzionante non basta a valutare la qualità di quest’ultimo. Occorrono infatti dei parametri che vanno valutati per definire quanto un algoritmo è funzionale rispetto a un altro.

In informatica questo concetto è molto importante, perché quando si fanno calcoli con un computer, le risorse predisposte ai calcoli sono limitate, infatti non esistono computer infinitamente veloci, ma calcolatori che hanno una predefinita capacità di calcolo e quindi delle limitazioni fisiche.

Detto in termini più semplici, un algoritmo dato in pasto ad un computer per essere eseguito, impiegherà un certo tempo per trovare la soluzione. Quindi un Intel i3, sarà meno veloce di un i7 se eseguono lo stesso algoritmo e quindi gli stessi calcoli. Però questa differenza di velocità di esecuzione potrebbe non essere significativa, infatti se l’i3 impiega due giorni a risolvere quell’algoritmo, l’i7 ne potrebbe impiegare 1,5 giorni. Quindi tra i due casi la differenza di esecuzione non produce un guadagno importante in termini di tempo.

Le cose cambiano quando passiamo da un algoritmo a un altro. Infatti, mentre un determinato algoritmo, con la potenza di calcolo disponibile ai giorni d’oggi, potrebbe impiegare 2 giorni per essere risolto, un altro potrebbe necessitare migliaia di anni con la stessa potenza di calcolo.

Hai capito bene. Potrebbero esserci delle delle differenze paradossali tra la soluzione di un problema e un’altra. Questo accade in virtù del fatto che i due algoritmi usano passi differenti per arrivare alle stesse soluzioni. In definitiva, un algoritmo potrebbe essere più macchinoso dell’altro.

Quindi, come dicevo, trovare l’algoritmo che risolve un problema, non è l’unica strada che va percorsa, ma è necessario qualcosa in più. Bisogna trovare anche l’algoritmo più efficiente. Quindi va valutata la complessità computazionale di un algoritmo.

Ecco perché quando si parla di algoritmi su software utilizzati pubblicamente spesso si sente dire: è stato migliorato l’algoritmo. Ci si riferisce al fatto che l’algoritmo potrebbe essere più performante ma anche più efficiente a trovare la soluzione corretta a un problema.

Vediamo adesso come si valuta la complessità computazionale.

Riprendiamo l’esempio dell’algoritmo di ordinamento. Precedentemente abbiamo analizzato l’algoritmo di ordinamento Bubble Sort, adesso è il caso di valutarne la complessità computazionale.

Avevamo una lista non ordinata di numeri e abbiamo detto che per ordinarla, gli elementi vanno confrontati a due a due, scambiandoli di posizione se questi non sono ordinati. Bene, questa operazione va fatta, nel caso peggiore n x n volte, perché abbiamo due cicli uno dentro l’altro: il ciclo esterno ripeterà n volte quello interno che a sua volta verrà ripetuto n volte.

Si dice allora che la complessità computazionale del Bubble Sort è O(n2) , cioè O di n al quadrato, una complessità computazionale troppo onerosa. Immaginate, infatti, di avere una lista di qualche milione di numeri da ordinare. Ci vorrebbero secoli per farlo.

Occorre dunque un algoritmo che sia più efficiente di questo e che quindi abbia una complessità computazionale più bassa. Vediamo quali sono i più famosi che abbiamo a disposizione.

AlgoritmoComplessità
Merge SortO( n log n)
Bubble Sort O(n2)
Quick Sort O(n log n)
(Con alcune eccezioni)
Insertion Sort O(n2)

Come si vede bene dalla lista, l’algoritmo più veloce e quindi meno dispendioso in termini di risorse, è il Merge Sort.

Diagramma a blocchi

I diagrammi a blocchi (o flow chart, o diagramma di flusso), sono delle rappresentazioni grafiche che ti consentono di disegnare un algoritmo senza l’ausilio di linguaggi di programmazione, in modo tale che questo sia comprensibile anche per i non addetti ai lavori.

E’ interessante notale che oltre ai diagrammi a blocchi esistono altri modi di descrivere un algoritmo, per esempio in pseudocodice. Lo pseudocodice è un linguaggio di programmazione molto vicino a quello dell’uomo, ma adatto a rappresentare algoritmi che possono essere scritti in linguaggi di programmazione come C, C++, PHP, Python, ecc.. E’ un linguaggio che tutti possono usare e comprendere perché non richiede grandi conoscenze specifiche.

Tornando al diagramma blocchi, diciamo subito che esistono dei software online per rappresentare questo tipo di grafici. Uno di questi è Draw.io, lo analizzeremo più avanti.

Figure del diagramma di flusso

Ellisse

La parte iniziale e finale di un diagramma di flusso si indica con un blocco a forma di ellisse, quindi tutti i nostri diagrammi a blocchi inizieranno e finiranno con un ellisse. Tutti i blocchi sono collegati da una freccia indicante il verso in cui deve andare l’algoritmo.

diagramma a blocchi di un algoritmo

Parallelogramma

Il parallelogramma è usato per prendere dall’utente un dato in input e restituire un dato in output. Ad esempio, l’algoritmo può prendere in input un dato digitato da testiera e restituire il risultato di una radice quadrata.

inserire un numero in un algoritmo

Rombo

Il rombo è utilizzato per le istruzioni condizionali, cioè per prendere decisioni in un algoritmo. La decisione poi prende una strada tra due, cioè la vera o la falsa. Quindi, per esempio, si potrà controllare se un numero è maggiore di 10. Se la risposta è vera verrà eseguito tutto ciò che c’è dopo la freccia Vero, altrimenti il programma prenderà il flusso della freccia Falso.

rombo condizionale

Cicli

Il rombo è usato anche per implementare degli algoritmi ciclici, come il while e il for. Infatti, può verificarsi che un’operazione venga compiuta fin quando una condizione si verifichi.

Nell’immagine viene sommato uno ad a fin quando a è maggiore di 10.

while e for

Draw.io

Draw.io è un software che ti consente di disegnare diagrammi di flusso direttamente online, quindi senza installare software, semplicemente connettendosi al loro sito internet.

L’applicazione online è in inglese, ma non importa se non sai l’inglese, dovrai disegnare, non leggere.

Appena entrati nella homepage, bisogna decidere se creare un nuovo diagramma o aprirne uno esistente. Scegliamo di crearne uno da zero cliccando su Create New Diagram. Si aprirà una finestra in cui è possibile scegliere i tipi di diagrammi più famosi, molti dei quali usanti nell’ingegneria del software o per creare dei work flow.

Dato che vogliamo fare le cose semplici, andremo sulla sezione Basic e cliccheremo su Blank Diagram. A questo punto si aprirà la finestra per disegnare, così come la vedi nella figura qui sotto. A sinistra puoi notare la toolbox, cioè la cassetta degli attrezzi da cui selezionare le figure da posizionare nello spazio centrale adibito a contenere le figure del nostro algoritmo.

Nell’esempio, ho posizionato un ellisse (l’ovale) e sotto un rettangolo che possiamo collegare cliccando sulla freccia blu al di sotto dell’ellisse. Se invece cliccherai dentro le figure, scoprirai di poter scriver un testo a tuo piacere. Quel testo descriverà quel preciso passo che dovrà compiere l’algoritmo.

Per salvare il grafico stampato, vai su File in alto a sinistra e premi Save. Successivamente sceglierai il nome del file. Se invece vuoi salvare nel formato JPG, PNG, PDF, HTML e altri formati, vai su File e scegli Export as e successivamente scegli il tipo di file in cui vuoi salvare.

Lascia un commento