Sommario
- Strutture di controllo
- Programmazione strutturata
- Sequenza di istruzioni
- Strutture di selezione
- If-then
- If-then-else
- Selezione a più vie (case)
- Strutture iterative
- A condizione finale
- A condizione iniziale
- Ciclo a conteggio
Strutture di controllo
- In un algoritmo sono normalmente presenti passi decisionali che servono a controllare la particolare sequenza dinamica che deve essere eseguita dall’esecutore per risolvere uno specifico caso di ingresso.
- Si può dimostrare che per descrivere qualunque algoritmo sono sufficienti solo due tipologie di passi decisionali a cui corrispondono nel linguaggio di programmazione due tipi di istruzioni: l’istruzione di selezione e l’istruzione iterativa.
Tassonomia delle istruzioni
- Istruzioni semplici
- Rappresentano azioni elementari del programma.
- Istruzioni strutturate
- Sono composte da azioni organizzate in strutture.
- Le azioni componenti possono essere istruzioni semplici o istruzioni a loro volta strutturate.
Blocco di istruzioni
NOTE
- Dopo un blocco non occorre il punto e virgola (esso termina le istruzioni semplici, non separa istruzioni).
- Il campo d’azione delle
che compaiono entro il blocco è il blocco stesso. - I blocchi possono essere innestati.
Programmazione strutturata
Si parla di programmazione strutturata se si utilizzano solo le seguenti strutture per alterare il flusso di controllo [Dijkstra, 1969]:
- Sequenza
- Selezione
- Iterazione
In questo modo è possibile scrivere un programma come una sequenza di istruzioni o blocchi di istruzioni più o meno complesse, in modo che ciascun blocco di istruzioni preveda un solo ingresso e una sola uscita.
Risorse in rete:
Archivio sulla vita e le opere di Edsger Wybe Dijkstra sul sito dell’Università di Austin, Texas
Letture:
Equivalenza funzionale di programmi
Due programmi si dicono funzionalmente equivalenti se, sottoposti ad un qualsiasi insieme di dati d’ingresso, entrambi terminano producendo gli stessi dati d’uscita o entrambi non terminano.
Insiemi funzionalmente completi
Un insieme S di istruzioni strutturate è funzionalmente completo se, per ogni programma P in un linguaggio L, ne esiste uno funzionalmente equivalente che usa solo le istruzioni strutturate di S.
Teorema di Böhm -Jacopini
L’insieme S costituito dalle strutture
- Sequenza (composizione)
- Selezione
- Iterazione
È un insieme funzionalmente completo.
In altre parole:
L’uso delle strutture di controllo ci consente di
- Scrivere programmi strutturati, facilmente leggibili e modificabili.
- Evitare l’uso della programmazione a salti (go to).
Risorse in rete:
Diagramma di flusso
Il comportamento delle istruzioni per il controllo della sequenza dinamica può essere descritto graficamente attraverso un diagramma di flusso:
- Le condizioni sono rappresentate da rombi.
- Le istruzioni sono rappresentate da rettangoli.
- Le linee orientate collegano gli elementi grafici per indicare l’ordine seguito dall’esecutore.
Sequenza di istruzioni
- Permette di eseguire le istruzioni secondo l’ordine sequenziale in cui sono scritte.
- È composta da istruzioni semplici e/o strutturate.
- È individuata da un delimitatore di inizio e da uno di fine sequenza (blocco).
- Le istruzioni componenti vengono eseguite come se si trattasse di un’istruzione unica.
Esempio:
{
a=3;
a=a+b;
}
Struttura di selezione: if-then-else
Q, S1, S2 rappresentano sequenze di istruzioni, R rappresenta una condizione logica da valutare.
L’esecuzione di un’istruzione di selezione di tipo if-then-else produce nell’ordine:
- La valutazione della condizione.
- L’esecuzione della parte-then se il valore logico della condizione è “vero” oppure l’esecuzione della parte-else se il valore logico della condizione è “falso”.
Struttura di selezione: if-then
Q e S rappresentano sequenze di istruzioni. R rappresenta una condizione logica da valutare.
In questo caso la parte “else” è vuota.
Istruzione vuota: non produce alcun effetto.
if-then-else annidati
La parte-then e la parte-else possono a loro volta contenere istruzioni di selezione dando luogo a scelte in cascata che permettono di descrivere algoritmi che devono operare una scelta tra più di due alternative.
Una volta che una condizione risulta verificata, le rimanenti istruzioni sono saltate.
Indentazioni profonde non sono molto usate in pratica.
Struttura di selezione: case
case e
val1: S1;
val2: S2;
…;
valn: Sn
end
L’esecuzione di un’istruzione di tipo case produce nell’ordine:
- La valutazione della espressione.
- L’esecuzione della sequenza di istruzioni etichettata mediante il valore assunto dall’espressione.
Osservazione
Nella struttura case l’espressione che viene valutata deve assumere valori in un insieme discreto.
Una selezione multipla si può implementare anche mediante più costrutti if-then in sequenza o con più costrutti if-then-else innestati (ma le tre figure non sono equivalenti).
Struttura di iterazione: ciclo a condizione iniziale
S è detta “corpo” dell’istruzione iterativa
- L’esecuzione di un’istruzione di iterativa a condizione iniziale di tipo while-do produce nell’ordine:
- La valutazione della condizione.
- Il termine dell’istruzione se il valore logico calcolato è “falso” oppure l’esecuzione del corpo e la ripetizione del punto 1 se il valore logico calcolato è “vero”.
Struttura di iterazione: ciclo a condizione finale
- L’esecuzione di un’istruzione di iterativa a condizione finale di tipo repeat –until produce nell’ordine:
- L’esecuzione del corpo.
- La valutazione della condizione.
- Il termine dell’istruzione se il valore logico calcolato è vero oppure la ripetizione dei punti 1 e 2 se il valore logico calcolato è falso.
Struttura di iterazione: ciclo a conteggio
- c è una variabile che rappresenta il “contatore”ed assume valori in un intervallo discreto.
- vi è il suo valore iniziale;
- vf il suo valore finale;
- succ(c) è una funzione che fornisce il valore.
- Successivo di c in funzione del passo k.
- Il passo k può anche essere negativo.
E’ necessario specificare:
- L’inizinializzazione del contatore.
- L’incremento del contatore.
- Il controllo di fine ciclo.
Prossima lezione
Esempi
- Semplici programmi con l’utilizzo di:
- Istruzioni semplici.
- Istruzioni strutturate.
Le lezioni del Corso
2. Introduzione al modello di von Neumann
5. Informazione, Elaborazione e Algoritmo
6. Elementi di Architettura: Struttura di un sistema di elaborazione
7. Elementi di Architettura: Memorie, Unità di ingresso e uscita
9. Programmazione - Tipi semplici, Variabili e Costanti
10. Programmazione: Istruzioni semplici
11. Programmazione , Programmazione Strutturata, Istruzioni Strutturate
12. Programmazione - Semplici Esercizi Svolti in C++
13. Programmazione - Metodologia di sviluppo per raffinamenti successivi
I materiali di supporto della lezione
C. Boehm and G. Jacopini. Flow diagrams, turing machines and languages with only two formation rules. Communications of the ACM, pages 366–371, May 1966
Fadini, C. Savy, Fondamenti di Informatica I, Napoli, Liguori Ed., 1997, Parte 2, cap. V.
