Algoritmi, problem solving e pseudocodifica

Approfondimento

Sul piano teorico un problema si formalizza come una funzione (o relazione) che a ogni istanza dei dati di ingresso associa i dati di uscita ammissibili: il dominio è l'insieme degli input validi, il codominio l'insieme delle possibili risposte, e risolvere il problema significa realizzare quella funzione con un procedimento effettivo. Questa lettura permette di distinguere tre grandi famiglie che ricorrono in tutto il programma: i problemi di decisione, la cui uscita è un semplice «sì/no» (un numero è primo?); i problemi di ricerca, che chiedono di esibire un oggetto con una data proprietà (trovare la posizione di un valore in un elenco); i problemi di ottimizzazione, che fra tutte le soluzioni ammissibili cercano la migliore secondo un criterio (il cammino più breve, la spesa minima). Un problema è ben posto quando la specifica è completa e non contraddittoria, cioè per ogni input ammissibile l'output atteso esiste ed è univocamente determinato. La fase di analisi è l'esercizio concreto del pensiero computazionale (computational thinking, J. Wing), che si articola in quattro operazioni intrecciate: la decomposizione (spezzare il problema in parti), il riconoscimento di schemi ricorrenti (pattern), l'astrazione (costruire il modello trascurando i dettagli irrilevanti) e la progettazione dell'algoritmo. È bene sapere fin d'ora che non tutti i problemi ben posti ammettono un algoritmo risolutivo: esistono problemi indecidibili, di cui la teoria della computabilità dimostra l'insolubilità meccanica.

Approfondimento

Conviene separare due nozioni di finitezza che spesso si confondono: la finitezza della descrizione (l'algoritmo è un testo di lunghezza finita, un numero finito di istruzioni) e la finitezza dell'esecuzione (per ogni input il calcolo termina dopo un numero finito di passi). Entrambe sono necessarie: un testo finito può descrivere un ciclo che non termina mai. Un procedimento che rispetta tutte le proprietà tranne la terminazione si dice semi-algoritmo o procedura, e non è un algoritmo. Il determinismo qui richiesto è quello degli algoritmi deterministici, in cui lo stato successivo è univocamente determinato dallo stato corrente; esistono però gli algoritmi randomizzati (probabilistici), che compiono scelte pseudo-casuali e la cui uscita o efficienza dipende dal caso — utilissimi in pratica, per esempio nel metodo Monte Carlo, ma da tenere distinti dal modello deterministico classico. La proprietà di eseguibilità si comprende appieno solo fissando l'esecutore e il suo repertorio finito di istruzioni elementari: ciò che è «passo elementare» per un calcolatore non lo è per una persona, e viceversa. Questa idea trova la sua formulazione rigorosa nella tesi di Church-Turing: la nozione intuitiva di «procedimento effettivo» coincide con ciò che è calcolabile da una macchina di Turing. È proprio tale tesi a fornire la definizione rigorosa di algoritmo — quella intuitiva delle quattro proprietà ne è la versione operativa — e sarà ripresa nel capitolo sulla teoria della computazione.

Approfondimento

Il fondamento della verifica di correttezza di un ciclo è l'invariante di ciclo: una proprietà che è vera immediatamente prima del ciclo e che, se vale all'inizio di un'iterazione, resta vera al termine della stessa. All'uscita, l'invariante combinato con la negazione della condizione di controllo fornisce la tesi da dimostrare. Per «S <- 0; per i da 1 a n: S <- S + i» l'invariante è «all'inizio dell'iterazione con contatore i, S contiene la somma 1+2+...+(i−1)»: è vero per i = 1 (S = 0, somma vuota), si conserva perché il corpo aggiunge proprio i, e all'uscita (i = n+1) dà «S = 1+2+...+n», cioè la correttezza cercata. Il teorema di Böhm-Jacopini non è solo un enunciato di esistenza ma è costruttivo: fornisce un procedimento per riscrivere qualunque diagramma di flusso, anche pieno di salti «goto», impiegando le sole tre strutture, eventualmente al prezzo di introdurre variabili di stato ausiliarie (flag booleane) che ricordano «a che punto siamo». È questo il motivo teorico per cui la programmazione strutturata non perde potere espressivo pur rinunciando al goto, salto che E. Dijkstra additò come fonte di codice illeggibile. Infine iterazione e ricorsione hanno lo stesso potere computazionale: ogni ciclo può essere riscritto come funzione ricorsiva e viceversa (quest'ultima con l'aiuto di una pila che simula i cicli annidati), un'equivalenza che sarà ripresa parlando di sottoprogrammi e ricorsione.

Approfondimento

Lo strumento principe per verificare a mano un algoritmo, prima ancora di eseguirlo su un calcolatore, è la tabella di traccia (desk check o dry run): si predispone una colonna per ogni variabile e una riga per ogni passo, e si aggiornano i valori istruzione per istruzione, simulando l'esecutore. Così si scoprono gli errori logici — un contatore che parte dal valore sbagliato, una condizione invertita — che nessun controllo puramente sintattico rivelerebbe. La distinzione fra sintassi e semantica è qui cruciale: la sintassi è l'insieme delle regole di forma (come si scrive un'istruzione), la semantica è il significato, cioè l'effetto sull'esecutore. L'assegnazione «x <- espressione» ha semantica di effetto sullo stato: prima valuta il membro destro nello stato corrente, poi vi memorizza il risultato distruggendo il valore precedente; per questo «x <- x + 1» non è l'uguaglianza impossibile «x = x + 1», ma l'istruzione «incrementa x di 1». Un formalismo alternativo al diagramma di flusso è il diagramma strutturato di Nassi-Shneiderman, che rappresenta l'algoritmo come blocchi annidati anziché come nodi collegati da frecce: poiché non esistono frecce libere, i salti sono impossibili per costruzione e la struttura a blocchi della programmazione strutturata risulta immediatamente leggibile. Ogni buona pseudocodifica rispetta inoltre la regola dell'unico ingresso e unica uscita per ciascun blocco, che rende l'algoritmo componibile e verificabile pezzo per pezzo.

Approfondimento

La nozione intuitiva di «ordine di grandezza» si formalizza con la notazione O-grande (big-O), che descrive il comportamento asintotico del costo per n grande. Si scrive «f(n) = O(g(n))» quando esistono una costante «c > 0» e una soglia «n₀» tali che «f(n) ≤ c·g(n)» per ogni «n ≥ n₀»: g(n) è allora un limite superiore alla crescita di f, a meno di un fattore costante. Da questa definizione discende perché si trascurino le costanti moltiplicative e i termini di ordine inferiore: «3n² + 5n + 7» è «O(n²)», perché per n grande il termine quadratico domina. Accanto a O (limite superiore) si usano «Ω» (limite inferiore) e «Θ» (ordine esatto, quando O e Ω coincidono). La gerarchia degli ordini più comuni è «O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)», e passare da un ordine al successivo cambia radicalmente la scalabilità del programma. Il costo logaritmico della ricerca binaria si ricava dalla sua equazione di ricorrenza: a ogni passo il problema si dimezza al prezzo di un confronto, cioè «T(n) = T(n/2) + O(1)», che sviluppata dà «T(n) = O(log₂ n)» — dopo circa «log₂ n» dimezzamenti l'intervallo si riduce a un solo elemento. Resta il compromesso di fondo: la ricerca binaria è velocissima ma esige dati ordinati, e ordinare costa a sua volta almeno «O(n log n)»; conviene quindi solo quando la stessa sequenza, ordinata una volta, viene poi interrogata molte volte.