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