I PROBLEMI E LE MACCHINE

I PROBLEMI E LE MACCHINE

Il termine informatica è una parola che ha voluto riunire i concetti di

informazione ^{e di} automazione ^{ed è la}

traduzione che si è data in Europa al vecchio termine anglosassone “computer science”

strumento per la

trasmissione

,

trasformazione

e

conservazione

dell’

informazione

intese come fatti di una certa realtà e codificati in

modo comprensibile alla macchina.

Risolvere un problema significa: “ricercare ed esprimere un elenco di istruzioni che, interpretate da un esecutore, conducono da determinate informazioni iniziali ad altre finali soddisfacenti un criterio di verifica”.

PROCEDIMENTO RISOLUTIVO DEL PROBLEMA

ESECUTORE DATI

INIZIALI

DATI FINALI (RISULTATI) CRITERIO DI VERIFICA

RISOLUTORE

In generale, il risolutore di problemi è guidato nella ricerca:

- dall’obiettivo di non contraddire il criterio di verifica;

- dalla sua esperienza, cioè dalle conoscenze già acquisite nella soluzione di problemi simili;

- da tecniche euristiche, cioè da criteri che si ritengono utili alla scoperta della soluzione, anche se non si sa bene come ciò possa avvenire.

A livello puramente intuitivo si può affermare che:

Un problema è ben formulato se:

• non è a priori evidente che non esistono soluzioni;

• il criterio di verifica della soluzione è univoco e si sa come applicarlo;

• l’insieme dei dati iniziali è completo, cioè non mancano dati.

Nella ricerca della soluzione dovremo necessariamente far riferimento a istruzioni eseguibili da un esecutore ed è quindi necessario fare delle ipotesi sulle sue capacità.

Esercizi e Problemi

1. Sono ben formulati i seguenti problemi:

a) Dimostrare che se A > 0 anche B > 0.

b) Dimostrare che se A > 0 e B > 0 anche A + B > 0.

c) Dimostrare che se A > B e B <= A allora A = B.

2. Giustificate la seguente affermazione:

“Ciò che è un problema per una persona può non

esserlo per un’altra”

Esercizi e Problemi

1. “Un pastore deve attraversare un fiume portando con sé un lupo, una capra e un cavolo. Egli può far uso di una barchetta che può ospitare solo un altro viaggiatore. Tenendo presente che il lupo tende a mangiare la capra e questa tende a mangiare il cavolo, cosa può fare il pastore per raggiungere il suo scopo?”

Quali sono i dati del problema? Qual’è il risultato? Qual’è la soluzione?

2. Trovare una soluzione al problema dei 3 cannibali e dei 3 esploratori.

similitudine

Esercizi e Problemi

“Un treno parte alle 9 da Milano con a bordo 12 persone; si ferma a Piacenza dove salgono 4 persone e ne scendono 5; si ferma poi a Bologna ove salgono 2 persone e non scende nessuno e giunge infine alle ore 17.43 a Roma.”

dettagli inutili

QUANTE FERMATE HA FATTO IL TRENO ?

Esercizi e Problemi

“A casa di un noto enigmista, Ugo Ics abitante in via Mauri, 36, si presenta un addetto del comune per dei rilevamenti statistici. Alla domanda sul numero dei figli e sulle loro età il signor Ics risponde: ‘Ho tre figli di cui due gemelli e caso strano il prodotto delle loro età coincide con il numero civico della mia abitazione”.

L’addetto, stando al gioco, fa alcuni conti e poi chiede nuove informazioni, poiché quelle date non sono sufficienti.

Il signor Ugo aggiunge allora che la somma delle tre età è dispari e, sorridendo, che il figlio maggiore ha gli occhi azzurri.

Quali sono le tre età dei figli del signor Ics ?

...ma non

sempre

Esercizi e Problemi

Ricevo da un amico questo messaggio:

“Sto partecipando ad una caccia al tesoro e devo risolvere questo problema:

occorre raccogliere esattamente 6 litri di 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 quant’acqua si vuole.

Trasmettimi al più presto via radio la soluzione che certo riuscirai a trovare.

Usa frasi semplici e brevi poiché la ricezione è disturbata e il tempo di trasmissione è limitato.

Ciao e grazie!”

necessità di

formalizzare

“un Algoritmo è un elenco finito di istruzioni univocamente interpretabili ciascuna delle quali deve essere precisamente definita e la cui esecuzione si arresta per fornire i risultati di una classe di problemi per ogni valore dei dati in ingresso”

Definizione astratta di algoritmo:

Consideriamo il problema:

“determinare il MCD (Massimo Comune Divisore) di due numeri naturali dati # 0”.

vedremo che per la sua soluzione potremo usare tre metodi diversi; per ciascuno di essi sarà necessario

fare delle ipotesi sulle capacità dell’esecutore.

1 1 3  

Algoritmo MCD1 (prima proposta)

istr.1] si scompongano i due numeri in fattori primi;

istr.2] si prendano in considerazione i solo fattori comuni;

istr.3] dei fattori comuni ottenuti si considerino quelli con esponente più piccolo;

istr.4] si moltiplichino fra loro i fattori individuati nei passi di esecuz. dell’istr.3] - il risultato è il MCD cercato.

E’ chiaro che qui si presume che l’esecutore sappia come si “ scompongono due numeri in fattori primi ^{”. Quali sono le altre capacità}

dell’esecutore?

Algoritmo MCD2 (seconda proposta)

istr.1] costruire l’insieme dei divisori del primo numero;

istr.2] costruire l’insieme dei divisori del secondo numero;

istr.3] costruire l’intersezione fra gli insiemi individuati nei passi di esecuzione delle istruzioni 1] e 2];

istr.4] cercare nell’insieme costruito nei passi di esecuz.

dell’istr.3] l’elemento più grande, esso è il MCD.

Quali sono le capacità dell’esecutore per

poter eseguire le istruzioni di MCD2 ?

Algoritmo MCD3 (detto “di Euclide”)

istr.1] dividere il primo numero per il secondo numero.

Chiamare r il resto della divisione;

istr.2] ser r = 0 hai finito: il secondo numero è il MCD;

istr.3] se r # 0 si operano i seguenti cambiamenti:

primo numero secondo numero;

secondo numero r;

istr.4] tornare all’istr.1].

Quali sono le capacità dell’esecutore per poter

risolvere il problema in questo caso ?

Requisiti del “buon esecutore” o Algoritmo

1.

Finitezza della descrizione.

Un algoritmo deve essere descrivibile con un numero finito di istruzioni.

2.

Non limitatezza dei dati in ingresso.

Si

escluderebbero tutti quei problemi che richiedono un numero superiore.

3.

Non limitatezza dei dati in uscita.

Analogamente agli ingressi, non si può porre nessun limite.

4.

Non limitatezza del numero dei passi eseguibili.

Imponendo un limite al numero dei passi eseguibili

(diciamo k) si escluderebbero gli algoritmi che richiedono n > k per la loro esecuzione.

5.

Definitezza.

Ad ogni passo di un algoritmo deve corrispondere una istruzione definita con precisione.

6.

Esistenza di un limite finito alla complessità delle istruzioni eseguibili.

Si devono escludere per es. operazioni del tipo: “conta il numero di volte che la sequenza di cifre decimali xyz compare nella espansione di p.

7.

Disponibilità per l’esecutore di una memoria

illimitata per conservare dati.

Non sarebbe possibile risolvere problemi del tipo: “data una lista illimitata di numeri positivi terminata da uno zero, produrre in uscita la stessa lista ordinata in modo crescente”.

8.

L’esecutore opera in modo discreto

. Opera cioè trasformazioni successive su insiemi di dati, separate da un intervallo di tempo finito.

9.

Terminazione o meglio (Sono ammesse

esecuzioni con un numero infinito di passi).

Certi procedimenti di calcolo possono in certe circostanze non terminare e vanno sotto il nome di metodi

computazionali. Una situazione di loop infinito può assumere un significato di incertezza rilevante sia dal punto di vista puramente matematico-logico, che da un punto di vista pratico.

metodo computazionale = algoritmo

Si consideri il seguente algoritmo per la divisione di due numeri con il metodo delle sottrazioni successive:

D e d (dividendo e divisore) sono interi non negativi istr.1] acquisisci dall’estreno D e d;

istr.2] assegna a Q il valore zero;

istr.3] se D<d allora hai finito: i risultati sono Q e D altrimenti vai alla 4];

istr.4] assegna a D il valore D - d;

istr.5] assegna a Q il valore Q + 1;

istr.6] ripeti a partire dall istr.3].

fare la traccia per D=3 e d=0;

loop infinito

Esercizi e Problemi

1. Descrivere l’abituale procedura usata per sottrarre due naturali A, B rappresentati nella notazione decimale.

Elencare le capacità ipotizzate per l’esecutore.

2. Costruire la tavola di traccia per l’algoritmo di Euclide con m (primo numero) = 770 ed n (secondo numero) = 175.

3. Riscrivere l’algoritmo di Euclide supponendo che l’esecutore non disponga dell’operazione di divisione.

L’esecutore è però capace di sottrarre due interi.

4. Possiamo definire “algoritmo” uno spartito musicale scritto in perfetto accordo con le regole della sintassi

Il matematico inglese Alan Turing fu il primo a dare una definizione concreta di algoritmo, costruendo per ogni

algoritmo una macchina chiamata: “macchina di Turing”:

OC = Organo di Controllo Elenco delle istruzioni

(programma)

Interprete delle istruzioni (esecutore)

--- ---

TLS = Testina di Lettura/Scrittura

Da un punto di vista funzionale, una MdT Z è una terna Z = {A, Q, P}

- A è l’alfabeto finito dei simboli leggibili/scrivibili - Q è l’insieme finito degli stati di OC

- P è l’insieme finito delle quintuple che ne descrivono il funzionamento (cioè il programma vero e proprio)

Ove una quintupla è:

stato attuale simbolo letto simbolo da scrivere nuovo stato direzione

<q

i

a

j

F(q

i

, a

j

) G(q

i

, a

j

) D/S>

MdT1: la macchina successore.

Problema: Progettare la MdT che, dato un numero scritto in notazione decimale, ne determini (e lo lasci scritto sul nastro) il successore.

In questo caso:

- A = {b, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Metodo: TLS esamina la cifra meno significativa e se essa e minore di 9 le aggiunge 1 e si ferma; se essa è uguale a 9 la sostituisce con 0 e passa a esaminare la cifra immediatamente a sinistra di quella appena trattata.

- Q = {q0, q1) dove q0 = 1 deve essere sommato

q1 = stato finale (1 è già stato sommato)

La configurazione iniziale comprende OC in stato q0 ad esempio:

Programma ESECUTORE

--- ---

Configurazione iniziale

1 2 9

OC in stato q0

Il programma o l’insieme di quintuple può essere costruito in maniera più compatta attraverso una “

MATRICE FUNZIONALE

”:

0 1 2 3 4 5 6 7 8 9 b

1 q1 D2 q1 D 3 q1 D 4 q1 D 5 q1 D 6 q1 D 7 q1 D 8 q1 D 9 q1 D 0 q0 S 1 q1 D

Definiamo una computazione di una MdT una sequenza finita di descrizioni istantanee di cui la prima sia iniziale e l’ultima finale, e ognuna ottenuta dalla precedente in un passo.

q0 q1

--- 1 2 0 ---

--- 1 3 0 ---

--- b 1 2 9 b ---

b b

b b

Esempio di computazione:

da ...

a ...

computazione

q0

q0

q1 ARRESTO

Prof. Filippo TROTTA 27

MdT: Verifica di parità

Progettare una MdT che produca un 1 se una stringa, costituita da 1 e 0 e terminata da $, contiene un numero dispari di 1, 0 altrimenti.

Sugg. A = {0, 1, $}, Q = {q

0

, q

1

, H}

dove q

⁰

= per la constatazione che gli 1 sono pari

q

1

= per la constatazione che gli 1 sono dispari H = stato finale

Metodo: partendo dallo stato

q

0, si muove progressivamente verso destra cambiando stato ogni qualvolta si incontra un 1.

Se quando incontra $ l’OC si trova in

q

0 scrive 0, altrimenti

Progettare una Macchina di Turing che accetti in ingresso una stringa di lunghezza arbitraria sull’alfabeto {0, 1, A, B, b } e restituisca in uscita la stringa di ingresso modificata secondo le seguenti regole:

1. I simboli A e B sono lasciati inalterati;

2. Se la stringa inizia con una sequenza di zeri e uni, tale sequenza è lasciata inalterata;

3. La sequenza di zeri e uni successiva ad un simbolo A è lasciata inalterata;

4. La sequenza di zeri e uni successiva ad un simbolo B viene complementata.

Esempio:

010ABAA1100BA11AAB010ABA produce in uscita

010ABAA1100BA11AAB101ABA

MdT: Individua B