• Autore: Antonio Guadagno
• Fonte: Seneta.it

Teorema di Böhm-Jacopini

Questo teorema ha un interesse essenzialmente teorico, in quanto i linguaggi di programmazione tendono ormai a dotarsi di istruzioni più complesse per evitare che i programmatori debbano occuparsi di istruzioni dispersive; in ogni caso, la sua attualità sta nel determinare strategie di programmazione “lineari, abolendo l’uso in passato delle istruzioni di salto incondizionato.

Il teorema di Böhm-Jacopini, enunciato nel 1966 da due informatici italiani, Corrado Böhm e Giuseppe Jacopini, dai quale prende il nome, afferma che:
"qualunque algoritmo può essere implementato utilizzando tre sole strutture, la sequenza, la selezione e il ciclo, da applicare ricorsivamente alla composizione di istruzioni elementari".

Gli schemi di composizione si suddividono quindi in tre tipi:

1. Sequenza : le istruzioni sono eseguite secondo l’ordine in cui sono scritte; possono essere di tre tipi: lettura, scrittura, assegnazione.
2. Selezione o Condizione : esiste una condizione da valutare e due possibili gruppi di istruzioni da eseguire; in funzione del valore della condizione, si sceglie un blocco oppure l’altro; per rappresentare la struttura condizionale, i linguaggi di programmazione usano la parole-chiave if, che può essere seguita da else («altrimenti») e da un end if.
3. Iterazione : consente la ripetizione di un blocco di istruzioni, per un certo numero di volte, definito a seconda dell’obiettivo da raggiungere; quando si vuole iterare per un numero prestabilito di volte, si usa il ciclo di tipo for, in cui una variabile intera (Chiamata generalmente contatore) viene incrementata di una unità a ogni iterazione. Quando invece il numero di iterazioni non è noto a priori, si usa il ciclo di tipo while (controllo in testa) oppure il ciclo di tipo do (controllo in coda).

Visite: 808

Dispense Scolastiche, Dispense Scolastiche: Informatica, Pillole 2.0, Tecnologia

algoritmi, Coding, Informatica, Seneta.it