Partea 1

Capitolul 1

ALGORITMI ŞI PROGRAME

Calculatorul poate constitui o prelungire utilă a inteligenţei umane în măsura în care el este programat astfel încât să permită rezolvarea eficientă a unor probleme concrete. Programul conţine informaţia necesară soluţionării unei probleme sub forma succesiunilor de instrucţiuni care descriu operaţii de prelucrare pe care un calculator real sau virtual le poate executa. Dacă programul descrie procesul de soluţionare automată a unei anumite probleme, sistemul de programe, produs informatic de o complexitate mai ridicată, conţine virtual soluţiile mai multor probleme distincte, dar legate

între ele. Astfel compilatorul reprezintă un program, în timp ce sistemul de operare al unui calculator sau sistemul de rezervare a biletelor de avion sunt sisteme de programe.

Din punct de vedere static, programul poate fi privit ca o funcţie f definită pe mulţimea datelor iniţiale X cu valori în mulţimea rezultatelor finale Y. Funcţia f: X->Y, care reprezintă în mod static programul, poate fi o funcţie parţială, dacă pentru orice x e X există cel mult o valoare y e Y astfel încât y = f(x), sau poate fi o funcţie totală dacă pentru orice xe X există o valoare y e Y astfel încât y = f(x). Astfel, funcţia totala corespunde unui program care permite soluţionarea unei probleme pentru orice date iniţiale posibile, în timp ce funcţia partiala corespunde unui program, care furnizează soluţii numai pentru anumite seturi de date iniţiale.

Noţiunea de funcţie nu poate modela complet un program deoarece eludează modul constructiv de soluţionare a problemei prin calculul efectiv al rezultatului pe baza unei succesiuni de operării simple. Acest aspect dinamic al programului poate fi modelat prin noţiunea de algoritm. Algoritmul este o procedură de evaluare a unei funcţii prin care se determină, pentru fiecare element din domeniul de definiţie al funcţiei, valoarea corespunzătoare [1]. Algoritmul este descris prin precizarea atât a domeniului datelor iniţiale, cât şi a instrucţiunilor formate din operaţii elementare, care pot fi executate de către un agent uman, mecanic sau electronic, în speţă de către un calculator. Algoritmul exprimat printr-o succesiune de instrucţiuni inteligibile de către calculator constituie însuşi programul.

O problemă rezolvabilă cu ajutorul calculatorului este reprezentată de o funcţie calculâbilă, adică algoritmică. Una şi aceeaşi funcţie poate fi evaluată de mai mulţi algoritmi. Există însă şi funcţii care nu pot fi evaluate de nici un algoritm. Cercetările matematice au stabilit care sunt clasele de funcţii calculable (algoritmice) [1]. Astfel, familia funcţiilor primitiv recursive constituie clasa de funcţii cel mai uşor de calculat.

Pentru a defini această clasă se consideră funcţiile de bază S(x) = x + 1 (funcţia succe sor) iar [x] este partea întreagă a lui x. Funcţia E(x) reprezintă abaterea faţă de cel mai apropiat pătrat perfect mai mic

decât x.Familia funcţiilor primitiv recursive este cea mai mică familie de funcţii care contine funcţiile S şi E si este închisă faţă de operabile de adunare, compunere şi iteraţie. Se observă că orice astfel de funcţie poate fi construită pornind de la funcţiile de bază si aplicând de un număr finit de ori cele trei operaţii, în orice ordine. Astfel funcţia f(x) = x + 4 este primitiv recursivă deoarece se obţine .prin aplicarea de patru ori a compunerii asupra funcţiei succesor f(x) = S(S(S(S(x)))).

Se demonstrează [1] că orice funcţie primitiv recursivă este totală. într-adevăr, funcţiile de bază S şi E sunt totale, iar operaţiile de sumă. compunere şi iteraţie păstrează această proprietate.

In cazul funcţiilor de mai multe variabile, rolul iteraţiei este jucat de recurenţa primitivă. Fie g şi h două funcţii totale de n, respectiv n + 2 variabile. Cu ajutorul lor se defineşte o funcţie unică f de n+l variabile astfel încât f( x₁,x₂,x_3, .. .x_n 0) = g( x₁,x₂,... x_n) şi f( x₁,x₂,, y+ 1)-A(x„ x₂,. . x„ y,fix_v x₂, x₃, ...,x„ y)).

Funcţia f a fost definită prin recurenţă primitivă cu ajutorul funcţiilor g şi h. Variabila y este variabilă de recurenţă, iar variabilele x₁,x₂,x_3, .. .x_n sunt parametri.

Se poate acum defini familia functiilor primitiv recursive de n variabile ca fiind cea mai mică familie de funcţii care conţine funcţiile constante C (x₁,x₂,x_3, .. .x_n) = m, proiecţii P(x₁,x₂,x_3, .. .x_n)= x; {1<=i<=, n), succesor S(x) = x + 1 şi este închisă faţă de operaţiile de compunere funcţională, f(x₁,x₂,x_3, .. .x_n) = h(x₁,x₂,x_3, .. .x_n), . . ., gx₁,x₂,x_3, .. .x_n) şi de recurenţă primitivă.

Multe funcţii uzuale ca funcţia exponenţială, factorial, predecesor, funcţiile semn şi de comparaţie sunt primitiv recursive. Există funcţii calculabile care nu sunt primitiv recursive. Asemenea funcţii sunt funcţiile parţiale care sunt calculabile pentru orice valoare a argumentului în domeniul de definiţie şi anumite funcţii care cresc mai repede decât orice funcţie primitiv recursivă. Pentru a extinde clasa recursivitătii primitive astfel încât să includă şi alte funcţii calculabile, se defineşte operaţia de minimizare. O funcţie f(x), se obţine prin minimizarea unei funcpi totale g(x, y) în felul următor: dacă există y astfel încât g(x, y) = 0, sumă fx) este cel mai mic ycare îndeplineşte condiţia respectivă; dacă, pentru orice y, g(x. y)!= 0 atunci f(x) nu este definită. O funcţie obţinută prin minimizare nu este neapărat totală, deci nu face parte în mod necesar din clasa funcţiilor primitiv recursive.

O clasă care include numai funcţii calculabile fără să fie toate primitiv recursive este clasa funcţiilor parţial recursive, care este cea mai mică familie de funcţii care conţine funcţiile succesor, constante şi proiecţii şi care este închisă faţă de operaţiile de minimizare aplicate unei funcţii totale, compunere funcţională şi recurenţă primitivă. Se observă că orice funcţie primitiv recursivă este parţial recursivă dar reciproca nu este adevărată. Operaţiile de compunere funcţională şi de recurenţă primitivă pot fi aplicate unor funcţii parţiale, dar operaţia de minimizare acţionează numai asupra funcţiilor totale. Familia funcţiilor parţial recursive conţine numai funcţii calculabile, deoarece funcţiile de bază sunt calculabile iar operaţiile de compunere funcţională, recurenţă primitivă şi minimizare conservă această proprietate.

O categorie intermediară între familia funcţiilor parţial recursive şi familia funcţiilor primitiv recursive este aceea a funcţiilor recursive, care include funcţiile care sunt în acelaşi timp totale şi parţial recursive. Astfel, o funcţie primitiv recursivă este şi recursivă, o funcţie recursivă este şi parţial recursivă, dar afirmaţiile reciproce nu sunt adevărate.

Funcţiile parţial recursive par să acopere întreaga mulţime a funcţiilor calculabile prin algoritmi, oricât de complicaţi. Teza Church-Turing afirmă că orice funcţie calculabilă este parţial recursivă, iar orice funcţie totală şi calculabilă este recursivă. Această teză nu poate fi demonstrată matematic, ci doar justificată pe baza unor argumente pre matematice. [1].

Admiţând valabilitatea tezei Church-Turing, rezultă o descriere matematic exactă a funcţiilor calculabile prin algoritmi, respectiv a problemelor care pot fi rezolvate cu ajutorul calculatorului Dacă aceste probleme pot fi descrise riguros din punct de vedere static cu ajutorul conceptului matematic de funcţie, descrierea lor dinamică, prin intermediul noţiunii de algoritm, este mai puţin riguroasă. Este uşor să se dea exemple de algoritmi sau de proceduri care nu sunt algoritmice, dar este dificil să se construiască un model matematic general pentru noţiunea de algoritm. Este important insă de relevat aptul că o funcţie care poate fi evaluată printr-un algoritm de un anumit tip. de exemplu de o maşină Turing, poate fi evaluată şi printr-un algoritm de alt tip, de exemplu un algoritm Markov.

Rezultă o invariantă a familiei funcţiilor calculabile în raport cu definiţia algoritmului, în concluzie, pentru o anumită problemă reprezentată de o funcţie parţial recursivă, există cel puţin un algoritm cu ajutorul căruia ea poate fi rezolvată, adică o procedură sistematică de calcul al rezultatelor printr-o succesiune controlată de operaţii elementare.

Abordarea programului la nivel global este o abordare statică prin care programul este văzut ca o funcţie calculabilă (parţial recursivă) care transformă datele de intrare în rezultate la ieşire. într-o abordare dinamică a modului de construcţie sistematică a rezultatelor, programul trebuie privit din unghi de vedere structural luând în consideraţie componentele sale şi relaţiile dintre ele.

La nivelul elementar, programul este compus din instrucţiuni, fiecare instrucţiune descriind o operaţie pe care o maşină reală sau virtuală o poate executa. Astfel de operaţii sunt operaţiile aritmetice (reductibile la adunare, în cod binar) şi comparaţia între două numere. Ordinea de execuţie la timp a instrucţiunilor constituie structura programului. Pentru descrierea structurilor fundamentale se pot folosi grafuri orientate (organigrame), pseudocodun şi diagrame arborescente. O organigramă este un graf orientat în care nodurile reprezintă procese de calcul, iar arcele reprezintă transferul de control

(ordinea în care procesele de calcul sunt executate). Pseudocodul este o notaţie care permite exprimarea logicii programelor într-un mod oarecum formalizat, fără a fi necesare reguli de sintaxă ca în limbajele de programare. Diagrama arborescentă este un mod de notare asemănător cu pseudocodul dar dispus sub o formă grafică sugestivă pentru etapele de rezolvare ale problemei.

Fig.1.1. Noduri: i) proces; b) predicat; c) colector,

Nodurile utilizate într-o organigramă sunt de trei feluri: noduri proces, noduri predicat şi noduri colector (fig. 1.1). Un nod proces este asociat unei funcţii calculabile f: X ->Y care transformă datele de intrarea în rezultatele parţiale Y la ieşirea nodului. Nodul predicat este asociat unei funcţii binare de comparaţie de tipul: funcţii care sunt primitiv recursive Acest nod transferă controlul pe una din cele două

ieşiri, realizând o ramificare a programului, după cum condiţia c este sau nu îndeplinită.

Nodul colector este asociat funcţiei identitate şi are rolul de dirijare a controlului într-un singur punct.

Un program propriu sau bine format este caracterizat printr-un singur arc de in trare şi un singur arc de ieşire, iar pentru orice nod, există cel puţin un drum de la arcul de intrare la arcul de ieşire care trece prin acel nod. Două programe sunt echivalente dacă definesc aceeaşi funcţie fără a avea structuri de control neapărat identice.

O structură de bază a unui program este structura secvenţială, în care ordinea execuţiei coincide cu ordinea sintactică, adică instrucţiunile sunt executate în ordinea în care au fost scrise. In reprezentarea cu pseudocoduri şi cu diagrame arborescente, structura secvenţială se notează (BLOCK, S₁,S₂ ) (fig. 1.2).

Structura alternativă (de selecţie) caracterizează acele părţi din program care conţin secvenţe de instrucţiuni care se execută numai în anumite condiţii (fig. 1.3). în reprezentarea prin organigramă, nodul predicativ indică succesiunea de execuţie S_tS₂dacă este îndeplinită condiţia c şi succesiunea S_tS_} în caz contrar. în celelalte două reprezentări, structura alternativă se notează (IF THEN ELSE, c, S₂,S₃).

Structura alternativă cu ramură vidă este un caz particular al celei precedente, caz în care într-una din variante nu se execută nici o instrucţiune. Notaţia utilizată este (IF THEN, c, S₂,) (fig. 1.4).

a b c

fig. 1.2. Structura alternativa reprezentata prin a)organigrama; b)pseudocod; c)diagaramana arborescenta.

(2. 9)

Durata de restabilire depinde de caracteristicile de mentenabilitate ale sistemului, respectiv de capacitatea acestuia şi a mijloacelor de întreţinere de a asigura revenirea cât mai rapidă la starea de funcţionare.

Menlenabilitatea este modelată prin caracteristicile numerice ale timpului de reparate, care suni matematic similare cu cele ale timpului de funcţionare. Astfel, probabilitatea G(v), ca repararea să se termine în intervalul (O,y), este analogi cu complementara funcţiei de Habilitate. Distribuţia duratei de reparare g(y) - G '(y) este similară cu distribuţia timpului de funcţionare/x) iar rata de reparare p(y) = g(v)/(l- G(y)) este similară cu rata de defectare z(x). Media timpului de reparare (p. sau MTTR) se calculează direct pornind de la distribuţia g(y).

O apreciere globală a eficienţei sistemului ţinând seama atât de fiabilitatea ţi de mentenabilitatea acestuia este posibilă cu ajutorul disponibilităţii A(t), care reprezintă probabilitatea ca la un moment arbitrar i, sistemul să se afle în stare de funcţionare.

Disponibilitatea A(t) permite calculul fracţiunii medii active dintr-un interval calendaristic (t. t+x), numită disponibilitate medie pe interval:

(2.10)

O relaţie importantă între disponibilitate si funcţiile de reînnoire este.

(2 11)

Relaţia (2.11) afirmă că probabilitatea ca sistemul să fie defect la momentul t este diferenţa dintre numărul mediu de defectări şi numărul mediu de puneri în funcţiune ale sistemului în (0, 0. Justificarea acestei relaţii este imediată.în teoria fiabilităţii se studiază modelul descris mai sus în diferite ipoteze care, dacă sunt adecvate studiului sistemelor hardware, sunt rareori aplicabile sistemelor de programe. Pentru exemplificarea modelului, vom considera clasa sistemelor fără uzură (CFR) deoarece, pe de o parte, se constituie un termen de referinţă în teoria fiabilităţii iar, pe de altă parte, ea include, în mod evident, sistemele de programe.

Sistemul fără uzură este caracterizat de o rată de defectare constantă- z(x) - k, astfel încât pericolul de defectare nu este influenţat de vârsta sistemului. Conform relaţiilor (2.4) şi (2.1), rezultă că funcţia de fiabilitate a unui sistem fără uzură este de tip

exponenţial şi depinde numai de intervalul de funcţionare, nu şi de vârsta sistemului:

(2 12)

Inversând relaţia (2.12) se obţine cuantila timpului de funcţionare, adică durata de funcţionare asociată probabilităţii R de succes.Densitatea de probabilitate a timpului de funcţionare are forma,cunoscuta lege de distribuţie exponenţială. Media timpului de funcţionare este egală cu durata medie reziduală de viaţă, iar ambele sum egale cu inversul ratei de defectare:s

(2.13)

Calculul dispersiei pe baza relaţiei (2.7) conduce la o abatere medie pătratică a = IM,, adică la un coeficient de asimetrie egal cu unitatea. Aceasta înseamnă că absenţa uzurii implică o mare diversitate între sistemele de acelaşi tip, unele defectându-se foarte devreme, altele foarte târziu.

Elementele calculate până acum sunt suficiente pentru prognoza primei defectări a sistemului. Dacă se ţine seama şi de posibilităţile de reparare ale sistemului fără uzură, sunt necesare ipoteze suplimentare asupra modului în care funcţionarea sistemului poate fi restabilită după defectare. Considerăm repararea minimală care, în cazul sistemelor iară uzură, este echivalentă cu reînnoirea propriu-zisă, sistemul rămânând în starea iniţială atâta vreme cât funcţionează. Admiţând, pentru moment, că durata de reparare este neglijabilă, se poate arăta [1] că procesul de reînnoire este de tip Poisson, adică probabilitatea producerii a rdefectări în (0, t) este:

(2.14)

Funcţia de reînnoire este B(l) = kt iar densitatea de reînnoire este constantă şi coincide cu rata de defectare h(t) = k. Astfel, procesul de defectare este staţionar şi numărul mediu de defectări se poate calcula împărţind intervalul de timp la media timpului de funcţionare, care, în cazul analizat, coincide cu media timpului între defectări succesive (MTTF = MTBF). Funcţia de fiabilitate în interval şi durată de viaţă reziduală nu sunt afectate de reparările efectuate, astfel încât R{i, t+x) = R(x) = e"**şi m{t) = IA.. Deoarece duratele de reparare au fost neglijate, disponibilitatea este mereu egală cu unitatea.

în cazul în care nu se neglijează duratele de reparare, trebuie făcute ipoteze suplimentare asupra legii de distribuţie a acestora. Presupunem că şi această lege este de tip

exponenţial, adică g(y) = pe~w, unde p este rata constantă de reparare, iar inversul ei este u>, media timpului de reparare. Această ipoteză este adecvată situaţiilor când repararea nu urmează o procedură sistematică astfel încât ea poate fi încheiată oricând, independent de durata efortului de diagnoză şi remediere. în acesta situaţie disponibilitatea poate fi calculată utilizând metodele din [1], care conduc la expresia:

(2.15)

Procesele de defectare, respectiv de punere în funcţiune sunt caracterizate de densităţile de reînnoire respective:

(2.16)

Integrarea expresiilor (2. 16) într-un interval oarecare conduce la stabilirea numărului mediu de defectări, respectiv de puneri în funcţiune care se produc în acel interval.

Funcţia de fiabilitate în interval şi durata medie de viaţă reziduală depind, de data aceasta, de caracteristicile procesului de reparare. Avem:

(2. 17)

Trecând la limită, pentru f -* , în relaţiile (2.15) - (2.17), se remarcă staţionarizarea asimptotică a proceselor de defectare ţi de punere în funcţiune. Disponibilitatea devine constantă în regim staţionar ţi egală cu raportul dintre media timpului între defectări succesive si media duratei unui ciclu funcţionare-reparare. Densităţile de reînnoire devin constante şi egale cu inversul duratei unui ciclu repetitiv. Funcţia de fiabilitate în interval şi durata medie reziduală de viaţă sunt fracţiuni constante (determinate de disponibilitate) din funcţia de fiabilitate iniţială, respectiv din media timpului de funcţionare.

Este, desigur, de dorit ca modelul global al fiabilităţii, descris şi exemplificat în acest capitol, să poată fi aplicat cu minime modificări ta analiza fiabilităţii sistemelor de programe. In acest scop vor fi studiate cauzele care dau un caracter aleator comportării în timp a programelor.

2.2. FIABILITATEA PROGRAMELOR

O viziune naivă asupra fiabilităţii programelor exclude orice preocupare privind comportarea lor în timp. Dacă un program este bun, in sensul că nu conţine erori, el rămâne bun un timp nelimitat, până la eventualele intervenţii in vederea modificării şi perfecţionării sale. într-adevăr, dacă etapele elementare ale rezolvării unei probleme sunt bine stabilite, este teoretic imposibil ca, în timp, ele să se dovedească incapabile să conducă la rezultate corecte. O examinare mai atentă arată că la elaborarea programuluinu putem avea în vedere întreaga mulţime A' a datelor iniţiale posibile. Programul este gândit şi testat iniţial pentru o submulţime ,f_rcl a datelor de intrare. Acest fapt nu garantează că pentru'orice x e X programul' va conduce în timp finit la rezultate corecte Vom admite că este totdeauna posibil să sesizăm comportarea incorectă a unui program Aceasta înseamnă că în mulţimea rezultatelor finale ¥ se poate delimita o submulţime Yf cr )' astfel încât dacă rezultatul concret y aparţine lui Yp putem trage concluzia că programul este incorect Un program este parţial corect dacă orice rezultat y obţinut prin prelucrarea unei date iniţiale iei aparţine domeniului complementar lui Yf, adică v e Y_F= Y-Y_r Programul este corect dacă rezultatul yeY_r este efectiv obţinut în timp finit, adică nu se execută de o infinitate de ori instrucţiunile unei structuri repetitive iar execuţia nu se întrerupe printr-un eventual mesaj de eroare.

Un program conţine erori dacă există o submulţime X_F inclusă în mulţimea datelor iniţiale posibile astfel încât, pentru orice x e X rezultatul y = F(x), fie nu se poate obţine in timp finit, fie aparţine submulţimii y,(fig. 2.1).

Un program este cu atât mai fiabil cu cât dimensiunea Y = 1 / X siunea domeniului X_r este mai redusă. Prognoza defectării unui program este afectată de două surse de WRITE Y

incertitudine. Pe de o parte, variabilitatea datelor ne _enrJ împiedică să prevedem dacă următoarele date vor aparţine domeniului X_F sau nu. Pe de altă parte, variabilitatea programelor care pol implementa o aceeaşi funcţie ne împiedică să ştim cu siguranţă dacă o anumită valoare particulară x se află sau nu în domeniul X_F al programului. Pentru exemplificarea consideratiilor de mai sus, se consideră două programe foarte simple care calculează inversul unui număr real (fig. 2.3). Primul program va da rezultate eronate (eroare de execuţie) de fiecare dată când variabila de intrare se întâmplă să fie mai mică decât EPS, adică decât cel mai mic număr real reprezentam! de către calculator. Astfel Xf, = {xeX\ x < EPS}. Al doilea program este mai fiabil deoarece Xf-, - {EPSJ, adică nu s-a prevăzut că în situaţia când variabila de intrare este egală cu cel mai mic număr posibil, inversul acestuia poate fi totuşi calculat. Deşi programele implementează aceeaşi funcţie, primul va conduce Ia defectare ori de câte ori la intrare apare o valoare x < EPS iar al doilea numai când la intrare apare x = EPS. Se observă atât aleatorismul apariţiei datelor cât şi cel generat de modul de construcţie al programului.

Variabilitatea dalelor de intrare şi a structurilor raţionamentului de rezolvare a problemei constituie sursele lipsei de fiabilitate a programelor. O exprimare cantitativă a acestei variabilităţi poate fi efectuată cu ajutorul noţiunii de entropie [4], Se ştie că, pentru o variabilă aleatoare Z, distribuită după legea 9(2), o măsură a împrâştierii este dată de entropia

(2,18)

Entropia (2.18) exprimă cantitatea de informaţie furnizată de un experiment în urma căruia se obţine rezultatul particular z.Pentru a exprima variabilitatea datelor de intrare cu ajutorul entropiei se admite că mulţimea X a acestor date este discretă, având cardinalul N*. Presupunem, pentru simplitate, că programul utilizează la fiecare executare, un unic element din X ca dată ini ţiala. Fie a* volumul de date procesate în intervalul (0, /). Un caz extrem de uniformitate este acela în care programul utilizează de a' ori aceeaşi dată iniţială xq ea". O astfel de situaţie se întâlneşte de exemplu la scăderea din inventar a unui aceluiaşi articol la fie care operaţie. Cazul opus este acela în care programul se execută mereu cu altă dată ini-

ţială, respectiv cu x_u x₂, . . ., x_y.Daca N<=N*, valorile iniţiale x_p x_t, . , ., x_H sunt dis tincte şi fiecare apare o singură dată. Dacă N > N*, este obligatoriu ca măcar unele din valorile domeniului de intrare X să se repete. într-un caz oarecare, diferit de cele extreme discutate anterior, datele de intrare se vor repeta de un număr oarecare de ori, astfel încât se poate considera că mărimea de intrare a programului în (O,t) este o variabilă aleatoare discretă distribuită după legea:

In expresia (2.19), n,n₁,n₂,n₃,...,n_n reprezintă numărul de apariţii repetate a datelor posibile x₁,x₂,x₃,...,x_n, astfel încât unii n₁ pot fi nuli si n₁+n₂+n₃+...+n_n = N. Particula rizând formula entropiei pentru acest caz, se obţine o măsură a variabilităţii datelor.

(2.20)

Cazul variabilitaţii minime este reprezentat de valorile particulare n_k = N şi {n_k = 0: j = I. 2, . , N* j !=K}, ceea ce înseamnă ci valoarea se repetă de -V ori Ia intrarea programului în (0. t). Din expresiile (2.19) şi (2.20) rezulta Hmin = 0.Cazul extrem de variabilitate maximă se obţine pentru n = {0, 1}. i = = 1.2,..., N*, ceea ce înseamnă că fiecare valoare din.Y poate apărea cel mult o dală la intrarea programului Evident, acest lucru implică A' < A'". Entropia datelor este în acest caz maximă şi, conform relaţiei (2,20), este egală cu log /V. Variabilitatea datelor creşte cu volumul de procesare, respectiv cu N, dar este limitată de numărul maxim posibil de date de intrare N* într-adevăr, dacă N > A*, unele din valorile r,. x₂, trebuie să se repete Entropia este maximă când distribuţia p(x) este uniformă. Dacă A' = A-A'*, (K = 2, 3, .), avem n_l~n_l = ...n_fr = K, adică fiecare valoare de intrare se repetă exact de A' ori iar entropia maximă rezultată este H_Xm = logA" în cazul în. care A' nu este divizibil cu A"*, entropia este maximă când valorile de intrare se repetă in mod cât mai egal. ceea ce înseamnă că entropia maximă este Hx** = log A"". Se observă deci că variabjlitatea datelor creşte de la zero până la log A¹ şi că valoarea maximă a variabilităţii nu poate depăşi log N*.

Pentru a defini variabilitatea la nivelul programului se grupează inu-o anumită categorie toate datele din .V care sunt procesate pe o anumită cale din graful orientat care reprezintă programul. Fie numărul acestor căi şi g„g,, categoriile dedate care apar în (O. (), corespunzătoare respectiv fiecărei căi de prelucrare. Categoria căreia îi aparţine o anumită valoare iniţială este o variabilă aleatoare distribuită după legea: