Informatica – Concetto di Algoritmo e Teorema di Böhm-Jacopini

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).
<div>Icons made by <a href="https://smashicons.com/" title="Smashicons">Smashicons</a> from <a href="https://www.flaticon.com/" title="Flaticon">www.flaticon.com</a></div>

Visite: 248

Pagine: 1 2 3