ALGORITMI
Un algoritmo (detto anche procedura, prescrizione, processo, routine,
metodo) è un insieme di regole (dette anche direttive o istruzioni)
che, eseguite secondo un ordine prestabilito, consentono di trovare
il risultato di un problema a partire dai dati in ingresso.
Le caratteristiche fondamentali degli algoritmi sono:
1. non ambiguità: le operazioni indicate devono essere
sufficientemente semplici e ben definite da poter essere
comprese da un esecutore non particolarmente esperto (uomo o
macchina);
2. eseguibilità: l’esecutore deve essere in grado di eseguire ogni
singola regola con le risorse a sua disposizione;
3. finitezza: ogni algoritmo deve terminare dopo un numero finito di
passi, cioè in un intervallo finito di tempo.
La parola “algoritmo” si è diffusa a partire dalla fine degli anni ’60
grazie allo sviluppo rapido della scienza dei calcolatori, che ha uno
dei suoi punti focali proprio nello studio degli algoritmi.
Questi si possono infatti tradurre in modo abbastanza semplice e
meccanico in programmi, in base alle regole di uno dei molti
linguaggi di programmazione oggi esistenti.
Se programmi per problemi numerici sono stati compilati fin dal 1800
a.C., quando matematici babilonesi stabilirono delle regole di
risoluzione per alcuni tipi di equazioni, l’esperienza con i calcolatori
ha mostrato che i dati elaborati dai programmi possono
rappresentare anche quantità non numeriche.
Di conseguenza l’informatica ha focalizzato la sua attenzione sullo
studio delle diverse strutture con cui si possono rappresentare le
informazioni, e sull’aspetto ramificato o decisionale degli algoritmi,
che permette di seguire differenti sequenze di operazioni in
dipendenza dallo stato delle cose in un determinato istante.
Per questa ragione i modelli algoritmici sono talvolta preferiti a
quelli matematici tradizionali per la rappresentazione e
l’organizzazione delle informazioni.
Gli algoritmi si possono esprimere in modo discorsivo tramite una
serie di frasi, oppure in forma grafica.
Ad esempio, per risolvere il PROBLEMA
quanti sono i giorni di maggio
si può applicare il noto ALGORITMO
trenta dì conta novembre
con april, giugno e settembre;
di ventotto ve n’è uno
tutti gli altri ne han trentuno
• Nel primo caso (serie di frasi) si può seguire una sintassi libera
(pseudo-linguaggio);
• nel secondo caso (forma grafica) si usano i simboli standard dei
diagrammi di flusso oppure la rappresentazione tramite
struttogrammi.
Nella fase finale l’algoritmo viene espresso o codificato secondo uno
specifico linguaggio di programmazione.
Diagrammi di flusso
Il diagramma di flusso è una rappresentazione grafica di un algoritmo
costituita da un insieme di simboli (figure geometriche standard)
collegate da frecce.
Questo metodo è stato messo a punto negli Stati Uniti da Larry
Constantine ed Edward Yourdon a metà degli anni ’80.
Esso presenta, rispetto alla descrizione verbale, una maggiore
concisione, una minore possibilità di ambiguità e una comprensione
più immediata.
Per consentire una comprensione uniforme dei diagrammi di flusso, è
bene disegnarli secondo alcune convenzioni grafiche standard.
Strutture di Controllo del programma
L’ordine con cui le diverse operazioni devono essere eseguite è
specificato da particolari costrutti linguistici, detti strutture di controllo.
Alla metà degli anni ‘60 i due studiosi italiani G. Jacopini e C. Boehm
hanno dimostrato che:
Teorema di Bohm-Jacopini: dato un algoritmo idoneo a risolvere un
problema, ne esiste sempre uno equivalente in cui compaiano
esclusivamente le tre seguenti strutture fondamentali:
1.sequenza
2.selezione (o alternativa)
3.iterazione (o ciclo)
La sequenza indica una successione di operazioni che devono essere
eseguite una dopo l’altra, ciascuna una sola volta; ne è un esempio il
diagramma di flusso precedente.
In molti linguaggi di programmazione, tra i quali il C, non esiste una
forma sintattica specifica per la sequenza in quanto, in assenza di
istruzioni di controllo di flusso, le istruzioni del programma vengono
eseguite nell’ordine in cui sono scritte.
La selezione (o scelta) permette a un programma di proseguire
secondo uno tra due (o più) flussi di istruzioni alternative, a
seconda del risultato di un test o del verificarsi di una condizione.
L’iterazione (o ciclo, o loop) consiste nella ripetizione di una o più
istruzioni, e si può ottenere collegando il flusso in uscita da un
blocco con il flusso in entrata nel blocco stesso o in uno precedente.
In tal modo si possono eseguire compiti ripetitivi senza specificare
uno per uno un gran numero di singoli passi, ma scrivendo per
esempio un’istruzione del tipo: “esegui il prossimo passo 1.000
volte”.
Selezione multipla. Non sempre la scelta prevede due sole
alternative; se queste sono più di due è necessaria una selezione
multipla (o n-aria), secondo il seguente schema:
Tuttavia i moderni linguaggi di programmazione dispongono anche del
costrutto di selezione multipla, che permette di realizzare
direttamente una scelta n-aria.
Nel linguaggio C, le istruzioni dell’esempio precedente sarebbero:
switch (numero)
{
case 1:
esegui la somma;
break;
case 2:
esegui il prodotto;
break;
case 3:
esegui la divisione;
break;
}
Struttogrammi.
Una rappresentazione grafica degli algoritmi alternativa a quella
basata sui diagrammi di flusso, e particolarmente adatta per
programmare secondo le tecniche della programmazione strutturata,
è quella degli struttogrammi (ingl. structure chart), introdotti nel 1973
da I. Nassi e B. Shneiderman all’IBM.
I grafi di Nassi-Shneiderman consistono in un rettangolo principale,
suddiviso a sua volta in rettangoli o triangoli più piccoli, che indicano
le operazioni elementari costituenti l’algoritmo.
A differenza di un diagramma di flusso, uno struttogramma non
impiega frecce né blocchi di inizio e fine.
La figura seguente indica la rappresentazione mediante struttogrammi
delle tre strutture fondamentali della programmazione: la sequenza,
la selezione binaria e l’iterazione.
Come si vede,
• la sequenza è rappresentata da una successione di rettangoli
sovrapposti;
• la selezione binaria è rappresentata da un rettangolo diviso in tre
parti da due segmenti obliqui: nella zona centrale si indica la
condizione da verificare, nelle due laterali le parole “vero” e “falso”
(oppure “then” - “else”, “allora” - “altrimenti”, “+” e “-”, o equivalenti);
• l’iterazione è rappresentata da un rettangolo interno a un altro, con
possibilità di porre il controllo all’inizio o alla fine del ciclo.
• la selezione multipla è rappresentata da una serie di colonne (blocchi
case) delle quali viene attivata quella il cui valore è uguale alla
condizione.
Esempio: divisione con sottrazioni ripetute. Come altro esempio,
esprimiamo con uno struttogramma l’algoritmo della divisione
tramite sottrazioni ripetute:
Un approfondimento dei grafi di Nassi-Shneiderman si trova in:
http://faculty.kutztown.edu/bobeck/nassi_schart.pdf