CALCOLO NUMERICOProf. Di Capua Giuseppe

Appunti di Informatica - Prof. Di Capua 1

INTRODUZIONE

• Quando algoritmi algebrici non determinano la soluzione di un problema o il loro «costo» è molto alto, allora si usano algoritmi di approssimazione che vanno sotto il nome di Algoritmi di Calcolo Numerico

• Si usano quando:• Non esistono algoritmi esatti

• Gli algoritmi esatti non sono efficienti avendo un costo computazionale in termini di tempo e memoria alto

Appunti di Informatica - Prof. Di Capua 2

INTRODUZIONE

• Le tecniche usate da questi algoritmi sono:• Tecniche di discretizzazione (quando il problema ha un dominio continuo ma

si studiano solo alcuni valori di tale dominio ovvero si passa ad un dominio discreto)

• Tecniche di approssimazione successive (ovvero si arriva ad approssimare il risultato attraverso iterazioni successive)

Appunti di Informatica - Prof. Di Capua 3

ALGORITMO DELLA RADICE QUADRATA

• Obiettivo: Calcolare la radice quadrata di un numero positivo n.

• Input: Numero n

• Si calcola un primo valore x0=n/2

• Si calcola un secondo valore x1=1/2*(x0+n/x0)

• E si prosegue iterando il procedimento per k-volte

• Output: il valore xk

Appunti di Informatica - Prof. Di Capua 4

ALGORITMO DELLA RADICE QUADRATA• Si utilizza una variabile rad_prec per

indicare la radice precedente ovvero x0 all’inizio

• Si itera per 10 volte con un ciclo

• Ad ogni iterazione si calcola la radice (variabile rad)

• Si fa diventare la radice calcolata il valore precedente per la nuova iterazione.

Appunti di Informatica - Prof. Di Capua 5

NUMERI PSEUDOCASUALI

• I computer lavora con algoritmi che sono per loro natura DETERMINISTICI (regole rigide, precise, stesso input produce sempre lo stesso output)

• Non è possibile ottenere numeri realmente casuali.

• Il computer genera numeri detti PSEUDOCASUALI ovvero numeri, ottenuti da algoritmi deterministici, che sembrano casuali ma non lo sono

• Gli algoritmi che generano numeri pseudocasuali hanno la caratteristica che dopo aver generato una certa quantità di numeri, questi incominciano a ripetersi.

• La quantità di numeri prima della ripetizione è detta PERIODO DELLA SEQUENZA

• La bontà di un algoritmo dipende dalla lunghezza di questo periodo.

Appunti di Informatica - Prof. Di Capua 6

NUMERI PSEUDOCASUALI

• I numeri pseudocasuali sono generati a partire da un primo numero iniziale detto SEME

• Se usiamo due volte lo stesso seme otterremmo la stessa sequenza di numeri pseudocasuali

• Il linguaggio C++ mette a disposizione 2 librerie.• SRAND(Num) genera un seme a partire dal numero Num

• RAND() crea un numero pseudocasuale

• Le due librerie richiedono l’include di stdlib.h

Appunti di Informatica - Prof. Di Capua 7

ALGORITMO GENERAZIONE DI UN NUMERO PSEUDOCASUALE

• Si prende in input un numero per il seme

• Si genera il seme (SRAND) a partire dal numero

• Si genera il numero Pseudocasuale (RAND)

Appunti di Informatica - Prof. Di Capua 8

ALGORITMO GENERAZIONE DI PIU’ NUMERI PSEUDOCASUALE

• Si prende in input un numero per il seme

• Si prendi in input quanti numeri si vogliono generare

• Si genera il seme (SRAND) a partire dal numero

• Si itera e si producono i numeri Pseudocasuali (RAND)

Appunti di Informatica - Prof. Di Capua 9

ALGORITMO GENERAZIONE DI PIU’ NUMERI PSEUDOCASUALE DA 1 a 90

• Si prende in input un numero per il seme

• Si prendi in input quanti numeri si vogliono generare

• Si genera il seme (SRAND) a partire dal numero

• Si itera e si producono i numeri Pseudocasuali (RAND)

• Ogni numero si divide per 90 , si prende il resto (da 0 a 89) e gli si aggiunge 1 per avere numeri da 1 a 90

Appunti di Informatica - Prof. Di Capua 10

NUMERI PSEUDOCASUALI – ALGORITMO LCG (Linear Congruential Generator)• Questo algoritmo è il più utilizzato per la generazione di numeri pseudocasuali.

• Occorre un seme

• La sequenza è data dalla formula • Xn = (a*Xn-1+C)%m

• Xo è il seme

• a, c ed m sono numeri che hanno le seguenti caratteristiche:• m> 0• m è una potenza di 2• 0<a<m• 0<c<m• Seme < m• c ed m sono primi tra loro• a-1 è divisibile per tutti i fattori primi di m

Appunti di Informatica - Prof. Di Capua 11

NUMERI PSEUDOCASUALI – ALGORITMO LCG (Linear Congruential Generator)• Esempio: a= 5, c = 1, m = 16, X0=1 (seme)

• m= 16 indica che i numeri saranno compresi tra 0 e 15.

• Se si generano più di 16 numeri la sequenza si ripete.

• Per generare diversi numeri occorre iterare (ciclo for) fino ad un massimo di numeri che si vogliono generare.

• In genere si usa m = 231

Appunti di Informatica - Prof. Di Capua 12

ALGORITMO LCG (numeri da 0 a 15)

• Si prende in input un numero per indicare quanti numeri si vogliono generare

• Si fissa a=5, seme = 1, c= 1 ed m=16

• Si stampa il seme

• Si itera per calcolare l’i-esimo numero e poi si assegna il numero calcolato al valore precedente

Appunti di Informatica - Prof. Di Capua 13

CALCOLO DEL π- Metodo di Montecarlo

• Si consideri una circonferenza di raggio 1 inscritta in un quadrato

• Si consideri il rapporto tra l’area del cerchio e l’area del quadrato

• Ac/Aq= πr2/(2 r)2= π/4 da cui ricaviamo π=4*Ac/Aq

Appunti di Informatica - Prof. Di Capua 14

CALCOLO DEL π- Metodo di Montecarlo

• Ora indichiamo con H la quantità di punti che sono nel cerchio e con N la quantità di punti che sono nel quadrato.

• Possiamo dire, con approssimazione , che:

•π=4*H/N• Ora quanti più punti H consideriamo (interni al cerchi) e quanti più

punti totali N consideriamo tanto più questo rapporto si approssima al π

• Ogni punto ha due coordinate x e y. Si calcolano due numeri (x e y) pseudocasuale e si trasformano (attraverso una divisione) in un valore compreso tra 0 e 1 (All’interno del quadrato)

Appunti di Informatica - Prof. Di Capua 15

CALCOLO DEL π- Metodo di Montecarlo

• Per ridurre un numero pseudocasuale ad un valore compreso tra 0 e 1 lo dividiamo con il massimo numero pseudocasuale che si possa avere.

• Tale numero è dato dalla variabile, in C++, RAND_MAX.

• Una volta definite le coordinate di un punto occorre verificare se si trova nel cerchio o meno

• L’equazione del cerchio è X2+Y2=1

• Sostituendo il nostro punto nell’equazione, se X2+Y2<1 allora il punto è nel cerchio e quindi è uno degli H (si incrementa H)

Appunti di Informatica - Prof. Di Capua 16

CALCOLO DEL π- Metodo di Montecarlo

• Si imposta la variabile tanti ad un numero alto (quanti numeri generare)

• Si determina il seme a partire da 1• Si determina x e y due numeri

pseudocasuali• Si divide per RAND_MAX per

portarlo da 0 a 1• Si verifica se il punto è all’interno

del cerchio in tal caso si incrementa la variabile dentro

• Fuori dal ciclo si esegue il calcolo per il pigreco

Appunti di Informatica - Prof. Di Capua 17

CALCOLO DEL NUMERO DI NEPERO e

• Il calcolo del numero si calcola, in modo approssimato, attraverso l’espressione

𝑒 = 1 +1

1!+

1

2!+

1

3!+⋯ .= 𝑘=0

∞ 1/𝑘!

Dove n! è il fattoriale del numero n

Occorre realizzare una funzione che prende in input un numero e restituisce il suo fattoriale.

Appunti di Informatica - Prof. Di Capua 18

CALCOLO DEL NUMERO DI NEPERO e

Appunti di Informatica - Prof. Di Capua 19