Algoritmo
In [[informatica]], con il termine algoritmo si intende un metodo per la soluzione di un problema adatto a essere implementato sotto forma di [[programma]].
Intuitivamente, un algoritmo si può definire come un procedimento che consente di ottenere un risultato atteso eseguendo, in un determinato ordine, un insieme di passi semplici corrispondenti ad azioni scelte solitamente da un insieme finito.
Da questa definizione si evincono le quattro proprietà fondamentali dell'algoritmo:
-
la sequenza di istruzioni deve essere finita (finitezza);
-
essa deve portare ad un risultato (effettività);
-
le istruzioni devono essere eseguibili materialmente;
-
le istruzioni devono essere espresse in modo non ambiguo (non ambiguità).
In generale, un algoritmo riceve un insieme di valori (dati) in input e ne genera uno in output (chiamato soluzione). Questa corrispondenza tra input e output rappresenta il problema risolto dall'algoritmo.
L'esecuzione di un algoritmo su un dato input richiede il consumo di una certa quantità di risorse; queste possono essere rappresentate dal tempo di computazione impiegato e dallo spazio di memoria utilizzato. È importante saper valutare la quantità di risorse consumate proprio perché un consumo eccessivo può pregiudicare le stesse possibilità di utilizzo di un algoritmo.
In particolare si valuta sempre quanto, al crescere della complessità del problema, cresce il tempo necessario a eseguire l'algoritmo e lo spazio di memoria occupato in un calcolatore.
La maggior parte degli algoritmi coinvolge metodi sofisticati per l'organizzazione dei dati utilizzati nelle elaborazioni. Gli oggetti creati con questi metodi vengono chiamati [[strutture dati]] (array, liste, code, ecc.). Algoritmi semplici possono richiedere strutture dati complesse e viceversa. Inoltre molte tipologie di algoritmi sono nate per la gestione di strutture dati complesse e per agevolarne la gestione.
Classificazione degli algoritmi
Gli algoritmi vengono raggruppati e catalogati a seconda della loro funzione, della loro struttura e delle tecniche utilizzate per realizzarli.
In informatica è possibile catalogare gli algoritmi in:
-
Algoritmi di ordinamento;
-
Algoritmi di ricerca (sequenziale, sequenziale con sentinella, binaria);
-
Genetici o evolutivi;
-
Ricorsivi;
-
Algoritmo combinatorio;
-
Codice automodificante;
-
Conversione e codifica ([[UUencode/UUdecode]], [[Mime]]);
-
Algoritmi di compressione:
-
Senza perdita di informazioni:
-
Run-length encoding (PackBits, PCX);
-
Codifica a riduzione locale di Entropia (Huffman, codifica aritmetica);
-
Codifica a dizionario (DEFLATE, [[ZIP]]);
-
Trasformata di Burrows-Wheeler;
- PPM;
-
- Con perdita di informazione:
-
Trasformata discreta del coseno ([[MPEG]], [[JPEG]]);
-
Compressione frattale (trasformazione frattale);
-
Wavelet ([[MP3]], [[JPEG2000]]).
-
-
