Pascal/Algoritmi

Wikibooks, manuali e libri di testo liberi.
Indice del libro

Prima di continuare ad analizzare le strutture del linguaggio Pascal, ci soffermeremo su un concetto molto importante in programmazione, e che assume ancora più significato con questo linguaggio: quello di algoritmo.

Il linguaggio Pascal è stato infatti creato molto rigido per costringere il programmatore ad un'accurata analisi del problema (e quindi dell'algoritmo).

Cos'è un algoritmo?[modifica]

Definizione

Un algoritmo, nel suo significato più ampio, è sequenza logica di istruzioni elementari (univocamente interpretabili) che, eseguite in un ordine stabilito, permettono la soluzione di un problema in un numero finito di passi

Dal punto di vista dell'informatica, possiamo quindi considerare ogni nostro programma un algoritmo, dove ciascuna istruzione è uno dei passi dell'algoritmo. Analizzare gli algoritmi ci aiuterà quindi a capire meglio come funziona la programmazione e, più in particolare, il concetto di programmazione strutturata su cui si basa il Pascal.

Vedremo inoltre come tutte le strutture possono essere rappresentate sotto forma di diagrammi a blocchi, il cui uso è molto comodo per analizzare gli algoritmi e lo sviluppo di programmi complessi.

Il teorema di Böhm-Jacopini[modifica]

Il teorema di Böhm-Jacopini, enunciato nel 1966 dai due informatici dai quale prende il nome, afferma che:

« qualunque algoritmo può essere implementato utilizzando tre sole strutture, la sequenza, la selezione ed il ciclo, da applicare ricorsivamente alla composizione di istruzioni elementari »
(teorema di Böhm-Jacopini)

Questo teorema in sostanza dice che ciascun algoritmo (e quindi, come abbiamo detto, ciascun programma) può essere realizzato utilizzando soltanto le tre strutture indicate, che ci appresteremo ad analizzare: la sequenza, la selezione (binaria o multipla) ed il ciclo (o ripetizione). Per struttura di controllo si intende una struttura sintattica che determina come e se devono essere eseguite certe istruzioni.

Le strutture di controllo[modifica]

Ciascuna istruzione di controllo in un linguaggio di programmazione strutturata ha alcune caratteristiche:

  • ha un solo punto di ingresso e punto di fine
  • la componibilità: ogni struttura di controllo può avere tra le strutture che controlla altre strutture di controllo, ricorsivamente, senza limiti.

La sequenza[modifica]

La struttura della sequenza è la più semplice, ed è stata già vista in precedenza: prevede che le istruzioni siano ripetute una dopo l'altra.
Nel caso di un semplice algoritmo come "prepara il caffè", i passaggi in ordine saranno ad esempio "prendi il caffè", "riempi il filtro della caffettiera", "accendi il gas", ecc.

La selezione[modifica]

La struttura di selezione permette di eseguire blocchi di istruzioni differenti in base ad una condizione valutata inizialmente.
Nel nostro algoritmo "prepara il caffè" potremmo quindi ad esempio prevedere azioni differenti se non c'è caffè in casa (si va a comprare il caffè); comunque, anche questa selezione poi ha un unico punto di uscita, cioè "riempi il filtro della caffettiera", sia che ci fosse il caffè in casa o no.
Questo è un caso di selezione binaria, ovvero che prevede due sole alternative: il caffè è in casa oppure non lo è.

Talvolta è possibile prevedere anche più di un caso, ad esempio il tipo di caffè che si vuole preparare (cappuccino, macchiato, semplice, ecc.): in base all'alternativa scelta bisogna effettuare operazioni differenti. In realtà questo costrutto (chiamato selezione multipla) può essere sostituito da più selezioni binarie.

Il ciclo[modifica]

Alcune operazioni possono poi richiedere la ripetizione di una o più istruzioni: questo è possibile grazie alla struttura chiamata "ciclo" o "ripetizione" o anche "iterazione" (dal verbo latino itero, ripetere).
Nel nostro algoritmo "prepara il caffè", ad esempio, si può inserire un ciclo per il numero di cucchiaini di zucchero necessari: se sono necessari tre cucchiaini di zucchero, allora si dovrà ripetere l'azione "versa zucchero" per tre volte.

Componibilità[modifica]

L'algoritmo appena descritto può essere reso più fine, prevedendo ad esempio al posto dell'operazione "vai a comprare il caffè" un sotto-algoritmo (in programmazione, un sotto-programma) che preveda la scelta del negozio da comprare in base ad esempio alla convenienza del caffè, ecc.

Input e output[modifica]

Altri due importanti concetti su cui soffermarsi prima di affrontare lo studio del Pascal sono quelli di input e output.

Per input si intendono tutte le informazioni in ingresso nell'algoritmo, che vengono cioè dall'esterno, e non sono state definite da chi ha formulato l'algoritmo o il programma. In informatica, ad esempio, è un input muovere il mouse, premere su un pulsante o digitare dei caratteri da tastiera.
Nel nostro algoritmo "prepara il caffè" sono informazioni in input il numero di tazzine da preparare, il tipo di caffè scelto, ecc.

L'output costituisce invece tutte le informazioni in uscita dall'algoritmo, cioè quello che produce effettivamente l'algoritmo verso l'esterno. In informatica, tipicamente, un output può essere un risultato stampato a schermo, oppure una finestra che ci avverte di un errore o di un'operazione avvenuta. A parità di input, l'output deve essere il medesimo.
Nel nostro algoritmo "prepara il caffè" può essere considerato output, in primis, il caffè che abbiamo preparato.