130-131 B2 Le basi della programmazione

PROBLEMI E ALGORITMI

3. L’algoritmo

Un procedimento risolutivo è un algoritmo quando, fissato l’insieme finito delle azioni elementari univocamente interpretabili e definite, è possibile descrivere passo per passo il procedimento che risolve un problema costruendo una successione ordinata e finita di istruzioni la cui esecuzione si arresta per fornire i risultati di un problema a partire da ogni valore assunto dai dati iniziali.

Esistono algoritmi che non si arrestano e sono pur sempre algoritmi.

Un algoritmo deve essere:

• finito: la strategia risolutiva descritta dall’algoritmo deve essere composta da un numero finito di azioni elementari. L’algorimo, inoltre, deve prevedere un solo inizio e una sola fine; univoco o non ambiguo o preciso: ogni azione deve essere definita nei suoi effetti rigorosamente e senza ambiguità per l’esecutore;
• generale: deve essere valido non solo per un particolare problema, ma per tutti i problemi di una stessa classe;
• completo: deve considerare tutti i casi possibili che si possono verificare durante l’esecuzione e, per ogni caso, indicare la soluzione da seguire;
• osservabile nei risultati: nell’esempio del problema “cucinare la pasta” ottengo della pasta da mangiare;
• deterministico: a ogni unità finita di tempo l’esecutore deve scegliere e compiere una e una sola azione. Si dice anche che, partendo dagli stessi dati iniziali, l’esecuzione dell’algoritmo deve fornire sempre gli stessi risultati finali.

Il parametro che consente di scegliere una strategia, e quindi un algoritmo, rispetto a un’altra è l’efficienza.

Un algoritmo si dice efficiente quando:

• è corretto, cioè produce il risultato atteso;
• è veloce in termini di tempo impiegato per produrre il risultato;
• è parsimonioso экономично  in termini di risorse allocate выделенные per produrre il risultato.