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.

Il termine deriva dal nome del matematico arabo Muhammad Bin Musa Al-Khwarizmi, che pubblicò, tra gli altri, il libro dal titolo Kitab al-jabr wal muqabala\ (metodo per numerare ed ordinare le parti di un tutto), 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 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:

• non ambiguo: le istruzioni devono essere univocamente interpretabili;
• eseguibile: ogni istruzione deve terminare in tempo finito.

Inoltre, in informatica, si richiede generalmente che un algoritmo sia finito, ovvero termini per ogni insieme di dati di ingresso.

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

• Di ordinamento
• Di ricerca
• Genetici o evolutivi
• Ricorsivi
• Codice automodificante
• Teoria della complessità algoritmica
• Conversione e codifica
  • UUencode/UUdecode
  • Mime
• Compressione
  • Senza perdita di informazioni:
    • Run Lenght Encoding
      • PackBits
      • PCX
    • Codifica a riduzione di Entropia
      • Huffman (semplice codifica a riduzione di entropia)
      • Codifica aritmetica (Codifica avanzata a riduzione di entropia)
    • Codifica a dizionario
      • DEFLATE
      • LZ77 & LZ78;
      • Lempel-Ziv-Welch (ZIP)
      • LZMA
    • Trasformazione Burrows-Wheeler
    • PPM
  • Con perdita di informazione
    • Trasformazione discreta del coseno
      • MPEG (Primo metodo di compressione ad alta diffusione basato si DCT e Delta)
      • JPEG (Compressione d'immagini basato su quantizzazione, DCT e Huffman)
    • Compressione frattale
      • Trasformazione frattale
    • Wavelet
      • MP3 (compressione audio basata su compressione simil-wavelet e DCT)
      • JPEG2000 (compressione d'immagini che usa wavelet, Huffman e quantizzazione)

Link

• Diagramma a blocchi

Astronomia | Biologia | Botanica | Chimica | Ecologia | Economia | Fisica | Geometria | Informatica | Matematica | Medicina | Statistica | Telecomunicazioni

---

|