Algoritmica

L’algoritmica è la disciplina che studia la progettazione, l’analisi e l’implementazione di algoritmi.

1 - Gli algoritmi

Definizione: algoritmo

Un algoritmo è la specificazione di una sequenza finita di operazioni (dette anche istruzioni) che consente di risolvere tutti i quesiti di una stessa classe, ognuno dei quali viene detto istanza del problema, o di calcolare il risultato di un’espressione matematica.

Un algoritmo, per essere considerato tale, deve essere:

• Finito: costituito da un numero finito di istruzioni e deve sempre terminare.
• Deterministico: partendo dagli stessi dati in ingresso, si devono ottenere i medesimi risultati.
• Non ambiguo: le operazioni non devono poter essere interpretate in modi differenti.
• Generale: applicabile a tutte le istanze del problema computazionale che si intende risolva.

Esempio: algoritmo dell'addizione in colonna

Quella dell’addizione in colonna è una sequenza finita di istruzioni che tutti conoscono e che, in realtà, è un vero e proprio algoritmo, usato per la somma di due numeri o più numeri. Ecco una possibile descrizione dell’algoritmo, usando come esempio la somma $712+2609+431$:

1. Scrivere i numeri da sommare uno sotto l’altro, separando le singole cifre e allineando le cifre per colonna (unità sotto unità, decine sotto decine, centinaia sotto centinaia, ecc.).

$$\begin{array}{ccccc}& 7& 1& 2& +\\ 2& 6& 0& 9& +\\ & 4& 3& 1& =\end{array}$$

2. Sommare le cifre nella colonna delle unità:
   • Se la somma è inferiore a $10$, scrivere il risultato sotto la colonna.
   • Se la somma è $10$ o maggiore, scrivere sotto la colonna delle unità la cifra delle unità della somma e “riportare” la decina in cima alla colonna delle decine.

$$\begin{array}{ccccc}& & {}_1& & \\ & 7& 1& 2& +\\ 2& 6& 0& 9& +\\ & 4& 3& 1& =\\ & & & 2& \end{array}$$

3. Sommare le cifre nella colonna delle decine, inclusa quella dell’eventuale riporto presente in cima alla colonna ed effettuare nuovamente il riporto se il risultato dovesse essere maggiore o uguale a $10$.

$$\begin{array}{ccccc}& & {}_1& & \\ & 7& 1& 2& +\\ 2& 6& 0& 9& +\\ & 4& 3& 1& =\\ & & 5& 2& \end{array}$$

4. Ripetere lo stesso procedimento anche per le colonne delle centinaia e delle migliaia.

$$\begin{array}{ccccc}{}_1& & {}_1& & \\ & 7& 1& 2& +\\ 2& 6& 0& 9& +\\ & 4& 3& 1& =\\ 3& 7& 5& 2& \end{array}$$

5. Il risultato finale dell’addizione è quello riportato nella riga in basso.

Osservazione: un algoritmo non è necessariamente matematico

Dal momento che l’algoritmo è semplicemente una sequenza di istruzioni da seguire per raggiungere un obiettivo, esso non deve necessariamente rappresentare una situazione matematica fatta di numeri e calcoli. Per esempio, si può descrivere un algoritmo per preparare una tazza di tè:

1. Raccogliere gli ingredienti e gli strumenti:

• tazza;
• bustina di tè;
• acqua;
• zucchero (facoltativo);
• limone (facoltativo);
• bollitore o pentola per riscaldare l’acqua.

2. Riempire il bollitore con acqua.
3. Accendere il bollitore e portare l’acqua a ebollizione.
4. Mentre l’acqua si riscalda, posizionare la bustina di tè nella tazza.
5. Quando l’acqua è bollente, versarla nella tazza sopra la bustina di tè.
6. Lasciare in infusione la bustina di tè per 3-5 minuti, a seconda dell’intensità desiderata.
7. Rimuovere la bustina di tè dalla tazza e scartarla.
8. Aggiungere zucchero o limone a piacere e mescolare bene.
9. Lasciare raffreddare un po’ e poi gustare il tè.

Si può notare come anche questa sequenza di istruzioni rispetti le condizioni per essere considerata un algoritmo: è una sequenza finita di passi (l’algoritmo termina dopo 9 passi), deterministica (usando sempre gli stessi ingredienti e lo stesso procedimento, al termine dell’algoritmo si otterrà lo stesso tipo di tè), non ambigua (le istruzioni descrivono precisamente i passi da compiere) e generale (con queste istruzioni si può preparare qualsiasi tazza di tè).

1.1 - Etimologia ed origine degli algoritmi

Il termine algoritmo deriva dalla trascrizione latina del nome del matematico persiano Muḥammad ibn Mūsā al-Khwārizmī, vissuto nel IX secolo d.C., che è considerato uno dei primi autori ad aver fatto riferimento a questo concetto scrivendo il libro Regole di ripristino e riduzione.

Le prime nozioni di algoritmo si trovano in documenti risalenti al XVII secolo a.C., conosciuti come papiri di Ahmes e noti anche come papiri di Rhind, che contengono una collezione di problemi con relativa soluzione comprendendo un problema di moltiplicazione che lo scrittore dichiara di aver copiato da altri papiri anteriori di due secoli.

2 - L’algoritmo in informatica

L’algoritmo è un concetto fondamentale dell’informatica, anzitutto perché è alla base della nozione teorica di calcolabilità: un problema è calcolabile quando è risolvibile mediante un algoritmo. Inoltre, l’algoritmo è un concetto cardine anche nella fase di programmazione dello sviluppo di un software: preso un problema da automatizzare, la programmazione costituisce essenzialmente la traduzione o codifica di un algoritmo per tale problema in programma, scritto in un certo linguaggio, che può essere quindi effettivamente eseguito da un calcolatore rappresentandone la logica di elaborazione.