Algoritmi – che cosa sono?

Algoritmi – che cosa sono?

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.

Nel senso più ampio della parola, “algoritmo” è anche una ricetta di cucina, o la sezione del libretto delle istruzioni di una lavatrice che spiega come programmare un lavaggio. Di norma, comunque, la parola viene usata in contesti matematici (fin dalle origini) e soprattutto informatici (più recentemente).

Un esempio più appropriato di algoritmo potrebbe essere, quindi, il procedimento per il calcolo del massimo comune divisore o del minimo comune multiplo.

Definizione: « Insieme di istruzioni elementari (univocamente interpretabili) che, eseguite in un ordine stabilito, permettono la soluzione di un problema in un numero finito di passi »

In base alla precedente definizione, evinciamo le quattro proprietà fondamentali dell’algoritmo:

  • La sequenza di istruzioni deve essere finita
  • Essa deve portare ad un risultato
  • Le istruzioni devono essere eseguibili materialmente
  • Le istruzioni non devono essere ambigue

Affermando che i passi costituenti di un algoritmo debbano essere “semplici”, si intende soprattutto che essi siano specificati in modo non ambiguo, ovvero immediatamente evidenti a chi sarà chiamato ad applicare l’algoritmo, cioè il suo esecutore.

Così, “rompete le uova” può essere un passo legittimo di un “algoritmo di cucina”, e potrebbe esserlo anche “aggiungete sale quanto basta” se possiamo assumere che l’esecutore sia in grado di risolvere da solo l’ambiguità di questa frase.

Al contrario, un passo come “preparate un pentolino di crema pasticciera” non può probabilmente considerarsi “semplice”; potrebbe però essere associato a un opportuno rimando a un’altra sezione del ricettario, che fornisca un algoritmo apposito per questa specifica operazione.

Infine, una ricetta che preveda la cottura a microonde non può essere preparata da chi è sprovvisto dell’apposito elettrodomestico.

Algoritmi e problemi

Il concetto di algoritmo ha una grande rilevanza in matematica e in informatica, in cui esso viene generalmente descritto come “procedimento di risoluzione di un problema”. In questo contesto, i “problemi” che si considerano sono quasi sempre caratterizzati da dati di ingresso variabili.

Per esempio, il calcolo del massimo comune divisore fra due numeri è un esempio di “problema”, e i suoi dati di ingresso, variabili di volta in volta, sono i due numeri in questione. A un non matematico questa potrebbe apparire come una “famiglia di problemi” (il problema di calcolare il massimo comune divisore fra 10 e 15, il problema di calcolarlo fra 40 e 60, fra 35 e 95, e così via).

Il matematico e l’informatico identificano con la parola “problema” l’intera famiglia e con “istanza” o “caso particolare” ciascuno dei quesiti specifici ottenuti fissando due particolari valori.

Data questa premessa, un algoritmo risolve un problema se è costituito da una sequenza di passi che, applicata indifferentemente a qualunque istanza del problema, produce in un tempo finito la soluzione desiderata.

Se questa idea aveva una certa importanza per il calcolo matematico, l’avvento dell’informatica l’ha arricchita di una nuova importanza (ed è infatti con l’informatica che il termine “algoritmo” ha iniziato a diffondersi). Infatti, se per ottenere un certo risultato (risolvere un certo problema) esiste un procedimento infallibile, che può essere descritto in modo non ambiguo fino ai dettagli, e conduce sempre all’obiettivo desiderato in un tempo finito, allora esistono le condizioni per affidare questo compito a un computer, semplicemente descrivendo l’algoritmo in questione in un programma scritto in un opportuno linguaggio comprensibile alla macchina.

La complessità di un algoritmo si misura asintoticamente.

Vi sono tre metodi per calcolare la complessità di un algoritmo:

  • metodo di sostituzione
  • metodo dell’albero di ricorsione
  • metodo dell’esperto

Si definisce asintotica per due motivi: poiché ogni calcolatore può implementare algoritmi in modo differente, non si può stimare il tempo preciso e poi perché si vuole dare un’idea quantitativa di come l’algoritmo possa crescere in consumo di tempo all’aumentare dell’input, per valori sempre maggiori.

La definizione di algoritmo riportata sopra è, evidentemente, piuttosto informale. Allo scopo di trattare il concetto di algoritmo con strumenti matematici, era necessario darne una definizione più rigorosa. Questo obiettivo è stato realizzato inventando una serie di modelli matematici di algoritmo. Uno dei più celebri è la macchina di Turing. Essa rappresenta una sorta di computer ideale corredato di un programma da eseguire. Rispetto a un computer ideale, la macchina di Turing ha un funzionamento più semplice, con il vantaggio però che il suo funzionamento è facilmente descrivibile in termini matematici, facendo uso di concetti come insieme, relazione e funzione. Inoltre, è stato dimostrato che la macchina di Turing è tanto potente quanto la macchina di von Neumann, che è il modello sottostante a tutti i computer reali. In altre parole, se un certo problema può essere risolto da un computer (opportunamente programmato), esso può certamente essere risolto anche da una macchina di Turing.

Dopo la macchina di Turing, proposta da Alan Turing nel 1936, altri matematici hanno elaborato rappresentazioni formali del concetto di algoritmo, fra i quali ricordiamo, per esempio, il lambda calcolo. Dopo alcuni anni, emerse che tutti questi modelli erano equivalenti. I problemi che una macchina di Turing poteva risolvere erano gli stessi che poteva risolvere una macchina di von Neumann e anche gli stessi che poteva risolvere una funzione costruita col lambda calcolo. Da questi risultati, tra l’altro, scaturì la tesi di Church-Turing, che afferma che qualsiasi algoritmo è modellabile con una macchina di Turing. In altri termini, questa tesi sostiene che è sostanzialmente impossibile cercare di immaginare un modello di algoritmo più potente e anche, come corollario, che nessuna macchina potrà mai risolvere problemi che una macchina di Turing non possa risolvere in linea di principio. Ovviamente, non si tratta di un teorema, in quanto la tesi stabilisce l’eguaglianza di due concetti (algoritmo e macchina di Turing) di cui solo il secondo ha una definizione formale. La tesi è ancora oggi generalmente condivisa, sebbene nuove ricerche nel settore dell’ipercomputazione sembrino volte a metterla in discussione.

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:

– esci dal salotto

  • curva a sinistra
  • prosegui per il corridoio fino all’ultima porta sulla sinistra
  • 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:

– controlla se la porta è aperta

  • nel caso che la porta sia aperta salta il passo seguente
  • apri la porta
  • avanza di un metro

L’algoritmo “apri la porta”, compreso nel precedente, a sua volta si compone di:

– protendi il braccio

  • afferra la maniglia
  • rotea la mano di 30 gradi in direzione antioraria
  • applica una pressione alla maniglia diretta di fronte a te

Un modo dettagliato di rappresentare l’algoritmo “attraversa la porta a sinistra” è allora il seguente:

– controlla se la porta è aperta

  • nel caso che la porta sia aperta salta il passo seguente
  • apri la porta
  • protendi il braccio
  • afferra la maniglia
  • rotea la mano di 30 gradi in direzione antioraria
  • applica una pressione alla maniglia diretta di fronte a te
  • 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.

Catalogazione degli algoritmi

Gli algoritmi vengono raggruppati e catalogati a seconda della loro funzione o delle tecniche utilizzate per realizzarli.

In informatica è possibile catalogare gli algoritmi in :

  • Algoritmi di ordinamento
  • Algoritmi di ricerca
  • Ricerca sequenziale
  • Ricerca sequenziale con sentinella
  • Ricerca 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
  • LZ77 e LZ78
  • Lempel-Ziv-Welch (ZIP)
  • LZMA
  • Trasformazione Burrows-Wheeler
  • PPM
  • Con perdita di informazione
  • Trasformata discreta in coseno (DCT)
  • MPEG (Primo metodo di compressione ad alta diffusione basato su 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)

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

[ fonte: wikipwedia, contenuto modificato rispetto all’originale ]

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *