Introduzione agli algoritmi – 2. Come descrivere gli algoritmi per computer

Eccoci alla seconda parte di questo corso di introduzione agli algoritmi.

Innanzitutto vorrei ringraziare chi, in vari modi, mi ha fornito un feedback consentendomi così di correggere le cose che non vanno bene.

In realtà è davvero difficile definire “corso” quella che è semplicemente una rielaborazione di appunti presi durante lo studio di algoritmi, ma è anche vero che, come diceva un vecchio saggio (di cui ignoro nome ed età):

Non hai capito una cosa fin quando non riesci a spiegarla a tua nonna.

Ed ecco che con questi post cerco di spiegare gli algoritmi alle tante nonne che leggono 😀

Bando alle ciance e buttiamoci a capofitto sull’argomento di oggi.
La scorsa volta abbiamo visto in maniera molto terra a terra il significato di algoritmo e alcuni dei concetti principali di cui bisogna tenere a mente quando si parla di algoritmi.

Oggi andiamo nello specifico e parliamo degli algoritmi per computer e in particolare di un semplice algoritmo per la ricerca di un elemento all’interno di un array.

Come descrivere algoritmi per computer

Solitamente si pensa che basti descrivere l’algoritmo utilizzando un linguaggio di programmazione, ma questo approccio può portare un problema: i dettagli riguardanti il linguaggio di programmazione rischiano di nascondere/offuscare la logica dell’algoritmo.

Per questo inconveniente ci viene incontro lo pseudocodice.

 

Come molti di voi sapranno, un programma può essere diviso in procedure.
Una procedura si occupa di ricevere dei parametri in input e, alla fine, di restituire un valore alla procedura chiamante.

Ecco ad esempio la chiamata a una procedura che calcola la radice quadrata di un numero:

L’input della procedura è il parametro x.
La chiamata a una procedura può o non può produrre output (leggasi restituire valori alla procedura chiamante).

Molti programmi e algoritmi lavorano con array di dati.

Un array aggrega dati dello stesso tipo nella stessa entità.
Ad esempio, ecco una tabella che mostra i primi 5 presidenti della Repubblica Italiana:

Schermata del 2016-08-01 22:55:08

Possiamo dire che il quarto elemento dell’array è Antonio Segni. Ciò che vediamo non è un insieme di elementi separati tra loro, bensì cinque voci di una tabella.

Un array è esattamente questo. Gli indici di un array sono numeri consecutivi che nei computer partono da 0 e in pseudocodice da 1, quindi occhio a non confondersi.

Dato il nome di un array e un indice dell’array, possiamo combinarli utilizzando le parentesi quadre.
Per denotare l’elemento i-esimemo di un array A, quindi, usiamo la notazione: A[i].
C’è anche un’altra cosa di cui tener conto, ovvero che il tempo di accesso ad un elemento dell’array è lo stesso per tutti gli elementi.

Ora che abbiamo gettato le fondamenta (array e procedure), iniziamo a vedere l’algoritmo che ci accompagnerà per tutta questa lezione: ricerca di un valore all’interno di un array.

Dato un array contenente n elementi, quindi, ci interessa sapere quale indice permette di accedere al valore ricercato (se esistente).

Facciamo finta che l’array sia uno scaffale di libri e che noi vogliamo sapere dove, nello scaffale, si può trovare un libro di Italo Calvino.

mastailibri-scaffale-libri-libreria-2

I libri presenti sullo scaffale potrebbero essere organizzati in ordine alfabetico per nome dell’autore, ma anche no.

Non sapendo come sono organizzati i libri nello scaffale, come facciamo a trovare il libro di Italo Calvino?

Guardando al problema con gli occhi di un programmatore possiamo dire che abbiamo un array A (lo scaffale di libri) di n elementi (i singoli libri) e vogliamo sapere se un valore x (un libro di Italo Calvino) è presente nell’array A.
Se sì, vogliamo determinare un indice i tale che A[i] = x.

Abbiamo bisogno anche di un modo per indicare che l’array A non contiene l’elemento x (il libro di Italo Calvino non è presente nello scaffale).

Se cerchiamo il libro di Calvino iniziando dall’estremità sinistra dello scaffale, controllando libro per libro man mano che ci muoviamo verso destra, allora stiamo utilizzando una tecnica chiamata ricerca sequenziale.

In termini di array, partiamo dall’inizio dell’array, esaminiamo ogni elemento in ordine (prima A[0], poi A[1], poi A[2], …, infine A[n-1]) e ci fermiamo quando troviamo x, se lo troviamo.

Procedura ricercaSequenziale(A, n, x)

Input:
  • A: un array.
  • n: il numero di elementi in A attraverso i quali cercare.
  • x: il valore ricercato.
Output:

O un indice i per il quale A[i] = x, o il valore speciale NON-TROVATO, che può essere un qualunque indice non valido per l’array (es. un numero negativo).

Algoritmo:
  1. settare risposta a -1 (ovvero NON_TROVATO);
  2. per ogni indice i, andare da 0 a n-1, in ordine:
    1. se A[i] = x, allora settare risposta al valore di i.
  3. restituire il valore di risposta come output.

Oltre ai parametri A, n ed x abbiamo utilizzato una variabile chiamata risposta. La procedura assegna il valore -1 (che idealmente possiamo far corrispondere a “non-trovato”) alla variabile risposta. Il valore della variabile poi cambia nel caso in cui venga trovato l’elemento x ricercato, prendendo il numero dell’indice.

L’esecuzione di azioni ripetute è chiamata ciclo, mentre ogni ripetizione presa a sé è chiamata iterazione.

Se andiamo a vedere bene, nell’algoritmo appena visto abbiamo un problema. Mettiamo il caso in cui il libro ricercato sia al primo posto… che senso ha continuare a cercarlo fino alla fine dell’array?
Nessuno, ma è ciò che avviene!

Il modo per ovviare a questo problema è far sì che il ciclo si interrompa una volta trovato l’oggetto cercato e ne restituisca l’indice.

Procedura ricercaSequenzialeMigliorata(A, n, x)

INPUT e output come prima.
Algoritmo:
  1. per ogni indice i, andare da 0 a n-1, in ordine:
    1. se A[i] = x, allora si restituisce il valore i in output (ciò comporta l’interruzione dell’algoritmo, quindi non viene eseguito il passo 2).
  2. restituire il valore di risposta come output.

Nonostante tutto, la ricerca sequenziale può essere resa ancora più efficiente.

Si noti, nella ricerca sequenziale migliorata, che a ogni iterazione vengono effettuati due controlli: il primo nel passo 1 per determinare se i < n-1,  e il secondo per verificare l’uguaglianza tra l’elemento ricercato e quello che si sta scorrendo nell’array.

Tornando all’esempio della libreria, questo significa controllare ogni volta se abbiamo superato la fine dello scaffale e, se no, se il libro successivo è quello di Calvino oppure no.

Il modo per migliorare l’algoritmo appena visto, quindi, è far sì che si riesca ad effettuare un solo controllo ad ogni iterazione invece che due.

Per far ciò, dobbiamo trovare un escamotage… che ne dite di prendere un libro finto, scrivere sulla copertina che è di Calvino e piazzarlo al posto dell’ultimo libro del scaffale?

In questo modo non ci serve controllare se abbiamo superato la fine dello scaffale perché siamo certi che alla fine dello stesso troveremo il libro ricercato smettendo così di iterare!

Uno potrà chiedersi: come facciamo a sapere se quello trovato è il vero libro di Calvino oppure no?
Semplice, quando si trova il libro di Calvino si controlla che questo non sia quello fantoccio, quindi il controllo avviene solo quando si trova il libro cercato.

Tradotto in termini di array, questo significa controllare che l’indice dell’elemento trovato sia minore della dimensione dell’array (array al quale alla fine abbiamo sostituito il “finto” elemento ricercato).

Il “finto” elemento inserito al posto dell’ultimo elemento dell’array si chiama sentinella.

Procedura ricercaSequenzialeSentinella(A, n, x)

INPUT e OUTPUT come prima.
ALGORITMO:
  1. Salvare A[n] in ultimo e mettere x in A[n].
  2. Settare i a 0.
  3. Mentre A[i] è diverso da x, fare ciò che segue:
    1. Incrementare i.
  4. Ripristinare il valore originale di A[n] settandolo a ultimo.
  5. Se i < n o A[n] = x, allora restituire il valore di i come output.
  6. Altrimenti, restituire NON-TROVATO come output.

Si può capire che la ricerca sequenziale con sentinella potrebbe risultare meno intuitiva delle altre, ma d’altro canto è più efficiente.
Si noti al passo 3 abbiamo un ciclo basato sul mantenimento o meno di una condizione, infatti il passo 3.1 viene eseguito fin quando la condizione “A[i] diverso da x” risulta vera.

Il fatto che vengano eseguiti molti meno controlli rispetto agli altri due algoritmi, rende la variante con sentinella il miglior algoritmo di ricerca sequenziale.

Dopo aver visto e formalizzato l’esecuzione di alcuni algoritmi, la prossima volta andremo ad analizzare gli stessi da un altro punto di vista, ovvero il tempo di esecuzione.
Da cosa è determinato? Come descriverlo?
Prepariamoci a vedere un po’ di matematica.

Sinhuè Angelo Rossi

print

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.