Algoritmi

In informatica e matematica, il termine algoritmo indica un procedimento che risolve un determinato problema attraverso un numero finito di passi. Un problema risolvibile mediante un algoritmo si dice computabile. Il termine "algoritmo" deriva dalla trascrizione latina del nome del matematico persiano al-Khwarizmi, che è considerato uno dei primi autori ad aver fatto riferimento a questo concetto.

Modelli formali 

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.

Proprietà fondamentali

Dalla precedente definizione si evincono alcune proprietà caratteristiche degli algoritmi, che essi devono possedere per essere definiti come tali:

  • i passi costituenti devono essere "elementari", ovvero non ulteriormente scomponibili (atomicità);
  • i passi costituenti devono essere interpretabili in modo diretto e univoco dall'esecutore, sia esso umano o artificiale (non ambiguità);
  • l'algoritmo deve essere composto da un numero finito di passi e richiedere una quantità finita di dati in ingresso (finitezza)
  • l'esecuzione deve avere termine dopo un tempo finito (terminazione);
  • l'esecuzione deve portare ad un risultato univoco (effettività);
  • ad ogni passo, il successivo deve essere uno ed uno solo, ben determinato (determinismo). (fanno eccezione gli algoritmi randomizzati)

Così, ad esempio, "rompere le uova" può essere considerato legittimamente un passo elementare di un "algoritmo di cucina" (ricetta), e potrebbe esserlo anche "aggiungere sale quanto basta", ammesso che l'esecutore sia in grado di risolvere da solo l'ambiguità di questa frase.

Al contrario, un passo come "preparare un pentolino di crema pasticciera" non può considerarsi legittimo perché ulteriormente scomponibile in sotto-operazioni (accendere il fuoco, regolare la fiamma, mettere il pentolino sul fornello, ecc.) e anche perché contenente ambiguità (quanta crema?); potrebbe, però, essere associato a un opportuno rimando a un'altra sezione del ricettario, che fornisca un sotto-algoritmo apposito per questa specifica operazione.

Questo suggerisce che, per comodità d'implementazione, gli algoritmi possano essere modulari, ovvero orientati a risolvere specifici sotto-problemi, e gerarchicamente organizzati.

Inoltre, una ricetta che preveda la cottura a microonde non può essere preparata da un esecutore sprovvisto dell'apposito elettrodomestico; questo rimanda al problema della realizzabilità degli algoritmi, ovvero della loro compatibilità con le risorse materiali e temporali a disposizione. Infine, possono darsi più algoritmi validi per risolvere uno stesso problema, ma ognuno con un diverso grado di efficienza.

Approccio informatico 

Il concetto di algoritmo ha molta più rilevanza in informatica che in matematica, 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 (input) variabili, su cui l'algoritmo stesso opererà per giungere fino alla soluzione.

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 "x" ciascuno dei quesiti specifici ottenuti fissando due particolari valori. Data questa premessa, un algoritmo risolve un problema se è costituito da una sequenza finita di passi che, applicata indifferentemente a qualunque istanza del problema, produce in un tempo finito la soluzione desiderata, ovvero un certo output.

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.

Un algoritmo può essere descritto attraverso l'uso di un diagramma di flusso o ricorrendo ad uno pseudocodice. Nella fase di programmazione l'algoritmo così scritto verrà tradotto in linguaggio di programmazione ad opera di un programmatore sotto forma di codice sorgente dando vita al programma; tale programma verrà poi ulteriormente tradotto in linguaggio macchina prima di essere eseguito dal calcolatore.

Particolare rilevanza teorica in tale ambito assume il teorema di Böhm-Jacopini che afferma che qualunque algoritmo può essere implementato utilizzando tre sole strutture, la sequenza, la selezione ed il ciclo (iterazione), da applicare ricorsivamente alla composizione di istruzioni elementari.

Complessità e stabilità

Controparte della complessità di un algoritmo, è la sua stabilità numerica: essa stabilisce quanto un algoritmo è "resistente" a degli insiemi di dati particolari.

Ovviamente il discorso è generalmente correlato all'analisi numerica, e alle implementazioni di algoritmi su macchine specifiche, tuttavia potrebbero darsi algoritmi prettamente matematici che per alcuni dati forniscono risultati indeterminati, tipo 0 \over 0, mentre altri algoritmi equivalenti con gli stessi dati arrivano comunque a dare risposte: i primi sono meno stabili dei secondi. Un esempio sono i limiti calcolati col metodo canonico, oppure col metodo di De l'Hôpital.

fonte: Wikipedia

Articoli Correlati

Videosorveglianza
views 47
Individuate le nuove garanzie per i cittadini Dossier 24 febbraio 2006 La tutela dei diritti si concilia con una efficace azione di sicurezza e prevenzione. L'installazione di telecamere è lecita...