Algoritmo

Un algoritmo è una procedura computazionale ben definita che, dato un insieme di valori in ingresso, produce un corrispondente insieme di valori in uscita attraverso una sequenza finita di passi elementari.

Le proprietà fondamentali di un algoritmo sono:

• finitezza: l’esecuzione termina dopo un numero finito di passi;
• determinismo: ogni passo è definito in modo non ambiguo;
• effettività: ogni operazione è eseguibile concretamente;
• generalità: risolve un’intera classe di problemi, non un singolo caso.

La complessità computazionale misura le risorse (tempo e spazio) necessarie all’esecuzione in funzione della dimensione dell’input $n$. Si usa la notazione asintotica $O$: un algoritmo con complessità $O(n \log n)$ è asintoticamente più efficiente di uno $O(n^2)$.

Esempi classici includono l’algoritmo di Euclide per il massimo comun divisore (complessità $O(\log \min(a,b))$), gli algoritmi di ordinamento (Merge Sort con complessità $O(n \log n)$ nel caso peggiore) e gli algoritmi di ricerca su grafi (Dijkstra, con complessità $O((V + E) \log V)$ usando code di priorità).

La formalizzazione del concetto di algoritmo è dovuta ad Alan Turing (1936) e Alonzo Church, i cui lavori hanno fondato la teoria della computabilità.

Paradigmi algoritmici

I principali paradigmi di progettazione degli algoritmi sono:

• Divide et impera: suddivide il problema in sottoproblemi della stessa natura, li risolve ricorsivamente e combina le soluzioni (es. Merge Sort, FFT).
• Programmazione dinamica: risolve sottoproblemi sovrapposti una sola volta memorizzando i risultati (memoizzazione); efficiente quando la struttura ottimale del problema soddisfa il principio di ottimalità di Bellman (es. shortest path, knapsack).
• Algoritmi greedy: a ogni passo sceglie l’opzione localmente ottimale; non garantisce l’ottimo globale in generale, ma lo raggiunge per particolari strutture del problema (matroidi, es. algoritmo di Kruskal, Dijkstra con pesi non negativi).
• Backtracking: esplora sistematicamente lo spazio delle soluzioni con potatura (pruning) dei rami non promettenti (es. problemi di soddisfacibilità SAT, N-regine).

Vedi anche: Algebra degli O-piccoli, Aritmetica Finita.