Algoritmi e diagrammi di flusso
Il concetto di algoritmo e i suoi requisiti, i simboli e le strutture di controllo dei diagrammi di flusso, la programmazione strutturata e alcuni esempi risolti.
Il concetto di algoritmo
Quando si parla di evoluzione di un sistema, si parla di un processo che accade o può accadere. L’algoritmo è la descrizione di tale processo mediante una successione di fasi che conducono alla realizzazione di un obiettivo prefissato.
L’esempio più comune per chiarire questo concetto è la preparazione del caffè:
- Mettere l’acqua e il caffè nella caffettiera.
- Chiudere la caffettiera.
- Mettere la caffettiera sul fornello.
- Accendere il gas.
- Attendere la bollitura.
- Spegnere il gas.
- Servire nella tazza.
Un algoritmo è adatto a descrivere un sistema: allo stesso modo di quest’ultimo, accetta dati in ingresso, effettua un’elaborazione e restituisce dati in uscita. Affinché sia un metodo realistico ed efficace per la risoluzione di un problema, deve soddisfare i seguenti requisiti:
- Finitezza: deve portare alla conclusione mediante un numero finito di passi; in particolare, non deve contenere cicli infiniti.
- Non ambiguità: deve essere interpretabile in modo univoco da qualsiasi esecutore.
- Determinismo: deve portare a risultati noti a priori sulla base dei valori di ingresso.
- Realizzabilità: deve essere realizzabile con le risorse disponibili.
Diagramma di flusso: strutture principali
Un diagramma di flusso è una rappresentazione visuale del problema, esposto secondo precise regole formali: è una mappa concettuale del processo. I simboli principali sono i seguenti:
- Elaborazione: è l’istruzione da compiere.
- Inizializzazione: imposta le variabili di input ai valori iniziali.
- Input/output: lettura degli ingressi e scrittura delle uscite.
- Inizio: punto di inizio dell’algoritmo.
- Condizione: stabilisce l’istruzione successiva sulla base di un test (ad esempio vero/falso).
- Fine: punto di termine dell’algoritmo.
Le strutture di controllo fondamentali, alla base degli algoritmi, sono le seguenti.
Sequenza semplice
Terminata l’elaborazione del blocco 1, il processo passa all’elaborazione del blocco 2.
Selezione multipla
All’inizio della struttura viene posta una condizione, che può essere vera o falsa. A seconda della risposta a tale condizione, il processo segue un ramo o l’altro.
Selezione semplice
C’è un solo ramo, corrispondente a una sola delle risposte (ad esempio vero); se si verifica l’altra risposta, il processo prosegue con l’istruzione successiva, senza eseguire un’elaborazione specifica.
Ciclo post-condizionale
Esegue una sequenza di istruzioni finché una determinata condizione non diventa vera (o falsa). La condizione viene controllata dopo l’esecuzione del blocco di istruzioni, pertanto la sequenza di istruzioni viene eseguita almeno una volta.
Ciclo pre-condizionale
Esegue un controllo sulla condizione prima di eseguire le istruzioni, pertanto può accadere che tali istruzioni non siano mai eseguite.
Ciclo iterativo
È un particolare ciclo pre-condizionale in cui una variabile interna è incrementata fino a raggiungere un valore massimo e a ogni iterazione viene eseguito un blocco di istruzioni.
Programmazione strutturata. È un criterio per la stesura di algoritmi che impone l’utilizzo di sole tre strutture di controllo fondamentali: sequenza, selezione e iterazione. Un programma ben strutturato facilita la leggibilità, la comprensione, la verifica della funzionalità, la correzione e l’aggiornamento.
Il teorema di Böhm–Jacopini stabilisce che, utilizzando solamente queste tre strutture, è possibile realizzare qualsiasi algoritmo.
Alcuni esempi di algoritmi
Maggiore fra due numeri
L’algoritmo riceve in input due numeri, li pone a confronto tramite un blocco di selezione e restituisce il maggiore. Vengono usate le variabili NUM1 e NUM2 per leggere i dati di input e MAG per salvare il risultato.
Maggiore fra tre numeri
Il risultato del confronto fra i primi due numeri viene confrontato con il terzo. Il secondo confronto è affidato a una selezione semplice: se la condizione risulta falsa, non deve essere intrapresa alcuna azione. In generale lo stesso problema può avere più algoritmi risolutivi.
Esempi
ES. 1. Avendo a disposizione un secchio da 4 litri e uno da 3 litri, descrivere l’algoritmo per riempire il secchio da 4 litri con 2 litri d’acqua.
- Riempire il secchio da 4 l.
- Travasare nel secchio da 3 l.
- Svuotare il secchio da 3 l.
- Trasferire il litro rimasto nel secchio da 3 l.
- Riempire di nuovo il secchio da 4 l.
- Travasare nel secchio da 3 l (ne entrano 2 l).
- Nel secchio da 4 l restano 2 l.
ES. 2. Trasformare i numeri negativi in positivi.
ES. 3. Conto alla rovescia di 20 secondi prima di lanciare il razzo.
Il conto alla rovescia usa un ciclo pre-condizionale: finché secondiMancanti è maggiore di 0, se ne sottrae uno; quando la condizione diventa falsa, si comunica «lancio effettuato».