La soluzione algoritmica di problemi
Algoritmo: il concetto fondamentale e centrale dell'informatica

Algoritmo, dal dizionario Webster: dal matematico arabo AL-KHOWARIZMI (825 dc). Una procedura per risolvere un problema matematico (come trovare il massimo comune divisore) in un numero finito di passi che implicano frequenti ripetizioni di un'operazione. In senso lato una procedura che eseguita passo a passo risolve un problema. Per esempio, algoritmi (o procedure) per costruire modellini di aerei (espressi nei fogli di istruzioni) o per azionare la lavatrice o per suonare una melodia al piano (espressa in un insieme di simboli negli spartiti). Inizialmente il termine algoritmo indicava esclusivamente procedure per il calcolo, come appunto l'algoritmo di Euclide per trovare il MCD (Massimo Comun Divisore). Algoritmo di Euclide, una procedura per trovare, dati due numeri interi e positivi m e n, il più grande intero che li divide entrambi: dividere m per n, e sia r il resto della divisione (con 0 £ r £ n) se r = 0 allora la risposta è n e STOP porre m = n e n = r e ripetere il passo 1. La procedura prescrive che si divida il primo dei due numeri dati per il secondo, si effettui un controllo, eventualmente si proceda nell'assegnare valori diversi a dividendo e divisore, introducendo il resto della prima divisione, quindi si ripeta il ciclo. La domanda sul tappeto ora è: ma funziona davvero?, nel caso si dovesse ripetere il ciclo un numero elevato di volte siamo certi che prima o poi si arrivare ad un termine? Dapprima possiamo provare con una coppia di numeri positivi e vedere empiricamente se otteniamo il risultato voluto. Questo metodo non ci da una dimostrazione di correttezza della procedura, ma certamente se trovassimo una coppia di numeri per cui la procedura non funzionasse, allora potremmo dire che questa non è corretta. Proviamo, quindi, ad esempio con m = 119 e n = 544: passo1: 119 diviso 544 dà risultato 0 e resto r = 119 passo2: poiché r <> 0 allora passo3: poniamo m = 544 e n = 119 (si noti che questi primi passi sono serviti a invertire i due dati di ingresso) passo1: 544 diviso 119 dà resto r = 68 passo2: poiché r <> 0 allora passo3: poniamo m = 119 e n = 68 passo1: 119 diviso 68 dà resto r = 51 passo2: poiché r <> 0 allora passo3: poniamo m = 68 e n = 51 passo1: 68 diviso 51 dà resto r = 17 passo2: poiché r <> 0 allora passo3: poniamo m = 51 e n = 17 passo1: 51 diviso 17 dà resto 0 passo2: r = 0 allora il MCD è n = 17 Come si vede ripetendo il ciclo di istruzione 7 volte siamo giunti alla risposta cercata per la coppia di numeri (119, 544). Sarà sempre così? Per tutte le possibili coppie possiamo garantire che ci siano sequenze, ancorchè lunghe, che conducono alla risposta. O esiste una coppia di numeri per cui non ci si arresta mai nella regressione dei 3 passi e che darà luogo ad una sequenza infinita? Potremo parlare di algoritmo solo se questo è costituito da un insieme finito di istruzioni che dia luogo ad una sequenza finita di operazioni. In altri termini dobbiamo garantire che il processo termini dopo un numero finito di passi e che ogni passo sia definito precisamente, in modo che non ci siano ambiguità. Per l'algoritmo di Euclide si può dimostrare (ma occorre farlo prima di poter dire funziona!) che il processo termina in un numero finito di operazioni, se si osserva che la sequenza dei resti è una sequenza di numeri interi positivi decrescenti, che quindi raggiunge senza dubbio lo 0. Alcune procedure mancano di questa caratteristica di finitezza dei passi di esecuzione per tutti i possibili valori dei dati di ingresso e in questo caso non possiamo parlare di algoritmi. Ad esempio, il problema: dati due numeri n e m interi e positivi, trovare l'intero x che soddisfa n + x = m potrebbe essere risolto dalla procedura seguente: porre x = 0 calcolare n + x = q se q = m allora x è la risposta e STOP incrementare x di 1 e ritornare al passo2 Questa procedura non soddisfa il criterio di finitezza, che richiede che la procedura termini dopo un numero finito di passi, nel caso in cui la soluzione al problema sia negativa. Andrebbe inserito quanto meno un test dopo il passo 3 per consentire di interrompere la regressione infinita, nel caso in cui la procedura fallisca: se x + n > m allora STOP la procedura non produce alcun risultato La ricerca di algoritmi è stata una parte rilevante del lavoro del matematico nei secoli, anche prima dell'era dei computer. Perchè la presenza di algoritmi semplifica e rende più affidabile la soluzione dei problemi. Quando l'algoritmo è stato scoperto la sua esecuzione non richiede la comprensione dei principi su cui esso si basa, ma abilita chiunque lo segua esattamente a risolvere il problema. In un certo senso l'intelligenza per risolvere il problema sta nell'algoritmo e non nella sua esecuzione. È attraverso la definizione di algoritmi che rendiamo il computer capace di assolvere compiti complessi. Solo se troviamo algoritmi per affrontare i problemi possiamo pensare che una macchina li risolva.

Lezione 1. La soluzione algoritmica di problemi Copyright © 2002. Alberti. DSI, Università degli Studi di Milano.