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

Introduzione agli algoritmi – 1. Cosa è un algoritmo?

In questo articolo, primo di una lunga serie, proverò a spiegare a chi per i motivi più disparati ne ha bisogno, qualcosa sugli algoritmi.

Infatti ho iniziato a studiare questa interessante e soprattutto utile materia attraverso un libro dell’ottimo Thomas H. Cormen, ovvero Algorithms Unlocked.
Credo che questo lavoro possa diventare utile sia per me che sono in fase di apprendimento, sia per chi leggerà, anche perché le risorse in italiano a riguardo sono abbastanza pochine (togliendo ovviamente le dispense universitarie).

Direi quindi di non perdere altro tempo e buttarci nel discorso ponendoci una importante domanda.

Cos’è un algoritmo?

Beh, dal punto di vista formale questa è una definizione ancora oggetto di discussione, quindi occorre accontentarci, specie inizialmente, di una definizione informale che però racchiude il concetto di algoritmo:

Un algoritmo è un insieme di passi necessari per portare a termine un compito.

Considerando il mondo reale, possiamo dire che eseguiamo algoritmi praticamente in ogni momento.

Vogliamo preparare un bel piatto di pasta? Bene! Non so cucinare, potrei sbagliare qualcosa.

  1. Scegliere il tipo di pasta che si vuole;
  2. Prendere una pentola;
  3. Riempire la pentola con acqua salata;
  4. Scaldare la pentola finché l’acqua non inizia a bollire;
  5. Buttare la pasta scelta nella pentola;
  6. Attendere per il numero di minuti indicato nella scatola;
  7. Scolare la pasta;
  8. Condire se volete;
  9. Servire.

Come potrete ben vedere in cucina sono un disastro, ma ciò non toglie che abbiamo appena visto un esempio di algoritmo che chiunque conosce (magari con qualche variazione).

Spostandoci sui nostri amati computer, invece, possiamo citare due esempi di gruppi di algoritmi che sono abbastanza diffusi:

  • Algoritmi del percorso minimo (o pathfinding);
  • Algoritmi di criptazione.

Tra gli algoritmi eseguiti da noi umani e quelli eseguiti dai computer è presente un’enorme differenza che occorre tenere ben presente: noi umani possiamo tollerare qualche imprecisione nell’algoritmo (nell’esempio non è stato precisato quale tipo di pasta scegliere, ma non sarà certo un problema!), il computer no.

Un computer non tollera imprecisioni di alcun tipo su un algoritmo, tutto dev’essere già stabilito per non avere spiacevoli sorprese.

Per sapere come scrivere un algoritmo per computer, però, dobbiamo dare una risposta alla seguente domanda: cosa vogliamo da un algoritmo per computer?

Vogliamo semplicemente che, dato un input, l’algoritmo produca sempre la soluzione corretta per un problema attraverso l’utilizzo efficiente delle risorse computazionali.

La correttezza e l’utilizzo di risorse sono due concetti chiave che meritano particolare attenzione.

Correttezza

Cosa significa produrre la soluzione corretta?

Aiutiamoci con un esempio. Mettiamo il caso in cui il nostro navigatore GPS debba calcolare il percorso più veloce per farci spostare da un punto A verso un punto B.

Potrebbe suggerirci un percorso che sì, è il più corto, ma magari è anche il più trafficato o il più lento a causa dei limiti di velocità.

Possiamo dire, in tal caso, che la soluzione data è quella corretta?

Beh, l’algoritmo ha funzionato correttamente, questo è fuor di dubbio, il problema è la mancanza di informazioni (sul traffico e sui limiti di velocità) ricevute in input necessarie a trovare il percorso più veloce.

La soluzione fornita dal navigatore, tenendo conto dell’input che ha ricevuto, può essere quindi considerata corretta.

In alcuni casi, però, si può accettare che un algoritmo possa produrre una risposta non corretta, almeno finché possiamo sapere quanto spesso ciò possa accadere. È questo il caso dell’algoritmo di crittografia asimmetrica RSA.

Ecco un interessantissimo documento in PDF che parla del crittosistema RSA.

Il problema a cui l’algoritmo deve fornire una soluzione è determinare l’appartenenza di un numero all’insieme dei numeri primi o meno.

La prima cosa che si può fare è scrivere un programma che prova a dividere il numero in questione n per tutti i numeri che vanno da 2 a n-1.

Viene facile pensare che se n è composto da centinaia di cifre, il computer potrebbe impiegare un bel po’ di tempo nel calcolo, occorrono quindi delle ottimizzazioni:

  • Eliminare tutti i possibili divisori pari una volta stabilito che 2 non è divisore di n;
  • Fermarsi quando si arriva a √(n). Infatti, se non si riesce a dividere n per un numero compreso tra 2 e √(n) significa che n è primo.

Un algoritmo che funziona in questo modo può determinare se n è numero primo o numero composto. C’è un problema, però.

Se l’algoritmo stabilisce che n è composto, allora questo lo è, ma se stabilisce che n è primo c’è una piccolissima possibilità che questo sia invece composto, stimabile intorno a 1 volta su 250.

In questo caso siamo quindi davanti ad un algoritmo di approssimazione.

Gli algoritmi di approssimazione vengono incontro a problemi di ottimizzazione che vanno affrontati quando si vuole risolvere un problema che richiederebbe svariato tempo di calcolo in un tempo che sia invece ragionevole.

Manca quindi un algoritmo capace di trovare una soluzione ottima in tempi ragionevoli, e di conseguenza ci si accontenta di una soluzione quasi ottima.

Insomma, possiamo accontentarci della soluzione data.

Utilizzo di risorse

Cosa significa per un algoritmo utilizzare efficientemente le risorse computazionali?

Abbiamo già velatamente parlato di un’unità di misura che ci consente di determinare l’efficacia di un algoritmo, ovvero il tempo.

Provate a pensare ad un algoritmo che fornisce una soluzione corretta ma in moltissimo tempo: che valore potrà mai avere?

Basta pensare all’esempio riguardante il navigatore GPS. Se quest’ultimo impiega svariate ore per calcolare un percorso, tanto vale non usarlo.

Il tempo, però, non è l’unica misura per l’efficacia di un algoritmo. Infatti ci sono anche altri fattori da considerare, vedi la memoria (un algoritmo in esecuzione deve stare entro i limiti di memoria disponibili), la comunicazione con la rete, le operazioni su disco, etc.

In più è da notare che la correttezza di un algoritmo non dipende dal computer utilizzato, mentre il tempo sì.

Tutti i computer possono essere diversi, idem gli input… come trovare un metodo per valutare la velocità di un algoritmo?

Si combinano due idee:

  • determiniamo quanto l’algoritmo impiega in funzione della dimensione del suo input (es. dimensione di una lista di oggetti o il numero di incroci facenti parte di una mappa);
  • ci concentriamo su quanto velocemente la funzione che rappresenta il tempo di esecuzione dell’algoritmo cresce in base alla dimensione dell’input, ovvero la complessità temporale.
Un confronto sulla velocità in relazione alla dimensione dell'input tra algoritmi di ordinamento.
Un confronto sul tempo di esecuzione (asse y) in relazione alla dimensione dell’input (asse x) tra algoritmi di ordinamento.

Mettiamo che possiamo determinare che una specifica implementazione di un algoritmo di ricerca in una lista di n elementi impieghi 50n + 125 cicli macchina.

50n supera di molto 125 quando n diventa abbastanza grande, a partire da n>=3.
Man mano che n cresce, quindi, 125 diventa sempre più insignificante, idem il coefficiente di n.

Un altro esempio può essere quello in cui determiniamo la durata di esecuzione di un algoritmo in
20n3 + 100n2 + 300n + 200 cicli macchina.

Possiamo dedurre che il tempo di esecuzione dell’algoritmo cresce in n3 perché 100n2 + 300n + 200 conterà sempre di meno all’aumentare di n.

Dal punto di vista pratico, i coefficienti che ignoriamo contano ma dipendono da fattori non rilevanti tali che diventa possibile confrontare due algoritmi A e B con stessa complessità temporale (o tasso di crescita) tali che A però va più veloce di B in alcuni computer e B va più veloce di A in altri.

Se sia A che B producono soluzioni corrette con A che però risulta veloce il doppio rispetto a B, allora chiaramente si preferisce A rispetto a B.

Per paragonare due o più algoritmi nell’astratto è necessario concentrarsi sulla complessità temporale, non considerando (come fatto precedentemente) tutti i coefficienti di termine più basso.

L’importanza degli algoritmi

Per avere un’idea dell’importanza dell’efficienza di un algoritmo basti pensare che dati due algoritmi di ordinamento A e B con A molto più efficiente rispetto a B, non è difficile che l’algoritmo A eseguito su un PC vecchissimo superi nettamente in velocità l’algoritmo B eseguito su un PC di ultima generazione.

Anzi, dirò di più, gran parte delle prestazioni di un sistema dipendono dagli algoritmi utilizzati e non dal computer su cui gira!

Concludendo, possiamo dire che gli algoritmi sono uno strumento indispensabile quando si tratta di tirare fuori il meglio da un computer.

Per tutto l’arco di questo corso cercherò di presentarvi al meglio delle mie possibilità tutto ciò che sto attualmente studiando, sperando che il tutto possa rivelarsi utile per il vostro corso di studi, per i vostri studi personali e quant’altro.