Algoritmi e strutture dati.

Alcune delle proprietà importanti di cui deve godere un algoritmo sono:
 

1. Finitezza: il numero delle istruzioni di cui si compone l' algoritmo deve essere finito. P. es. un algoritmo la cui soluzione dipenda dall' esistenza di una determinata sequenza di cifre nella rappresentazione decimale di pi greco potrebbe richiedere l' esecuzione di un numero infinito di passi se la sequenza non apparisse.
2. Definitezza: ogni istruzione deve essere non ambigua. Questa richiesta non implica solo che le istruzioni devono essere espresse chiaramente ma anche che il pssaggio da un' istruzione alla successiva deve avvenire in modo esplicitamente previsto dall' algoritmo.
3. Effettuabilità: deve esistere un agente di calcolo in grado di eseguire ogni istruzione in un tempo finito. È chiaro che un algoritmo il cui tempo di esecuzione sia estremamente lungo su scala umana è di scarso interesse pratico.
4. Risolutività: deve produrre un output che consista nella soluzione del problema o nella diagnostica sulla mancata soluzione. Non sempre un algoritmo puo' produrre un risultato. Tuttavia richiediamo che fornisca sempre un output, sia pure sotto forma di comunicazione della mancata soluzione.

Ogni algoritmo opera su dati. Alcuni dei dati possono essere forniti in ingresso all' algoritmo stesso. I risultati dell' algoritmo possono essere considerati dei dati in uscita.

Tra i dati su cui opera un algoritmo possono sussistere delle relazioni logiche che costruiscono "strutturazioni" tra i dati stessi. Per esempio, se considero i dati eterogenei corrispondenti a nome, cognome, data di nascita, immagine digitalizzata di una persona, potrei considerare un "dato" costituito dall' insieme dei  due campi  alfabetici, uno alfa-numerico ed uno per la sequenza di bits corrispondente all' immagine digitalizzata. Oppure per i dati alfabetici corrispondenti ai nomi delle persone che arrivano ad uno sportello, possiamo considerare la strutturazione rappresentata dall' ordine di arrivo nella coda.

La definizione delle strutture logiche presenti tra i dati, corrisponde all' introduzione di strutture dati astratte nell 'algoritmo.

La connessione tra algoritmi e strutture dati è estremamente stretta: strutture dati diverse richiedono in genere algoritmi diversi e la scelta della struttura dati piu' adeguata puo' essere estremamente importante per l' efficienza di un algoritmo.

In fase di programmazione, all' algoritmo corrisponderà il programma concreto nel linguaggio di alto livello utilizzato.
Alle strutture dati astratte corrisponderanno le strutture dati concrete del linguaggio in questione secondo il seguente schema:
 
 

Algoritmo	Programma
Strutture dati astratte	Strutture dati concrete

Le strutture dati astratte possono essere implementate direttamente dai tipi primitivi di un linguaggio di alto livello oppure possono richiedere l' implementazione mediante questi ultimi.

Per esempio, la struttura corrispondente ai numeri complessi, potrebbe essere già presente in un linguaggio (come nel fortran) oppure potrebbe essere implementata  a partire da altri tipi primitivi.

Cerchiamo di vedere meglio la relazione tra questi concetti approfondendo l' esempio dei numeri complessi.
Supponiamo di voler descrivere l' algoritmo per il prodotto di due numeri complessi.

Sappiamo dall' analisi che possiamo rappresentare  un qualsiasi numero complesso z mediante una coppia ordinata di numeri reali (a,b) .
In questa rappresentazione, la moltiplicazione di due numeri complessi  z=(a,b)  e  w=(c,d)  e' definita come l' applicazione da CxC in C che alla coppia di numeri complessi z e w associa il numero complesso  t=(ac-bd,ad+bc).

Quindi, se utilizziamo la struttura dati astratta coppia ordinata di numeri reali per  rappresentare i complessi, l' algoritmo risultante coincide con la formula su data per t, supponendo di avere un agente di calcolo in grado di eseguire l' aritmetica dei reali.

Supponiamo adesso di avere un linguaggio (p.es. il fortran) che possiede una struttura dati concreta  complex  per la rappresentazione dei numeri complessi  (in realtà, per rappresentarne un sottoinsieme finito, a causa delle ovvie  limitazioni dell' aritmetica dei computers).

Un programma che implementi l' algoritmo della moltiplicazione che stiamo discutendo, si limiterà a definire due variabili (z e w) come appartenenti al tipo dati  complex  e potrà far riferimento alla sintassi di quel tipo dati per implementare in modo trasparente l' operazione:

...
complex ::  t,w,z
...
t = z * w
...

Se invece abbiamo un linguaggio di programmazione che manca di una struttura dati predefinita per i complessi (p.es. il linguaggio C nel vecchio standard dell' 1989),
occorrerà  utilizzare un tipo dati esistente (p.es. una struttura C) ed implementare l' algoritmo mediante opportuni costrutti del linguaggio (p.es. attraverso una function):

...
typedef struct {
       float real,imag;
               } complex;  /* definizione del nuovo tipo dati */

/* definizione della function che implementa l' algoritmo di moltiplicazione */

complex cmplx_mul( complex a, complex b)
{
   complex t;
   t.real = a.real*b.real - a.imag*b.imag;
   t.imag = a.real*b.imag + a.imag*b.real;
   return (t);
}

/* esempio di utilizzo */
...
int main()
{
   complex t, w, z;
...

  t = cmplx_mul(z,w); 
...