Cos'è un algoritmo
Un algoritmo è un insieme di istruzioni che, eseguite in ordine, portano alla soluzione di un problema. È la "ricetta" che trasforma i dati di partenza nel risultato voluto.
Le proprietà
Non basta una sequenza qualsiasi di passi: perché sia un vero algoritmo, deve rispettare alcune proprietà.
- Finitezza: deve terminare dopo un numero finito di passi (niente cicli infiniti).
- Non ambiguità (determinismo): ogni istruzione deve essere chiara e interpretabile in un solo modo.
- Eseguibilità: ogni passo deve essere realmente realizzabile da chi esegue (l'elaboratore).
- Generalità: deve risolvere un'intera classe di problemi, non un solo caso specifico.
- Input e output: parte da zero o più dati in ingresso e produce almeno un risultato.
I tre costrutti
Qualunque algoritmo, per quanto complesso, si costruisce combinando solo tre costrutti fondamentali. È un risultato sorprendente ma dimostrato (teorema di Böhm-Jacopini).
1 · Sequenza
Le istruzioni vengono eseguite una dopo l'altra, nell'ordine in cui sono scritte. È il costrutto più semplice.
2 · Selezione
Si verifica una condizione booleana (vera o falsa) e, in base al risultato, si esegue il ramo vero oppure il ramo falso. È la capacità di "decidere".
3 · Iterazione
Un blocco di istruzioni (il corpo del ciclo) viene ripetuto finché una condizione resta vera. È ciò che permette di non riscrivere mille volte lo stesso codice.