Il più importante teorema sulla teoria degli algoritmi!
Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari, chiari e non ambigui. (Wikipedia)
In informatica, risolvere un problema vuol dire ricevere dei dati in
input, eseguire una elaborazione e, in un tempo finito, restituire
dei dati in output.
Input → Elaborazione → Output
Nel 1966 due informatici italiani hanno
enunciato il seguente teorema: Un qualsiasi algoritmo può essere
espresso usando esclusivamente le strutture di sequenza, di
alternativa e di ripetizione.
Un algoritmo ha sempre un inizio e una fine per definizione. Per il teorema di Böhm-Jacopini un algoritmo avrà solo:
| SEQUENZA | ALTERNATIVA | RIPETIZIONE |
|---|---|---|
| Istruzione 1 Istruzione 2 Istruzione 3 Istruzione 4 |
SE condizione allora Istruzione 1 altrimenti Istruzione 2 Fine SE |
RIPETI Istruzione 1 Fine RIPETI 5 |
Avremo dei problemi risolvibili con algoritmi contenenti
solo istruzioni in sequenza. Ad esempio la somma di due numeri.
Alcuni problemi per essere risolti hanno bisogno di
sequenza e del blocco di alternativa (o selezione o struttura
condizionale). Ad esempio il confronto fra due numeri.
Alcuni problemi per essere risolti hanno bisogno di
sequenza e ripetizione. Ad esempio la somma di 10 numeri.
Data una traccia di un problema
individuare per
prima cosa INPUT e OUTPUT
individuare eventuali istruzioni di
elaborazione
individuare SE oppure RIPETIZIONI.
Primi concetti sugli algoritmi.
Introduzione all'impostazione dei primi algoritmi tramite flow chart
Il più importante teorema sulla teoria degli algoritmi!
Introduzione ai linguaggi di programmazione
