Algoritmo

Nella sua definizione più semplice ed intuitiva un algoritmo è una sequenza ordinata di passi semplici che hanno lo scopo di portare a termine un compito più complesso (una ricetta da cucina, ad esempio, può essere considerata come un algoritmo che partendo da un insieme di singoli alimenti di base ed eseguendo una sequenza di passi, produce come risultato un piatto composto). In un modo più formale, possiamo quindi definire l'algoritmo come una sequenza ordinata e finita di istruzioni che, dato uno od una serie di elementi in input, produce uno od una serie di risultati in output.

La sequenza delle operazioni deve essere chiara, mai ambigua, deve avere un ordine ben preciso, e deve giungere a termine per ogni input. Tuttavia, l'aderenza all'ultimo requisito è indimostrabile, per il teorema di Turing, ed inoltre è anche possibile mostrare che esiste almeno un input per cui ogni programma non termina.

Il termine deriva dal nome del matematico persiano Muhammad ibn Mūsa 'l-Khwārizmī, che pubblicò, tra gli altri, il libro dal titolo Kitāb al-djabr wa 'l-muqābala (Libro sulla ricomposizione e sulla riduzione), dal quale prende le origini la parola Algebra.

Se, come visto, una ricetta da cucina rappresenta un discreto esempio di algoritmo direttamente eseguibile da un essere umano, l'istruzione "aggiungere sale quanto basta" difficilmente sarà comprensibile per una macchina. Il linguaggio formale in cui i passi da seguire saranno espressi, dovrà quindi essere rigoroso e chiaro, senza dare adito a forme interpretative differenti, soprattutto nel caso in cui l'esecutore è un automa (di qualunque tipo: un computer, un telaio a schede, un robot saldatore).

Un esempio esplicativo

Un passo di un algoritmo può essere definito anche tramite un altro algoritmo (chiamato in questo caso sottoalgoritmo), che suddivide il compito in compiti ancora più elementari. Facciamo un esempio:

l'algoritmo "va dal salotto alla cucina" si compone in realtà delle seguenti istruzioni:

  1. esci dal salotto
  2. curva a sinistra
  3. prosegui per il corridoio fino all'ultima porta sulla sinistra
  4. attraversa la porta a sinistra

Questo è certamente fin troppo esplicito per un operatore umano (al quale già il problema originale "va dal salotto alla cucina" sembra probabilmente abbastanza elementare da non richiedere, in apparenza, suddivisioni), ma nel caso di un automa richiederebbe di specificare i passi con ben altra complessità.

L'algoritmo "attraversa la porta a sinistra" si compone di:

  1. controlla se la porta è aperta
  2. nel caso che la porta sia aperta salta il passo seguente
  3. apri la porta
  4. avanza di un metro

L'algoritmo "apri la porta", compreso nel precedente, a sua volta si compone di:

  1. protendi il braccio
  2. afferra la maniglia
  3. rotea la mano di 30 gradi in direzione antioraria
  4. applica una pressione alla maniglia diretta di fronte a te
  5. ...

Un modo dettagliato di rappresentare l'algoritmo "attraversa la porta a sinistra" è allora il seguente:

  1. controlla se la porta è aperta
  2. nel caso che la porta sia aperta salta il passo seguente
  3. apri la porta
    1. protendi il braccio
    2. afferra la maniglia
    3. rotea la mano di 30 gradi in direzione antioraria
    4. applica una pressione alla maniglia diretta di fronte a te
    5. ...
  4. avanza di un metro

Una breve analisi dell'esempio sopra, porta a delineare alcune caratteristiche essenziali di un algoritmo:

Inoltre, in informatica, si richiede generalmente che un algoritmo sia finito, ovvero termini per ogni insieme di dati di ingresso. La Teoria della complessità algoritmica studia l'andamento delle risorse (tempo di calcolo, memoria) al variare della dimensione dei dati in ingresso.

Catalogazione degli algoritmi

Gli algoritmi vengono raggruppati e catalogati a seconda della loro funzione o delle tecniche utilizzate per realizzarli. Questa è una lista dei principali algoritmi utilizzati in informatica:


Molte categorie di algoritmi sono strettamente legate all'organizzazione dei dati in memoria (strutture dati).

Voci correlate

separatore

Antropologia | Archeologia | Arte e Musica | Astronomia e Cosmologia | Biologia | Chimica | Ecologia e Ambiente | Economia | Fisica | Informatica e Telecomunicazioni | Ingegneria e Tecnologia | Matematica e Geometria | Medicina e Fisiologia | Paleontologia | Psicologia e Scienze cognitive | Geografia e Scienze della Terra | Scienze dello spazio | Scienze naturali | Scienze politiche | Statistica e Scienze sociali | Storia della scienza

See also: Algoritmo, Al-Khwarizmi, Algebra, Algoritmo di ordinamento, Algoritmo di ricerca, Algoritmo genetico, Algoritmo ricorsivo, Antropologia, Archeologia