Algoritmo

Tante volte abbiamo sentito il termine algoritmo, il più delle volte in campo prettamente informatico. (Uno dei più celeberrimi, è sicuramente l’algoritmo PageRank di Google, che stabilisce quale sito far apparire prima nei risultati di una ricerca).

Cos’è un algoritmo?

E’ un procedimento, una serie di passi, un susseguirsi di istruzioni (in numero finito), che dato un INPUT restituisce un OUTPUT. Tutti noi quotidianamente eseguiamo degli algoritmi. Anche una banale ricetta di cucina è un algoritmo, per arrivare al nostro piatto finale usiamo i giusti ingredienti e procedimenti. In ambito informatico, gli algoritmi risolvono problemi, in modo più o meno efficente. E questo lo fanno seguendo determinate proprietà (Definite dall’informatico statunitense Knuth, negli anni 60):

Finiteness: "An algorithm must always terminate after a finite number of steps"
Definiteness: "Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case"
Input: "...quantities which are given to it initially before the algorithm begins. These inputs are taken from specified sets of objects"
Output: "...quantities which have a specified relation to the inputs"
Effectiveness: "... all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a man using paper and pencil"

• Finitezza: “Un algoritmo deve terminare, dopo un numero finito di passi”
• Definitezza: “Ogni passo deve essere rigorosamente definito; Le azioni da svolgere devono essere rigorose e non ambigue”
• Input: “Un algoritmo deve avere un certo numero di dati in entrata, un input”
• Output: “E certamente deve produrre un risultato, un output”.
• Efficacia: “Tutte le operazioni da svolgere nell’algoritmo devono avvenire in un tempo finito ragionevole, algoritmi con tempi di esecuzione biblici non hanno senso”

Gli algoritmi risolutivi possono essere disparati e diversissimi fra loro. Proprio per questo motivo ha senso parlare di Complessità Computazionale.

La complessità computazionale esiste in termini di tempo e spazio. Ma ai giorni nostri, grazie ad hard disk sempre più capienti e a buon mercato, lo spazio non è più un fattore determinante tenuto in considerazione. Ciò che veramente ci interessa, è la complessità computazionale in termini di Tempo.

Una complessità computazionale bassa in termini di tempo, indica una risposta veloce al nostro problema, da parte del nostro algoritmo. Con tempi di esecuzione ridotti al minimo indispensabile. E’ fondamentale durante la scrittura di un programma, pensare a più procedure per definire determinate funzioni che in termini di tempo, risultino computazionalmente più efficenti rispetto ad altre.

Su questo sito è possibile trovare un’intera categoria dedicata agli algoritmi di programmazione accademici più conosciuti (Scritti in C, Python etc.).