Pillole 2.0 – Algoritmo e Teorema di Böhm-Jacopini

La risoluzione dei problemi con l’ausilio dei computer è un processo che richiede un’analisi attenta, una pianificazione accurata e coerenza logica. Implica l’esecuzione di un insieme di istruzioni esplicite e non ambigue, espresse in un linguaggio di programmazione, il programma.

Concetto di Algoritmo

Questo insieme di istruzioni molto semplici è un esempio di algoritmo; quindi, un algoritmo è una sequenza di istruzioni perfettamente comprensibili ed eseguibili tali che, se eseguite in un ordine specificato e determinato, permettono la soluzione di un problema in un numero finito di passi.

Un algoritmo può essere rappresentato in modi diversi:

  1. con un linguaggio testuale, che può essere di vari tipi:
    – linguaggio di programmazione (Pascal, Java, C++, etc.);
    – linguaggio naturale (inglese, italiano);
    – pseudocodice (descrive a parole il compito svolto dall’algoritmo)
  2. con un linguaggio grafico (schema di flusso – Flow Chart), costituito da simboli grafici che rappresentano entità logiche diverse in relazione alla forma e consentono di rappresentare le azioni mediante composizione dei vari simboli secondo i differenti modelli logici.

Gli schemi di composizione si suddividono in tre tipi:

  1. Sequenza : le istruzioni sono eseguite secondo l’ordine in cui sono scritte;
  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;
  3. Iterazione : consente la ripetizione di un blocco di istruzioni, per un certo numero di volte, definito a seconda dell’obiettivo da raggiungere.
Selezione, Condizione, Iterazione

Teorema di Böhm-Jacopini

Il teorema di Böhm-Jacopini, enunciato nel 1966 da due informatici italiani 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“.

In altre parole, ciascun algoritmo può essere realizzato utilizzando soltanto le tre strutture indicate.

chip

Visite: 1878