Informatica 5 Liceo Scientifico Scienze Applicate/Algoritmi

Algoritmi

Un algoritmo e' la tecnica/procedimento utilizzato per risolvere una specifica classe di problemi ad esempio :

l'ordinamento di un vettore (BubbleSort, QuickSort),
la ricerca di un elemento in un vettore ordinato (ricerca binaria o dicotomica),
indicizzazione/ricerca dati presenti nei siti web ( motore di ricerca di Google),
compressione dei file musicali (mp3, flac, ...),
compressione immagini( gif, jpeg, ....)
crittografia a chiave asimmetrica (Algoritmo di Diffie-Hellman, Algoritmo RSA (Rivest-Shamir-Adleman)),
compressione filmati (divx, avi, ...), 
ricerca percorso minimo di un grafo (Algoritmo di Dijkstra).

Un algoritmo nell'ambito informatico e' un codice che risolve con efficienza un particolare problema, per un matematico la definizione di algoritmo e' mirata a garantire l'effettiva computabilita' del metodo

un algoritmo e' una sequenza ordinata e finita di istruzioni elementari 
che eseguita permette di ottenere un determinato risultato in un tempo finito .

La "bellezza" di un algoritmo spesso e' legata ai soli tempi di elaborazione cioe' a quanto velocemente riesce a risolvere un certo problema , in altri casi alla scelta della struttura dati utilizzata per formalizzare il problema (scelta del modello) e alla eleganza logica della tecnica risolutiva (chiarezza del codice e compattezza dello stesso).

Il termine algoritmo deriva dalla latinizzazione del nome del matematico persiano Al-Khwārizmī che scrisse un libro sulle regole per il calcolo aritmetico usando il sistema di numerazione indiano-arabo nel 12° secolo.

Vediamo un semplice algoritmo che permette di ordinare gli elementi di un vettore :

Per ordinare gli elementi di un vettore dal piu' piccolo al piu' grande si possono usare diversi algoritmi, quello piu' semplice da spiegare e' il BubbleSort e quello piu' veloce e' il QuickSort. Un algoritmo e' un particolare programma che risolve una classe di problemi (nel nostro caso l'ordinamento degli elementi di un vettore) con una certa efficienza ( generalmente espressa in termini di velocita' di calcolo).

Bubblesort

Per ordinare un vettore di n elementi bisogna fare n-1 passate, ad ogni passata l'elemento piu' piccolo rimasto nella parte di vettore ancora da ordinare viene spostato nella posizione corretta, per ordinare il vettore bastano n-1 passate perché sistemati i primi n-1 elementi anche l'ultimo numero e' per forza di cose al posto giusto. In una singola passata , pensiamo sia la passata i-esima si prendono in considerazione tutti gli elementi partendo dall'ultimo (indice n-1) fino a quello con l'indice con lo stesso numero della passata, ogni elemento considerato ad esempio quello k-esimo viene confrontato con quello che lo precede k-1-esimo e se vett[k] < vett[k-1] i due elementi del vettore si scambiano fra loro , altrimenti si passa a considerare l'elemento successivo. Facciamo un esempio , vettore di 6 elementi , passate da fare 5, nella prima passata si ha

come si vede, alla fine della prima passata il vettore e' composto da due parti una ordinata (colore verde) che contiene il numero piu' piccolo (2) e una che deve essere ancora ordinata, la seconda passata si occupa di ordinare soltanto di quest'ultima, si vede che per fare la prima passata bisogna considerare via via gli elementi in giallo con il corrispondente elemento che lo precede, sono queste coppie di valori che vengono confrontate ed eventualmente scambiate fra loro. Nella seconda passata si ha:

il vettore ordinato e' composto ora da due numeri e il vettore da ordinare e' diventato piu' piccolo, si nota che il numero di confronti che si devono fare si riduce di conseguenza di una unità ad ogni passata.Vediamo la passata 3

Vediamo la passata 4

vediamo la passata 5

si nota che durante la passata 4 non ci sono stati scambi , quando non ci sono scambi durante tutta una passata il vettore risulta ordinato e ele passate successive non sono piu' necessarie, in questa spiegazione e nel programma seguente non utilizzeremo questa particolarita' che consente di velocizzare la fine dell'algoritmo.

Il programma e' caratterizzato da un primo ciclo for che conta le passate ( conta da 1 ) e all'interno della singola passata c'e un secondo for che prende in analisi i diversi elementi J (partendo dal fondo n-1 fino a quello di indice pari al numero della passata) che devono essere confrontati con l'elemento del vettore che lo precede J-1 , si nota poi la necessita' dell'uso della variabile temp per poter scambiare due celle di un vettore senza perdersi uno dei valori delle celle.
In questo programma l'ordinamento e' fatto su un vettore di stringhe (parole), in questo caso l'ordinamento e' quello alfabetico (antonella minore di zorro)

BubbleSort

#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;

/* dato un vettore disordinato  ordinarlo con il bubblesort
   e poi stamparlo
*/    

int main(int argc, char *argv[])
{
  int n=5;
  string vett[5];
  int i,j;
  string temp;
  
  for (i=0;i<n;i++)
     { cout<<"inserisci il "<<i<<" elemento ";
       cin>>vett[i];
     }
     
  cout<<"stampa vettore disordinato"<<endl;
  for (i=0;i<n;i++)
     { cout<<vett[i]<<" , ";
     }
  cout<<endl;
 
//Bubblesort
 
  for (i=1;i<n;i++)
     for ( j= n-1;j>=i;j--)
        if(vett[j]<vett[j-1])
          { temp= vett[j];
            vett[j]=vett[j-1];
            vett[j-1]=temp;
          } 
     
  cout<<"stampa vettore ordinato"<<endl;
  for (i=0;i<n;i++)
     { cout<<vett[i]<<" , ";
     }
  cout<<endl;     
  
  system("PAUSE");            
  return 0;
}

In Octave

v=[3 1 5 23 67 0 78 -4 88 23 ]
n=10;
for i=2:n
 for j= n:-1:i
  if (v(j)<v(j-1))
    temp=v(j);
    v(j)=v(j-1);
    v(j-1)=temp;
   endif
  endfor
endfor
v

L'efficienza di un algoritmo viene espressa con l'ordine di complessita', generalmente esso dipende dal numero n di elementi del vettore, se le operazioni da fare per completare l'algoritmo fossero proporzionali al numero di elementi del vettore l'odine di complessità sarebbe indicato come $O(n)$ e si legge O grande di n. Nel caso del bubblesort le cose vanno peggio di O(n) e i calcoli da farsi sono proporzionalia a $n^{2}$ secondo un fattore di proporzionalita' di 0.5 si ha allora $O({\frac {n^{2}}{2}})$. Per il quicksort l'ordine di complessita' e' del $O(n\log _{2}n)$ , meglio del bubblesort ma peggio di un andamento solamente proporzionale ad n . Vediamo in un grafico l'andamento delle istruzioni da effettuare in 3 casi diversi di complessita'

Complessita' computazionale