Follow

Foto di un programma che usa algoritmi scadenti.

Abbiamo visto cos’è un algoritmo, come è suddiviso e come lo si rappresenta astrattamente in fase di “progetto”.

Ora affronteremo il come progettarlo e in particolare il metodo del Dividi et Impera.

La progettazione di un algoritmo è la fase più delicata del processo di programmazione. Spesso scelte che sembrano ininfluenti nella nostra mente si tramutano in barriere computazionali invalicabili (cosa che appare manifesta se si combatte con il Progetto Eulero).

Possiamo distinguere 3 fasi:

1) SCOMPOSIZIONE IN SOTTO PROBLEMI

In questa fase abbiamo nella nostra testa solamente l’obbiettivo che ci prefiggiamo (risultato) e i punti di partenza (dati in ingresso). Per esempio abbiamo l’obbiettivo di fare la spesa nel minor tempo possibile avendo come dati in ingresso la posizione dei supermercati della città.

La prima cosa da fare a questo punto è trovare a grandi linee i passi che ci portano dalla partenza all’obbiettivo. Nel nostro esempio sappiamo che la soluzione consiste nel:

1. Trovare la strada più breve per arrivare ad un supermercato.
2. Andare a fare la spesa.
3. Trovare la strada più breve per tornare a casa.

2) RISOLUZIONE DEI SOTTO-PROBLEMI

Trovati i sotto problemi del nostro problema principale dobbiamo risolvere i sotto-problemi (i quali di solito sono più semplici del problema di partenza) tenendo conto che abbiamo a disposizione solo tre elementi:

1. Istruzioni (le istruzioni da eseguire).
2. Controlli su condizioni (corrisponde all’italiano se…).
3. Salti (per saltare ad un istruzione specifica).

Qui non c’è un metodo universale. Bisogna lavorare di intuito suddividendo, se necesarrio, il sotto-problema in sotto-sotto-problemi, se necessario fino al punto in cui i sotto-sotto-sotto-…..-sotto-problemi non diventino le istruzioni base di cui disponiamo.

3) UNIONE DEI RISULTATI

Questa fase non è banale come sembra. Per ricostruire il problema principale sembra ovvio che vadano messi in fila i risultati dei sotto-problemi. Invece no. Qui è il punto (non l’unico ma uno dei principali) in cui entra in gioco l’efficienza.

Per tornare all’esempio della spesa ci rendiamo conto. Che i sotto-problemi (1) e (2) in realtà fanno la stessa cosa: la strada più breve all’andata, con buona possibilità, sarà anche la più breve al ritorno.

Quindi perchè calcolarla due volte? Basta salvare da qualche parte il risultato del problema (1) e riutilizzarlo in (3) senza pagare due volte il costo (in termini di calcolo) dell’elaborazione del percorso.

In questo esempio sembra ovvio ma vi assicuro che non è cosi. Spesso quando si programma si tende a andare a risparmio sulle variabili (forse per non sforzarsi a trovare un nome) e quindi a volte per usare un valore si applica più volte la funzione che lo genera. Ma spesso questo appesantisce enormemente il lavoro e l’efficienza.

Sul costo e la complessità di un algoritmo torneremo in seguito perchè è un argomento interessante e utile.

Abbiamo quindi definito queste fasi: SCOMPOSIZIONE-RISOLUZIONE-UNIONE. Questo principio prende il nome di Dividi et Impera ed oltre ad avere il vantaggio di aiutare nella “creazione” rende il software modulare il che comporta:

1. Maggiore capacità di manutenzione e individuazione degli errori.
2. Possibilità di riutilizzare la stessa soluzione di un sotto-problema di un algoritmo in un altro algoritmo (Per esempio il problema di trovare la strada più breve per fare la spesa lo si può riutilizzare nel trovare la strada più breve per un viaggio).

Bene. Poichè per approfondire maggiormente alcuni concetti non posso trascendere dall’informatica, dobbiamo abbandonare per un po gli algoritmi per introdurre concetti di programmazione dei calcolatori vera e propria.