Însă un matematician utilizează aceleaşi cuvinte – „variabilă aleatoare”, punînd în sensul acestor cuvinte ceva bine determinat. Într-adevăr, spune un matematician, noi nu ştim ce valoare va primi variabila aleatoare în cazul dat concret, dar noi putem determina ce valori poate primi această variabilă, şi putem calcula care este probalilitate de apariţie a evenimentelor.

Pe baza acestor date noi nu putem să anticipăm care ar fi rezultatul unui experiment legat de această mărime, dar noi putem să ştim care ar fi rezultatul unei serii întregi de experimente. Cu cît este mai mare numărul de experimente cu atît mai exact putem să prezicem care va fi rezultatul.

Pentru a defini o variabilă aleatoare, trebuie să indicăm ce valori ar putea lua această variabilă şi care sunt probabilităţile de apariţie ale acestor valori.

Există două tipuri de variabile aleatoare: continue şi discrete.

§1. Variabile aleatoare continue

Variabile aleatoare, valorile căreia aparţin unui interval, se numeşte continuă.

În cazuri particulare acesta poate fi nu un singur interval, dar reuniunea a mai multor intervale. Intervalele pot fi finite, parţial finite sau infinite, de exemplu:  (a; b], (–µ ; a), [b;µ), (–µ; µ).

În general variabila aleatoare continuă este o abstractizare. Вообще непрерывная случайная величина – это абстракция. Obuzul, lansat de un proectil, poate să parcurgă o distanţă cuprinsă între 5 şi 5,3 km, dar nimănui nu-i va veni în gînd să măsoare această distanţă cu exactitatea de pînă la milimetri, nemaivorbind de exactitatea absolută. În practică această distanţă va fi o variabilă aleatoare discretă, la care fiecare valoare a variabilei se deosebeşte de alta cel puţin cu distanţa de un metru.

La descrierea unei variabile aleatoare continue principial nu pot fi scrise şi numerotate toate valorile pe care le poate lua această variabilă, care aparţin unui interval destul de îngust. Aceste valori formează o mulţime nenumărabilă, care se numeşte „”continuu”.

Dacă x este o variabilă aleatoare continuă, atunci egalitatea x = х reprezintă în sine, ca şi în cazul variabilei aleatoare discrete, un careva eveniment aleator, dar pentru variabila aleatoare continuă acest eveniment poate fi legat cu o probabilitate egală cu zero, ceea ce nu indică că evenimentul este imposibil. Aşa de exemplu, putem spune, că obuzul va parcurge distanţa de 5245,7183m cu probabiliatea zero, sau, că diametrului unei piese deviază de la cel ideal cu 0,001059 milimetri. În aceste cazuri este greu să ne dăm seam  - avut loc experimentul sau nu, deoarece măsurarea acestor mărim se efectuiază cu o careva eroare, şi în calitate de rezultat pot fi doare indicate limitele între care se va afla mărimea dată.

Valorilor variabilelor aleatoare le este specifică o careva nedeterminare. De exemplu, nu are sens distingem două valori care se abat de la valoarea matematic ideală cu 0,5mm şi 0,5000025mm. Probabilitatea, diferită de zero, poate fi legată doar cu nimerirea  mărimii în intervalul dat, chiar dacă este destul de îngust.

Fie x – o variabilă aleatoare continuă. Vom cerceta pentru un careva număr х probabilitatea inegalităţii  х < x < х + Dх

P(х < x < х + Dх).

Aici Dх – mărimea unui interval îngust.

Evident, că dacă  Dх ® 0, atunci P(х < x < х + Dх) ® 0. Notăm prin р(х) limita raportului P(х < x < х + Dх) la Dх , cînd Dх ® 0, dacă această limită există:

Funcţia р(х) se numeşte densitatea de repartiţie a variabilea aleatoare. Di for formula (1) rezultă egalitatea, care este adevărată pentru valori foarte mici lae lui Dх şi care poate fi considerată definirea funcţiei  р(х):

P(х < x < х + Dх)

Evident, că funcţia p(x) este o funcţie nenegativă. Pentru definirea probabilităţii, că variabila aleatoare x va lua valori din intervalul [a, b] de lungime finită, vom alege pe acest interval numerele arbitrare x₁, х₂,¼,  х_n care satisfac condiţiei а=х₀<х₁<x₂<¼<x_n<b=x_n+1. Aceste numere impart intervalul [a, b] în n+1 părţi, care nu sunt altceva decît tot nişte intervale [х₀, х₁), [х₁, х₂), ¼,[х_n, b]. Introducem notaţiile:

Dх₀= х₁ – х₀, Dх₁= х₂ – х₁, ¼, Dх_n = b – х_n,

şi formăm suma

teza_var_aleatoare

Să considerăm, una din cele mai simple probleme. Se dă un vector cu n componente. Se cere sa se calculeze maximul dintre componentele sale.

Reamintim, pe scurt algoritmul:

Timpul de calcul depinde, în primul rînd, de lungimea(mărimea) datelor de  intrare, pe care o vom nota cu n.

Exemple:

Pentru a calcula timpul de calcul ar trebui inventariem toate instrucţiunile programului şi să ştim d cîte ori se execută fiecare din ele(în funcţie de n).Mai mult, ar trebuie să cunoaştem cît durează execuţia fiecărui tip de instrucţiune.

Observaţie 1.

Exemplu. Pentru calculul maximului, nu putem şti de cîte ori se execută atribuirea max:=v[i]. Cu toate acestea putem considera că există o proporţionalitate între valoarea n şi numărul de execuţii.

Observaţia 2.

Datorită acestor considerate vom proceda astfel.

Se alege o operaţie numită operaţie de bază, şi se vede de cîte ori se execută aceasta. Cerinţa pentru operaţia de bază este ca aceasta să se execute de un număr de ori, numărul care să poată calcula de la început pornind de la n.

Exemplu.

În astfel de cazuri(cînd avem de ales între mai multe operaţii de bază), vom alege acea operaţie care corespunde cît mai bine scopului propus.

Astfel, dacă analizăm un algoritm de generare a permutării comparativ cu altele de aceeaşi natură vom alege ca operaţie de bază comparaţia.

În cazul în care analizăm un algoritm oarecare, în care soluţia este sub formă de permutare, putem considera ca operaţie de bază permutarea. Problema se spune în felul următor: dacă căutăm soluţia printre toate permutările pe care se pot genera vom avea n! căutări(un număr imens !), oare nu se poate altfel?

Exemple de probleme la care se foloseşte un astfel de raţionament: problema comis voiajorului, problema celor n dame.

Timpul estimat de calcul se trece sub formă aproximativă astfel:

O(număr estimat de execuţii ale operaţiei de bază)

Exemplu de exprimare a timpului.

Dacă un algoritm efectuiază 3n²+7n+5 operaţii de bază, vom spune că aceasta este un algoritm cu O(n²).

Exemple.

În cazul de faţă operaţia aleasă este cea de comparare. Pentru un vector cu n componente se fac n-1 comparaţii. Aceasta înseamnă că dacă vectorul are o sută de componente se fac 99 de comparaţii ş.a.m..d.. Se poate demonstra faptul că un algoritm mai bun nu există!

2.  Pentru generarea permuntărilor(în cazul în care se consideră ca operaţie de bază generarea unei permutări) timpul estimat de calcul este O(n!).

În anumite cazuri nu putem preciza nici macar numărul de execuţie ale operaţiilor de bază.

Exemplu. Sortarea prin interschimbare(vezi 6.2.1). În cazul în care vectorul este sortat se execută n-1 comparaţii (se parcurge vectorul o singură dată), dacă vectorul este sortat invers se execută n(n-1)/2 operaţii de bază (se parcurge vectorul de n ori).

În astfel de cazuri se poate considera:

De fiecare dată cînd se trece timpul estimat se precizează despre care este vorba (minim, mediu, maxim). În practică, prezintă interes timpul madiu sau maxim.

Dacă timpul estimat este sub forma O(n^k), k=N*, spunem că algoritmul este în timp polinomial.

Exemlu. Sortarea prin interschimbare are timpul (mediu, maxim) polinomial şi anume O(n²).

Un algoritm în O(n) se numeşte algoritm liniar.

Dacă un algoritm are un timp estimat O(2ⁿ), O(3ⁿ).. spunem că algoritmul este în timp exponenţial.

Un algoritm în timp O(n!) este asimilat unui algoritm în timp exponenţial.

n!=1x2x…n<2x2x….x2=2^n-1.

În practică nu sunt admişi decît algoritm în timp polinomial, deşi nu este deloc indiferent gradul polinomului.

Şi totuşi pentru ce tot acest efort de estimare a timplui de calcul? Oare viteza de lucru a unui calculator nu este atît de mare, în cît abstracţie făcînd de cîteva minute de calcul, în plus sau în minus, să renunţăm la estimarea lui? Răspunsul la această la această întrebarea este categoric negativ. Mai mult timpul de calcul este esenţial dacă este prea mare algoritmul nu are nici un fel de valoare practică. Să ne imaginăm un algoritm care are un timp de calcul O(2ⁿ). Dacă n este de 10, calculatorul va efectua aproximativ 1024 operaţii elementare. Dacă n este 100 acesta va trebui să efectueze 1024^*1024^*…^*1024 operaţii elementare, adică un număr mai mare decît 1000^*1000^*…^*1000 adică 1000000…0000 (de treizeci de ori). Aceasta este un număr imens. Dar dacă n este 1000? pentru un n nu foarte mare, nici cel mai modern calculator din lume nu scoate rezultatul decît în sute sau în mii de ani. De astfel ce înseamnă în asemenea cazuri un calculator modern? Să presupunem că un sistem PENTIUM are o viteză de circa 25 de ori mai mare decît un sistem XT. Să presupunem că avem un program care are un timp de calcul de ordinul O(2ⁿ). Se cere să rezolvăm o problemă pentru n=30. Fie că timpul necesar rulării acestei probleme pe un XT. Această problemă va fi rulată pe PENTIUM în timpul t/25. Dorim să rezolvăm problema pe PENTRIUM pentru n=35 (n a crescut numai cu 5). Dar 2³⁵=2^30*2⁵=32^*2³⁰. Deci dacă n a crescut cu 5, vom avea nevoie de mai mult timp de lucru să rezolvăm problema pe PENTIUM decît timpul pentru rezolvarea ei pentru n=30 pe XT.

Vă daţi seama ce înseamnă un timp de calcul de ordinul O(2ⁿ)? Sporul lui n cu o singură unitate duce la dublarea timpului de calcul.

Ce concluzie tragem de aici? De cîte ori avem de rezovat o problemă căutăm pentru aceasta un algoritm în timp polinomial (polinomul va avea gradul minim). Mai mult căutăm un algoritm care să rezovle problema în timp polinomial de grad minim.

analiza timpului de calcul

§1. Tabloul

Fie Ani={1,2,….ni} mulţimea primelor ni numere naturale. Fie M=An1 x An2 x…..x Ank produsul cartezian a k astfel de mulţimi. Definiţie: Se numeşte tablou o funcţie f:M→T, unde T este o mulţime oarecare. Numărul k este dimensiunea tabloului. Dacă k=1 tabloul se mai numeşte şi vector. Vectorul are n1 componente. Dacă k=2 tabloul se mai numeşte şi matrice. Matricea are n1xn2 elemente. Majoritatea limbajelor de programare evoluate au implementat tipul tablou (array în Turbo Pascal). Pentru a identifica elementele unui tablou se folosesc indicii. Exemplul 1: Distanţa dintre două mulţimi în plan se consideră distanţa dintre două puncte ale acestor mulţimi, situate cel mai aproape unul de altul. Aflaţi distanţa dintre două mulţimi de puncte date. (pr.38, §5, [1])

Download Alocarea-memoriei

Program P2.1;

uses crt;

var i,n,s : integer;

f : boolean;

begin

clrscr;

repeat

write(‘Introduceţi un număr natural n=’);

readln(n);

until n>2;

if n mod 2=0 then f:=false else f:=true;

write(‘s=’);

for i:=1 to n-2 do

if(not f) and (i mod 2 =0)then write(‘*’,i)

else

if f and (i mod 2<>0)then write(‘*’,i);

writeln(‘*’,n);

readkey;

end.

Se dă un număr natural n. Verificaţi daca acest număr este prim sau nu.

Program P2.2;

uses crt;

var i,n,f : integer;

begin

clrscr;

repeat

write(‘Introduceţi un număr natural n=’);

readln(n);

until n>2;

f:=0;

for i:=2 to n div 2 do

if n mod i=0 then f:=1;

if f=0 then

writeln(‘Numărul’,n:6,’ este prim’)

else

writeln(‘Numărul’,n:6,’ nu este prim’);

readkey;

end.

Este dat intervalul numerelor naturale de la n pina la m. Determinati toate numerele naturale din acest interval.

Program P2.3;

uses crt;

var i,n,f,j,r,m : integer;

begin

clrscr;

repeat

write(‘Introduceţi limita de jos a intervalului n=’);

read(n);

write(‘Introduceţi limita de sus a intervalului m=’);

readln(m);

until (n>0) and(m>0) and(n<m);

writeln(‘Introduceţi intervalul de la’,n:6,’pina la’,m:6′);

r:=0;

for j:=n to m do

begin

f:=0;

for i:=2 to j div 2 do

if j mod i=0 then f:=1;

if f=0 then

begin r:=1;

writeln(‘Numărul’,j:6,’ este prim’)

end;

end;

if r=0 then writeln(‘Numărul nu este prim’);

readkey;

end.

Se da un număr natural n. Determinaţi toate numerele prime, inclusiv n.

Program P2.4;

uses crt;

var i,n,f,j,r,m : integer;

begin

clrscr;

repeat

write(‘Introduceţi un număr natural n=’);

readln(n);

until n>0;

writeln(‘Introduceţi intervalul de la 1 pînă la’,n:6′);

r:=0;

for j:=1 to n do

begin

f:=0;

for i:=2 to j div 2 do

if j mod i=0 then f:=1;

if f=0 then

begin r:=1;

writeln(‘Numarul’,j:6,’ este prim’)

end;

end;

if r=0 then writeln(‘Numărul nu este prim’);

readkey;

end.

Introduceţi doua numere naturale m si n. Determinaţi împărţitorul lor comun NOD.

Program p2_5;

uses crt;

var i,m,n,k,nod:integer;

begin

clrscr;

repeat

write(‘Introduceţi numărul natural n=’);

readln(n);

write(‘Introduceţi numărul natural m=’);

readln(m);

until (n>0) and (m>0);

if n>m then k:=m else k:=n;

for i:=1 to k do

if (n mod i=0) and (m mod i=0) then nod:=i;

writeln(‘Împărţitorul numărului comun ‘,n, ‘şi’, m,

‘nod=’,nod);

readkey;

end.

Tema 3:

Sunt date următoarele n numerele naturale. Găsiţi suma tuturor numerelor naturale negative.

Program P3.1;

uses crt;

var n,x,sum,i : integer;

begin

clrscr;

repeat

write(‘Introduceţi lungimea următoarelor numere n=’);

readln(n);

until n>0;

sum:=0;

for i:=1 to n do

begin

writeln(‘introdu x=’);

readln(x);

if x<0 then sum:=sum+x;

end;

if sum=0 then writeln(‘Numărul negativ nu exisţă’)

else

writeln(‘Suma numerelor negative este sum=’,sum);

end.

Sunt date următoarele n numere naturale. Găsiţi numărul maximal.

Program P3.2;

uses crt;

var n,x,max,i : integer;

begin

clrscr;

repeat

write(‘Introduceţi lungimea următoarelor numere n=’);

readln(n);

until n>0;

writeln(‘introdu x=’);

readln(x);

max:=x;

for i:=2 to n do

begin

writeln(‘introdu x=’);

readln(x);

if (x>max) then max:=x;

end;

writeln(‘Numărul maximal este max=’,max);

end.

Download probleme rezolvate Pascal

Printr-un tip de dată  înţelegem o mulţime cu elemente numite valori.

Exemplu:{-32768, 32767, …….0,1,……..32767} este omulţime de numere întregi. Atunci cînd nu există posibilatea de confuzie, putem nota mulţimea de mai sus astfel: [-32768,32767]. Un element al acestei mulţimi este 7 (valoarea 7). În Turbo Pascal un astfel de tip se numeşte integer. Şi este predefinit (este cunoscut de limbaj, nu trebuie definit de programator).

Pe mulţimea valorilor unui tip se definesc operaţiile asociate tipului.

Exemplu: Pentru tipul integer se definesc operaţiile de adunare, scădere, înmulţire etc.

Pentru fiecare tip se defineşte modul în care se valorile sale.

Exemplu: Pentru tipul integer valorile se memorizează utilizînd codul complementar şi se folosesc 2 octeţi consecutivi.

Pentru a lucra cu date de un anumit tip se folosesc variabile.

O variabilă se caracterizează prin: tip (natura datelor şi modul de memorare), nume (prin care aceasta se adresează) şi adresă (număr de ordine al primului octet în care se reţin datele, memoria internă fiind privită ca o succesiune de octeţi numerotaţi).

Tipuri de date pot fi simple (mulţimile care alcătuiesc nu sunt rezultate ca produs cartezian a altor mulţimi) şi stucturate în caz contrar. Exemplu:tipul integer este simplu, iar tipul record este structurat.

Limbajele de programare evoluate utilizează din plin tipurile de date. Mai mult, unele din ele permit programului, folosind tipurile existente, să definească noi tipuri de date. Limbajul Turbo Pascal este un exemplu în acest sens.

Noţiunea de tip de date este strânsă legată de un anumit limbaj de programare. În situaţia în care se renunţă la această legătură, se ajunge la o altă noţiune mult utilizată şi anume cea de structură de date.

Exemplu: Mulţimea este o structură de date (după cum vom arăta). În limbajul Turbo Pascal există tipul mulţime (set). Alte limbaje (de exemplu C) nu cunosc acest tip. Aceasta nu înseamnă că în C nu vom putea lucra cu mulţimi. Sarcina noastră este să înţelegem structura de date numită mulţime şi să o implementăm în orice limbaj de programare dorim.

Un curs de algoritmi trebuie să fie independenţi de orice limbaj. Fapt că în aceasta lucrare algoritmii se implementează în Turbo Pascal nu înseamnă că ei pot fi folosiţi numai în acest limbaj. Din acest motiv, orice curs de algoritmi va utiliza noţiunea de structură de date.

Download Limbajul Pascal Stive Cozi