ALGORITMI
E
MACCHINE DI TURING
1
algoritmi
fondamenti di informatica:
imparare a risolvere problemi di vario genere
con le
tecniche proprie dell’informatica, e quali problemi sono
risolubili...
... da Aho & Ullman (fondamenti di informatica) :
l’informatica e’ la scienza dell’ astrazione
->cioe’ studia come
creare il giusto modello per un problema e
individuare le tecniche appropriate per risolverlo in modo
automatico (con l’aiuto del calcolatore)
2
algoritmi
3
(continua citazione da Aho Ullman):
La fisica studia il funzionamento del mondo reale non cerca di creare un mondo con leggi fisiche piu’semplici o
piu’piacevoli o piu’adatte agli interessi del signor Bronsky
L' informatica crea astrazioni del mondo reale che possano
essere rappresentate e manipolate in un elaboratore.
Un modello di macchina per “elaborare dati” o per “eseguire
procedure di calcolo” e’ la “macchina” di Turing.
La macchina di Turing e' un formalismo per definire
procedimenti di calcolo o algoritmi.
algoritmi
4
fondamenti di informatica quindi presenta (oltre alle informazioni di contorno [ambiente HW/SW] )
modelli dati, strutture dati, algoritmi
(c’e’ un libro di Niklaus Wirth che si chiama appunto “Algoritmi + Strutture Dati =
Programmi”)
modelli di dati
- sia come astrazioni di dati in vari problemi
- sia come astrazioni di dati disponibili in un linguaggio di
programmazione (Pascal,C++,Java,...)
strutture dati: nel caso il modello dei dati del problema da
risolvere non ha corrispondenza in uno dei modelli dati del
linguaggio usato, allora dovremo rappresentare il modello
dati del problema con meccanismi di astrazione presenti nel
linguaggio (Pascal,C++,Java,...)
algoritmi
5
Per risolvere un problema “generico” con il calcolatore e’
necessario conoscere almeno un linguaggio (comprensibile al
calcolatore) in cui scrivere la soluzione del problema cioe' il
programma; quindi e’ necessario:
* imparare un linguaggio di programmazione
(grammatica, vocabolario, significati)
in cui scriveremo i nostri programmi
* imparare cosa puo’ fare un calcolatore e come lo fa
* imparare alcune tecniche di risoluzione di problemi
abbastanza semplici, e
* imparare a usare queste tecniche per risolvere problemi
piu’ complicati ...
algoritmi
ALGORITMO
=
una lista di istruzioni (una ricetta)
da eseguire (con una macchina o da una persona)
per risolvere un problema.
6
7
algoritmi
o procedure di calcolo:
alcuni discorsi (brevi)
sulla definizione e
sui limiti
di un processo di calcolo formalizzabile.
8
algoritmi
o procedure di calcolo:
alcuni discorsi (brevi)
sulla definizione e
sui limiti
di un processo di calcolo formalizzabile.
9
algoritmi
o procedure di calcolo:
alcuni discorsi (brevi)
sulla definizione e
sui limiti
di un processo di calcolo formalizzabile.
10
algoritmi
o procedure di calcolo:
alcuni discorsi (brevi)
sulla definizione e
sui limiti
di un processo di calcolo formalizzabile.
algoritmi
1.o esempio di algoritmo:
problema:
decidere se
a>b ?
decidere se a e’piu’ grande di b,
con a e b due numeri interi positivi,
utilizzando solo operazioni di
incremento,
decremento,
test di eguale a zero
e ripetizione.
11
algoritmi
12
1.o esempio: decidere se a > b, (a, b due interi positivi)
utilizzando solo operazioni di incremento, decremento,
test di eguale a zero e ripetizione.
una possibile procedimento di soluzione (ALGORITMO) :
1 test a=0 ? se si’, procedi da 6 {a=0, b non si sa}
2 test b=0 ? se si’, procedi da 7 {a non zero, b=0}
3 {qui a non zero, b non zero, non si sa ancora}
decrementa sia a che b di 1 di uno: b<=b-1, a<=a-1;
4 ripeti da 1 ("vai a" 1)
5 {ora (a=zero e b=zero) oppure (a=0, b>0) in ogni caso->}
6 risposta FALSO (a=0, b>=0, quindi non e’ a>b) e STOP
7 risposta VERO (a non 0, b=0, quindi a>b) e STOP
1.o esempio di algoritmo:
13
a>b ?
qui riportato il diagramma a blocchi del
procedimento di soluzione utilizzando solo
incremento/decremento e test se zero
1
a=0?
si
6
falso
(a non >b)
stop
2 b=0?
3
a = a-1
b = b-1
4
si
7
vero
(a >b)
stop
nota: nel diagramma a blocchi i
numeri sono etichette (label) dei
blocchi a fianco (destra/ sotto);
le frecce indicano la progres
sione delle azioni da eseguire
osservazione sull’algoritmo per decidere se
a>b ?
14
(con a e b due numeri interi positivi, con le sole operazioni di
incremento, decremento, test di eguale a zero e ripetizione)
che ripetiamo qui:
1 test a=0 ? se si’, procedi da 5 {a=0, b non si sa}
2 test b=0 ? se si’, procedi da 7 {a non zero, b=0}
3 decrementa a di 1 e decrementa b di uno
4 ripeti da 1 [CICLO!]
5 {qui (a=zero e b=zero) oppure (a=0, b>0) in ogni caso->}
6 risposta FALSO (non e’ a>b) e STOP
7 risposta VERO (e’ a>b) e STOP
nell’algoritmo vi sono alcune istruzioni che saranno ripetute
piu’ volte (a seconda dei dati), altre non saranno mai eseguite;
il numero delle istruzioni dell’algoritmo (qui 7) NON coincide
con il numero istruzioni che saranno effettivamente eseguite !!
algoritmi:
15
un algoritmo e’
una definizione precisa, completa e non ambigua
della sequenza di passi da fare ->
( ovvero: una lista di
istruzioni [una ricetta] da eseguire -> )
-> per risolvere un problema, in un tempo finito
passi (o istruzioni) che saranno meccanicamente eseguiti da
un “esecutore” - quindi: la definizione puo' essere fornita
in un linguaggio generico purche’ comprensibile al
destinatario (persona o macchina) in particolare
un algoritmo scritto in un linguaggio di programmazione
comprensibile ad un elaboratore e’ un PROGRAMMA
calcolo automatico?
un calcolo automatico e’ composto da:
un insieme di dati iniziali A
un insieme P di regole F che chiameremo programma
o algoritmo; ogni regola F trasforma una parte X dei
dati in altri dati Y :
una "macchina" che e’ in grado di interpretare ed
eseguire le regole del programma;
• l’esecuzione del programma da parte della macchina
produce (a partire dai dati iniziali A) ad ogni passo k
di esecuzione dati intermedi Ik e alla fine produce dei
risultati (dati finali) Z :
Z = P ( A );
16
... calcolo automatico?
17
quindi un calcolo automatico o elaborazione e’:
1) un insieme di dati iniziali A,
2) un programma o insieme P di regole F (ogni regola F
trasforma [elabora] una parte X dei dati A in altri dati Y)
3) un “elaboratore” che applica le F su A ripetutamente;
in generale un’ elaborazione e’ una trasformazione
Z = P(A)
con
A = insieme dei dati iniziali, Z = ins.dei dati finali,
P = regola che fa corrispondere Z ad A, o funzione
---------------------------
P e’ una funzione nel senso piu’ lato: una somma di due numeri, la
preparazione del bilancio di una societa’, la stampa di un certificato
anagrafico, il calcolo della situazione meteorologica di domani,
l’esecuzione di una mossa nel gioco degli scacchi...
2.o es. di algoritmo: somma due numeri
18
Il concetto di "fare dei conti" e' abbastanza intuitivo. Alle
elementari ci insegnano l'aritmetica, ad esempio l'addizione
di numeri di n cifre, con riporto; in dettaglio,
il primo passo da fare e' calcolare (rango per rango, ovvero
per colonne) le due righe sotto, le somme e i riporti:
1
9
9
1
2
3
0
9
------------------------3
2
9
0
0
1
0
1
+
AA dato uno
BB dato due
sommando rango per rango:
= le cifre di somma in colonna
= le cifre di riporto in colonna
nota: le cifre della somma sono date dalle due "regole":
1) cifraS=cifraA + cifraB; 2) se cifraS>9
allora cifraS=cifraS-10 e riportoS = 1;
( procedimenti di calcolo )
2.o es. di algoritmo: somma due numeri
19
1
9
9
1
+
ripetiamo: sommando
2
3
0
9
=
due dati AA e BB di 4
------------------------cifre ciascuno otteniamo
3
2
9
0
le cifre somma in colonna
0
1
0
1
e le cifre riporto
se i riporti non sono nulli devo sommare al risultato parziale
i riporti spostati di una colonna a sinistra : di nuovo somma:
0
0
3
2
9
0
1
0
1
------------------------4
2
0
0
0
0
1
-
AA = le somme dei ...
BB = i riporti dei ...
cifre somma in colonna
NUOVE cifre riporto
ripetiamo:
1)
1
1)
2
20
9
3
9
0
1
9
+ primo dato iniziale
= secondo dato iniziale
-------------------------------------------------------------------------
2)
2)
0
3
1
2
0
9
1
0
-
(somme)
(riporti spostati di una
colonna a sinistra)
0 ...ripeto sommando:
- (nuovi riporti gia’ spostati
-------------------------------------------------------------------------
3)
3)
0
4
0
2
1
0
-
-------------------------------------------------------------------------
4)
4
3
0
0 cifre somma in colonna
4)
0
0
0
0 cifre riporto (non spostate)
... a questo punto non ripeto piu' perche’ si verifica la
situazione di nessun riporto (tutti i riporti nulli)- ottengo:
5)
4
3
0
0
e' la somma ... e ho finito
2) procedimenti di calcolo: addizione di due numeri
Schema del procedimento visto (o "ricetta") :
per fare la somma di due numeri di 4 cifre:
date 10 variabili (*)
(a,b,c,d,e f, g,h,i,j)
con valori iniziali (da 0 a 9) (0,1,9,9,1, 0,2,3,0,9)
applichiamo ripetutamente la funzione f(X) -> Y
f (a,b,c,d,e, f,g,h,i,j) -> (a1,b1,c1,d1,e1, f1,g1,h1,i1,j1),
con a1 = nuovo valore di a, .. j1 = nuovo valore di j,
{ dove a1,b1,..e1 sono le somme delle cifre: a1= a+f, b1=b+g, ...
f1,g1,..j1 sono i riporti: f1 =riporto(cifra delle decine)di( b+g)
g1=riporto(c+h), h1=rip(d+i), i1=rip(e+j), infine j1=0 },
fino a che sono nulli tutti i valori dei riporti (f,g,h,i,j).
-------------------------------------------------------------------------
(*) variabile: oggetto dotato di nome e di valore; il valore varia
durante il procedimento ma e’unico in ogni istante di tempo.
21
22
ad es. con i dati di prima, AA=1991 e BB=2309 avremo:
f(0,1,9,9,1, 0,2,3,0,9) -> (0,3,2,9,0, 0,1,0,1,0) poi
f(0,3,2,9,0 ,0,1,0,1,0) -> (0,4,2,0,0, 0,0,1,0,0) poi
f(0,4,2,0,0, 0,0,1,0,0) -> (0,4,3,0,0, 0,0,0,0,0) e basta:
la somma si ottiene applicando ripetutamente la f alle variabili
(a..j) a partire dai valori iniziali dati, fino a che sono nulli i
valori di (e,f,g,h,i,j). Il processo di calcolo e' l' insieme delle
10-tuple dalla prima fino all'ultima:
1) (0,1,9,9,1, 0,2,3,0,9) "stato iniziale"
2) (0,3,2,9,0, 0,1,0,1,0) "stato intermedio"
3) (0,4,2,0,0, 0,0,1,0,0) "stato intermedio"
4) (0,4,3,0,0, 0,0,0,0,0) "stato finale"
ogni 10-tupla e' ottenuta dalla precedente applicando la
funzione definita prima.
elaborazione o procedimento di calcolo: una definizione
dato un insieme K di dati (variabili a valore intero =
oggetti capaci di asumere un valore intero)
data una funzione di trasformazione f(K) = K1
( la f trasforma K in un K1 =
insieme delle stesse variabili di K con valori nuovi
dato un esecutore M [generico: persona, macchina] di f:
quindi f deve essere eseguibile da M !
il processo di calcolo = sequenza degli insiemi dei
dati K0 (dato iniziale) K1, K2, ... Kn , con K1 = f( K0) ...
... Ki+1 = f( Ki) ... e con Kn dato finale:
la sequenza dei dati intermedi deve essere finita:
cioe’ tale che esista n (finito) tale che Kn = risultato
23
... definizione di algoritmo...
24
il concetto di algoritmo e’ preesistente all’informatica
(i primi procedimenti di calcolo risalgono a 3000 anni fa, nella
regione babilonese (es: calcolo del volume di una botte, calcolo
delle radici di un’ equazione di secondo grado, calcolo
dell’interesse composto ecc;) la parola algoritmo (dal matematico
Al Khowarismi, 800 d.c.,Baghdad) indicava fino ad un secolo fa le
procedure dell'aritmetica decimale (somme,prodotti,...))
e genericamente indicava un procedimento matematico
per risolvere un problema;
oggi e’ associato al concetto di elaborazione:
un algoritmo e’la specifica (finita) di una sequenza
finita di azioni elaborative (passi di elaborazione)
che risolve automaticamente un problema.
... una curiosita’ sulla definizione di algoritmo:
25
Dal dizionario Zingarelli, ed. 1959, (comperato presso il Centro di
Calcolo dell'Univ. di Trieste nel 1963)
la parola algoritmo e' riportata ancora con una sua definizione storica:
....
algore, m. * ALGOR -ORIS. Freddo grande. | Stagione fredda.
+algorismo, -itmo, m. *sp. ALGUARISMO. Cifra arabica (dal
matematico ar. Al-Kuarismi che apprese dagl'Indiani
l'abbaco e lo insegno' in Spagna circa l' 820). Aritmetica col
sistema arabo. | Pratica dell'aritmetica.
algoso, v. sotto
aliare,
....
a l g a.
un’ osservazione sugli algoritmi e su Al-Kuarismi
per non sottovalutare i primi algoritmi per
l’aritmetica con le cifre decimali arabe, basti pensare
alla differenza di costo (in termini di tempo) tra:
calcolo con il sistema di numerazione arabo:
17 x 1524 + 44 = ?
calcolo con il sistema di scrittura di numeri romano:
XVII
x
MDXXIV + XLIV = ?
--------------------(curiosita’: per un periodo la Chiesa in Italia vieto’ l’ uso delle cifre arabe di
provenienza degli infedeli, poi si accetto’ il sistema migliore...)
26
definizione informale di algoritmo
un algoritmo e’
una procedura effettiva di calcolo
eseguibile da un esecutore ovvero e’
una lista di istruzioni eseguibili e non ambigue
che eseguita a partire da un dato valido (un insieme di dati)
produce in un numero finito di passi un risultato
N.B.:
* lista finita
* istruzioni eseguibili e non ambigue e deterministiche:
eseguendo piu’ volte lo stesso algoritmo sugli stessi dati si
ottiene sempre lo stesso risultato
* il procedimento di elaborazione finito:
la sequenza dei dati intermedi e’ finita, ovvero e’ garantito
che prima o poi si arriva al risultato
27
algritmo = programma ?
28
un algoritmo e’ una lista di istruzioni eseguibili e non
ambigue che eseguita a partire da un dato valido (un
insieme di dati)
produce in un numero finito di passi un risultato
1) lista finita
2) istruzioni eseguibili, non ambigue, deterministiche: se
eseguo piu’ volte lo stesso algoritmo sugli stessi dati ottengo
sempre lo stesso risultato
3) il procedimento di elaborazione finito: la sequenza dei
dati intermedi e’ finita: prima o poi arrivo al risultato !
NOTA: i punti 1 e 2 sono sempre soddisfatti da un
programma scritto in un linguaggio di programmazione –
il punto 3) invece NON e' sempre rispettato in un programma
29
Analizziamo
piu’ a fondo
questa definizione di algoritmo
ritorniamo alla definizione di procedimento di calcolo
• dato un insieme K0 di dati
• data una funzione di trasformazione f(K) = K1
• esiste un esecutore M [persona o macchina] di f
- f deve essere eseguibile da M !
f definisce un procedimento di calcolo che parte da K0
(dato iniziale) e attraverso K1 [con K1 = f( K0)], K2 ,
K3 ... Ki dove ... Ki+1 = f( Ki) arriva a Kn dato finale.
con sequenza dei dati intermedi K0, K2, ... Ki, ... Kn
finita: esiste n finito tale che Kn = risultato
vediamo ora i singoli punti
30
1) esaminiamo in dettaglio il primo punto: i dati
1) dato un insieme K0 di dati
==>>
i dati possono essere rappresentati come un insieme di
variabili a valore intero
= oggetti capaci di asumere un valore intero
quindi al posto dei dati (del problema reale) consideriamo
un insieme di variabili S = {a,b,c,...} a valori interi,
che "descrivono lo stato di un sistema", (del problema)
ogni insieme di valori S rappresenta un possibile stato
e in particolare abbiamo un insieme
S(0) ovvero S0 di valori iniziali delle variabili a,b,c,..
(non solo UN specifico dato iniziale K0 )
31
2) : le regole o la funzione di trasformazione
32
2) data una funzione di trasformazione f(S) = S1
(S = insieme delle variabili,
S1 = insieme delle stesse variabili con valori nuovi)
==>>
la funzione di trasformazione f e’ definita per i valori di S e
assume valori in S - scriveremo: f ( S ) -> S,
f e' la procedura di calcolo:
a partire da una generica situazione Si = stato = insieme
dei valori delle variabili al passo i-esimo del
procedimento risolutivo la f
produce i valori Si+1 = stato = valori delle variabili al passo
successivo (i+1)-esimo del procedimento risolutivo
parte da S0, poi f(S0)= S1 poi f(S1)=S2 poi f(S2)= S3 ecc
3) esecutore:
33
... data una funzione di trasformazione f(S) = S1
[ f e' la procedura di calcolo: da Si = statoi produce Si+1 = statoi+1
(valori delle variabili al passo (i+1)-esimo) quindi:
f(S0) -> S1; f(f1)-> S2 , f(f2)-> S3 , f(f3)-> S4 , ecc ]
• esiste un esecutore M di f
ipotesi importante: tutto il procedimento e’ automatico,
eseguibile da una “macchina” (o anche da una persona);
• si richiede che la funzione f sia:
* eseguibile (dall’ esecutore: persona o macchina),
* deterministica (da S(k) produce sempre lo stesso S(k+1))
* completa (definita per tutti i possib.insiemi S(k)
ottenibili dai possibili dati iniziali validi)
finitezza: abbiamo presentato 3 componenti:
# insieme S0 di dati ;
# esecutore M
# funzione di trasformazione f(S) = S1
questa terna ( f S0 M ) definisce la sequenza dei dati
intermedi S0, S2, ... Si, ... Sn-1 , fino a Sn con S0 [dato
iniziale],
f( S0) = S1, ... f( Si) = Si+1 ... f( Sn-1)= Sn [dato finale]
ipotesi importante sulla durata:
la sequenza S0, S2, ... Si, ... Sn e’ finita:
dati ( f, S0, M ) esiste n finito tale che Sn = risultato
ovvero il numero di passi dallo stato iniziale S(1) allo stato
finale S(n) deve essere finito
34
soluzione algoritmica di problemi
35
Per risolvere un problema con il calcolatore
dobbiamo
* specificare e delimitare il problema
* individuare un procedimento risolutivo del
problema - cioe' un insieme di regole che, eseguite
ordinatamente, permettono di calcolare i risultati del
problema a partire dalle informazioni a disposizione = definire un algoritmo (insieme finito di regole,
eseguibili da un esecutore ipotetico, non ambigue,cioe'
univocamente interpretabili, e finite, nel senso che
l'esecuzione dell'algoritmo termini in un tempo finito per
ogni insieme di valori dei dati di ingresso)
cont. soluzione algoritmica di problemi
abbiamo detto che
per risolvere un problema con il calcolatore dobbiamo
* specificare e delimitare il problema
* trovare un procedimento risolutivo (un algoritmo)
infine dobbiamo -
* individuare una rappresentazione [PROGRAMMA]
dell' algoritmo, delle informazioni date e di quelle
usate dall'algoritmo [DATI INIZIALI, INTERMEDI
e RISULTATI] per mezzo di un linguaggio di
programmazione comprensibile sia a noi che al
calcolatore
36
ancora due esempi:
3.o algoritmo :
calcolo dell’ interesse composto:
dato un capitale iniziale (ad es. 1000 dobloni d’oro)
dato un tasso di interesse (ad es. 27 percento)
quanti dobloni avro’ tra 10 anni?
37
3.o algoritmo : calcolo dell’ interesse composto:
dati i valori iniziali di S0 = (cap, int, num, 1)
(cap = capitale iniziale [es. 100,000,000.00] , int = interesse
annuo [es. 9 %], num = numero anni di deposito [es. 8] )
trovare il procedimento per calcolare il capitale dopo n anni
ovvero trovare f tale che dato S0 produca la sequenza
S0 , S1 , S2 , ... Si , ... Snum
dove Snum = (capnum, intnum, numnum, num) = risultato
trovare una f funzione che da quadrupla di valori:
(cap, int, num, konta) [konta = varibile ausiliaria, e’ un
"contatore" a valori da 1 a n ]
produce una quadrupla di valori nuovi:
(cap1, int1, num1, konta1) <= f (cap, int, num, konta)
38
cont. calcolo dell’ interesse composto:
• valori iniziali S0 = (cap, int, num, 1)
(capitale iniziale, interesse annuo, num. anni di deposito)
• f (cap, int, num, konta) = (cap1, int1, num1, konta1)
una f che definisce il procedimento e’:
(c, i, n, k) <= f (c, i, n, k) = ( ( c*(100+i) ) /100 , i, n, k+1 )
e per calcolare il capitale dopo n anni si esegue:
(1) dato iniz. ( c,i,n,1 ); (k=1 !)
(2) ripeti l’istruz.seguent.(3) fintantoche k<n
(3) calcola i valori c1,i1,n1,k1 dai valori
c,i,n,k: (c1,i1,n1,k1) = f(c,i,n,k)
sostituisci ai vecchi valori c,i,n,k
questi valori nuovi c1,i1,n1,k1
alla fine k=n, c = capitale accumulato dopo n anni.
39
4) interesse composto: esempio di traccia di esecuzione
40
f (c, i, n, k) = ( (c*(100+i))/100, i, n, k+1 )
n.istr. cap. int. n
k
(prima dell’istr (1) i valori
1
delle var. non sono def !)
3
1000 4 5
1
valori iniziali -> val.nuovi:
4
1040 4 5
2
k<n quindi ripeti da 3
3
1040 4 5
2
val. correnti -> val.nuovi:
4
1082 4 5
3
k<n quindi ripeti da 3
3
1082 4 5
3
val. correnti -> val.nuovi:
4
1125 4 5
4
k<n quindi ripeti da 3
3
1125 4 5
4
val. correnti -> val.nuovi:
4
1170 4 5
5
k=n -> ho il risultato
4.o ALGORITMO: il massimo comune divisore
calcolo del massimo comune divisore
dati due numeri A e B
quale e’ il numero intero piu’ grande che e’ divisore sia
di A che di B ?
ad es. dati due numeri A = 1996 e B = 768
1996 = 4*499, 768=3*4*64, massimo comun divisore e’4
ad es. per 2310 e 203 che sono rispettivamente
2310=2*3*5*7*11 e 203=7*29
quindi 7 e’ il massimo comun divisore dei due numeri
41
4) algoritmo: calcolo del massimo comune divisore
due versioni di soluzione (Batini,Carlucci, e altri)
4.a) un primo procedimento:
* dati I e J numeri interi positivi,
* calcola SI = l'insieme dei divisori di I
* calcola SJ = l'insieme dei divisori di J
* calcola l'insieme SK dei divisori comuni a I e J,
ovvero SK = l'intersezione degli insiemi SI e SJ
* calcola nm = il numero massimo che sta in SK
* la soluzione e' nm
42
cont. es. del calcolo del massimo comune divisore
4.b) un secondo procedimento (Euclide):
siccome vale la proprieta' seguente:
mcd(m,n) =
se m=n allora mcd = m oppure mcd=n,
se m>n allora = mcd( m-n, n )
se n>m allora = mcd( m, n-m )
* allora per calcolare il m.c.d. si eseguono le istruzioni :
(algoritmo di Euclide, 4.o secolo a.C.)
* finche' m e' diverso da n si ripetano le azioni:
* se m> n
* allora sostituisci a m il valore di m-n,
altrimenti sostituisci a n il valore di n-m;
quando m = n abbiamo finito, e m e’ il m.c.d. cercato
43
1.) es. del calcolo del massimo comune divisore di x e y
Esempio di esecuzione dell’algoritmo (qui ripetuto):
@ finche' m e' diverso da n si ripetano le azioni:
se m> n * allora sostituisci a m il valore di m-n,
# altrimenti sostituisci a n il valore di n-m;
una "traccia" di esecuzione con dati 18 e 12
(sono usati @,#,* come riferimenti all’algoritmo qui sopra):
1) m = 18, n=12;
2) m>n ? si allora * calcola m-n = 18-12 = 6 e assegna a m:
3) m = 6, n=12
4) m>n ? no allora # calcola n-m = 12-6 = 6 e assegna a n
5) m=6,
n=6,
6) m=n ? si,
allora @ non ripetere piu’,
7) il risultato e’ il valore di m cioe' 6
44
2.) es. del calcolo del massimo comune divisore di m, n
45
@ finche' m e' diverso da n si ripetano le azioni:
se m> n * allora sostituisci a m il valore di m-n,
# altrimenti sostituisci a n il valore di n-m;
2.) es. dati A = 1996 e B = 768
0)
1)
2)
3)
4)
5)
6)
7)
m0 = 1996 e
n0 = 768
* m1=1996-768=1228, n1=768;
* m2=1228-768=460, n2=768;
# m3=460,
n3=768-460=308;
* m4=460-308=152,
n4=308;
# m5=152,
n5=308-152=156;
# m6=152;
n6=156-152=4
* m7=152-4=148,
n7=4; ...
... (ripeto per altre 36 volte)
43) * m43=8,
n43=4;
44) @ m44=8-4=4,
n44=4;
m==n => ho finito ! => MCD=4
3.) es. del calcolo del massimo comune divisore di m, n
@ finche' m e' diverso da n si ripetano le azioni:
se m> n * allora sostituisci a m il valore di m-n,
# altrimenti sostituisci a n il valore di n-m;
3.) es. dati 2310 e 203
1)m1=2310,n1=203;
4)m1=1701,n4=203;
7)m7=1092..
10)483,..;
13)m13=77,n13=126;
16)m16=28,n16=21;
19)m19=7,n19=7
2)m2=2107,n2=203;
3)m3=1904,n3=203;
5)m5=1498,n5=203;
6)m6=1295,n6=203;
8)m8=889,...;
9)686,...;
11)m11=280,n11=203; 12)m12=77, n12=203;
14)m14=77,n14=49;
15)m15=28,n15=49;
17)m17=7,n17=21;
18)..7,..14
e ho finito ... ==>> MCD=7
46
traccia di UNA esecuzione:
nota: un algoritmo ed un particolare insieme di dati in
ingresso o di partenza
definiscono un particolare processo di calcolo
come questo visto per il calcolo del MCD di 18 e 12,
oppure per i due esempi MCD(1996 ,768)=4 e MCD(2310, 203)=7
oppure come quello visto prima per il calcolo del capitale
con interesse composto con capitale iniziale 1000
interesse annuo 4 e numero anni 5,
oppure come l’ esempio iniziale di calcolo della somma di
due numeri interi a=1991 e b=2309 con s= 4300...
NOTA: un algoritmo puo’ essere applicabile a un dato solo,
oppure a un numero finito di dati, oppure a un numero
infinito di dati ...
47
formalismi
48
Esistono moltissimi formalismi per definire (esprimere,
specificare) algoritmi:
formalismi astratti:
Macchina di Turing, (vedremo nel prossimo capitolo)
Lambda Calcolo,
linguaggi per calcolatori:
linguaggi macchina, ...
ling. di programm. imperativi o procedurali, come ad es.:
Algol 59, Basic, C, C++, Cobol, Fortran 57, Fortran 90,
Java, Modula, Oberon, Pascal, , Smalltalk, Snobol, ...
ling. di progr. funzionali (Lisp,Scheme, ...),
ling. di progr. logici (Prolog, ...)
... ancora sulla definizione di algoritmo...
49
la nozione di algoritmo o procedura effettivamente
computabile e' del 1935, ed e’ stata ripresa da piu' autori
con diversi formalismi negli anni 30, 40 e 50.
oggi si puo’definire un algoritmo come un programma
eseguibile da un calcolatore che a partire da un dato valido
produce in un tempo finito e sempre lo stesso risultato (*)
esistono algoritmi (programmi) per risolvere un enorme
quantita’ di problemi
ma ATTENZIONE: non esistono algoritmi risolutivi per tutti i
problemi [vedremo un esempio in dettaglio]
----------------------------------------------
(*) implicita l’ipotesi che il linguaggio di programmazione in
cui scrivo il programma sia non ambiguo,deterministico e
eseguibile dal calcolatore ...
50
di seguito sono riportati alcuni esempi
di problemi da risolvere con procedure
automatiche:
qualche es. di problemi (..procedimenti) di calcolo:
51
esempi di problemi: alcuni semplici, altri difficili fino a
“praticamente intrattabili”, altri impossibili ...
1) problema della somma di due interi di 4 cifre (abbiamo
visto prima un procedimento)
2) dati due numeri, trovare il maggiore;
3) calcolo del capitale maturato dopo dieci anni, con dati l’
interesse composto e il capitale iniziale;
4) dati tre valori numerici a,b,c calcolare le radici
dell’equazione di secondo grado a * x2 + b * x + c = 0
5) dato un elenco di nomi e relativi numeri di telefono (in
rubrica o elenco telefonico o nel cellulare della zia), trovare
il num.o di telefono di una persona (ad. es. Mario Rossi);
qualche es. di problemi (..procedimenti) di calcolo:
52
6) scrivere una lettera di sollecito di pagamento alla ditta
“Sgraffigna,Nonpaga,Fuggi&co”.
7) calcolo della mossa migliore per ogni possibile situazione
del gioco del filetto / della dama / degli scacchi
8) data una rete stradale di una citta' e le informazioni sui
flussi di veicoli (per ogni strada e per ogni istante) trovare il
percorso ottimo (tempo o consumo o altro) da casa propria
all' universita';
9) calcolo del percorso ottimo di un robot semovente in
ambiente con ostacoli (ad es.durante una partita di calcio
del campionato internazionale per squadre di robot);
10) calcolo dei comandi per il controllo di una macchina
operatrice di un impianto industriale;
qualche es. di problemi (..procedimenti) di calcolo:
11) calcolo delle tasse per gli studenti del primo anno
della facolta' di ingegneria;
12) calcolo del comando da trasmettere sull' interfaccia
MIDI nell'ambito di un programma che produce
musica da partitura memorizzata da/di Buxtehude;
13) calcolo dell’immagine da inviare sullo schermo
sinistro relativo al gioco virtuale Destroyer71;
14) scrittura automatica da parlato di Porpetto
15) traduzione automatica delle poesie di Saba in urdu
16) scrivere tutti gli n per cui l' equazione
x n + y n = z n ha soluzioni x,y,z intere;
53
qualche es. di problemi (..procedimenti) di calcolo:
54
17) scrivere un programma per comprimere una sequenza di
immagini video codificate in versione digitale in modo da
poter memorizzare dieci filmati su un disco da 10 Mega byte
18) scrivere un programma che controlla se un qualunque
programma scritto in C++ e’ sintatticamente corretto e se
si ferma dopo un numero finito e limitato di passi
19) trovare una procedura per decidere per ogni x intero e
per ogni f(x) (f funzione da intero a intero) se f(x) e' o
meno una funzione costante;
20) scrivere un programma per decidere per ogni matricola
del corso di Fondamenti di Informatica se passera’ l’esame
entro la prossima sessione.
- ancora sui procedimenti di calcolo:
specifica del problema: in ogni caso si chiede di ottenere a
partire da certe informazioni iniziali (dati di ingresso del
problema) informazioni nuove, o risultati del problema.
la formulazione del problema non da' alcuna indicazione su
come risolvere il problema;
talvolta il problema e’ ambiguo:
cerco ad es. il nome di Furlan Giuseppe nella guida
telefonica di Trieste oppure di John Brown nella guida
telefonica di Manchester e trovo molti nomi uguali.
55
talvolta il problema e’ praticamente intrattabile, perche’
richiede un numero di passi troppo grande
(un esempio: per calcolare la funzione di Ackermann
A(4,2) ci vuole un po’ di tempo (circa 10 secondi), il
risultato e’ un numero intero di 19729 cifre:
A(4,2) = 2,00352 ...6733 x 10 +19728 ;
(H.J.Smith, programma VPCalc per calcoli con dati fino a
114.639 cifre e con valori di grandezza fino a
10^15.032.385.525, da: ModulaTor nr.11, vol.1, dec 91)
per il calcolo A(4,3) ci vorrebbero piu’ di A(4,2)
secondi [n anni, dove n ha piu’di 10000 cifre...]
e un calcolatore con piu’ di A(4,2) byte di memoria [k
Gbyte, dove k ha piu’di 10000 cifre...] ... e’ un
problema non risolubile in pratica
56
57
talvolta si dimostra che un problema non ha soluzione
ad es. il problema di decidere per ogni x intero e ogni
funzione f(x) da intero a intero se f(x) e' costante o no,
ovvero trovare una F tale che
F(f) = 1 se f(x) e’ costante per tutti gli x e
F(f) = 0 se f(x) non e’ costante
si puo’ dimostrare che il problema NON ha soluzione
58
Un altro problema che non ha soluzione (come si puo’
dimostrare) e’ il seguente “Halting Problem” :
scrivere (il testo di) un programma (un “super-compiler”) SC
che sia in grado di leggere un testo di un programma
generico P e di un dato generico D per il programma P, e
poi, analizzando il testo P e i dati D, sia in grado di
rispondere se
* il programma P con questo dato generico D una volta
avviata l’esecuzione si ferma in un tempo finito (si arresta
dopo aver eseguito un numero finito di istruzioni)
* oppure no, e in questo secondo caso ha luogo una
computazione infinita.
Nota che NORMALMENTE un compilatore analizza il
testo di un programma generico e per prima cosa decide
se la sintassi e’ corretta oppure no;
nota: il numero di algoritmi e’ infinito ma numerabile 59
vi sono tanti algoritmi quanti i numeri naturali
(un programma in C e’ un testo; posso immaginare di
costruire una sequenza di tutti i programmi in C, iniziando
dal piu’ piccolo - il programma vuoto “main(){}” e poi
“allungando” in ordine lessicografico con costrutti che
mantengano la sintassi legale -> elenco tutti i programmi...
un algoritmo puo’ essere considerato come una funzione da
intero a intero (l’insieme dei dati “ e’ “ un intero (formato
appunto da tutti i dati codificati), l’insieme dei risultati e’ un
intero);
nota: il numero di funzioni da intero a intero non e’
numerabile – solo una piccola parte delle
f(int)->int
e’ un algoritmo!
BIBLIOGRAFIA per questa parte:
(ma solo per chi sia molto interessato all’argomento
M.A. Arbib, A.J. Kfoury, R.N. Moll: "A Basis for
Theoretical Computer Science", Springer Verlag 1981
(BIBL.FAC.ING)
R.Y.Kain, "Automata Theory, Machines and
Languages", McGraw Hill,72. (BIBL.FAC.ING)
M.L. Minsky: " Computation: Finite and Infinite
Machines", Prentice Hall 1967, (Centro Calcolo ,
DEEI) cap. 6,7,8.
C.Ghezzi, D.Mandrioli: "Informatica Teorica", Clup,
Milano, 1989.
60
cont. BIBLIOGRAFIA per questa parte:
D.E.Knuth: "The Art of Computer Programming",
vol. 1, "Fundamental Algorithms", Addison Wesley
1968, (FAC./5/XXIIc/41a/I)
B.A. Trakhtenbrot: "Algoritmi e macchine
Calcolatrici", Ed. Progresso tecnico, 1964,
(FAC/5/Cont.3/7)
J.E.Hopcroft, J.D.Ullman: “Introduction to Automata
Theory, Languages and Computation”, Addison
Wesley, Reading, Mass., 1979.
61