0 - Algoritmi.

0.3 – Algoritmi e loro Rappresentazione

Il concetto di Algoritmo occupa una posizione centrale nell'informatica teorica: l'analisi della sua struttura e delle tecniche di rappresentazione e verifica occuperanno il resto del capitolo.

Un Algoritmo è un programma che viene formulato senza fare riferimento ad un particolare esecutore.

In un certo senso, l'algoritmo è una procedura computazionale comprensibile dall'uomo, mentre un programma è una procedura computazionale comprensibile dalla macchina.

Per comprendere la natura del concetto di algoritmo, calcoliamo il Massimo Comun Divisore di 10881 e 1488:

L’algoritmo ( intuito da Euclide duemila anni fa ) può essere scritto in questo modo:

INPUT a,b (cioé, dammi due numeri interi a e b)
Ripeti questo gruppo di istruzioni finché il resto non diventa ZERO
Calcola il resto della divisione tra a e b
Poni b in a ( poni il divisore nel dividendo: a=b )
Poni il resto della divisione in b: b=resto
Quando il resto è ZERO, il MCD è l'ultimo divisore nonnullo, cioé il numero contenuto in a
OUTPUT a (restituiscimi il valore di a che è il MCD)

Notiamo come il linguaggio sia ricco di istruzioni, al di là delle operazioni sui numeri. Per esempio, l’algoritmo ripete 3 volte lo stesso gruppo di due istruzioni, per cui esistono comandi del tipo
Ripeti 3 volte questo gruppo di istruzioni .
Ancora: come possiamo ordinare all'esecutore di eseguire le operazioni soltanto per numeri positivi? Ebbene, possiamo supporre di poter dare la seguente istruzione
Se a e b sono numeri positivi allora esegui le operazioni successive...
Dalle osservazioni precedenti si evince che l’algoritmo è determinato dal modo in cui si esprimono le istruzioni-base e quindi da un opportuno linguaggio.

Secondo Donald E. Knuth, autore di diversi volumi intitolati "The art of computer programming", nel suo primo volume dal titolo "Fundamental Algorithms", il termine algoritmo deriva dal nome del matematico persiano "Al-Khowarizmi", vissuto nel IX secolo d.C.

Nello stesso libro, Knuth associa al termine algoritmo le seguenti proprietà:

  1. Finitezza: un algoritmo deve terminare dopo un numero finito di passie, quindi, in un tempo finito
  2. NON ambiguità: ogni passo di un algoritmo deve essere definito in modo preciso: le azioni devono essere rigorose, chiaramente definite e specificate in tutti i casi possibili
  3. Eseguibilità: un algoritmo deve essere effettivamente eseguibile, cioé tutte le azioni possono essere svolte, senza problemi ed in un tempo finito, da un esecutore opportuno, uomo o macchina
  4. Input: un algoritmo può avere zero o più dati in ingresso
  5. Output: un algoritmo può avere zero o più dati in uscita.

Dalle considerazioni svolte fino a questo momento, possiamo immaginare che un esecutore deve saper gestire queste tre strutture:

  1. Sequenza: un insieme di azioni da eseguire l'una dietro l'altra;
  2. Selezione: un'azione che spezza il flusso sequenziale in più flussi;
  3. Iterazione: un insieme di azioni che vanno ripetute più volte.

Innanzitutto supporremo che il nostro esecutore sappia eseguire senza errori tutte le operazioni e confronti con i numeri. Successivamente introduciamo due linguaggi di rappresentazione degli algoritmi che ci consentiranno di descrivere un semplice algoritmo:
assegnato un numero intero positivo N, stampare tutti i numeri pari multipli di 5 e minori o uguali ad N.

0.4 - Diagrammi di flusso (flow chart)

I diagrammi di flusso descrivono un algoritmo utilizzando delle figure geometriche convenzionali collegate da frecce.
Le frecce uniscono i vari blocchi dei diagrammi ed indicano l'ordine in cui saranno eseguite le varie istruzioni. Il flusso dei comandi procede dall'alto verso il basso e da sinistra a destra, a meno che le frecce indichino una direzione diversa.

funzioni
Figura 0.2

La figura successiva mostra, in particolare, la struttura di selezione. Essa traduce in maniera schematica la seguente espressione del linguaggio naturale:

SE il numero N è maggiore di zero allora scrivi sul monitor "è positivo" ALTRIMENTI scrivi sul monitor "è negativo o nullo".

funzioni
Figura 0.3

La figura 0.4 illustra, invece, il caso in cui la selezione è unica:
SE si avvera una certa situazione allora si agisce in un certo modo, ALTRIMENTI non si fa nulla. L'esempio in figura afferma:

SE il numero N è uguale a zero allora scrivi sul monitor "è nullo".

funzioni
Figura 0.4

La figura 0.5 illustra, invece, l'iterazione, cioè la ripetizione di un "Blocco" di istruzioni.
L'algoritmo chiede un numero intero N minore di 100 e, successivamente, stampa tutti gli interi compresi tra N e 100.

funzioni
Figura 0.5

L'ultima figura propone l'algoritmo che risolve il problema proposto alla fine del paragrafo precedente: assegnato un numero intero positivo N, stampare tutti i numeri pari multipli di 5 e minori o uguali ad N.

funzioni
Figura 0.6

I diagrammi di flusso diventano rapidamente illegibili se superano certe dimensioni e sono facilmente esposti ad errori logici. Inoltre, come potete vedere anche dall'esempio proposto, è difficile evidenziare a dovere le strutture ed i blocchi presenti nell'algoritmo.
Dove sono annidate le strutture di selezione ed iterative nell'esercizio proposto?

0.5 - Struttogrammi (Nassi-Schneidermann)

Questi diagrammi, appartenenti alla categoria delle rappresentazioni grafiche, presentano una forma diversa per ognuna delle strutture fondamentali ( vedi figure 0.7 e 0.8).

funzioni
Figura 0.7

funzioni
Figura 0.8

La figura successiva illustra l'algoritmo proposto nella versione "diagrammi di flusso" nel paragrafo precedente (figura 0.5).
Notate come sia più chiara la distinzione tra programma complessivo e "Blocco ripetuto".

funzioni
Figura 0.9

Gli Struttogrammi sono molto utili nella fase di apprendimento dei principi della programmazione e della realizzazione degli algoritmi, in quanto uniscono un grande rigore ad una discreta flessibilità. Il flusso di azioni procede infatti sempre dall'alto verso il basso ( come nella scrittura ) e non vi sono possibilità di altre vie d'uscita. In più è facile costruire blocchi all'interno di blocchi, semplicemente disegnando gli ultimi all'interno dei primi; nella sequenza, ad esempio, è facile pensare di sostituire una o più azioni con dei blocchi.

L'ultima figura propone l'algoritmo che risolve il problema proposto alla fine del paragrafo 0.3 e già presentato nella discussione sui diagrammi di flusso: assegnato un numero intero positivo N, stampare tutti i numeri pari multipli di 5 e minori o uguali ad N.

funzioni
Figura 0.10

I due capitoli successivi introdurranno i primi elementi del linguaggio C++. Il primo capitolo ci aiuta a scrivere il nostro primo programma servendoci di un "sistema di sviluppo", il secondo capitolo ci aiuta a comprendere come siano rappresentati i dati all'interno della memoria. Riprenderemo gli Struttogrammi nel terzo capitolo, quando cominceremo a "progettare" anche semplici algoritmi.