Scrivere un programma che “funzioni” è solo il primo passo. La vera sfida dell’informatica moderna non è solo calcolare una soluzione, ma scovare quella ottimale, capace di bilanciare efficacia e dispendio di risorse. Se un tempo eravamo ossessionati dalla RAM perché le macchine erano limitate, oggi lo siamo perché la mole di dati (pensiamo al Machine Learning) è diventata monumentale. Senza una solida base teorica sulla complessità, non avremmo idea se un algoritmo possa reggere l’urto di milioni di dati o se finirà per bloccarsi proprio sul più bello. Il bello della complessità è che ci regala una misura universale: la qualità della nostra idea resta valida a prescindere da quanto sia potente l’ultimo processore uscito sul mercato.
Misurare l’Efficienza: La Notazione O-grande
Per valutare un algoritmo, gli informatici utilizzano un concetto mediato dalla matematica, la notazione O-grande (O), che paragona il comportamento asintotico di una funzione y = f(x), quando x tende all’infinito, al comportamento di funzioni conosciute che limitano superiormente la funzione f(x), in pratica se una funzione f(x) è O(g(x)) si manterrà minore c*g(x) da una certa x in poi (c è una costante).
In questo caso il nostro problema è “misurare” il tempo t di esecuzione di un algoritmo al tendere della dimensione dell’input (n) all’infinito, quindi dobbiamo trovare una rappresentazione del tempo di esecuzione di un algoritmo in funzione della dimensione dell’istanza di input: t = f(n).
Potremmo avere algoritmi polinomiali (considerati efficienti o “facili”) e algoritmi non polinomiali (difficili o intrattabili). La differenza è abissale: se un algoritmo O(n) impiega frazioni di secondo per eseguire un algoritmo su una certa istanza, un algoritmo non polinomiale come O(2n) potrebbe richiedere secoli.
Gli Algoritmi Fondamentali: Ricerca e Ordinamento
Possiamo insegnare questo modulo dell’informatica ponendo inizialmente il problema della ricerca di un dato valore in una lista, possiamo risolvere inizialmente questo problema utilizzando l’algoritmo di ricerca sequenziale introducendo successivamente la ricerca dicotomica.
Nella ricerca, l’algoritmo lineare ha una complessità O(n), tuttavia, se i dati sono ordinati, la ricerca dicotomica riduce lo sforzo a O(log2 n), un miglioramento enorme per liste di grandi dimensioni.
Possiamo poi passare ai problemi di ordinamento, algoritmi semplici come il Selection Sort e il Bubble Sort hanno una complessità quadratica O(n2), rendendoli inefficienti per grandi dataset. Al contrario, il Merge Sort e il Quick Sort (nella maggior parte dei casi) raggiungono una complessità O(nlog2n), ottimizzando drasticamente il numero di operazioni necessarie attraverso strategie di suddivisione binaria.
Grafi e Flussi: Modellare la Realtà
I problemi esaminati fino a qui sono problemi facilmente comprensibili e fanno parte del bagaglio di algoritmi che uno studente ha già affrontato, possiamo ora introdurre problemi più articolati per dimostrare che questo argomento ha ramificazioni anche nell’applicazione reale.
Per rendere più comprensibili questi algoritmi dobbiamo introdurre la teoria dei grafi, i grafi sono strutture di dati potenti e versatili, ampiamente utilizzate per modellare e risolvere una varietà di problemi del mondo reale. Problemi complessi come il calcolo del percorso più breve tra due punti, l’organizzazione delle reti di trasporto e la gestione delle relazioni sociali possono essere efficacemente rappresentati e risolti mediante l’uso dei grafi.
Per esempio l’algoritmo di Dijkstra è essenziale per trovare il cammino minimo in reti con pesi non negativi, esso ha una complessità di O((A+N)log2N) (dove A è il numero degli archi e N il numero dei nodi).
Supponiamo per esempio di voler aiutare Marco a scegliere il percorso migliore in termini di tempo dalla sua casa alla scuola sulla mappa stradale:
Oppure potremmo voler determinare il percorso più efficiente per inviare dati da un web server a un client in una rete di computer (sul grafo è stato attribuito a ogni arco della rete il tempo di latenza necessario a coprire la distanza).
Parallelamente, l’algoritmo di Ford-Fulkerson risolve il problema del flusso massimo in una rete (come la distribuzione idrica o elettrica), operando con una complessità di tipo cubico O(n3); per introdurre questo algoritmo potremmo proporre il problema di immaginare una rete elettrica con una centrale (nodo sorgente) e delle città (B, C, D e E). Il flusso massimo ci dice quanta energia elettrica al massimo può essere distribuita dalla centrale alle città, considerando la capacità dei cavi (archi).
La Sfida dei Problemi NP-completi
Infine, possiamo affrontare i problemi più difficili, definiti NP-completi, come il Problema dello Zaino (Knapsack), il Partizionamento o il Commesso Viaggiatore (TSP). Per questi problemi non si conoscono algoritmi polinomiali risolutivi e la loro complessità cresce esponenzialmente con la dimensione dell’input. In questi casi, si utilizzano tecniche come il branch-and-bound, che esplora lo spazio delle soluzioni attraverso “ramificazione e potatura”, cercando di gestire l’esplosione combinatoria delle soluzioni possibili.
In conclusione, il calcolo dell’efficienza computazionale non è solo un esercizio accademico, ma una necessità pratica per ottimizzare gli algoritmi, prevedere le prestazioni hardware e scegliere la strategia risolutiva più adeguata di fronte alla complessità dei dati moderni.
Per approfondire, si veda G. Barberis, E. Dari, Informatica bit a bit.