1ALGORITMI

E

MACCHINE DI TURING

2

fondamenti di informatica:

imparare a risolvere problemi di vario genere con le tecniche proprie dell’informatica, e quali problemi sono risolubili...

... cito Aho & Ullman:l’informatica e’ la scienza dell’ astrazione

->cioe’ studia comecreare il giusto modello per un problema e individuare le tecniche appropriate per risolverlo in modo

automatico (con l’aiuto del calcolatore)

3

(continua citazione da Aho Ullman):

Uno studioso di 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 dottor Spiff...

Un informatico 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.

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)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;

5

Per risolvere un problema “generico” con il calcolatore e’ necessario conoscere almeno un linguaggio in cui scrivere la soluzione del problema [il programma], linguaggio comprensibile al calcolatore, e 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 ...

6ALGORITMI

ALGORITMO

=

una lista di istruzioni (una ricetta) da eseguire (con una macchina o con una persona) per

risolvere un problema.

7ALGORITMI

o procedure di calcolo:

alcuni discorsi (brevi) sulla definizione e sui limiti di un processo di calcolo formalizzabile.

81.o esempio di algoritmo: a>b ?

decidere se a e’piu’ grande di b, con a e b due numeri interi positivi, utilizzando solo le operazioni di incremento, decremento, test di eguale a zero e ripetizione.

una possibile soluzione (ALGORITMO) : 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 {qui a non zero, b non zero, non si sa ancora} decrementa a di 1 e decrementa b di uno 4 ripeti da 1 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

9osservazione sull’algoritmo per decidere se a>b ? (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): il numero delle istruzioni dell’ algoritmo (qui 7) in generale NON coincide con il numerodelle istruzioni che andranno effettivamente eseguite !!

10algoritmi:

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 daun “esecutore” - quindi - la definizione e’ fornita in unlinguaggio 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

11calcolo automatico?

un calcolo automatico e’ composto da:un insieme di dati iniziali Aun insieme P di regole F che chiameremo programma o algoritmo; ogni regola F trasforma una parte X dei

dati in altri dati Yuna "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) dati intermedi I e alla fine produce dei risultati (dati finali) Z

12

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 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...

... calcolo automatico?

132.o es. di algoritmo: somma due numeri

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:

1 9 9 1 + AA dato uno2 3 0 9 BB dato due------------------------- sommando rango per rango:3 2 9 0 = le cifre di somma in colonna0 1 0 1 = le cifre di riporto della

somma in colonna

14

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 colonna0 1 0 1 e le cifre riporto

che, sommando i riporti spostati di una colonna a sinistra :

3 2 9 0 AA = le somme dei ... 0 1 0 1 - BB = i riporti dei ...

-------------------------4 2 0 0 cifre somma in colonna0 0 1 - cifre riporto

... procedimenti di calcolo: addizione di due numeri

15ripetiamo:1) 1 9 9 1 + primo dato iniziale1) 2 3 0 9 = secondo dato iniziale -------------------------------------------------------------------------

2) 3 2 9 0 (somme)2) 0 1 0 1 - (riporti spostati di una ------------------------------------------------------------------------- colonna a sinistra) 3) 4 2 0 0 ...ripeto sommando:3) 0 0 1 - - (riporti gia’ spostati) -------------------------------------------------------------------------

4) 4 3 0 0 cifre somma in colonna4) - - - - cifre riporto... a questo punto non ripeto piu' perche’ si verifica la situazione di nessun riporto - ottengo la somma:5) 4 3 0 0 ... e ho finito

16

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) -> Yf (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.

... procedimenti di calcolo: addizione di due numeri

17ad 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.

18elaborazione 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 nuovidato 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:in pratica la sequenza dei dati intermedi deve essere finita: cioe’ che esista n finito tale che Kn = risultato

19... definizione di algoritmo...

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)

e genericamente indicava un procedimento matematico per risolvere un problema;

oggi e’ associato al concetto di elaborazione:

un algoritmo e’ la specifica di una sequenzafinita di azioni elaborative (o passi di elaborazione) che risolve automaticamente un problema.

20... una curiosita’ sulla definizione di algoritmo: 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 a l g a.aliare, ....

21un’ 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...)

22definizione 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

23

Analizziamo

piu’ a fondo

questa definizione di algoritmo

24ritorniamo 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

251) 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", (<- problema)ogni insieme di valori S rappresenta un possibile statoe in particolare al posto del specifico dato iniziale K0 abbiamo un insieme S(0) ovvero S0 di valori iniziali delle variabili a,b,c,..

262) : le regole o la funzione di trasformazione

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

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

273) esecutore:

... 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)

28finitezza: 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 = risultatoovvero il numero di passi dallo stato iniziale S(1) allo stato

finale S(n) deve essere finito

29soluzione algoritmica di problemi

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)

30cont. 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

31ancora 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?

32esempio del calcolo dell’ interesse composto:

dati i valori iniziali di S0 = (cap, int, num, 1) (cap = capitale iniziale [es. 100,000,000.-] , 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)

33cont. 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.

34interesse composto: un esempio di traccia di esecuzione

f (c, i, n, k) = ( (c*(100+i))/100, i, n, k+1 )n.istr. cap. int. n k (prima dell’istr (1) i valori1 - - - delle var. non sono def !)3 1000 4 5 1 valori iniziali -> val.nuovi:4 1040 4 5 2 k<n quindi ripeti da 33 1040 4 5 2 val. correnti -> val.nuovi:4 1082 4 5 3 k<n quindi ripeti da 33 1082 4 5 3 val. correnti -> val.nuovi:4 1125 4 5 4 k<n quindi ripeti da 33 1125 4 5 4 val. correnti -> val.nuovi:4 1170 4 5 5 k=n -> ho il risultato

35 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 = 7681996 = 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*29quindi 7 e’ il massimo comun divisore dei due numeri

364) 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

37cont. 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

381.) 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=124) m>n ? no allora # calcola n-m = 12-6 = 6 e assegna a n5) m=6, n=6,6) m=n ? si, allora @ non ripetere piu’, 7) il risultato e’ il valore di m cioe' 6

392.) 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;

2.) es. dati A = 1996 e B = 7680) m0 = 1996 e n0 = 768 1) * m1=1996-768=1228, n1=768;2) * m2=1228-768=460, n2=768; 3) # m3=460, n3=768-460=308; 4) * m4=460-308=152, n4=308; 5) # m5=152, n5=308-152=156; 6) # m6=152; n6=156-152=47) * 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

403.) 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; 2)m2=2107,n2=203; 3)m3=1904,n3=203; 4)m1=1701,n4=203; 5)m5=1498,n5=203; 6)m6=1295,n6=203;7)m7=1092.. 8)m8=889,...; 9)686,...; 10)483,..; 11)m11=280,n11=203; 12)m12=77, n12=203; 13)m13=77,n13=126; 14)m14=77,n14=49; 15)m15=28,n15=49; 16)m16=28,n16=21; 17)m17=7,n17=21; 18)..7,..1419)m19=7,n19=7 e ho finito ... ==>> MCD=7

41traccia 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)=7oppure 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 ...

42formalismi

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, ...)

43... ancora sulla definizione di algoritmo...

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 ...

44qualche es. di problemi (..procedimenti) di calcolo:

in questo elenco alcuni problemi sono 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 = 05) 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);

45qualche es. di problemi (..procedimenti) di calcolo:

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;

46qualche 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 Porpetto15) traduzione automatica delle poesie di Saba in urdu16) scrivere tutti gli n per cui l' equazione x n + y n = z n ha soluzioni x,y,z intere;

47qualche es. di problemi (..procedimenti) di calcolo:

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.

48- 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.

49talvolta 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

50

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

51Un 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 teso di un programma generico e per prima cosa decide se la sintassi e’ corretta oppure no;

52

nota: si osservi che il numero di algoritmi e’ infinito ma numerabile ...

vi sono tanti algoritmi quanti i numeri naturali (si pensi ad es. che 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;

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);

il numero di funzioni da intero a intero non e’ numerabile - solo una piccola parte delle f(int)->int e’ un algoritmo!

53

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.

BIBLIOGRAFIA per questa parte:(ma solo per chi sia molto interessato all’argomento

54cont. 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.