La programmazione e la soluzione dei problemi: il concetto di algoritmo.

La programmazione e la soluzione dei problemi: il concetto di algoritmo.

Fin da piccoli, tutti noi abbiamo appreso la nozione di problema: un quesito

cui si deve dare una risposta, detta soluzione del problema. Sappiamo anche

che quando si pone un problema a qualcuno si suppone che questi non conosca

già la soluzione: il problema deve cioè richiedere uno<< sforzo>> mentale da

parte del risolutore. Questo lavoro mentale è detto <<processo di risoluzione>>

e consiste nella ricerca della soluzione. La nozione di ricerca richiama quella di

tentativo: la soluzione viene cercata per tentativi ( non necessariamente scelti

<<a caso>>). Se un tentativo fallisce si <<torna indietro>> per tentare un'altra

strada sfruttando, eventualmente, una parte della soluzione scartata. Per alcuni

aspetti risolvere un problema è un pò come muoversi in un labirinto: si cerca la

soluzione (l'<<uscita>>) per tentativi.

Come in un labirinto ci possono essere diverse strade che portano all'uscita, così

un problema può ammettere diverse soluzioni. Alcune possono essere ritenute

migliori di altre. Ad esempio, nel caso del labirinto, sarà conveniente scegliere il

percorso più breve.

Infine, così come in un labirinto potrebbe non esistere alcun modo di raggiungere

lìuscita, così un problema potrebbe non avere soluzione: alcuni problemi possono

non essere risolvibili.

Prima di procedere oltre è meglio indagare, attraverso tre esempi, su quello

che intenderemo esattamente per soluzione di un problema. Questo ci permetterà

anche di restringere la nozione di problema agli ambiti di interesse della

programmazione.

Problema LCC. Problema del Lupo, della Capra e de Cavolo.

<<Un contadino deve attraversare un fiume portando con sè un Lupo, una Capra e un Cavolo. Egli dispone però di una barca che può portare uno solo dei tre suddetti <<passeggeri>> oltre a se stesso. Trovare una sequenza di azioni per portare il Contadino sull'altra sponda con le sue cose tenendo presente che, in assenza del Contadino, il Lupo mangerebbe la Capra e la Capra mangerebbe il cavolo>>. Dopo alcuni tentativi, tutti noi siamo in grado di proporre una soluzione come questa:

esegui in sequenza:

Porta la capra sull'altra sponda;

Torna indietro;

Porta il cavolo sull'altra sponda;

Porta indietro la capra;

Porta il lupo sull'altra sponda;

Torna indietro;

Porta la capra sull'altra sponda.

La soluzione consiste dunque di un elenco di istruzioni, dirette ad un ipotetico esecutore (in questo caso il contadino) in grado di comprenderne il significato e di eseguirle. La frase iniziale<< esegui in sequenza>> era implicitamente richiesta dal testo del problema ma si è qui voluto esplicitare anche questo aspetto della soluzione. In prima approssimazione potremmo dunque già affermare:

Soluzione di un problema= istruzioni per un esecutore.

La soluzione è quindi qualcosa che può essere eseguita: la sequenza di azioni svolte dall'esecutore è nota come<<processo di esecuzione>>. Ogni azione viene prodotta da un esecutore per effetto dell'esecuzione di una determinata istruzione:

Azione= istruzione + esecutore.

Le azioni dell'esecutore vanno distinte dalle azioni svolte dal risolutore per trovare la soluzione. Il processo di risoluzione va cioè distinto da quello di esecuzione. Da un punto di vista concettuale, esecutore e risolutore sono due agenti distinti. Nela caso specifico, il contadino potrebbe chiedere ad un'altra persona di risolvere il problema. Questa agirebbe quindi da stupido e pedissequo esecutore della soluzione fornita per iscritto dal risolutore. Di fatto, nella vita di ogni giorno, tutti noi ci troviamo di fronte a molte situazioni problematiche in cui svolgiamo alternativamente (o contemporaneamente) il duplice ruolo di risolutori e di esecutori. Alla base della programmazione c'è invece la necessità di distinguere nettamente questi ruoli. Il ruolo di risolutore viene svolto dal programmatore mentre quello di esecutore può essere svolto da una <<macchina>> (autonoma esecutore) nel qual caso si parla di ESECUTORE AUTOMATICO.

Problema EQUAZ. Consideriamo ora un noto e semplice problema di algebra:

Data l'equazione aX+b=0 trovare la sua radice (supponiamo, per semplicità, che sia a\neq0).

In questo caso, applicando le regole dell'algebra, un risolutore trova che X=-b/a è la soluzione del problema dato. Cerchiamo tuttavia di esprimere la soluzione come elenco di istruzioni dirette ad un ipotetico esecutore (1) cui corrispondono altrettante azioni elementari:

esegui in sequenza:

INFORMATI sui valori di a e di b;

Calcola -b;

Dividi quello che hai ottenuto per a e chiama X il risultato;

Comunica il valore di X.

Rispetto all'esempio precedente si osserva una sostanziale differenza: l'esecutore chiede ad un ipotetico agente esterno di comunicargli delle informazioni, cioè, nel caso specifico, i valori dei due coefficenti a eb dell'equazione. In conseguenza di questa comunicazione l'esecutore produce a sua volta una comunicazione, detta <<risultsto>> (la radice dell'equazione). Si osservi che ora la sequenza di istruzioni non risolve uno specifico problema ma ogni problema ottenuto assegnando ad a e b dei particolari valori. In altre parole, si devono fornire all'esecutore delle <<informazioni iniziali>> (dette parametri o dati di ingresso) necessarie a particoleggiare (istanziare, in gergo) il problema. Di conseguenza l'esecutore fornisce una o più informazioni finali (dette risultati o dati di uscita) che devono soddisfare un criterio di verifica insito nel testo del problema. Nel nostro caso si chiede che il risultato soddisfi l'equazione. Applicare il criterio di verifica consiste quindi nel verificare che aX+b=0, sostituendo ad a e b i dati di ingresso e ad X il dati in uscita (risultato). Queste operazioni di comunicazione dall'esterno o verso l'interno sono chiamate in informatica rispettivamente operazioni di (lettura) e di (scrittura). D'ora in poi useremo dunque i termini (leggi) in luogo di INFORMATI e scrivi in luogo di COMUNICA:

INFORMATI=leggi

COMUNICA=scrivi

In definitiva questo problema si differenzia dal primo perchè ci dà la possibilità di apprezzare la differenza fra risultati e soluzione:

RISULTATI\neqSOLUZIONE

I risultati sono infatti le informazioni prodotte da un esecutore cui venga chiesto di applicare una certa soluzione (trovata da un risolutore) a particolari dati di ingresso. Questo concetto è ben noto agli insegnanti di matematica: nella correzione di un compito essi distinguono tra errori di metodo ed errori di calcolo. Nel primo caso si attribuisce un errore al <<risolutore>> del problema. Nel secondo, ritenuto generalmente meno grave, l'errore viene attribuito all'<<esecutore>> che ha sbagliato l'instanzazione dei parametri o i calcoli (<<il metodo è giusto ma i risultati sono sbagliati>>). In informatica, al termine <<metodo>> si preferisce quello di algoritmo. Inizialmente, questo termine veniva usato solo per indicare regole di calcolo per operazioni su rappresentazioni decimali dei numeri. Il termine <<algoritmo>>, deriva con molta probabilità, da quella del matematico persiano Al-Khuwarizmi (sec.VIII d.C.) cui vennero attribuite le regole per il calcolo delle quattro operazioni su numeri rappresentati in decimale. Oggi esso ha un significato più esteso che sarà esposto con rigore solo nella prossima sezione. Tuttavia, in modo approssimativo, possiamo già dire che:

un ALGORITMO è un elenco di istruzioni la cui esecuzione consente di conoscere alcune informazioni finali in dipendenza di alcune informazioni iniziali.