Page 331 - Informatica dalla A a Z

Introduzione alla Programmazione

344
Lo studio degli algoritmi riveste il ruolo più importante nell’ambito della programma-
zione. Infatti, la comprensione di un problema e la capacità di impostare una soluzione è
condizione fondamentale per chiunque voglia avvicinarsi al mondo della “programma-
zione”. Gli algoritmi sono alla base della programmazione.

Un algoritmo è un procedimento formato da una sequenza logica di istruzioni elementari,
non ambigue che, eseguite in un ordine stabilito, consentono di trovare la soluzione di un
problema in un numero finito di passi. Questo poi deve essere tradotto in un programma

eseguibile. L’algoritmo, partendo da dei dati in ingresso, genera dei dati in uscita, come
risultato di una serie di operazioni. In particolare l’algoritmo si presenta quale una serie
finita di istruzioni, che sono elaborate da un computer, dopo essere state trasformate in
un programma attraverso l’uso di un linguaggio di programmazione.

Approfondimento: Un algoritmo è un procedimento formale che risolve un determinato
problema attraverso un numero finito di passi.

Un problema risolvibile mediante un algoritmo si dice “computabile”.

Proprietà fondamentali degli algoritmi: i passi costituenti devono essere “elementari”,

ovvero non ulteriormente scomponibili (atomicità); i passi costituenti devono essere “in-
terpretabili” in modo diretto e univoco dall’esecutore, sia esso umano o artificiale (non
ambiguità); l’algoritmo deve essere composto da un “numero finito di passi” e richiedere
una quantità finita di dati in ingresso (finitezza).

L’esecuzione deve avere termine dopo un tempo finito (terminazione); l’esecuzione deve
portare a un risultato univoco (effettività); a ogni passo, il successivo deve essere uno e
uno solo, ben determinato (determinismo). (fanno eccezione gli algoritmi randomizzati).

345
La complessità di un algoritmo si misura “asintoticamente ”.
Esistono 4 metodi per calcolare la complessità di un algoritmo: metodo di sostituzione, me-
todo dell’iterazione, metodo dell’albero e metodo dell’esperto.

344 La parola algoritmo è entrata in uso negli anni ‘50 del secolo scorso per sostituire la parola algorismo che, dal medioevo,
designava il processo di calcolare con i numeri arabi. Contrariamente a quanto molti suppongono, il suo nome deriva dal nome
di Al-Khwarizmi, un grande matematico arabo del IX secolo, famoso per avere formalizzato il sistema di numerazione posizio-
nale
usato oggi in tutto il mondo.
Le procedure che permettevano di effettuare i calcoli divennero note come algorismi o algoritmi, e lo stesso termine fu in
seguito usato per definire le procedure di calcolo necessarie ad ottenere un determinato risultato.
345 Si definisce asintotica per due motivi: poiché ogni calcolatore può implementare algoritmi in modo differente, non si può
stimare il tempo preciso; si vuole dare un’idea quantitativa di come l’algoritmo possa crescere in consumo di tempo all’aumen-
tare dell’input, per valori sempre maggiori.
327