CALCUL NUMERIC. Elemente de modelare 1

Desenul 2: globul-machet al planetei

Desenul 1: imagine paleolitic a unui bizon

ELEMENTE DE MODELARE

1. NOIUNE DE MODEL CLASIFICAREA MODELELOR Imitarea unor procese, obiecte sau fenomene este

caracteristic societii umane pe tot parcursul istoriei sale. Primele desene, realizate de oamenii epocii de piatr pe pereii peterilor erau n acelai timp i primele ncercri de a imita

obiectele i fenomenele reale prin imagini (desenul 1). Globul-machet al planetei noastre este i el o imitaie a

unui corp real. El ne transmite diferite informaii despre forma i micarea Terrei, amplasarea continentelor i oceanelor, rilor i oraelor (desenul 2). Dar elementele mache-tei nu sunt reale. Avem de a face doar cu un corp sferic, prin centrul cruia trece o ax, care permite rotirea, iar pe suprafa avnd imprimate diverse informaii despre planet. Globul-machet posed anumite proprieti ale corpului cosmic real, dar se deosebete de el: difer dimensiunile, proprietile fizice, structura etc. Globul-machet este o realizare simplificat a Terrei, care permite studierea doar a anumitor proprieti ale ei un model.

Modelul este un obiect material sau ideal, care nlocuiete n procesul de cercetare obiectul original, pstrnd unele caracteristici eseniale, importante pentru procesul de cercetare.

Modelele sunt utilizate din cele mai vechi timpuri pentru cercetarea fenomenelor i proceselor complicate, construcia ansamblurilor arhitecturale complicate etc. Un model reuit este mai accesibil pentru cercetri dect obiectul real. Mai mult chiar: unele obiecte i fenomene nu pot fi cercetate n original. Sunt inadmisibile experienele economice la nivel macroeconomic; imposibile experienele cu elementele Sistemului Solar; experienele tempo-rale etc. Un alt aspect important al modelrii l constituie evidenierea factorilor, ce genereaz anumite proprieti ale obiectului real, caracteristici eseniale ale lui.

Modelul permite instruirea n vederea utilizrii corecte a obiectului real, verificnd di-ferite moduri de a reaciona pe modelul acestui obiect. Experienele cu obiectul real pot fi imposibile sau foarte periculoase (durata mare a procesului n timp, riscul de a deteriora obiectul). n cazurile cercetrii obiectelor dinamice (caracteristicile crora depind de timp) o importan primordial capt problema prognozrii strii obiectului sub aciunea unor anumii factori.

Un model bine construit permite obinerea unor cunotine noi despre obiectul original cercetat.

Procesul de construire al modelului se numete modelare.

Exist cteva tipuri de modelare, ce pot fi unite n dou grupe mari: modelare materia-l i ideal.

La modelarea material se atribuie metodele, la care cerce-tarea originalului se reali-zeaz prin reproducerea n model a caracteristicilor geometrice, fizice, dinamice, funcionale de baz. Exemple: machetele cldirilor, a diferitor aparate (avioane, automobile, vehicule

CALCUL NUMERIC. Elemente de modelare 2

militare). Modelarea ideal difer cardinal de cea material: ea se bazeaz pe analogia ideal a modelului fa de original.

Modelarea ideal poart un caracter teoretic. Uneori se poate baza pe o concepie in-tuitiv despre obiectul cercetrilor. n acest sens experiena de via a fiecrui om poate fi considerat drept modelul lui a lumii nconjurtoare. n cazul cnd modelarea nu este intuiti-v, se folosesc anumite simboluri, modelarea fiind numit simbolic. n calitate de simboluri se folosesc diverse scheme, grafice, formule. n categoria modelelor simbolice un loc aparte l ocup modelarea matematic, la care cercetarea obiectului se realizeaz prin intermediul unui model formulat n termeni i noiuni matematice, cu folosirea unor metode matematice. Un exemplu clasic al modelrii matematice este descrierea i cercetarea legilor de baz ale mecanicii lui I. Newton cu instrumentele matematice.

Pentru cercetarea unui proces sau fenomen nu este suficient s fie construit modelul. Modelul descrie anumite legiti, relaii, caracteristici. De obicei ns, problema pus cere ca n baza unor mrimi cunoscute s se determine alte mrimi i caracteristici, care s-ar acorda modelului matematic.

ntrebri i exerciii 1. Explicai noiunea de model. Determinai perechi obiect (fenomen) real i modelul

su. Enumerai caracteristicile obiectului real preluate de model 2. Definii noiunea de model material. Dai exemple de modele materiale. Motivai ne-

cesitatea utilizrii modelrii materiale n diferite domenii 3. Definii noiunea de model ideal. Exemplificai. Motivai necesitatea modelrii ideale.

CALCUL NUMERIC. Elemente de modelare 3

2 2

121

x

x y

=

+ =

2. MODELUL MATEMATIC I MODELAREA MATEMATIC Dezvoltarea informaticii ca tiin a fost generat de progresul n sfera tehnicii de cal-

cul, tehnologiilor informaionale. Scopurile de baz ale acestei tiine sunt elaborarea metode-lor de soluionare a problemelor complicate de cercetare i de calcul cu ajutorul calculatoru-lui. Iniial informatica se dezvolta ca o ramur a matematicii aplicative. Primele probleme puse erau de asemenea pur matematice: calcule complicate, analiza unor mulimi complexe de situaii etc. La moment informatica este o tiin independent, cu metode proprii de cercetare (dar care sunt fundamentate matematic). Informatica cerceteaz i rezolv probleme din domeniul matematicii, fizicii, chimiei, biologiei, economiei, ecologiei, filologiei, sociologiei. Dar, oricrui domeniu n-ar aparine problema, n procesul de soluionare a ei informatica se bazeaz pe matematic. Nu e ntmpltor. nainte de a soluiona problema cu ajutorul calcula-torului este necesar descrierea fenomenelor i proceselor din problem cu ajutorul noiunilor matematice. Acestea pot fi funcii, ecuaii, inecuaii, sisteme de ecuaii etc.

Descrierea unui proces sau fenomen prin intermediul noiunilor matematice se numete model matematic.

Exemplul 1 S se determine coordonatele punctelor de intersecie a dreptei x=1/2 i a unei circumferine unitare cu centrul n originea coordonatelor.

Modelul matematic al acestei probleme este determinat de sistemul de ecuaii

Algoritmul de rezolvare e urmtorul:

1. Se consider x=1/2.

2. Se calculeaz 1 21 11 ; 1 ;4 4

y y= =

3. Soluia este 1 3 1 3, ; ,2 2 2 2

Exemplul 2 Pe o mas neted se afl o bil metalic, fixat de un arc. Arcul se com-prim, fr a i se deteriora elasticitatea, apoi se elibereaz. Ce cere s se determine, unde se va afla bila peste t secunde.

Dac k coeficientul de elasticitate a arcului, m masa bilei, x - mrimea deformaiei arcului, atunci n baza legii lui Huk i a legii 2 Newton, modelul matematic al sistemului bil arc va avea forma:

ma = - kx, unde a acceleraia. Deformarea iniial se noteaz prin x0. Trebuie s se determine deformarea peste t se-

cunde. Pentru aceasta modelul precedent se va transforma astfel nct s fie prezentat depen-dena deformaiei de timp. Pentru deformri mici i lipsa forei de frecare se va folosi ecuaia deplasrilor armonice

CALCUL NUMERIC. Elemente de modelare 4

Soluia problemei iniiale se calculeaz prin introducerea datelor n formula obinut.

ntrebri i exerciii 1. Definii noiunea de model matematic. Este el oare un model material? 2. Descriei modelul matematic care permite calculul soluiilor ecuaiilor de forma

024 =++ cbxax 3. Izotopul radioactiv plutonium-235 are perioada de njumtire de 26 minute. n aceat

perioad jumtate din cantitatea iniial a izotopului dispare. Descriei modelul mate-matic, care permite calculul numrului ciclurilor de njumtire necesare pentru dis-pariia a k% din cantitatea iniial a izotopului.

tm

kxtx cos)( 0=

CALCUL NUMERIC. Elemente de modelare 5

3. SOLUII ANALITICE I SOLUII DE SIMULARE Fie propus urmtoarea problem:

ntr-un bazin cu volumul 100 m3 se pompeaz ap cu ajutorul unei pompe cu capacitatea de 15 m3/or. Totodat, 5m3/or se scurg din bazin n dispozitivul de filtrare. Iniial n bazin se conin 20 m3 de ap. Se cere s se determine, peste cte ore bazinul va fi plin.

Desigur, exist mai multe metode de rezolvare a acestei probleme. Una din cele mai simple este modelarea volumului de ap n bazin peste fiecare or, cu ajutorul unui tabel.

Timp (ore) Pompa Scurgerea Bazin 0 0 0 20 1 +15 -5 30 2 +15 -5 40 3 +15 -5 50 4 +15 -5 60 5 +15 -5 70 6 +15 -5 80 7 +15 -5 90 8 +15 -5 100

Soluia problemei a fost obinut printr-un numr relativ mare de calcule consecutive, care au reconstruit dinamic starea bazinului la nceputul fiecrei ore urmtoare. Sigur, nu este cea mai eficient metod: se utilizeaz un numr mare rezultate intermediare, numrul de operaii realizate este la fel nemotivat de mare.

O alt soluie se bazeaz direct pe modelul matematic al problemei. Timpul necesar pentru umplerea bazinului este determinat din formula:

1001020 =+ t , sau

810

20100=

=t .

Prima din metodele realizate utiliza un proces iterativ, care determina volumul de ap dup fiecare interval elementar de timp (1 or), i calcula rezultatele noi, folosind datele obinute la etapa precedent. Cu alte cuvinte, a fost realizat simularea procesului de umplere a bazinului. Modelul realizat a fost un model de simulare iar soluiile obinute la fiecare iteraie soluii de simulare.

De obicei modelele de simulare se folosesc atunci cnd este necesar observarea dez-voltrii dinamice ale sistemului cercetat.

Cea de a doua metod, n care starea sistemului este descris prin o formul, permite ca starea sistemului (bazinului) s fie determinat n orice moment de timp ulterior. Desigur, pentru aceasta este necesar modificarea formulei obinute anterior. Noua formula (care, de altfel, permite rezolvarea problemei generale a bazinului) este urmtoarea:

CALCUL NUMERIC. Elemente de modelare 6

scurgerepompa

initialbazin

CCVV

t

= ,

unde Vbazin volumul total al bazinului, Vinitial cantitatea iniial de ap n bazin, Cpompa capacitatea pompei (pe or), Cscurgere capacitatea gurii de scurgere (pe or).

Astfel putem calcula timpul necesar pentru umplerea oricrui bazin, cu orice cantitate iniial de ap i cu orice capacitate a pompei, care depete capacitatea de scurgere, care de asemenea poate varia. Metoda de rezolvare care utilizeaz formulele analitice, ce permit calculul direct al rezultatului final, fr iteraii i rezultate intermediare se numete metoda analitic de rezol-vare. Soluiile obinute cu ajutorul metodei analitice sunt numite soluii analitice. Fiecare dintre metodele expuse are prioritile i neajunsurile sale. Pentru unele probleme este foarte complicat sau practic imposibil de determinat formula analitic (de exemplu, coordonatele unei comete sau asteroid n funcie de timp), pentru altele este destul de complicat de simulat un model adecvat, chiar i folosind un numr foarte mare de calcule intermediare. Cunoaterea formulei analitice permite calculul imediat al soluiei finale; utilizarea unui proces iterativ permite construirea dinamic a soluiei n dependen de factorii utilizai n problem. Alegerea metodei este influenat de mai muli factori, principalii fiind:

Posibilitatea de determinare a soluiei analitice Costul calculelor Numrul de calcule necesare pentru determinarea soluiei de simulare Gradul de apropiere a soluiei de simulare de soluia real (exact) a problemei

ntrebri i exerciii 1. Definii noiunea de simulare. Ce este o soluie de simulare? 2. Ce nelegei prin metod analitic de rezolvare? Ce este o soluie analitic? Care sunt

proprietile soluiilor analitice? 3. Enumerai proprietile soluiilor de simulare. Care dintre aceste proprieti implic

utilizarea calculatorului pentru rezolvarea problemelor prin metode de simulare? 4. Determinai o metod de simulare pentru obinerea elementului cu numrul N din irul

de numere 1, 1, 2, 3, 5, 8, 13, 21, ... Exist oare o metod analitic pentru determinarea elementului cu numrul N?

5. Rezolvai problema prin metoda simulrii: a) buburuz urc n timpul zilei pe un stlp 5 m, iar noaptea coboar 3m. Ascen-

siunea ncepe dimineaa. nlimea stlpului este de 15m. Cnd va ajunge bu-buruza n vrful stlpului?

b) n condiiile punctului precedent ascensiunea ncepe dimineaa de la nlimea de 6m.

c) n condiiile punctului precedent ascensiunea ncepe seara.

CALCUL NUMERIC. Elemente de modelare 7

4. ETAPELE REZOLVRII PROBLEMEI LA CALCULATOR Instrumentele informatice permit rezolvarea problemelor att prin metode analitice,

ct i prin metode de simulare. Dar, rezolvarea oricrei probleme n informatic se divide n mai multe etape, fiecare din ele avnd acelai grad de importan.

Analiza problemei iniiale. La aceast etap este studiat problema real. Sunt sepa-rate datele iniiale, se determin ce trebuie de obinut, care sunt relaiile dintre datele iniiale i rezultat. Tot aici sunt determinate restriciile suplimentare asupra datelor iniiale i rezultatu-lui.

Crearea modelului problemei. Este creat modelul matematic al problemei. n depen-den de problem acest model poate fi analitic sau de simulare. Pentru modelul analitic este necesar s se determine formulele de calcul, care exprim rezultatul cutat prin datele iniiale. Pentru un model iterativ se stabilesc valorile iniiale ale datelor, relaiile (formulele) de trecere la iteraia urmtoare, condiia de ntrerupere a calculelor. Tot la aceast etap are loc (dac e posibil) divizarea problemei n subprobleme i elaborarea modelelor pentru fiecare din ele.

Elaborarea algoritmului. n cazul rezolvrii informatice a unei probleme algoritmul conine metoda de rezolvare a problemei, descris ntr-o form acceptabil (pseudocod, schem logic etc.) i relaiile dintre diferite etape de rezolvare. Dac problema a fost divizat n subprobleme, algoritmul mai conine date despre relaiile dintre modelele subproblemelor. n procesul de rezolvare la calculator a problemei este deosebit de important consecutivitatea ndeplinirii instruciunilor. Anume algoritmul divizeaz modelul matematic n pai elementari i stabilete ordinea de efectuare a calculelor la fiecare pas.

Scrierea programului. Pentru ca s devin posibil rezolvarea problemei de ctre calculator, nu este suficient algoritmul de rezolvare. Algoritmul trebuie transpus ntr-o form neleas de calculator program ntr-un limbaj de programare. Paii algoritmului sunt descrii cu ajutorul instruciunilor limbajului de programare, iar consecutivitatea lor de consecutivitatea instruciunilor. n procesul de scriere a programului pot s apar erori sintactice sau semantice. Procesul de corectarea a lor este de asemenea inclus n etapa de scriere a programului. Etapa se consider ncheiat atunci cnd compilarea sau interpretarea programului finalizeaz fr erori.

Testarea programului. O compilare reuit nu nseamn o problem rezolvat co-rect. Pentru verificarea corectitudinii se realizeaz o serie de teste, care cerceteaz lucrul programului n funcie de seturi de date de intrare simple, medii i extreme. Dac pentru toate testele efectuate programul determin rezultate corecte, se poate presupune c problema a fost rezolvat corect. Dac n procesul de testare se obin rezultate eronate, urmeaz s fie cerceta-te din nou etapele precedente, ncepnd cu analiza problemei i pn la scrierea programului. Procesul de rezolvare a unei probleme la calculator poate fi ilustrat cu ajutorul urm-toarei scheme:

Exemplul 1 Problema: Ion a elaborat un nou model de robot. Robotul se deplaseaz dup un algoritm care conine doar instruciuni din setul: un pas la Sud (S), un pas la Nord (N), un pas la Vest (W), un pas la Est (E). Instruciunile algoritmului se ndeplinesc consecutiv. Dup sfritul programului robotul se oprete. Axele de coordonate sunt paralele direciilor geo-grafice. Unitatea de msur coincide cu un pas al robotului. Determinai ci algoritmi

Problema

real Analiza Algoritm Program Model Testare

CALCUL NUMERIC. Elemente de modelare 8

Desenul 3. Poziia ini-ial a robotului i di-reciile de deplasare

Desenul 4. Numrul de posibiliti de a ajunge n K micri n (X,Y) se determin ca suma numrului de posibiliti de a ajunge n K-1 micri n unul din punctele (X,Y+1) (X,Y-1) (X+1,Y) (x-1,Y)

distinci din exact K ( 160 K ) instruciuni deplaseaz robotul din punctul cu coordonatele (0,0) n punctul cu coordonatele (X, Y) ( 16|||,| YX ). Analiza problemei: Este dat o suprafa de reea, nodurile reelei fiind puncte cu coordonate ntregi. Se cere de determinat numrul de trasee diferite pe reea fin nodul cu coordonatele (0,0) n nodul cu coordonatele (X,Y). Reeaua este format din nu mai mult de 33 de linii i 33 de coloane. Numrul de micri nu depete 16. Datele iniiale vor fi introduse de la tastatur. Rezultatele vor fi afiate la ecran. Modelul matematic: Se construiete schema grafic a problemei (desenul 3). Iniial robotul se afl n originea coordonatelor. Poziia final este determinat de valorile X i Y date iniial. Se observ c numrul de algoritmi din K instruciuni care permit deplasarea din (0,0) n (X, Y) este egal cu suma numerelor de algoritmi din K-1 micri, cu care se poare ajunge n punctele vecine celui cu coordonatele (X,Y).

Iniial n 0 micri se poate ajunge doar din (0,0) n (0,0) ntr-un singur mod. La fiecare iteraie urmtoare se folosete formula

Ni+1(X,Y) = Ni(X,Y+1)+ Ni(X+1,Y)+ Ni(X,Y-1)+ Ni(X-1,Y) Algoritm: Pas 0. Iniializarea. Se formeaz tablourile A, B [-20..20,-20..20] cu

elemente de tip ntreg lung. Elementul A[I,J] indic numrul de algoritmi din R (R= 0..K) micri care deplaseaz robotul din (0,0) n (I,J). Matricea B pstreaz valorile elementelor matricei A de la iteraia precedent. R se iniializeaz cu 0; A[0,0] cu 1, celelalte elemente ale matricei A cu 0.

Pas 1. R R + 1; B A Pas 2. Pentru toi I de la -R pn la R

Pentru toi J de la -R pn la R A[I,J] B [I, J+1] + B [I, J-1] + B [I+1, J] + B [I-1, J]

Pas 3. Dac R=K se trece la pas 4, n caz contrar se revine la pas 1 Pas 4. Afiare A[X,Y]. Stop.

Program program cn001; type grid = array [-18..18, -18..18] of longint; var a, b: grid;

CALCUL NUMERIC. Elemente de modelare 9

i, r, j, k, n, x, y: longint; begin read(k, x, y); a[0,0] := 1; for r := 1 to k do begin b := a; for i := -r to r do for j := -r to r do a[i,j] := b[i+1,j]+b[i-1,j]+b[i,j-1]+b[i,j+1];

end; writeln(a[x,y]); end.

Testare Pentru testare a fost folosit urmtorul set de teste: Date iniiale Rezultat 0 0 0 1 7 - 4 1 147 8 1 3 1568 12 4 2 174240 16 0 -16 1 16 2 2 103062960

ntrebri i exerciii 1. Enumerai etapele rezolvrii unei probleme la calculator. Explicai necesitatea fiecrei

etape. 2. Care sunt metodele de descriere a algoritmului unei probleme? Exemplificai. 3. Care este impactul divizrii unei probleme n subprobleme elementare? Dai exemple

de probleme, care pot fi divizate n subprobleme. Indicai dou sau mai multe pro-bleme, care conin subprobleme identice

4. Pentru urmtoarele probleme realizai modelul matematic: a) Sunt cunoscute coordonatele a trei vrfuri ale unui dreptunghi cu laturile para-

lele axelor de coordonate. Se cere s se determine coordonatele celui de al pa-trulea vrf.

b) n condiiile punctului precedent laturile dreptunghiului pot fi poziionate arbi-trar fa de axele de coordonat

5. Pentru urmtoarele probleme descriei algoritmul, folosind una din metodele de des-criere cunoscute

a) Este dat un ir din cel mult 100 numere naturale. Se cere s se ordoneze ele-mentele irului n ordine cresctoare

b) Este dat un ir din cel mult 100 de numere ntregi. Se cere s se determine ele-mentul cu valoare maxim din ir i numrul de repetri ale lui prin o singur parcurgere a irului.

6. Elaborai programe pentru rezolvarea problemelor din exerciiile 3 i 4. 7. Elaborai seturi de teste pentru programele realizate n exerciiul 5.