Subiectul 1 - 2 puncte - teorie
1. randuri diferențele dintre tipurile asimptotice de evaluare a eficientei
algoritmilor:
Răspuns: Tipurile asimptotice de evaluare a eficientei algoritmilor
sunt eficiente atunci când dimensiunea problemei tinde către infinit și
diferențele de ordine de creștere devin din ce în ce mai semnificative.
Cele trei tipuri asimptotice sunt Theta, O și Omega. Diferenta dintre
acestea este data de limitele pe care acestea le impun. Theta impune
atât marginire superioară, cat și inferioară. O impune doar marginire
superioară, iar Omega impune marginire inferioară. Cu alte cuvinte,
Theta se analizează doar cand cunoaștem atât cazul cel mai favorabil,
cât și cel mai defavorabil. În schimb, la celelalte două cazuri, doar
unul dintre cazuri este luat în evidenta. Referitor la proprietățile
acestora, toate au proprietățile de reflexivitate si tranzitivitate, însă
doar Theta este simetrică
2. Explică în 5-6 rânduri care este rolul indicatorilor statistici de împrăștiere.
Dați 3 exemple și explicați rolul acestora.
Răspuns: Indicatorii statistici de imprastiere au în vedere cat pot fi de
aglomerate sau de dispersate valorile dintr-o serie în jurul mediei.
Astfel, se oferă informații privind extinderea datelor. Totodată, sunt
utili în stabilirea reprezentativitatii măsurilor de centralitate și un rol
în estimarea parametrilor statistici și în predicția statistica. Cei trei
indicatori statistici sunt: dispersia, abaterea standard şi coeficientul de
variaţ[Link] standard este indicatorul folosit cel mai des pentru
aprecierea împrăştierii Atunci când mediile diferă mult, este mai util
coeficientul de variaţie Dispersia este folosită ca măsură a împrăştierii
în testele statistice
3. Explicați rolul activității de control intern în cadrul realizării unui audit
informatic:
Răspuns: Activitatea de control intern în cadrul realizării auditului are
rolul de a verifica corectitudinea rezultatelor prelucrărilor realizate în
interiorul firmei. Se au în vedere măsuri de protectie a echipamentelor,
datelor și programelor care privesc toate aplicațiile unui sistem
informatic. Se fac controale organizatorice, se verifica documentația
de sistem, se fac controale hardware și de siguranta.
4. Care este diferenta dintre coeficienții de corelație Pearson si Spearman.
Explicați rolul acestor indicatori în evaluarea performanțelor unui produs
informatic:
Răspuns:
Acești doi indicatori, Pearson si Spearman au rolul de a masura gradul
de legatura dintre variabile
Pearson : variabile cantitative continue normal distribuite. Pearson se
calculează ca fiind raportul dintre covarianță seriilor și produsul
deviatiilor standard. La Pearson, exista o relație de liniaritate între cele
două variabile de interes.
În schimb, coeficientul Spearman se folosește atunci cand datele nu au
o distributie normala, dar care se pot ordona, fără a avea un număr
mare de valori egale între ele.
5. Indicați trei metode de evaluare a unor clasificatori. Aratati modul prin care
aceste metode ajuta la evaluarea clasificatorilor.
Răspuns:
Trei metode de evaluare:
HOLD-OUT METHOD - antrenează un clasificator folosind datele de
antrenare și îl testează pe datele de testare. Pentru a reduce varianța
metodei Hold-out se poate repeta algoritmul de mai multe ori și se
calculează valoarea medie a estimatorului. Este folosit pentru date de
dimensiuni mari
K-FOLD CROSS-VALIDATION - Se divide setul aleator în k
subseturi disjuncte, k-fold: se folosesc k-1 subseturi pt antrenare, iar al
k-lea se foloseşte pt testare (evaluarea performanţei)
CROSS-VALIDATION - Metodă standard de validare: validare
încrucișată stratificată de 10-fold deoarece acolo avem cel mai bun
compromis între bias și varianță pentru estimarea măsurilor de
performanță. Stratificarea reduce varianța estimării. Stratificarea
reduce varianța estimării Este ideale pentru date de mărime medie.
6. Care este rolul indicatorilor ROC și AUC?
Răspuns:
Curba ROC pentru un clasificator este o curbă bidimensională care
prezintă grafic valorile perechi ale sensibilităţii (axa OY, rata adevărat
pozitivilor-TPR) şi specificităţii (axa OX, rata falşi pozitivilor-FPR) și
(0,0) semnifică un clasificator ce eticheteaza toate datele ca negative
(TPR = FPR = 0)
(1,1) semnifică un clasificator care etichetează toate datele ca fiind
pozitive (TPR = FPR = 1)
Clasificatorii ale căror ieșiri se poziționează pe diagonala principală
(TPR = FPR) etichetează datele în mod aleatoriu
AUC este un indicator unidimensional care rezumă localizarea
"generală" a întregii curbe [Link] corectă se face cu
ajutorul intervalului de încredere/confidenţă de 95% asociat: dacă
AUC ≥ 0,9 acurateţea diagnostică este excelentă, 0,8 ≤ AUC ≤ 0,9
indică o acurateţe diagnostică foarte bună, iar o valoare AUC sub 0,8
indică un test cu acurateţe diagnostică slabă. Dacă AUC are valoarea 1
indică un test diagnostic perfect.
7. Explică în 5-6 rânduri care este rolul indicatorilor statistici tendinței centrale.
Dați 3 exemple și explicați rolul acestora:
Răspuns:
Rolul indicatorilor tendintei centrale este de a vedea unde sunt
acumulate majoritatea valorilor. Media indică tendinţa centrală atunci
când seria de valori este repartizată simetric în jurul ei şi când valorile
nu au o dispersie exagerat de mare. În cazul seriilor de valori
distribuite foarte asimetric, tendinţa centrală nu mai este indicată de
către medie, ci de către mediană. Modul, este un indicator al tendinţei
centrale, la seriile unimodale, adică atunci când în tabelul de frecvenţe
există un singur maxim.
Subiectul 2 - 2 puncte - semi-teorie
Subiectul 3 - 2 puncte - demonstrație corectitudine și complexitate
Pentru acest subiect trebuie urmati urmatorii pasi:
- Mai intâi se vor identifica precondiția(P) și postcondiția(Q). Apoi se
vor face adnotările pentru algoritm.
- Se identifica invariantul dacă este
- Se identifica functia de terminare
- Se demonstrează prin inductie ca invariantul este corect
- Se demonstrează ca funcția de terminare este descrescătoare și ajunge
la 0
- Se calculeaza cazul favorabil, nefavorabile, mediu(dacă este știut de
pe net)
- Pe baza cazurilor se afla în ce categorie de complexitate se afla
algoritmul
Exemplu simplu pentru for:
P: n>=1 deoarece pentru a putea alege maximul trebuie să existe măcar un
element în vector;
Q: max(a[i]) cu i = 0..n-1 (maximul dintre elementele vectorului)
{P0}: (max, i)
A1: max = a[0];
{P1}: (max = a[0], i)
{I}: (max = max(a[j]), j = 0..i-1)
for (i = 1; i < n; ++i)
{Pi ^ (i < n)}: (max, i)
if ( max < a[i] )
{Pi ^ (i < n) ^ (max < a[i])}: (max, i)
A2: max=a[i];
{Pi+1}: (max, i) {Pn ^ (i=n)}: (max = max(a[i], i = 0..n-1), i = n)
{P0} -A1>{P1}
{Pi ^ (i < n) ^ (max < a[i])} -A2>{Pi+1}
{Pn ^ (i = n)} ->{Q}
Invariantul este maximul dintre elementele parcurse din vector
{I}: (max = max(a[j]), j = 0..i-1)
Demonstrație: La început max= a[0]
Pp ca la momentul k avem max(a[i], i = 0..k-1)
Dem că la momentul k+1 avem max(a[i], i = 0..k)
La momentul k se va afla maximul dintre elementele de la 0..k-1. La
momentul k+1 prin A2: max = max, a[k] < max max = a[k], a[k] > max
Rezultă că la momentul k+1 avem max(a[i], i=0..k)
Functia de terminare:
F(i) = n - i - 1, i = 0..n-1. Rezultă că în cazul în care i = n -1 F(n -1) = 0 =>
Algoritmul este finit
Complexitate:
Caz favorabil: maximul este in primul element
din for avem 1 atribuire, n cicluri si 1 verificare de iesire din ciclu
din cauza ca verificam if-ul dar nu intram in el, fiecare ciclu va avea 1
Rezulta 1+ (1 + n + n - 1) (for-ul) + (n - 1) (ciclul) = 3n => O(n)
Caz nefavorabil: maximul este ultimul element
Din for avem 1 atribuie, n cicluri si o verificare de iesire din ciclu
Din cauza ca verificam if-ul si facem atribuirea, fiecare ciclu va avea 2
Rezulta 1 + (1 + n + n - 1) (for-ul) + 2 * (n - 1) (ciclul) = 4 n - 1 => O(n)
Caz favorabil = Caz nefavorabil => Theta(n)
Exemplu simplu pentru while:
P:n=> 1 pentru a executa macar o data
Q: in S se va afla suma de la 1 la n s = 1 + 2 + 3 + 4 + … + n
{P0}:(s,i)
A1: s = 0;
{P1}:(s = 0 , i)
A2: i = 0;
{P2}:(s = 0, i = 0}
{I}: (s = 1 + … + i)
while(i < n)
{ {P2 ^ (i < n)}:(s, i)
A3: i = i + 1;
{P3}:(s, i + 1)
A4: s = s + i;
{P4}:(s = 1 + 2 + … i, i)
}
{P4 ^ (i = n)}:(s = 1 + 2 + … + n, i = n)
{P0} -A1> {P1}
{P1} -A2> {P2}
{P2 ^ (i < n)} -A3> {P3}
{P3} -A4> {P4}
{P4 ^ (i < n)} -> {P2}
{P4 ^ (i = n)} -> {Q}
Invariantul este suma elementelor de la 1 la i.
Demonstratie:
La inceput s = 0 si i = 0
Pp ca in momentul k in s avem 1 + 2 + .. + i, i = k
La momentul k + 1 mai intai se va incrementa i, apoi se va aduna la suma
anterioara => în s se va afla 1 + 2 + .. + i + i + 1, i = k.
Functia de terminare:
F(i) = n - i - 1, i = 0 .. n - 1 Rezultă că în cazul în care i = n -1 F(n -1) = 0 =>
Algoritmul este finit.
Complexitate:
În acest caz cazul favorabil si nefavorabil va fi acelasi(nu exista instrucțiuni
volatile, conditii)
Avem 2 atribuiri la început, apoi n cicli fiecare a cate 2 instrucțiuni, si
while-ul ce are n + 1 verificari.
Rezultă 2 + 2n + n + 1 = 3n + 3 instructiuni => O(n)
Caz favorabil = Caz nefavorabil => Theta(n)
Insertion sort:
P: n>1 pentru ca sa se sorteze ceva
Q: x[i] > x[i - 1], i = 1, n - 1
{P0}:(x, i, j, aux)
{I1}:(x[j] > x[j - 1], j = 1, i)
for(i = 2; i <= n; ++i)
{
{P0 ^ (i <= n)}:(x, i, j, aux)
A1: aux = x[i];
{P1}:(x, i, j aux = x[i])
A2: j = i - 1;
{P2}:(x, i, j = i - 1, aux)
{I2}:(x[k] > x[k - 1], k = 1, j)
while(j >= 1 && aux < x[j])
{
{P2 ^ (j >= 1 ^ aux < x[j])}:(x, i, j, aux)
A3: x[j+1] = x[j];
{P3}: (x, i, j, aux)
A4: j = j - 1;
{P4}:(x, i, j, aux)
}
{P2 ^ !(j >= 1 ^ aux < x[j])}:(x, i, j, aux)
A5: x[j+1] = aux;
{P5}:(x, i, j, aux)
}
{P0 ^ (i = n + 1)}:(x, i, j, aux)
{P0 ^ (i <= n)} -A1> {P1}
{P1} -A2> {P2}
{P2 ^ (j >= 1 ^ aux < x[j])} -A3>{P3}
{P3} -A4> {P4}
{P4 ^ (j >= 1 ^ aux < x[j])} -> {P2}
{P2 ^ !(j >= 1 ^ aux < x[j])} -A5>{P5}
{P5 ^ (i <= n) } -> {P0}
{P0 ^ (i = n + 1)} -> {Q}
Conditiile din bucle valide:
Bucla i:
i<=n
Din preconditii n>=2
Din initializare i=2
=> se executa macar o data, bine def
Bucla j:
j>=1 and aux> x[j]
J = i-1 => j =1
I=2
1>=1 adevarat
Aux = x[i] = v[2]
x[i-1] = x[1]
x[1] =< x[2] => nu se intra in bucla, pentru ca vectorul este deja sortat si se
indeplineste postconditia pentru B2, inv2
x[2]> x[1] => atunci se intra in bucla și se executa permutarile
Dem invariant bucla 2:
J: {x[1],... x[j]} sortat aux<=x[j+1] ….x[i]
PP ca
{ x[1],...x[j-1]} sortat si aux<=x[j]...x[i]
Dem ca
{x[1], ...x[j]} sortat si aux <= x[j+1]...x[i]
Caz 1 x[j] < aux -> secventa pana la x[1]...x[j] ordonata
Caz 2 x[j] > aux -> se executa bucla 2 pana cand:
Se intalneste un element x[j] < aux -> secventa este deja sortata si prin
plasarea lui aux pe poziția j invariantul se pastreaza
J =1 -> aux cea mai mica valoare din vector -> după așezarea lui pe prima
poziție prop invariantului se pastreaza
Dem invariant bucla 1:
I : {x[1]... x[i-1]} sortat
Pp {x[1].. x[i-1]} sortat
Dem ca { x[1]...x[i]} sortat
Caz1: x[i] >= x[i-1] -> elem este pe poz care trebuie -> vector sortat
Caz 2: x[i] < x[i-1] -> se gaseste o noua poz in bucla 2 si elementul este
inserat pe poz corecta -> vector sortat
Functiile sunt finite:
Bucla 1: f1:N->N, f1(i) = n - i (1)
Fct descrescatoare f1(i) >f1(i+1) -> n-i> n-i-1 => n > n-1 (adevarat) -> fct
desc
Exista i =n a. I f1(i) =0 => n-n = 0
Bucla 2: f2:N->N, f2(j)= 0, daca j=0 sau aux>=x[j] (2)
j , daca j>=1 si aux <x[j]
J scade la fiecare pas ->Fct descrescătoare
Exista j =0 pt care f2(j) = 0
Din (1) si (2) -> buclele sunt finite
Complexitate:
Se ia doar pentru instrucțiunea dominanta -> while(j >= 1 && aux < x[j])
Caz favorabil: vectorul este deja sortat. Avem n-1 cicli, si se face doar
verificarea => 2*(n - 1) = 2n -1 => O(n)
Caz nefavorabil: vectorul este descrescător. Prima data ciclul din while se va
executa o data, apoi de 2 ori, si tot asa pana la n-1. =>
Avem 4 *(n-1) *n/2 + n-1 => 2* n^2 - 2n + n -1 = 2*n^2 - n - 1 => O(n^2)
Caz favorabil < caz nefavorabil => alg Omega(n) si O(n^2)
Subiectul 4 -
P1: Care este probabilitatea ca o valoare, dintr-un set de date cu distribuţie normală, să
se afle la cel mult 1,5 deviaţii standard deasupra mediei? (P=? dacă z ≤ 1,5)
Răspuns: Probabilitatea se poate calcula direct din tabel => P = 0.933= 93.3%
P2: Care este probabilitatea ca o valoare, dintr-un set de date cu distribuţie normală, să
se fie mai mică decât valoarea situată la 0,8 deviaţii standard sub medie? (p=? dacă z ≤
-0,8)
Răspuns:Deoarece graficul este simetric fata de 0. Probabilitatea sa fie mai mic decât
numere negative este la fel cu cea mai mare decât numere pozitive(se înmulțește tot cu
-1)
P3: Se considera ca valoarea nivelului seric al 1,25 dihidroxivitamina D în sangele
adolescentelor este normal distribuită, avand o medie de 65 pg/ml și o deviație standard
de 12,5 pg/ml.
a) ce procent din totalul adolescentelor au nivelul seric al dihydroxivitaminei D mai mare
(mic) de 65 pg/ml?
b) cat la sută din totalul adolescentelor au nivelul seric al dihydroxivitaminei D situat
între 40 pg/ml și 90 pg/ml?
Rezolvare:
a) Trebuie duse datele la distribuția z. Deoarece media este 65, aceasta
va fi punctul 0. => P(z< 65) =P(z>65) = 0.5 (50%)
b) P(45 < z < 90) = 1 - P(z < 45) - P(z > 90)
P(z < 45) = (45-65)/12.5 = -2
P(z>90) = (90-65)/12.5 = 2
Cele două probabilități sunt egale și este 1 - 0.9773 = 0.0227
Rezultă P(45 < z < 90) = 1 - 2*0.227 = 0.9546 (95.4%)
SUBIECT 3 FOR SIMPLU
max = a[0];
for(i = 1; i< n; ++i)
if(max < a[i])
max = a[i];
[Link] 1
P: n > 0 -> vectorul trebuie sa contina elemente
Q: max = max(A[i], i = 0,n-1) -> maximul dintre elementele vectorului
2. Pas 2 - se fac adnotari
{Pi}:(variabile) -> preconditia pi (variabilele cu ce stare au ele)
Ai -> se pune pentru intructiuni
I-> invariant
Pi -Ai> Pi+1
P0:(max, a, i)
A1: max = a[0];
P1:(max = a[0], a, i)
I: max(A[j], j = 0 ,i)
for(i = 1; i< n; ++i)
P1 ^ ( i< n):(max, a, i)
if(max < a[i])
P1 ^ ( i< n) ^(max < a[i]): (max, a, i)
A2: max = a[i];
P2:(max = a[i], a, i)
P0 -A1> P1
P1 ^ (i< n) ^(max < a[i]) -A2> P2
P2 ^ ( i<n) -> P1
P2 ^ (i ==n) ->Q
Pas 3
Invariantul max(A[j], j = 0 ,i)
La inceput max = a[0]
PP in pasul k max(a[j], j = 0,k - 1)
Dem in pasul k + 1 avem max (a[j], j = 0, k)
In pasul k + 1 avem primele k-1 elem verificate si avem doua cazuri:
max < a[k] -> max = a[k]
max > a[k] -> max ramane
Rezulta la pasul k+1 avem maxim(a[j], j = 0, k)
Pas4:
F(i)= n - i - 1, i = 1, n - 1. in cazul in care i = n-1 ->F(n-1) = n - n + 1 -1 = 0
F(i) < F(i+1), oricare ar fi i. n - i - 1 < n - i (Adevarat)
Pas5:
Complexitate timp:
Cazul
max = a[0]; -> 1
for(i = 1; i< n; ++i) -> 1 atribuire, n-1 cicli completi, încă o verificare de a ieși din for ->
2(n-1) + 2 = 2n unit timp
if(max < a[i]) -> 1
max = a[i]; -> 1
Calculăm pentru ciclu 1
Total 1 + 2n + 2*(n-1) = 2n + 1 + 2n -2 = 4n -1
● favorabil: maximul este primul element: 1 + 2n + 1*(n-1) = 3n => O(n)
● nefavorabil: maximul este ultimul element: 2n + 1 + 2n -2 = 4n -1 => O(n)
● mediu: este greu de calculat
● Caz favorabil = Caz nefavorbil => Tetha(n)
Caz favorabil < Caz nefavorabil => Omega(fav) si O(nefav)
SUBIECT 3 INSERTION SORT
for(i = 2; i <= n; ++i)
{
aux = x[i];
j = i - 1;
while(j >= 1 && aux < x[j])
{
x[j+1] = x[j];
j = j - 1;
}
x[j+1] = aux;
}
Pas1: scriem pre si postconditiile
Preconditii: trebuie sa sortam un vector => trebuie sa avem in vector sa le putem sorta
=> P: n >= 1
Postconditie: la final de algoritm sa avem vectorul sortat
Q: a[j-1] < a[j], j = 1,n-1
Pas2: Se fac adnotari
P0:(a, i, j, aux) => inca nu stim nimic despre elem din vector
I1: x[j-1] < x[j], oricare ar fi j = 1,i //invariantul dupa ce se termina un ciclu de for
//SE PUNE CE SE INTAMPLA LA SF DE CICLU
for(i = 2; i <= n; ++i)
{
P0:(a, i, j, aux) ^ (i<=n)
A1: aux = a[i];
P1:(a,i,j, aux = a[i])
A2: j = i - 1;
P2:(a,i,j=i-1, aux)
I2: x[k-1] < x[k] oricare ar fi k = 1, j
//toate elementele vor fi sortate de pana la j
while(j >= 1 && aux < a[j])
{
P2 ^ (j>=1) ^ (aux < a[j))
A3: a[j+1] = a[j];
P3:(a,i,j,aux)
A4: j = j - 1;
P4: (a,i,j = j-1,aux)
}
P4 ^!(j >= 1 && aux < a[j])
A5: a[j+1] = aux;
P5:(a,i,j,aux)
}
Asertiunile:
P0 ^ (i<=n) -A1> P1
P1 -A2> P2
P2 ^ (j>=1) ^ (aux < a[j)) -A3> P3
P3 -A4> P4
P4 -> P2 (se continua while ul)
P4 ^!(j >= 1 && aux < a[j]) -A5> P5
P0 ^ (i > n) -> Q (se termina for ul si se termina alg)
Dem corectitudinii invariantului 2:
Pp ca suntem la pasul k, deci la pasul k o sa avem vectorul sortat de la 1,k-1. Urmeaza
sa facem verificarea cu elementul k. Avem 2 cazuri:
1. La pasul k +1 verificam daca elementul de pe pozitia k + 1 este mai mic decat
pozitiile dinaintea lui. Daca da, se face o shiftare la dreapta cu o pozitie pana
cand elem de pe k + 1 va fi mai mare decat elem dinaintea lui. => o sa fie un sir
crescator
Facem finititudinea pt while:
Pentru fiecare i în cel mai rău caz se parcurg i-1 iterații pana ajunge j la 0, dupa care
face iese din while.
Calculul complexitatilor:
Cazul favorabil : cand vectorul este deja sortat crescator
Pentru ca e ft greu de calculat pt tot alg, gasim operatia dominanta, cea care se executa
de cele mai multe ori, adica while.
i=2,n, i <=n
N-1 ori
while(j >= 1 && aux < x[j]) //avem 2 verificari in while
{
x[j+1] = x[j]; //o atribuire, 1 dar nu se executa daca vectorul e deja ordonat cresc
j = j - 1; // o atribuire, 1
}
T(n)= 2(n-1) = O(n)
Cazul nefavorabil : cand vectorul e ord descres
In while, se tot fac interschimbari
123456
654321
5 6 4 3 2 1 -> 1
4,5,6,3,2,1,-> 2 mutari etc pana nu mai putem
1+2+3+...+n-1 = n(n-1)/2 + n-1 -> O(n^2)
4 5 6 3 2 1 -> 4 5 6 6 2 1 -> 4 5 5 6 2 1 -> 4 4 5 6 2 1 -> 3 4 5 6 2 1
Caz fav < caz nefav
Omega(n) O(n^2)