34 / 36
20
Scienze e tecnologie informatiche
In effetti, la definizione corretta e completa è la seguente.
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.
Analizziamo nel dettaglio le proprietà dell’algoritmo:
>
>
generale
: il metodo deve risolvere una classe di problemi e non un singolo
problema (ad esempio deve essere in grado di calcolare l’area di tutti i trian-
goli e non solo quella di un particolare triangolo);
>
>
finito
: le istruzioni che lo compongono ed il numero di volte che ogni azio-
ne deve essere eseguita devono essere finiti;
>
>
completo
: deve contemplare tutti i casi possibili del problema da risolvere;
>
>
non ambiguo
: ogni istruzione deve essere definita in modo preciso ed uni-
voco, senza alcuna ambiguità sul significato dell’operazione;
>
>
eseguibile
: deve esistere un agente di calcolo in grado di eseguire ogni
istruzione in un tempo finito.
Dato un problema, quindi, si cercherà di trovare un algoritmo che lo risolva; se
tale algoritmo perviene alla soluzione del problema si dirà corretto, se inoltre
la soluzione è raggiunta anche nel modo più breve possibile si dirà efficiente.
Gli algoritmi possono venire classificati secondo la seguente suddivisione:
>
>
algoritmi
deterministici
;
>
>
algoritmi
non deterministici
.
Un algoritmo si dirà
deterministico
se per ogni istruzione esiste, a parità di
dati d’ingresso, un solo passo successivo; in pratica esiste uno e un solo pos-
sibile percorso dell’algoritmo, quindi a fronte degli stessi dati di partenza si
produrranno sempre gli stessi risultati.
È
non deterministico
l’algoritmo che contiene almeno un’istruzione che am-
mette più passi successivi che hanno la possibilità di essere scelti: l’algoritmo
potrà produrre risultati diversi a partire da uno stesso insieme di dati com-
piendo percorsi diversi; tra gli algoritmi non deterministici troviamo quelli
probabilistici, nei quali almeno un’istruzione ammette più passi successivi,
ognuno dei quali ha una certa probabilità di essere scelto.
1.4.2
La programmazione strutturata
La programmazione strutturata rappresenta una tappa fondamentale dell’e-
voluzione della cosiddetta
programmazione mainstream
, ovvero di quella
sequenza di paradigmi che, nel corso degli anni, l’uno succedendo all’altro,