Approccio induttivo e deduttivo

Sviluppare software significa creare applicazioni per sistemi informatici attraverso una attività creativa che fa uso di metodologie tecniche e progettuali ed è supportata da strumenti software di sviluppo.

Cosa si intende per attività creativa? Significa che non esiste una procedura meccanica, una metodologia sempre identica per risolvere qualunque tipo di problema. Ogni problema infatti richiede una soluzione specifica, un procedimento particolare che porta ad una determinata sequenza di istruzioni che risolvono quel determinato problema. Ogni problema è diverso, diversa l’idea che bisogna sviluppare e diverso quindi l’algoritmo prodotto.

Conoscere un linguaggio di programmazione ed i principi di funzionamento di un computer sono necessari, ma non sufficienti.

La realizzazione di un programma è “un’arte” che combina creatività, tecnica e metodologie, e la soluzione è a tutti gli effetti una invenzione artigianale. 

Questo processo creativo si compone di due fasi di ragionamento: il pensiero induttivo per analizzare un problema, ed un processo deduttivo per creare un algoritmo ed un programma.

In questa lezione vedremo diversi strumenti di ragionamento e di metodologia a supporto di questo processo. Resta fondamentale capire che la capacità di produrre creativamente programmi si sviluppa principalmente con l’esercizio continuo: è tramite la pratica costante che si sviluppa quell’elasticità mentale che rende possibile affrontare un sempre maggior numero di problemi e trovare una soluzione.

Pensiero induttivo

Col pensiero induttivo il programmatore parte da un insieme di informazioni in suo possesso (ad esempio il testo di un esercizio, o un insieme di richieste del committente, o un funzionamento spiegato per esempi o altro ancora) e, tramite un processo di ragionamento logico, detto induzione, arriva alla produzione di leggi o regole generali.

E’ sempre necessario arrivare a regole generali: un algoritmo per computer infatti non si basa su casi particolari, ma deve funzionare per qualsiasi insieme di dati che gli viene sottoposto per quello specifico problema.

Obiettivo del processo induttivo è quindi quello di di analizzare un determinato problema da risolvere e a partire da un insieme di esempi concreti costruire una soluzione generale (detta modello) che vada bene sia per gli esempi ricevuti sia per qualsiasi tipo di dato compatibile con quel problema.

Per capire questo concetto partiamo da un problema concreto, dobbiamo trovare un modello generale per calcolare la circonferenza del cerchio a partire dal diametro. Certo noi sappiamo già come si calcola ma ipotizziamo di non averlo studiato a scuola e vogliamo scoprirlo per conto nostro. Partiamo quindi dal presupposto che ci serve una regola generale che ci permetta di calcolare la circonferenza dato il raggio, in modo tale da non doverlo fare ogni volta a mano.

Per risolvere questo problema in modo induttivo dobbiamo trovare una regola generale che ci possa aiutare. Per farlo dobbiamo quindi partire da un un insieme di circonferenze che disegneremo in un foglio (ad esempio con un goniometro) e misurare per ciascuna di esse la relativa circonferenza ed il diametro e vedere se c’è qualche correlazione. Qui un esempio di valori misurati concretamente:

E così via. Se proseguiamo con le prove, notiamo che il rapporto tra diametro e circonferenza (al netto di errori di misura) non cambia qualsiasi sia il raggio ed è approssimabile ad un valore che è circa 3,141. Per essere sicuri possiamo anche disegnare nuove circonferenze non misurate a mano, fare il calcolo e verificare che effettivamente questa regola è sempre valida.

Ecco, abbiamo creato il nostro primo modello a partire da un problema concreto, che possiamo sintetizzare con la grafica seguente.

Ora proviamo a fare un esempio più complesso, che ha sempre a che fare con il pi greco, ma che ha come obiettivo quello di semplificare un calcolo con una regola generale.

E’ possibile calcolare pi greco π tramite un prodotto di frazioni crescenti detto prodotto di Wallis ^[1]

maggiore è il valore di n, più precisa l’approssimazione di π.

Ci viene quindi richiesto di scrivere un programma che dato n ci calcoli una approssimazione di pi greco.

Certo una soluzione potrebbe essere quella di calcolare tutti i moltiplicandi di questa espressione e poi di moltiplicarli tra loro. Questo algoritmo funziona ma è molto inefficiente perché ci costringe ad enumerare ogni moltiplicando, con n molto grande sono un gran numero di operazioni.

Proviamo quindi a cercare una qualche regola generale per costruire la nostra moltiplicazione. Proviamo quindi a riscrivere l’espressione nel seguente modo:

Come si vede ogni coppia ha questa struttura: 

che è immediatamente verificabile con l’esempio per i = 2,4,6,8,…

Quindi il prodotto si può semplificare con una espressione, chiamata produttoria^[2], dove ogni elemento dipende da un indice i che va da 2 a n con passo 2 (quindi 2,4,6,8, …).

Proviamo a vedere un terzo esempio. Ci è richiesto di scrivere un programma che dati due numeri a e b, ne calcoli il minimo comune multiplo. Come noto mcm è il più piccolo numero che è multiplo sia di a che di b. Ad esempio:

Una soluzione al problema consiste nel procedere per tentativi con i multipli del numero più grande fino a quando non se ne trova uno che è multiplo anche del più piccolo. Questo algoritmo, formalmente corretto, può essere efficace in alcuni casi (per 24 e 36 per esempio ci basta 1 tentativo) ma molto oneroso in altri (13 e 17 hanno bisogno di ben 13 tentativi) col risultato che in generale un algoritmo di calcolo di questo tipo è piuttosto inefficiente nella maggior parte delle situazioni.

Proviamo ancora una volta a vedere se esiste una qualche regola che ci aiuti a ridurre il numero di operazioni.

Possiamo infatti osservare dalle coppie di numeri che esiste una correlazione tra i nostri numeri a e b ed il loro mcm. Ad esempio 24 e36 hanno “qualcosa” in comune che invece 13 e 17 non ne hanno. Questo qualcosa sono i fattori che hanno in comune. Vediamolo scomponendo 24 e 36 in fattori primi:

Ora vediamo 13 e 17:

Come si può vedere:

– mcm ha tutti i fattori primi NON comuni tra a e b;

– mcm ha tutti i fattori primi COMUNI tra a e b (cioè è multiplo di tutti i fattori primi presenti sia in a che b) presi però una volta sola;

– mcm NON ha fattori primi non presenti in a o b;

Andiamo quindi a verificare le nostre ipotesi in altri casi.

1) 15 e 18 hanno rispettivamente [5,3] e [3,3,2] come fattori primi. Quelli comuni sono [3] e quelli non comuni sono [5] e [3,2]. Ci dobbiamo quindi aspettare che l’mcm sia il prodotto di [5,3,3,2] ovvero 90. 

2) 14 e 20 hanno rispettivamente [7,2] e [5,2,2] come fattori primi. Quelli comuni sono [2] e quelli non comuni sono [7] e [5,2]. Mcm è quindi dato dal prodotto di [2,7,5,2] ovvero 140. 

3) 36 e 48 hanno rispettivamente [3,3,2,2] e [3,2,2,2,2]. Comuni [3,2,2] e non comuni [3] e [2,2]. Il risultato sarà quindi [3,2,2,3,2,2] cioè 144.

Questa regola ci consente quindi di trovare molto rapidamente una soluzione anche per numeri molto grandi.

Conclusioni

Da questa procedura possiamo quindi capire in cosa consiste l’analisi del problema tramite induzione.

Questo procedimento si può quindi descrivere nel seguente modo:

1) Si cerca di individuare delle proprietà non immediatamente enunciate dal problema iniziale: si chiamano “ipotesi aggiuntive” ed allargano le nostre conoscenze sul problema partendo dall’osservazione di esempi concreti di dati da elaborare.

2) Questa conoscenza aggiuntiva ci permette di fare delle ipotesi sulle correlazioni tra gli esempi a disposizione (nella formula di Wallis si nota una correlazione tra coppie di prodotti, nell’mcm le correlazioni tra fattori).

3) A questo punto si propone una regola generale, che va nuovamente verificata con i dati iniziali ma anche con nuovi dati per validarla.

Il terzo punto è molto importante, perché può anche accadere che esistano delle correlazioni tra i dati presi ad esempio, ma che non sono valide in generale perché i dati di esempio sono in qualche modo viziati da qualche problema di correlazione tra loro.

Per capirlo leggiamo la breve storia triste del tacchino induttivista^[3]:

Il tacchino osservava che nella fattoria in cui viveva gli veniva dato cibo ogni mattina ed ogni sera. Ma siccome lui conosceva il metodo induttivo, non trasse immediatamente conclusioni. Osservò che il cibo gli veniva dato anche se pioveva o c’era il sole, che veniva servito anche la domenica e nei giorni di festa, che facesse freddo o caldo. Annotava ogni circostanza collegata all’erogazione di cibo e invariabilmente osservava che il cibo veniva fornito sempre e comunque, ogni mattina ed ogni sera. Alla fine fu soddisfatto di ogni esperienza fatta ed arrivo alla generalizzazione che “il cibo viene sempre dato mattina e sera”.

Una generalizzazione che si rivelo tuttavia errata. Infatti il giorno dopo era la vigilia di Natale.

Da questa storiella dobbiamo imparare quindi che ogni nostra generalizzazione non vale “sempre” ma soltanto ” fino a prova contraria” e che il metodo induttivo è valido ma non infallibile.

Quando si sviluppa il software è necessario creare un modello generale che rappresenta il problema da risolvere. E’ necessario inoltre che il modello sia valido qualsiasi sia l’input del problema e quindi dobbiamo verificarlo coi dati a nostra disposizione, ed anche con nuovi dati, per capire se effettivamente la soluzione individuata ha senso.

Pensiero deduttivo

Ottenuta la generalizzazione del problema, ovvero un modello, si passa alla fase successiva: realizzare un programma che traduce il modello in codice. 

In questo caso entra in gioco il processo deduttivo: a partire da un modello si procede per passi allo sviluppo del programma finale:

1) Derivare dal modello generale l’algoritmo;

2) Implementare l’algoritmo in un programma codificato;

3) Verificare il programma con gli input.

4) Se ci sono errori, correggere il programma.

Il metodo deduttivo si basa sul concetto di sillogismo ^[4] che possiamo spiegare con questo esempio: 

• tutti gli studenti che studiano prendono la sufficienza
• lo studente Mario studia
• Quindi Mario prende la sufficienza

Il sillogismo è un procedimento che consiste nel ricavare nuova informazione non a partire dai dati concreti, ma da precedenti affermazioni generali, tramite un collegamento tra queste. E’ un procedimento che si basa sulla pura logica, che mette insieme sia le nostre conoscenze per esempio di programmazione (espressioni, condizioni, cicli, variabili, strutture dati, ecc.) con quelle del problema (la formula semplificata di Wallis, il calcolo dei fattori primi, ecc.)

Vediamo cosa significa concretamente.

Nell’esempio del prodotto di Wallis eravamo giunti a questa conclusione:

Ovvero:

• il prodotto finale è un prodotto di espressioni che dipendono da un valore i
• i va da 2 a n con passo 2 (2,4,6,8,…)
• Quindi per ogni i calcoliamo l’espressione e la moltiplichiamo per il prodotto parziale. 

A questa regola associamo quanto già sappiamo dei cicli:

• un ciclo è una sequenza di operazioni di ripetute;
• un ciclo ad iterazione definita è un tipo di ciclo dove possiamo usare un indice i che va da X a Y con passo Z.

Correliamo tramite sillogismo queste due conoscenze che abbiamo:

• è possibile fare un ciclo ad iterazione definita da i=2 a n con passo 2.

Ecco il nostro algoritmo di calcolo.

A questo punto si passa all’applicazione tecnica dell’algoritmo, che dipende dal linguaggio di codifica e dai particolari costrutti sintattici del linguaggio. 

In questo caso una soluzione in C++ sarà (si omettono header e direttive):

int main() {
    double i, n, pi=1;
    cout << "Inserisci valore n:";
    cin >> n;
    for (i = 2; i<=n; i+=2) {
        pi = pi * (i / (i-1)) * (i / (i+1));
    }
    pi = 2 * pi;
    cout << "Il valore di pi con approssimazione " << n << " è: " << pi << endl;
    return 0;
}

Il programma va poi eseguito e va verificato se effettivamente risolve la problematica che ha generato quel modello. Per farlo dobbiamo sperimentarlo con gli esempi a nostra disposizione, facendo molta attenzione a proporre al programma un set valido di esempi che copra anche situazioni particolari.

Vediamo un altro esempio, quello del mcm. Come sappiamo questo è dato da:

– fattori primi comuni;

– fattori primi non comuni.

Una soluzione intuitiva è quella di calcolare i fattori primi di ciascun numero e fare tre liste, quella di quelli comuni, quelle dei non comuni e infine moltiplicare tutti i fattori insieme. Questo approccio, per quanto funzionante, è piuttosto “brutale” in quanto produce un algoritmo inefficiente che richiede molto calcolo (bisogna infatti calcolare i fattori primi di ciascun numero) e molta memoria (per memorizzarli da qualche parte). 

Possiamo usare un altro approccio che sfrutta alcuni sillogismi. Come sappiamo infatti:

– un mcm è il prodotto dei fattori primi comuni di a e b;

– un mcm è il prodotto dei fattori primi non comuni;

Ma questo vuol dire che:

• se il numero x è fattore primo di a ma non di b, allora è fattore primo anche di mcm
• se il numero x è fattore primo di b ma non di a, allora è fattore primo anche di mcm
• se il numero x è fattore primo sia di a che di b, allora è fattore primo anche di mcm

Inoltre:

• qualsiasi numero i (da 2 in avanti) è fattore primo di un numero K se K è divisibile per i. K viene poi diviso per K e si ricomincia. Se non è divisibile per i, allora i=i+1 e si ricomincia.

Da queste considerazioni, possiamo ricostruire mcm procedendo in modo incrementale:

1) si parte da i=2 e mcm=1

2) se i è divisore di a o b, allora mcm = mcm * i. Si divide a o b o entrambi per i.

3) altrimenti si incrementa i=i+1

4) se a=1 e b=1 abbiamo finito, altrimenti si torna al punto 2

Si tratta di un ciclo ad iterazione indefinita, dove la variabile sentinella è data a e b.

Qui il codice C++:

int main() {
    int a,b;
    cout << "Inserisci a: ";
    cin >> a;
    cout << "Inserisci b: ";
    cin >> b;
    int mcm = 1;
    int factor = 2;
    while (a > 1 || b > 1) {
        if (a%factor == 0 && b%factor == 0) {
            mcm = mcm * factor;
            a = a / factor;
            b = b / factor;
        } else if (a%factor == 0) {
            mcm = mcm * factor;
            a = a / factor;
        } else if (b%factor == 0) {
            mcm = mcm * factor;
            b = b / factor;
        } else {
            factor++;
        }
    }
    cout << "Il mcm è: " << mcm << endl;
    return 0;
}

Per esercizio, testare con diverse coppie di valori per verificare la correttezza dell’algoritmo. 
Questa soluzione è molto efficiente, usa un solo ciclo, non memorizza nulla. 

Conclusioni

La programmazione è un processo deduttivo, che a partire da un modello deduce un programma che è derivato dal modello stesso.

La sua trasposizione in uno specifico linguaggio è invece una pura attività tecnica che richiede competenze specifiche ma che non ha alcun valore se dietro non c’è una conoscenza dei principi ed i fondamenti della programmazione.

In altre parole la sola conoscenza di linguaggi ci da accesso solo a dei formalismi, ma senza la capacità di utilizzare i processi induttivi e deduttivi non siamo in realtà in grado di programmare.

Inoltre ogni linguaggio per sua natura privilegia o penalizza alcuni o altri aspetti della programmazione. Per questa ragione saper programmare significa non dipendere da uno specifico linguaggio coi suoi limiti e peculiarità, ma padroneggiare diversi linguaggi in modo da non dipendere da specificità tecniche.

^[1] https://it.wikipedia.org/wiki/Prodotto_di_Wallis

^[2] In matematica la produttoria è una operazione che sintetizza una moltiplicazione di fattori, che usa il simbolo ∏ seguito da due indici: la variabile con valore iniziale e il valore finale. Qui un riferimento: https://it.wikipedia.org/wiki/Produttoria

^[3] Si tratta di una celebre metafora del Karl Popper, intesa a spiegare i limiti del processo induttivo.

^[4] Il sillogismo e la stessa logica sono frutto del pensiero del filosofo Aristotele.