il “problema dei secchi” Definire esattamente il testo del

LE STRUTTURE PRIMITIVE DELLA PROGRAMMAZIONE
Proposta di lavoro 1: il “problema dei secchi”
Ricevo da un amico questo messaggio:
"Sto partecipando ad una caccia al tesoro e devo risolvere questo problema:
Occorre raccogliere esattamente 6 litri d'acqua. Sono a
disposizione due recipienti non graduati e non graduabili in grado
di contenere uno 9 litri e l'altro 4. Si può attingere quanta acqua
si vuole.
Trasmettimi questa sera via radio la soluzione che sono certo riuscirai a
trovare.
Usa frasi semplici e brevi poiché la ricezione è disturbata e il tempo di
trasmissione è limitato.
Ciao e grazie!"
Definire esattamente il testo del messaggio da trasmettere
specificando a parte le motivazioni che vi hanno portato a
scegliere quella forma.
Risposta
Dall'esame del testo della proposta di lavoro appare evidente la presenza di
due problemi distinti che riguardano l'uno la ricerca delle soluzioni al quesito,
l'altro, che è sicuramente il più importante, la scelta del testo del messaggio e
la sua struttura.
Osserviamo inoltre che la problematica proposta da adito a diverse
interpretazioni e risulta quindi indispensabile costruirsi un modello restrittivo e
vincolante della situazione reale.
Nel nostro caso possiamo e dobbiamo evidenziare dei vincoli oggettivi
definibili chiaramente dal testo.
♦ I recipienti sono da 9 e da 4 litri.
♦ I recipienti non sono graduati e neppure graduabili.
♦ La ricezione è disturbata e il tempo di trasmissione è limitato.
♦ L'amico ha disposizione quanta acqua vuole.
Ma a questi vincoli occorre, se vogliamo completare il modello della
situazione in esame, aggiungere alcune ipotesi soggettive che in questo
caso scegliamo in modo arbitrario:
1
♦
♦
impossibilità da parte del nostro amico di rispondere via radio.
necessità di garantire al ricevente la possibilità di effettuare un controllo
sulle integrità del messaggio ricevuto.
Analizziamo a questo punto il quesito inviatoci dal nostro amico per poter
scegliere testo e struttura del messaggio.
Analisi del problema dei due contenitori
Se occorre ottenere 6 litri d'acqua dovrò ovviamente togliere 3 litri dal
recipiente grande inizialmente pieno fino all'orlo.
6 = 9 – (3)
Posso dunque riformulare il problema in esame nel modo seguente: far sì che
nel contenitore piccolo si possano versare dal grande esattamente 3 litri.
(3) = 4 - 1
Il problema è dunque: riuscire ad avere nel contenitore piccolo 1 litro d'acqua
o meglio riuscire ad ottenere in uno dei due contenitori 1 litro.
Per far ciò è sufficiente riempire il contenitore grande (da 9 litri) e toglierne
due volte 4 con il contenitore più piccolo.
1 = (( 9 - 4) - 4)
A questo punto basta ripercorrere al contrario ragionamento appena fatto per
trovare la sequenza delle operazioni da compiere.
Scelta del testo del messaggio da trasmettere
Per garantire la possibilità di un controllo da parte del ricevente su quanto
trasmesso abbiamo preferito:
♦ inviare una sola volta un messaggio chiaro piuttosto che più volte un
messaggio più breve ma di difficile interpretazione;
♦ racchiudere ogni azione tra due " parentesi logiche" che identificano
l'inizio e la fine dell'azione stessa;
♦ numerare ciascuna coppia di queste parentesi in modo da evidenziare la
collocazione dell'azione rispetto messaggio.
Ciò dovrebbe permettere al ricevente, anche in caso di parziale perdita del
messaggio, di ricostruirlo con maggiore felice facilità.
Considerati i vincoli oggettivi e soggettivi siamo in grado di scrivere la nostra
soluzione alla proposta di lavoro:
uno
due
tre
quattro
cinque
sei
sette
otto
nove
dieci
vuota i due contenitori
riempi il contenitore grande
riempi con il contenitore grande il piccolo
vuota il contenitore piccolo
riempi con il contenitore grande il piccolo
vuota il contenitore piccolo
vuota il contenitore grande nel piccolo
riempi il contenitore grande
colma con il contenitore grande il piccolo
nel contenitore grande
2 ha il 6 litri
fine uno
fine due
fine tre
fine quattro
fine cinque
fine sei
fine sette
fine otto
fine nove
fine dieci
Alcune note relative al testo del messaggio:
♦ Gli spazi tra le parole del testo corrispondono a pausa di diversa
durata tra le parole.
♦ Non sono presenti nel testo del messaggio simboli numerici o
grafici, dato che in trasmissione radio non sarebbero trasmissibili
se non nella loro corrispondente forma verbale. Si è fatta
eccezione per le maiuscole d'inizio frase e per gli “a capo” che
non vengono trasmessi ma utilizzati per un'evidente chiarezza
formale.
Formalizzazione tramite Diagramma a Blocchi
Estrapoliamo ora dal testo del messaggio la sequenza delle azioni che il
nostro amico deve realmente effettuare per ottenere il 6 litri utilizzando una
rappresentazione di tipo grafico (Diagramma a Blocchi).
INIZIO
Vuota i due contenitori
Riempi il contenitore grande
Colma con il contenitore grande il piccolo
Vuota il contenitore piccolo
Colma con il contenitore grande il piccolo
Vuota il contenitore piccolo
Vuota il contenitore grande nel piccolo
Riempi il contenitore grande
Colma con il contenitore grande il piccolo
FINE
3
Formalizzazione avanzata
Dati:
contenitore da 9 litri = A
contenitore da 4 litri = B
Repertorio:
Riempi contenitore X …………………………………….
Vuota contenitore X ……………………………………...
Travasa tutto il contenuto del contenitore X nel
contenitore Y finché il contenitore X non è vuoto……...
Colma con il contenuto del contenitore X il contenitore Y
finché il contenitore Y non è pieno ……………………..
Azioni :
V(A)
V(B)
R(A)
C(A,B)
V(B)
C(A,B)
V(B)
T(A,B)
R(A)
C(A,B)
R(X)
V(X)
T(X,Y)
C(X,Y)
Considerando che lo stato del sistema può essere descritto come una coppia
ordinata di valori rappresentanti il contenuto dei due contenitori (Acqua nel
contenitore da 9 litri, acqua nel contenitore da 4 litri) si può immaginare di
rappresentare il sistema inizialmente con i contenitori vuoti; quindi lo stato
iniziale è descritto dalla coppia (0,0). Ora si può operare sistematicamente
con tutte le possibili azioni del repertorio per analizzare tutti i possibili stati
dopo la prima operazione. Alla prima mossa si ha il seguente quadro:
Azione Stato finale
R(A)
9,0
R(B)
0,4
V(A)
0,0
V(B)
0,0
T(A,B)
0,0
T(B,A)
0,0
C(A,B)
??
C(B,A)
??
Dove l’operazione C(X,Y), se X è vuoto, non avrà mai termine.
Si potrebbe procedere sistematicamente, per ciascuno degli stati raggiunti
con la n-esima operazione, applicando ogni azione possibile (e sensata), e si
4
raggiungeranno tutti gli stati possibili alla n+1-esima operazione. In tal modo
si genererà l’albero di tutti gli stati possibili del sistema.
0,0
R(A)
R(B)
R(B)
9,0
T(A,B)
T(B,A)
C(A,B)
C(B,A)
0,4
C(A,B)
9,4
5,4
V(B)
Costruzione
in discesa (a
partire dallo
stato iniziale)
5,0
C(A,B)
1,4
V(B)
1,0
Costruzione
in salita ( a
partire dallo
stato finale)
T(A,B)
0,1
R(A)
9,1
Esplorazione
in profondità
C(A,B)
Esplorazione
in ampiezza
(per livelli)
6,4
Alcuni paradigmi di linguaggi dell’Intelligenza Artificiale sono improntati a schemi simili al
precedente. A seconda del tipo di costruzione dell’albero degli stati del problema si
possono privilegiare criteri per trovare la soluzione (se c’è) ottimale rispetto al numero
delle mosse (esplorazione in ampiezza), o con meno impiego di risorse di calcolo
(esplorazione in profondità).
Segue la mappa concettuale degli argomenti implicati nella presente proposta di lavoro.
5
6
Proposta di lavoro 2: La macchina del caffè
Prova a rappresentare i passi che deve compiere una macchina
automatica per la distribuzione del caffè una volta che sia stata
effettuata la selezione e già accettato il gettone.
La macchina, perfettamente funzionante, è dotata di due manopole
di selezione, di cui una permette di scegliere tra il caffè normale e
quello ristretto, e l'altra tra il caffè dolce o amaro.
La macchina si avvia sulla selezione indicata solo dopo
l'accettazione del gettone.
Fuori servizio
In funzione
Dolce Amaro
Normale
Ristretto
Risposta
Tra le ipotesi aggiuntive si immagina:
♦ che la macchina inizialmente sia funzionante;
♦ che l’utente prima effettui la sua selezione e successivamente inserisca il
gettone;
♦ che al termine del servizio la macchina possa determinare se è in grado
di effettuare un successivo prossimo servizio o se debba attivare la spia
del fuori servizio in seguito alla rilevata mancanza di qualche ingrediente.
7
Diagramma a blocchi
INIZIO
Cade il caffè nel miscelatore
Cade una dose
di zucchero
SI
Dolce ?
NO
Cade una dose
di acqua
SI
Ristretto ?
NO
Cadono due
dosi di acqua
Si attiva il miscelatore
Scende il bicchiere
Scende il prodotto
Si accende la spia
FUORI SERVIZIO
SI
NO
Finito un
ingrediente ?
FINE
Pseudocodifica.
Inizio Programma CAFFÈ;
cade una dose di caffè nel miscelatore;
se è scelto dolce allora
cade una dose di zucchero;
fine se
se è scelto ristretto allora
cade una dose di acqua
altrimenti
cadono due dosi di acqua;
fine se
si attiva il miscelatore;
scende il bicchiere nell'apposito scomparto;
scende il prodotto;
8
Si accende la spia
IN FUNZIONE
se è finito un ingrediente allora
si accende spia fuori servizio
altrimenti
si accende spia in funzione;
fine se
Fine Programma.
Proposta di lavoro 3: il gioco del Fan-Tan
In Cina, parecchi secoli fa, che ebbe origine un gioco il cui nome è Fan-Tan.
Esso si gioca su un tavolo con gli angoli numerati da 1 a 4. I
giocatori scommettono sui numeri 1,2,3,4 collocando le puntate
sull'angolo prescelto.
Terminate le puntate, il banco prende una manciata di piccoli semi
da un sacchetto e li pone in una ciotola al centro del tavolo.
Quindi, usando un bastoncino cavo, toglie dalla ciotola 5 semi alla
volta, finché il numero di semi presente nella ciotola è cinque o
meno di 5.
Il numero di semi rimasti determina l'angolo vincente.
Se il numero di semi rimasti è 5, il banco risulta essere l'unico
vincitore.
Rappresenta la procedura che scandisce le operazioni
compiute dal banco dall'inizio alla fine di una partita di gioco,
come se fosse un automa, senza però affrontare il problema
del rapporto tra puntate vincite.
Risposta
Le competenze del banco sono complesse, infatti si ipotizza che egli:
♦ sappia controllare la correttezza delle puntate; il gioco ha senso se se la
somma in ballo è sufficiente a pagare la puntata vincente; il tempo che
intercorre tra inizio del gioco e termine delle puntate è “ragionevole”;
♦ esegua il gioco (sa prendere una manciata di semi dal sacchetto, sa
toglierne cucchiaiate da 5 semi, sa individuare l’angolo vincente, cioè sa
contare fino a 5);
♦ ritiri le puntate perdenti e paghi le vincite.
9
Diagramma a blocchi
INIZIO
Apri il gioco
Accetta le puntate
Dichiara chiuse
le puntate
Prendi una manciata di semi
Ponila nella ciotola
Togli 5 semi
>5
Semi
rimasti
≤5
Raccogli tutte le
puntate
=5
≠5
Semi
rimasti
Raccogli le
puntate perdenti
Paga l’angolo
vincente
FINE
Pseudocodifica
Inizio Programma FAN-TAN;
comunica "Il gioco ha inizio. Signori, puntate! ";
accetta e controlla le puntate per un tempo finito;
comunica " Signori, le puntate sono chiuse ";
prendi una manciata di semi dal sacchetto;
ponila nella ciotola al centro del tavolo;
ripeti
togli con il bastoncino 5 semi dalla ciotola
finché restano 5 o meno di 5 semi;
10
se rimangono 5 semi allora
raccogli tutte le puntate
altrimenti
raccogli le puntate dagli angoli perdenti;
paga l'angolo vincente;
fine se
Fine Programma.
11
ELEMENTI DI SISTEMATIZZAZIONE
Linguaggio e metalinguaggio
Metalinguaggio = linguaggio per esprimere le regole di un linguaggio
Nel caso di un linguaggio naturale:
Il metalinguaggio è espresso con i termini del linguaggio stesso.
Nel caso di un linguaggio artificiale (di programmazione):
Il metalinguaggio è inciso nella struttura dell’esecutore,
cioè l’esecutore è definito tramite il suo repertorio.
ESECUTORE
UMANO
Linguaggio
naturale
?
ESECUTORE
MECCANICO
Linguaggio
artificiale
UOMO CON
PROBLEMA
Che cosa è un problema
Un problema nasce se un soggetto ha degli stimoli che lo spingono verso la
mèta e se è fallito un primo tentativo per raggiungerla.
Stimolo
intransitività
12
Mèta
1° passo: fase di riconoscimento (definizione del problema)
Risorse
Obiettivo
Risorse
Risorse
Realtà
Modello
Situazione
problemica
2° passo: fase analitica
♦ organizzazione delle risorse
♦ formulazione delle ipotesi
♦ scelta di un metodo risolutivo
3° passo: applicazione di un metodo
♦ ottenimento dei risultati
4° passo: analisi dello scostamento
♦ confronto OBIETTIVO / RISULTATO
5° passo: comunicazione dei risultati
♦ capitalizzazione esperienza
Una classificazione dei problemi
13
Problema
Come esempio di problema non algoritmizzabile si propone il 10° problema di
Hilbert: la funzione
1
se il polinomio a coefficienti
interi P(x1,x2,…,xn)
ammette soluzioni intere
0
altrimenti
f(x1, x2, …,xn) =
non è calcolabile, ossia non esiste un algoritmo che, dato P, decida il valore
di f.
Caratteristiche del procedimento risolutivo
eseguibile da “qualche esecutore” descritto in termini
Effettività
chiari e univoci
Finitezza di
successione finita di passi da eseguire
espressione
Finitezza di calcolo eseguibile in un numero finito di passi
ad ogni passo della procedura è definita una ed una sola
Determinismo
operazione da eseguire successivamente
Una sequenza di istruzioni che possieda le caratteristiche precedenti si
definisce:
ALGORITMO
Per istruzione si intende
♦ La descrizione dell’azione che deve essere eseguita per
raggiungere la mèta
♦ La parte minima dell’algoritmo comprensibile dall’esecutore
Definizione qualitativa di algoritmo:
♦ un algoritmo è un insieme ordinato di istruzioni, ciascuna delle quali deve
essere eseguibile da un dato esecutore (umano / meccanico)
(EFFETTIVITA’)
♦ le istruzioni debbono essere espresse in linguaggio NON AMBIGUO
♦ le istruzioni debbono essere in numero finito; ciascuna deve essere
terminata in un intervallo di tempo finito; l’esecutore deve poter terminare
in un tempo finito (FINITEZZA)
♦ in ogni fase dell’esecuzione il prossimo passo è determinato in modo
univoco (DETERMINISMO)
PROBLEMA
ALGORITMO
LINGUAGGIO
14
ESECUTORE
Esempi di algoritmi
1. calcolo del Massimo Comun Divisore di due numeri interi
2. calcolo del quoziente tra due interi di più cifre
3. reperimento del numero di telefono del sig. Rossi sull’elenco telefonico
4. una ricetta gastronomica
5. le istruzioni per fare un maglione con i ferri da lavoro
6. le regole del gioco di briscola
7. le istruzioni per il montaggio di uno scaffale
8. …
Linguaggi per esprimere algoritmi
♦ Linguaggio naturale
♦ Diagramma a blocchi
♦ Pseudocodifica (o Notazione Lineare Strutturata)
Diagrammi a blocchi
Per rappresentare algoritmi si può usare il linguaggio dei Diagrammi a
Blocchi.
INZIO
FINE
OPERAZIONE
LEGGI
X
?
BLOCCO DI INIZIO. Non ha ingressi, ma solo un'uscita. In
ogni D.aB. c'è un solo blocco di inizio.
BLOCCO DI FINE. Non ha uscita, ma solo ingressi. Anche se
in un algoritmo ci sono più terminazioni, è opportuno che in un
D.aB. ci sia solo un blocco di fine.
LINEA DI FLUSSO. Congiunge due blocchi. La freccia indica
la successione nell'esecuzione dei blocchi. Più linee possono
concorrere in un punto (detto “nodo”).
BLOCCO DI OPERAZIONE. Ha una sola uscita e almeno un
ingresso. Nel suo interno viene descritta un'operazione
eseguibile.
BLOCCO DI INPUT / OUTPUT. È una specializzazione del
blocco di operazione, in quanto rappresenta operazioni di
comunicazione con l'esterno. Nel suo interno può essere
descritta un'operazione di acquisizione dati (o input) o
un'operazione di emissione dati (o output).
BLOCCO DI DECISIONE. Ha uno o più ingressi, ma è l'unico
blocco che ha due uscite. Nel suo interno è contenuta una
domanda che può avere solo due risposte (vero o falso). Il
flusso continua in quella direzione che corrisponde alla
risposta. Decisioni multiple possono essere ricondotte a
decisioni binarie.
15
A
BLOCCO DI RIFERIMENTO. Non corrisponde a nessuna
operazione, ma è un utile simbolo per riferirsi ad un punto del
di D.aB. (per esempio per andare a pagina nuova). Può avere
solo ingressi senza uscite o solo un’uscita senza ingressi, o
può avere uno o più ingressi e un’uscita.
I Diagrammi a blocchi sono facili da interpretare e semplici da usare; per
problemi elementari sono uno strumento molto espressivo e da utilizzarsi
proficuamente in classe.
Pseudocodifica
I Diagrammi a blocchi non vanno bene per problemi complessi perché si fa
difficoltà a seguire la loro logica; inoltre non sono univoci.
Il difetto principale però consiste nel fatto che nascondono i costrutti
effettivamente usati nel pensare gli algoritmi. Infatti sia il caso di una
decisione (si segue una sola tra due strade “in discesa”) sia il caso di una
iterazione (si ripete un blocco di istruzioni fino al verificarsi di una condizione,
e quindi si “torna ad un punto precedente”), nel linguaggio dei D.aB. sono
ugualmente espressi in termini di “blocco di decisione”.
Il linguaggio della pseudocodifica esprime in modo esplicito tale diversa
situazione, usando apposite parole chiave.
Le tre proposte di lavoro riguardano i tre costrutti fondamentali: sequenza,
decisione e ciclo.
Come riconoscere e tradurre i costrutti fondamentali
E' necessario riconoscere le espressioni del Linguaggio Naturale che
rimandano ai costrutti fondamentali:
• sequenza
• decisione
• ciclo
per poterli tradurre in corrette espressioni della Pseudocodifica
Alcune espressioni del Linguaggio Naturale
Sequenza
;
,
.
E
Quindi
Allora
Decisione
Se … allora
Quando
Nel caso in cui
A condizione che
Controllo (attenzione!)
Solo per
16
Ciclo
Ripeti … fino a che
Fintantoché
Mentre
Per x volte
Continua
Controllo (attenzione !)
Ma
Talvolta
<Gerundio>
E così via
Rifai
Procedi
Per tutti
Per ciascuno
Eccetera
<Gerundio>
Espressioni corrispondenti della Pseudocodifica
Sequenza
Decisione semplice
Inizio
Se <condizione> allora
Fine
<sequenza>
FineSe
Decisione con
alternativa
Se <condizione> allora
<sequenza1>
Altrimenti
<sequenza2>
FineSe
Decisione multipla
Nel caso in cui
<variabile>
Ciclo non enumerativo con controllo in testa
Mentre <condizione>
<sequenza>
FineMentre
Ciclo non enumerativo con controllo in coda
Ripeti
<sequenza>
Finché <condizione>
Ciclo enumerativo
Per <variabile>=<Valore1> a <Valore2> passo
<valore3> fai
<sequenza>
FinePer
<valore1>:<sequenza>
<valore2>:<sequenza>
…
FineCaso
17