Teorema di Bohm e Jacopini

(1)

Elementi di Informatica Prof. G.A. Di Lucca - Univ. del Sannio

1

Riepilogo strutture di controllo

default

c1 c2

…

cn

Teorema di Corrado Bohm e Giuseppe Jacopini [1966]

“qualunque algoritmo può essere implementato utilizzando tre sole strutture: la sequenza, la selezione e il ciclo, da applicare

ricorsivamente alla composizione di istruzioni elementari”.

Ovvero, qualsiasi algoritmo può essere definito usando solo tre differenti tipologie di strutture di controllo:

- una struttura di sequenza - una (sola) struttura di selezione - una (sola) struttura di ciclo

Teorema di Bohm e Jacopini

Ad es.

la sequenza

solo la struttura if … then per la selezione solo la struttura while per i cicli

… problema: quante e quali “strutture di controllo” sono effettivamente necessarie per descrivere un qualsiasi tipo di algoritmo?

(2)

3

Nella Programmazione strutturata è ammesso solo l’utilizzo di strutture di controllo one-in/one-out

Non è ammesso ‘entrare’ nella struttura o ‘uscire’ dalla stessa da punti diversi da quelli di in e di out

Una struttura di controllo può seguirne un’altra collegando il punto di out della prima a quello di in della seconda; in tal caso le strutture sono dette ‘in sequenza’

Una struttura di controllo può essere contenuta totalmente in un’altra ed in tal caso le strutture sono dette ‘innestate’

Le strutture di controllo non devono mai “intersecarsi”

Le strutture di controllo sono i “mattoncini” con cui costruire i programmi

La Programmazione strutturata

4

… do S0 while (C0);

S1

if (C1) then S2 else

S3 endif

… Esempio:

Strutture in sequenza

vero falso S0

C0

S2 C1 S3

S1

S4 punto di in do while

punto di out do while punto di in S1

Punto di out S1 punto di in if … else

punto di out if … else punto di in S4

(3)

5

… do S0 while (C0);

S1

if (C1) then S2 else

S3 endif

… Esempio:

Strutture in sequenza

punto di in do while

punto di out do while punto di in S1

Punto di out S1 punto di in if … else

punto di out if … else punto di in S4

S4

vero falso S0

C0

S2 C1 S3

S1

if(C0) then

if(C1) then S1 else S2 endif

else

if(C2) then S3 else S4 endif

endif Esempio:

Strutture innestate

Ciascuna struttura di controllo di selezione a due vie è totalmente contenuta in quella più esterna

C0

C1

S1 S2

C2

S3 S4

vero falso

(4)

7

Esempio di flusso di controllo di un programma non strutturato

S2

C1

S3 S4 S5 S6

S8 S7 vero

falso

S1 Il flusso di controllo non è strutturato:

presenza di strutture NON one-in/one-out

La freccia da S6 a S2 implica un ciclo (che però è di difficile individuazione), e la freccia da S3 a S7 rappresenta l’uscita da tale ciclo

La struttura di selezione con condizione C1 ha due punti di uscita su due diverse istruzioni

(evidenziati con i due cerchietti rossi)

Il ramo ‘falso’ dopo l’istruzione S6 ‘torna’ a S2 Il ramo vero dopo l’istruzione S3 va alla istruzione S7

8

Istruzioni implicanti forme NON strutturate di un programma

Istruzione di salto incondizionato goto goto <label>

dove label è una etichetta che individua una istruzione nel codice.

L’istruzione goto provoca il trasferimento incondizionato del flusso di controllo del programma all’istruzione identificata da label, saltando tutte le altre istruzioni comprese tra quella di goto e quella con la label indicata

E’ la principale fonte di non strutturazione dei programmi: il suo uso rende i programmi poco comprensibili, poco testabili e poco

manutenibili

NON DEVE MAI ESSERE USATA

si può evitare il suo uso usando opportunamente le strutture di controllo

(5)

9

#include <stdio.h>

main()

{int count = 1;

start: /* label */

if (count > 10) goto end;

printf("%d ", count);

count++;

goto start;

end: /* label */

printf("%d\n", count);

}

Notare come start: , end: e goto sono usate generando strutture NON 1-in/1out

Esempio di programma non strutturato con ‘goto’

start

count > 10

goto end printf count++

goto start

printf end vero

falso count = 1

l’istruzione “goto start” implica un ciclo (che però è di difficile individuazione), e l’istruzione “goto end” rappresenta l’uscita da tale ciclo

Esempio di programma non strutturato con ‘goto’

start

count > 10

goto end printf ++count goto start

falso

count = 1 Il flusso di controllo non è strutturato:

presenza di strutture NON one-in/one-out La struttura if ha due punti di uscita su due diverse istruzioni (evidenziati con i due cerchietti rossi)

Il ramo ‘falso’ va all’istruzione printf Il ramo vero (‘goto end’ ) va alla label end

… il tutto per implementare un ciclo a condizione iniziale … (o finale) … !!!

(6)

11

main() {

int count = 1;

while(count <= 10)

{ printf("%d ", count);

count++;

}

Il programma in forma strutturata

(con ciclo a condizione iniziale)

… one in / one out …

… molto più semplice e comprensibile !!!

count<= 10

printf (…) count++

printf vero falso

count=1

12

main() {

int count = 1;

do

count++;

}

while(count <= 10) printf("%d\n", count);

}

Il programma in forma strutturata

(con ciclo a condizione finale)

… molto più semplice e comprensibile !!!

count<= 10

printf

vero falso

count=1

(7)

13

Confronto tra forma NON strutturata e strutturata

/* Using goto */

main()

{int count = 1;

start: /* label */

if (count > 10) goto end;

printf("%d ", count);

count++;

goto start;

end: /* label */

}

In forma NON strutturato

main() {

int count = 1;

while(count <= 10)

count++;

}

… molto più lineare e comprensibile !!!

In forma strutturata Con ciclo while

Confronto tra forma NON strutturata e strutturata

In forma strutturata Con ciclo while

count<= 10 printf (…)

count++

printf vero falso In forma NON strutturata

start count> 10

(8)

15

Confronto tra forma NON strutturata e strutturata

In forma NON strutturata

start count> 10

count<= 10

printf

vero falso

count=1

In forma strutturata Con ciclo do- while

16

Altre istruzioni implicanti forme NON strutturate

Istruzioni che possono essere usate all’interno di strutture cicliche per alterarne il flusso di controllo:

• break

provoca l’uscita immediata da una struttura, in particolare da un ciclo

• continue

fa riportare il flusso di controllo immediatamente all’inizio del ciclo che la contiene senza che le istruzioni che la seguono siano eseguite

(9)

17

main()

{int cont;

for (cont = 1; cont <= 10; cont++) { if (cont == 5)

break; /* termina il ciclo se cont == 5 */

printf("%d ", cont);

}

printf("\n Ciclo interrotto per cont == %d\n", cont);

}

… esce anticipatamente dal ciclo quando cont = 5 …

… ovvero è eseguito solo 5 volte invece che 10 come indicato nella definizione del for stesso …

… la stampa del valore di cont è eseguita fino a quando cont = 4

Esempio di uso dell’istruzione breakin una struttura for

cont=1

cont++

cont<=10 vero

falso

printf("%d\n",cont)

printf(” Ciclo interrotto

….”) cont==5 falso

break vero

main()

{int cont;

for (cont=1;cont<=10; cont++) {

if (cont == 5) break; /* interrompe il ciclo se

cont == 5 */

}

printf("\n Ciclo interrotto per cont == %d\n", cont);

}

Esempio di uso dell’istruzione breakin una struttura for NON strutturata

Due punti di uscita dal ciclo for !!!

… one in / two outs !!???

(10)

19

main()

{int cont;

for (cont = 1; cont < 5; cont++) printf("%d ", cont++);

printf("\n Ciclo strutturato bene");

}

… one in / one out !!

cont=1

cont++

cont<5 vero

falso

printf("\n Ciclo strutturato bene")

Si può ottenere lo stesso risultato cosa senzabreak strutturando opportunamente …

… basta far eseguire il ciclo for solo 4 volte …

20

main()

{int cont;

for (cont = 1; cont < 5; cont++) printf("%d ", cont++);

printf("\n Ciclo strutturato bene");

}

Confronto tra forma NON strutturata e strutturata

main()

{int cont;

for(cont=1;cont<=10;cont++) {if (cont == 5)

break; /*interrompe il ciclo se cont=5 */

}

printf("\n Ciclo interrotto per cont == %d\n", cont);

}

In forma strutturata

(11)

21

cont=1

cont++

cont<5 vero

falso

printf("\n Ciclo strutturato bene")

Confronto tra forma NON strutturata e strutturata

cont=1

cont++

cont<=10 vero

falso

printf(” Ciclo interrotto ….”) cont==5

falso

break vero

main() {int x;

for (x = 1; x <= 10; x++) {

if (x == 5)

continue; /* salta le successive istruzioni tornando all’inizio del ciclo se x == 5 */

printf("%d ", x);

}

printf("\n Uso di continue per saltare la stampa del valore 5\n");

}

Esempio di Uso dell’istruzione continuein un for in forma NON struturata

… stampa i valori di x tranne che per x = 5

(12)

23

main() {

int x;

for (x = 1; x <= 10; x++) {

if (x == 5)

continue;

/* salta le successive istruzioni tornando all’inizio del ciclo se x == 5 */

printf("%d ", x);

}

printf("\n Uso di continue per saltare la stampa del valore 5\n");

}

Uso dell’istruzione continuein una struttura for x=1

x++

x<=10

vero

falso

printf("%d\n",x)

printf(” Uso di continue ….”)

x==5

falso

continue

vero x++

Due punti di ritorno al ciclo for !!!

… two ins / one out !!??

24

main() {int x;

for (x = 1;x <= 10;x++) { if (x != 5)

printf("%d ", x);

}

printf("\n salta la stampa del valore 5\n");

}

Si può ottenere lo stesso risultato senza usarecontinue strutturando opportunamente ….

x=1

x++

x<=10

vero

falso

printf(” salta la ….”)

x!=5

falso vero

(13)

25

Confronto tra forma NON strutturata e strutturata

main() {int x;

for (x = 1; x <= 10; x++) {if (x == 5)

continue;

/*salta le successive istruzioni tornando all’inizio del ciclo se x == 5 */

printf("%d ", x);

}

printf("\n Uso di continue per saltare la stampa del valore 5\n");

}

main() {int x;

for (x = 1;x <= 10;x++) { if (x != 5)

printf("%d ", x);

}

printf("\n salta la stampa del valore 5\n");

}

Confronto tra forma NON strutturata e strutturata

x=1

x++

x<=10

vero

falso

printf(” salta la ….”)

x!=5 ^falso

vero

x=1

x++

x<=10

vero

falso

printf(” Uso di continue ….”)

x==5

falso

continue vero

x++

(14)

27

main() {int i;

for (i = 1; i <= 10; i++) { ...

i = ...; /* è modificato il valore dell’indice di controlo del ciclo for: NON è più un ciclo a conteggio */

...

} ...

}

Altri tipi di forme NON strutturate da evitare

… nel corpo del ciclo non va modificato artatamente il valore dell’indice di controllo (usato per contare il numero predefinito dei passi del ciclo for)

28

main()

{int i, a=5;

for (i = 1; i <= a; i++) { ...

a = ...; /* è modificato il valore di una

variabile usata per controllare il ciclo for: NON è più un ciclo a conteggio */

...

} ...

}

… nel corpo del ciclo non vanno modificati artatamente i valori delle variabili usate per controllare il numero predefinito dei passi del ciclo for

(15)

29

main()

{int i, a=5;

i = 1;

while (i <= a) { ...

a = ...;

i++;

} ...

}

… in entrambi i casi visti prima va usato un ciclo while anziché un ciclo for

main() {int i;

i = 1;

while(i <= 10) { ...

i = ...;

...

} ...

}

Istruzioni NON strutturate

L’uso delle istruzioni NON Strutturate:

goto <label>

continue break

va sempre evitato ed in particolare l’istruzione goto <label>

NON

DEVE MAI ESSERE USATA

Inoltre non vanno mai modificati i valori delle variabili usate per controllare un ciclo for all’interno del corpo del ciclo stesso

E’ sempre possibile scrivere programmi strutturati usando opportunamente le strutture di controllo