Algoritmo
L'algoritmo è un procedimento che permette di calcolare un risultato e risolvere un problema, eseguendo una serie di ordini e condizioni impostate a priori. Nell'informatica è la logica di calcolo seguita dal programma informatico per elaborare i dati.
L'origine dell'algoritmo nella storia. La parola "algoritmo" viene usata per la prima volta dal matematico persiano Muhammad ibn Mûsa 'l-Khwârizmî nel IX secolo d.C. È il primo a utilizzare il termine per indicare i procedimenti di calcolo numerico sulle cifre arabe. Nel corso del tempo la parola algoritmo diventa il sinonimo generale del calcolo logico-matematico.
Il funzionamento degli algoritmi
Un algoritmo è un metodo di calcolo esplicito (inconfutabile) ed è descritto con un numero finito di regole. È composto da un numero di operazioni e passi in sequenza.
Per rappresentare un algoritmo si utilizza un diagramma di flusso ( flow chart ).
Ogni blocco del diagramma descrive un'operazione di calcolo o di assegnazione dei dati.
Generalmente, i primi passi dell'algoritmo consistono nell'inserimento dei dati di input ( entrata ). I passi intermedi riguardano l'elaborazione dati mentre quelli finali la visualizzazione dei risultati in output ( uscita )
La differenza tra algoritmo e programma. L'algoritmo e il programma informatico non sono la stessa cosa. L'algoritmo è il metodo di risoluzione del problema. Il programma è un codice in linguaggio macchina eseguibile dal computer. Per essere eseguito da un computer l'algoritmo deve essere codificato in un programma informatico tramite un linguaggi di programmazione.
In alternativa al diagramma a blocchi, un algoritmo può anche essere rappresentato da uno pseudocodice.
Le caratteristiche dell'algoritmo
Le principali caratteristiche di un algoritmo sono le seguenti:
- Completezza. È la capacità dell'algoritmo di trovare una soluzione al problema per cui è stato sviluppato.
- Ottimalità. Questa caratteristica si verifica se la soluzione trovata dall'algoritmo è la migliore possibile.
- Complessità. È la difficoltà di utilizzo dell'algoritmo in termini di tempo di elaborazione impiegato ( complessità temporale ) e di memoria utilizzata ( complessità spaziale ).
Un problema trattabile può essere risolto utilizzando algoritmi diversi, più o meno complessi.
La teoria della complessità
È la branca dell'informatica che studia la complessità degli algoritmi e individua l'algoritmo più efficiente a parità di efficacia dell'algoritmo, ossia quello in grado di risolvere il problema con minore tempo di esecuzione e minore consumo di risorse.
La complessità polinominale. Un problema si dice trattabile ( problema trattabile ) se esiste un algoritmo in grado di risolverlo computazionalmente con una complessità polinomiale. In caso contrario, è detto problema intrattabile.
