Informatiile si reprezentarea lor in informatica

Informatiile si reprezentarea lor

1. Introducere

Dupa unii autori informatia trebuie privita ca o notiune primara. Din acest punct de vedere ea prezinta doua aspecte esentiale[1]: primul este aspectul semantic si al doilea aspect sintactic.

Sa incercam sa detaliem aceste doua aspecte. Sub aspect semantic, orice informatie trebuie privita ca niste mesaje transmise, idei emise, cunostinte cu caracter de noutate etc. Astfel perceputa informatia nu poate exista decat pe suporturi de informatie materializate prin diverse medii fizice ori biologice. Asa de pilda memoria umana, memoria animala (in mica masura), memoria unui computer, casetele audio si video, discurile magnetice, hartia de scris, CD-ul, pelicula foto etc. reprezinta doar cateva din exemplele de suporti de informatie existenti in natura si exploatati in mod curent. Privita sub aspect sintactic informatia trebuie inteleasa prin modul ei de reprezentare pe diversele suporturi de informatii.

De cele mai multe ori informatia nu este un element singular, ci se gaseste impreuna cu ale informatii, fie de acelasi tip fie de tipuri diferite, grupate in multimi. Prin definitie intelegem prin multime informationala, orice multime ale carei elemente sunt informatii. Asa de exemplu multimea numelor studentilor dintr-un an de studiu al unei facultati reprezinta o multime informationala, dupa cum multimea de elemente (x, y, z), unde x reprezinta numele studentului dintr-un an de studiu al unei facultati, y reprezinta domiciliul respectivului student si z reprezinta media sa de admitere in facultate, este de asemenea o multime informationala. Este de la sine inteles ca putem avea si submultimi informationale care prin reuniune dau o multime informationala. De pilda, daca ne referim la exemplul precedent, multimea de elemente (x, y, z) care se refera la studentii unei facultati, este constituita in urma reuniunii elementelor (x₁, y₁, z₁) corespunzatoare semigrupelor de studenti sau reuniunii elementelor (x₂, y₂, z₂) corespunzatoare grupelor de studenti ai unei specializari sau reuniunii elementelor (x₃, y₃, z₃) corespunzatoare specializarilor care pe care le are facultatea. Prin urmare multimile (x₁, y₁, z₁), (x₂, y₂, z₂) si respectiv (x₃, y₃, z₃) sunt submultimi informationale ale multimii informationale (x, y, z).

Asa cum se cunoaste din matematica cu multimile (in general) se pot efectua diverse operatii si prelucrari. Prin urmare si cu multimile informationale (in special) se pot efectua prelucrari. Prin definitie intelegem prin prelucrarea informatiilor, la modul cel mai general, un proces de sistematizare si sintetizare a multimilor informationale in vederea unui scop bine definit.

Ansamblul teoriilor, tehnicilor, metodelor, procedeelor si modelelor matematice concepute in scopul prelucrarii multimilor informatice se numeste informatica

Prelucrarea informatiilor se poate face in mod manual, in mod automat sau mixt. Prelucrarea manuala a informatiilor presupune interventia nemijlocita a factorului uman de la culegerea informatiilor pana la obtinerea rezultatelor finale, a caror scop este de a ajuta actul decizional sau de a pastra rezultatele pentru a fi un element documentar necesar unor prelucrari ulterioare. Daca prelucrarea informatiilor se face cu ajutorul unui sistem de calcul electronic (calculator electronic) atunci avem prelucrarea automata a informatiilor. Doar in cazul conducerii cu calculatorul a proceselor industriale, unde culegerea de date si prelucrarea se face in mod automat, putem vorbi de o adevarata prelucrare automata a informatiilor. Deoarece culegerea primara se face manual si doar prelucrarea se face automat putem spune ca in marea majoritate a cazurilor avem o prelucrare mixta a informatiilor. Totusi in cele mai multe cazuri in loc de prelucrare mixta a informatiilor se utilizeaza notiunea de prelucrare automata a informatiilor.

Un calculator (sistem de calcul electronic) nu este capabil sa prelucreze informatiile sub aspectul lor semantic ci numai sub aspect sintactic, motiv pentru care el nu este capabil sa ia niciodata decizii proprii, orice decizie pe care o ia calculatorul intr-un proces de prelucrare a fost prevazuta de cel care a proiectat si realizat procesul de prelucrare respectiv. Din acest punct de vedere, "inteligenta" calculatorului este direct proportionala cu inteligenta celui care a conceput procesul de prelucrare a informatiilor.

Tinand seama de cele prezentate anterior rezulta ca absolut oricarui proces de prelucrare automata a informatiilor trebuie sa-i fie indicat, intr-o forma pe care-i capabil sa o inteleaga, fara ambiguitati si fara echivoc, o descriere secventiala de actiuni (reguli) care se numeste algoritm.

Ca fundament al fiecarui proces de prelucrare automata a datelor sta faptul ca aspectul semantic al informatiilor, care specifica procesul de prelucrare, trebuie neaparat sa fie in deplina concordanta cu aspectul semantic al acestor informatii.

Actiunile si regulile care apar intr-un proces de prelucrare automata a informatiilor sunt materializate in calculator prin niste informatii, specifice fiecarui tip de calculator, numite instructiuni. Totalitatea secventei de instructiuni care materializeaza un algoritm de prelucrare automata se numeste programul acelui proces de prelucrare. Pentru a putea fi mai usor conceput un program el trebuie introdus intr-un anumit limbaj informational. Retinem ca programul si date pe care le prelucreaza pot coexista in memoria interna a calculatorului. Sarcina de a face distinctie intre zona de program si zona de date revine calculatorului printr-o componenta esentiala numita sistem de operare. Sistemul de operare asigura gospodarirea tuturor resurselor hardware (echipamentele fizice ale calculatorului) si software (programele de prelucrare).

Hardware prescurtat hard) este un termen generic desemnand circuitele electronice, dispozitivele si echipamentele componente ale unui sistem de calcul electronic, el specifica toate unitatile fizice existente, cu functii bine determinate, in cadrul sistemului de calcul, aceste functii sunt specificate de catre fabricant si stau la dispozitia utilizatorului care le poate exploata dupa propria lui dorinta[2].

Software (prescurtat soft) este termenul generic reprezentat de totalitatea programelor de sistem cu care este echipat un calculator, privite prin prisma relatiilor reciproce realizate si a functiilor realizate[3]. Din punct de vedere al domeniului de aplicatie software-ul se clasifica in software de baza si software aplicativ.

2. Limbaje informationale si codificarea informatiei

2.1. Limbaje informationale

Sa consideram o multime informationala pe care s-o numim vocabular informational si pe care s-o notam cu V, care genereaza monoidul liber V*, adica:

V* = V⁰ U V¹ U V² U . . . U Vⁿ U . . .

Numim limbaj informational pe V, orice submultime informationala L a monoidului liber V*. Numim prin conventie informatii elementare elementele vocabularului V, deoarece L V*, iar informatii compuse oricare din elementele multimii informationale V* - . In general oricare multime informationala M poate fi considerata fie ca un vocabular informational, fie ca un limbaj definit pe un vocabular informational. Daca vom considera in continuare limbajul informational L definit pe vocabularul V, atunci structura informatiilor din L este data de gramatica limbajului L. Gramatica limbajului L este data de o colectie finita de reguli cu ajutorul carora se pot genera toate informatiile din L.

Sa consideram un limbaj informational L definit pe vocabularul finit V, a carui gramatica o notam cu Γ = <V_T, V_N, q A> unde V_T = V, V_N, = , A = U U U } unde V_i cu I=1,,6 sunt elementele unei partitii a lui V iar q este simbolul de start pe care-l numim si axioma gramaticii. In continuare, se observa imediat ca limbajul informational L este de fapt multimea informationala a carei expresie este:

L = = V₁ x V₂ x V₃ x V₄ x V₅ x V_6.

Prin conventie , daca scriem regulile A sub forma:

A (v₁, B, C)

B (v₂, v₃)

C (v₄, D)

D (v₅, v₆)

vom scoate in evidenta structura informatiilor din limbajul informational L. Iar daca exprimam limbajul informational prin:

L = = V₁ x (V₂ x V₃ )x (V₄ x (V₅ x V₆))

putem reprezenta sub forma de graf, fiecare informatie iIL ca in figura 1.

Fig. 1. Graficul informatiei apartinand unui limbaj informational 

Daca exceptam radacina A, ordinea nodurilor din graf este data de regulile multimii de reguli A in felul urmator: pentru fiecare regula n n₁n₂ . . . n_k din multimea A si pentru orice 1 i j k, n_i impreuna cu absolut toti descendentii sai sunt situati la stanga lui n_j si evident a tuturor descendentilor acestuia.

Din punct de vedere conceptual toate limbajele de programare au respectat teoria prezentata anterior. Bazandu-se fiecare pe reguli si gramatici proprii s-a ajuns la un numar foarte mare de limbaje, a caror evolutie este prezentata sub forma de schema in cele ce urmeaza. Mai trebuie remarcat ca numarul limbajelor este mult mai mare decat cel prezentat de noi in schema (peste 2500 implementari de limbaje de programare, multe disparute la ora actuala datorita performantelor scazute sau lipsei portabilitatii lor), noi aratand evolutia doar a celor mai semnificative. Cu siguranta ca si viitoarele proiecte de limbaje si implementari ale acestora vor respecta conceptele generale prezentate aici.

2.2 Codificarea informatiei

Una din operatiile cele mai importante in manipularea informatiilor este codificarea lor. Aceasta operatie este legata de o serie importanta de termeni pe care incercam sa-i definim. Daca vom continua sa presupunem ca avem o multime informationala M care are cardinalul card.M, si o multime C finita si nevida de elemente numite coduri a carui cardinal este card.C, si in plus presupunem ca exista relatia card.Mcard.C, atunci prin definitie numim o codificare (reprezentare) a elementelor multimii M prin elementele multimii C, orice functie injectiva avand domeniul de definitie in M si codomeniul C, adica c:M C. In multe lucrari de specialitate se simplifica exprimarea sunandu-se ca functia c este codificarea multimii M prin multimea C. 

Acceptam fara demonstratie urmatoarea lema:

Daca c_i:M_i C_i (1in) sunt codificari ale multimilor M_i prin multimile C_i, atunci functia:

data de expresia: c(x₁,~x₂, . . . , x_n) = (c₁(x₁), c₂(x₂), . . . , c_n(x_n))

care este codificarea multimii prin multimea

De exemplu, sa consideram multimea informationala finita .

Fie c_i:M_i C_i codificarile multimilor M_i prin codurile C_i , unde presupunem ca:

C₁ C₂ = C₃ =

C₄ = C₅ = C₆ =

C₇ C₈ =

Presupunem ca: c₁(x₁) = 7; c₂(x₂) = ; c₃(x₃) = ; c₄(x₄) = ; c₅(x₅) = z; c₆(x₆) =  ; c₇(x₇) =  i c₈(x₈) =  atunci, in conformitate cu lema anterior enuntata, informatia:

i (x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈) I

se va codifica prin:

c(i) = (7 ,,  ,, z , ,  , ) I

Exemplul ne sugereaza posibilitatea folosirii oricaror simboluri de codificare, de la litere, cifre, ideograme si caractere din orice limba.

Dimensiunea cantitativa a informatiilor

Academicianul Mihai Draganescu considera informatia ca "a patra stare de existenta a materiei"[4], idee sustinuta de tot mai multi oameni de stiinta ai lumii. Acest fenomen se confera prin faptul ca toate procesele care au loc in natura, societate, activitate productiva etc. sunt generatoare de informatii si isi mentin viabilitatea pe cale informationala.

Informatia are rolul de a inlatura nedeterminarea care apare la un moment dat, legata de desfasurarea unui proces. Datorita dualitatii informatie-nedeterminare, este de presupus ca o modalitate eleganta de evaluare a cantitatii de informatie poate fi facuta prin exprimarea nedeterminarii. De la aceasta idee a plecat, in anul 1948, Claude E. Shannon in teza sa de doctorat, pentru a gasi o expresie pentru exprimarea cantitatii de informatie.

Pentru un numar finit de evenimente elementare (x₁, x₂, x₃, , x_n), notam probabilitatile de realizare a acestor evenimente cu (p₁, p₂, , p_n) si presupunem ca sistemul (x₁, x₂, , x_n) este un sistem complet, adica in urma efectuarii experimentului X se obtine ca rezultat unul din evenimentele x_i, I=1, , n asadar:

Astfel experimentul X este pus in evidenta de campul de probabilitate exprimat prin matricea (1):

(1)

Neputandu-se cunoaste de la inceput rezultatul experimentului X, inseamna ca acesta contine un anumit grad de nedeterminare, rezultatul lui inlatura gradul de nedeterminare existent la inceput.

Daca notam cu H masura gradului de nedeterminare a experimentului X, aceasta masura este evident o functie de probabilitatile evenimentelor elementare:

C.E. Shannon a reusit sa dea o forma explicita lui H(X) prin formula:

care reprezinta masura gradului de nedeterminare, si care reprezinta, de fapt, entropia experimentului X.

In particular, daca consideram b=2, n=2 si p₁=p₂ (asadar, x₁ si x₂ sunt echiprobabile) obtinem expresia:

De aici a aparut ideea unitatii de masura a nedeterminarii, ca fiind gradul de nedeterminare continut de un experiment format din doua evenimente care au aceeasi probabilitate. Shannon a propus ca denumire, pentru unitatea de masura a nedeterminarii, BIT‑ul (BInary digiT), adica cifra binara.

El a demonstrat proprietatile entropiei (pe care noi le prezentam aici fara demonstratie), ele sunt:

1⁰. H(p₁,p₂,,p_n)0

2⁰. H(p₁,p₂,,p_n)=0  daca p_i=1;

3⁰. Pentru orice evenimente care au probabilitatile (p₁,p₂,,p_n) si care au proprietatile:

exista relatia:

adica, entropia este maxima pentru evenimentele elementare echiprobabile.

4⁰. H(p₁,p₂,,p_n,0)=H(p₁,p₂,,p_n)

5⁰. Pentru doua experimente X si Y:

exista relatia:

H(X,Y) = H(X) + H(Y)

6⁰. Pentru doua experimente X si Y, exista relatia:

H(X,Y) = H(X) + H_X(Y)

unde:H_X(Y) este entropia experimentului Y, dependent de experimentul X. Desigur, daca X si Y sunt independente, atunci H_X(Y) = H(Y).

7⁰. Pentru doua experimente X si Y, exista relatia:

H_X(Y)  H(Y).

8⁰. Daca se dau doua experimente X si Y, exista relatia:

H(X,Y)  H(X) + H(Y).

9⁰. Daca se dau n experimente X₁, X₂, , X_n oarecare, atunci avem relatia:

Ca o concluzie a celor aratate mai sus rezulta ca intr-un experiment X care pune in evidenta repartitia :

ca fiind cantitatea de informatie pe care o obtinem dupa efectuarea experimentului este:

numita formula lui Shannon[5].