Riepilogo: la radice quadrata - carlostrapparava.com fileIl problema di calcolare la radice quadrata...
-
Upload
hoangtuyen -
Category
Documents
-
view
222 -
download
0
Transcript of Riepilogo: la radice quadrata - carlostrapparava.com fileIl problema di calcolare la radice quadrata...
1
Carlo Strapparava - Informatica
Riepilogo: la radice quadrata
Il programma sqrt mostra come il semplice linguaggio introdottosia sufficiente per scrivere piccoli programmi
sqrt-iter mostra come l’iterazione possa essere realizzata conla sola chiamata procedurale senza particolari costrutti iterativi
(define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))
(define (improve guess x) (average guess (/ x guess)))
(define (average x y) (/ (+ x y) 2))
(define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001))
(sqrt 9)=> 3.00009155413138(sqrt (+ 100 37))=> 11.704699917758145(sqrt (+ (sqrt 2) (sqrt 3)))=> 1.7739279023207892(square (sqrt 1000))=> 1000.000369924366
(define (sqrt x) (sqrt-iter 1.0 x))
Carlo Strapparava - Informatica
Riepilogo:regola generale di valutazione
L’interprete prima valuta l’ operatore e glioperandi, poi applica la procedura risultanteagli argomenti risultanti (applicative order).
Lo Scheme implementa l’applicative order Eccezioni alla regole generale di valutazione si
dicono Forme Speciali (Syntactic Sugar)
2
Carlo Strapparava - Informatica
Esercizio: new-if
La signorina Hacker ridefinisce if come
poi, testa la procedura
e, deliziata, ridefinisce sqrt-iter comeQuale sarà ora il comportamento di sqrt-iter ?
(define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause)))
(new-if (= 2 3) 0 5)=> 5(new-if (= 1 1) 0 5)=> 0
(define (sqrt-iter guess x) (new-if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))
Carlo Strapparava - Informatica
Procedure come black boxes
Il problema di calcolare la radice quadrata sidecompone in un certo numero di sottoproblemi come fare a dire che una proposta di soluzione è
abbastanza buona come fare a migliorare una soluzione …
E’ cruciale che ogni procedura individui uncompito ben preciso
3
Carlo Strapparava - Informatica
Astrazione procedurale
Non importa come sono implementate leprocedure che utilizzo per es. nella scrittura digood-enough?, le vedo come scatole nere
Decomposizione procedurale di sqrt
sqrt
sqrt-iter
good-enough?
square
improve
averageabs
Carlo Strapparava - Informatica
Nomi locali e scope
I nomi dei parametri di una procedura sono localialla procedura: sono variabili legate
La definizione di procedura lega i suoi parametriformali
Una variabile che non è legata si dice libera L’insieme delle espressioni su cui vale il legame di
un nome si dice scope (= portata) di quel nome
(define (square x) (* x x))
(define (square y) (* y y))Sono indistinguibili !
4
Carlo Strapparava - Informatica
Nomi locali e scope (cont.)
Il significato di good-enough? è indipendente dai nomi che scegliamo perguess e x, fintantoché sono distinti tra loro e differenti da < - abs esquare
Il significato di good-enough? non è indipendente dalle sue variabili libere Se ridenominassimo il parametro guess in abs avremmo introdotto un baco
chiamato capturing della variabile abs. Da variabile libera, diventerebbevariabile legata.
(define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001))
• guess e x sono variabili legate• < - abs square sono variabili libere
Carlo Strapparava - Informatica
Definizioni interne e struttura a blocchi
L’unica procedura che interessa è sqrt Non è permesso definire un’altra procedura chiamatagood-enough? solo perché la usa sqrt
Dobbiamo avere la possibilità di definire procedure localinascondendole dentro sqrt
(define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))
(define (improve guess x) (average guess (/ x guess)))
(define (average x y) (/ (+ x y) 2))
(define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001))
(define (sqrt x) (sqrt-iter 1.0 x))
5
Carlo Strapparava - Informatica
Questa struttura di innestamento di definizioni si chiamastruttura a blocchi
Possiamo non solo nascondere le definizioni, ma anche semplificarle
(define (sqrt x) (define (good-enough? guess ) (< (abs (- (square guess) x)) 0.001)) (define (improve guess ) (average guess (/ x guess))) (define (sqrt-iter guess ) (if (good-enough? guess ) guess (sqrt-iter (improve guess) ))) (sqrt-iter 1.0 ))
Definizioni interne e struttura a blocchi
x
x
x x
x x
x
x
x x
x x
x
x
x x
x x
Carlo Strapparava - Informatica
Definizioni interne e struttura a blocchi
Lexical scoping: le variabili libere in unaprocedura si riferiscono a bindings (= legami)fatti nelle definizioni delle procedure che leincludono
6
Carlo Strapparava - Informatica
Riepilogo
Finora abbiamo considerato alcuni elementi dellaprogrammazione Operazioni aritmetiche primitive Espressioni composte con queste operazioni Astrazioni di queste espressioni composte tramite la
definizione di procedure
Carlo Strapparava - Informatica
Procedure e processi che esse generano
Sapere le regole degli scacchi non implica ilsapere giocare a scacchi
Occorre avere: Conoscenza di quali mosse vale la pena di fare
(=> quali procedure vale la pena definire) Esperienza per prevedere le conseguenze di una mossa
(=> quali sono le conseguenze dell’esecuzione di unaprocedura)
7
Carlo Strapparava - Informatica
Procedure e processi che esse generano
Dobbiamo essere in grado di visualizzare iprocessi generati da un programma e
Capire quante risorse computazionali (tempoe spazio) consumano i vari tipi di processi
Ci sono alcune “pattern” di processo chebisogna conoscere
Carlo Strapparava - Informatica
Ricorsione lineare e Iterazione lineare
Consideriamo la funzione fattoriale
n! = n ! (n "1) ! (n " 2) ! … ! 3 ! 2 ! 1
0!= 1n!= n ! (n "1)!# $ %
Definizione per ricorrenza (usa il principio di induzione come linea guida)
8
Carlo Strapparava - Informatica
Fattoriale di N
Un modo per calcolare il fattoriale è quello diutilizzare la definizione per ricorrenza
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))
Carlo Strapparava - Informatica
Fattoriale di N (cont.)(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))
Possiamo usare il modello di sostituzione e vedere questa procedura in azioneProviamo a calcolare 5!
(fact 5)(* 5 (fact 4))(* 5 (* 4 (fact 3)))(* 5 (* 4 (* 3 (fact 2))))(* 5 (* 4 (* 3 (* 2 (fact 1)))))(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))(* 5 (* 4 (* 3 (* 2 (* 1 1)))))(* 5 (* 4 (* 3 (* 2 1))))(* 5 (* 4 (* 3 2)))(* 5 (* 4 6))(* 5 24)120
9
Carlo Strapparava - Informatica
Fattoriale di N (cont.)
Guardiamo al calcolo del fattoriale da unaprospettiva diversa
((1! 2)prodotto! " # ! 3)
prodotto! " $ # $
! 4 !…! N
prodotto! contatore " prodottocontatore ! contatore +1
N! è il valore del prodotto quando il contatore è maggiore di N
Carlo Strapparava - Informatica
Fattoriale di N (cont.)
Possiamo riscrivere la procedura per calcolare ilfattoriale
(define (fact n) (fact-iter 1 1 n))
(define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count)))
Esercizio: Riscrivere il tutto usando la struttura a blocchi (semplificando)
10
Carlo Strapparava - Informatica
Fattoriale di N (cont.)
Possiamo usare il modello di sostituzione e calcolare 5!
(fact 5)(fact-iter 1 1 5)(fact-iter 1 2 5)(fact-iter 2 3 5)(fact-iter 6 4 5)(fact-iter 24 5 5)(fact-iter 120 6 5)120
(define (fact n) (fact-iter 1 1 n))
(define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count)))
Carlo Strapparava - Informatica
Processo Ricorsivo e Processo Iterativo
Tutti e due i processi richiedono un numero di passi proporzionale a N(i.e. lineare rispetto a N)
Il primo costruisce una catena di operazioni differite (le moltiplicazioni)=> è un processo ricorsivo
Il secondo non cresce né si contrae => è un processo iterativo Un processo iterativo può essere “descritto” dalle sue variabili di stato
(nel nostro caso product, counter, max-count)
(fact 5)(fact-iter 1 1 5)
(fact-iter 1 2 5)(fact-iter 2 3 5)(fact-iter 6 4 5)
(fact-iter 24 5 5)(fact-iter 120 6 5)120
(fact 5)(* 5 (fact 4))(* 5 (* 4 (fact 3)))(* 5 (* 4 (* 3 (fact 2))))(* 5 (* 4 (* 3 (* 2 (fact 1)))))(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))(* 5 (* 4 (* 3 (* 2 (* 1 1)))))(* 5 (* 4 (* 3 (* 2 1))))(* 5 (* 4 (* 3 2)))(* 5 (* 4 6))(* 5 24)120
11
Carlo Strapparava - Informatica
Processo Ricorsivo vs. Procedura Ricorsiva
Processo ricorsivo: processo caratterizzato dauna catena di operazioni differite
Procedura ricorsiva: una procedura che“sintatticamente” si riferisce a se stessa
Carlo Strapparava - Informatica
Linguaggi di prg. e Tail-Recursion
Purtroppo nella maggior parte dei ling. di prg. (inclusiAda, C, Pascal) tutte le procedure sintatticamentericorsive generano processi ricorsivi, anche se ilprocesso generato è in principio iterativo.
Come conseguenza questi linguaggi devono ricorrerea speciali costrutti iterativi (do, repeat, for, while, …)
Lo Scheme non ha questo difetto: ha la proprietà ditail-recursion
Un linguaggio tail-recursive non ha bisogno di syntactic-sugar per l’iterazione=>
12
Carlo Strapparava - Informatica
Esercizio: ricorsivo o iterativo ?
Per ognuna delle seguenti procedure dire che tipodi processo genera (i.e. ricorsivo o iterativo)
(define (my+ a b) (if (= a 0) b (inc (my+ (dec a) b))))
(define (my+ a b) (if (= a 0) b (my+ (dec a) (inc b))))
Sono supposte già definite le funzioni inc e dec che rispettivamenteincrementano e decrementano il loro argomento di 1