ALGORITMI

IN GENERALE

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.

LA STORIA

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.

DEFINIZIONE

Esistono diverse ed innumerevoli definizioni di algoritmo, ognuna delle quali fa riferimento a svariati campi, ne riportiamo una su tutte:

          "Un algoritmo è un insieme ordinato di passi eseguibili e non ambigui, il cui unico

            scopo è la risoluzione di problemi tra loro simili e il cui processo (di risoluzione)

            deve essere temporalmente limitato".

In senso più ampio l'algoritmo è:

·Un metodo per risolvere un insieme di problemi tra loro simili (non necessariamente uguali), dove per problema si intende la definizione di una situazione problematica che può variare dall’usuale problema di matematica, all’obiettivo da raggiungere in un qualsiasi gioco, allo scopo che ci si propone in un qualsiasi lavoro (basti pensare agli algoritmi di decrittografia che venivano usati nella Seconda Guerra Mondiale per intercettare i movimenti nemici).

·Un’insieme ordinato di passi eseguibili e non ambigui, dove per passi intendiamo anche le istruzioni. Pensiamo, per esempio, al gioco degli scacchi presente nelle settimane enigmistiche quando si chiede di vincere in un certo numero di mosse.

·Un processo che deve avere comunque un limite temporale (cioè deve “produrre” una soluzione in un tempo finito). Non consideriamo algoritmo un insieme di istruzioni che fanno riferimento a cicli infiniti. Così diciamo con assoluta certezza che un’istruzione del tipo “gira su te stesso” non potrà mai costituire un algoritmo se non verrà specificato con precisione un termine, per esempio “gira su te stesso per tre volte”.

·L’algoritmo non è un programma: mentre un algoritmo è il procedimento da seguire per risolvere un problema a prescindere dal linguaggio utilizzato, un programma consiste nella descrizione di un algoritmo in uno specifico linguaggio di programmazione (l’algoritmo in questa punto è inteso come“oggetto” esclusivamente informatico).

ALCUNE PROPRIETA' FONDAMENTALI DEGLI ALGORITMI 

·i passi costituenti devono essere "elementari", ovvero non ulteriormente scomponibili (atomicità);

·i passi costituenti devono essere interpretabili in modo 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 un passo, il successivo deve essere uno ed uno solo, ben determinato (determinismo).

ESEMPIO

Il calcolo delle radici di una equazione di secondo grado: 

ax2 + bx + c = 0

 Si generano una sequenza di passi che possano portare alla soluzione del problema.

 Si calcola il delta dell’equazione e si distinguono i tre casi;

 Caso delta negativo: esistono due soluzioni complesse coniugate;

 Caso delta nullo: esiste una soluzione doppia pari a –b/2a;

 Caso delta positivo: si calcolano le due soluzioni secondo la formula nota;

 Si ottengono x1 e x2.

Questo è un semplicissimo algoritmo matematico.

!!!ATTENZIONE!!!

Molto spesso si considera l’algoritmo come un qualcosa da legare esclusivamente all’utilizzo del computer per cui risulta difficile riconoscerlo nelle sue più svariate forme ed applicazioni

APPROCCIO INFORMATICO

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.

ARGOMENTI CORRELATI

La complessità 

Con complessità di un algoritmo o efficienza di un algoritmo ci si riferisce alle risorse di calcolo da esso richieste.

Per complessità si intende una funzione che associa il numero di dati da trattare al numero di operazioni da eseguire per trattare i suddetti dati. Il simbolo utilizzato è una o minuscola "o" seguito da una parentesi dove è indicata la complessità come una funzione che dipende da N, dove N è il numero che rappresenta i dati in ingresso.

Quindi o(N) rappresenta un algoritmo la cui funzione che cresce il modo lineare (cresce come una retta).

Così o(N²) rappresenta un algoritmo la cui funzione complessità cresce come un quadrato quindi un raddoppio dei dati in ingresso provoca una quadruplicazione delle operazioni da eseguire.

La complessità di molti algoritmi è pesantemente influenzata dai dati in ingressi. in questo caso quando si calcola la complessità si considerano tre casi: OTTIMO, PESSIMO E MEDIO.

Il caso ottimo è il caso in cui i dati sono i migliori dati possibili per l'algoritmo, cioè quelli che richiedono meno elaborazioni per essere trattati.

Il caso pessimo invece prevede i dati più sfavorevoli per l'algoritmo.

Il caso medio è il caso più utile da analizzare perché fornisce un reale indicatore della complessità dell'algoritmo ma tendenzialmente è anche quello più complesso da analizzare dato che spesso è difficile determinare quali sono i dati medi. A volte per risolvere il problema del caso medio si preferisce eseguire molte simulazioni dell'algoritmo e poi dai tempi ottenuti con le simulazioni estrarre una formula che approssimi adeguatamente l'andamento medio.

Lo pseudo-codice

In informatica per pseudocodice, pseudolinguaggio o linguaggio di progetto si intende un linguaggio di programmazione fittizio, non direttamente compilabile o interpretabile da un programma compilatore o interprete, il cui scopo è quello di rappresentare algoritmi. Lo pseudolinguaggio può essere utilizzato alternativamente al diagramma di flusso e non è soggetto a molte limitazioni intrinseche di quest'ultimo tipo di rappresentazione.

Non esiste uno pseudolinguaggio standard e convenzionalmente usato: gli autori di libri o corsi di programmazione definiscono spesso un proprio pseudolinguaggio, utilizzato nelle loro pubblicazioni; inoltre ciascun programmatore può essere portato ad utilizzare una propria variante. Ogni pseudolinguaggio ha un proprio lessico, una propria  sintassi e una propria semantica, ma la progettazione di questo tipo di formalismo è volta alla comprensibilità e alla leggibilità del codice; la sintassi sarà quindi meno rigorosa rispetto ad un vero linguaggio e le parole chiave saranno evocative, in modo da rendere più intuitiva la sua interpretazione.

Lo pseudolinguaggio è strettamente dipendente dal paradigma di programmazione scelto per risolvere un problema, mentre dovrebbe essere pressoché indipendente dal linguaggio di programmazione, purché quest'ultimo rispetti naturalmente il paradigma scelto. Tuttavia, ciascun linguaggio di programmazione possiede istruzioni e/o caratteristiche proprie, che potrebbero essere sfruttate per una migliore implementazione dell'algoritmo, ad esempio più efficiente.

Spesso si usano le caratteristiche del Pascal come base per definire uno pseudolinguaggio.