Home - qdidactic.com
Didactica si proiecte didacticeBani si dezvoltarea cariereiStiinta  si proiecte tehniceIstorie si biografiiSanatate si medicinaDezvoltare personala
referate stiintaSa fii al doilea inseamna sa fii primul care pierde - Ayrton Senna





Aeronautica Comunicatii Drept Informatica Nutritie Sociologie
Tehnica mecanica


Informatica


Qdidactic » stiinta & tehnica » informatica
Identificarea surselor discrete de informatie



Identificarea surselor discrete de informatie


IDENTIFICAREA SURSELOR DISCRETE DE INFORMATIE



1.1. Obiectivele lucrarii


Prezentarea unor notiuni de baza din teoria informatiei;

Stabilirea unui model informational pentru o sursa de informatie, plecand de la o realizare a acesteia sub forma unui fisier text.



1.2. Introducere


1.2.1. Sistem de transmisiune a informatiei


A transmite o informatie este echivalent cu a face o comunicare despre ceva ce nu se cunoaste. Informatia este cantitativ cu atat mai mare cu cat gradul de incertitudine asociat comunicarii respective este mai mare.




Modelul cel mai simplu al unui sistem de transmisiune a informatiei contine sursa, un canal de transmisiune si destinatarul, si este prezentat in figura 1.1. Un astfel de model este valabil pentru distante mici, unde erorile introduse de perturbatiile de pe canal sunt mici, si pentru situatiile in care sursa poate transmite direct mesaje pe canal fara o prelucrare deosebita.



Figura 1.1  Sistem de transmisiune a informatiei


Sursa este mecanismul prin care, din multimea simbolurilor sursei S, se alege intr-un mod aleator, un simbol particular destinat a fi transmis unui corespondent. In schema din figura 1.1 s-a presupus ca sursa de informatie este o marime fizica de natura electrica. Daca sursa este o marime fizica oarecare, se presupune implicit existenta unui traductor.


Prin canal (sau mediu de transmisiune) se intelege orice sistem fizic prin care se pot propaga semnalele de la un capat la altul al acestuia: cablu coaxial, cablu telefonic sau telegrafic, mediu inconjurator (atmosfera), fibra optica etc. Toate semnalele care influenteaza in mod aleator semnalul util, purtator de informatie, constituie perturbatii.


Destinatarul reprezinta destinatia finala la care trebuie sa ajunga mesajul sursei.



1.2.2. Modelarea surselor discrete de informatie


O multime de evenimente formeaza un sistem complet de evenimente daca acestea sunt incompatibile doua cate doua si reuniunea lor este evenimentul sigur. Altfel spus, la fiecare realizare se obtine unul si numai unul din cele N evenimente, ce definesc multimea.


Vom considera o sursa ca fiind un experiment notat cu S, in care rezultatele acestuia pun in evidenta un numar finit de evenimente, notate s1,,sn, asociate cu probabilitatile de realizare p(s1),..,p(sn). Sursa se considera un camp de probabilitate complet cu distributia:


(1.1)


Intrucat sursa este completa si simbolurile sunt distincte, sunt valabile relatiile:


(1.2.a)

(1.2.b)


iar probabilitatile de aparitie a simbolurilor satisfac conditiile:


(1.2.c)


(1.2.d)


Daca numarul evenimentelor este finit, sursa se numeste discreta. Daca se indeplineste si conditia (1.2.d), sursa este completa. Sursa este fara memorie daca evenimentele sk sunt independente, adica furnizarea unui simbol la un moment dat nu depinde de simbolurile furnizate anterior. Totalitatea simbolurilor unei surse formeaza alfabetul sursei. Orice succesiune finita de simboluri, in particular un singur simbol, se numeste cuvant. Totalitatea cuvintelor formate cu un anumit alfabet se numeste limbaj.


In concluzie, pentru a descrie o sursa discreta fara memorie (SDFM) sunt necesare doua marimi: alfabetul sursei si probabilitatile de furnizare a fiecarui simbol.



1.2.3.  Marimi informationale


Informatia reprezinta o notiune (marime) strict legata de un eveniment. Cu cat evenimentul este mai incert, deci cu cat cunoastem mai putin despre el, cu atat cantitatea de informatie este mai mare. 



Definitia 1.1. Se furnizeaza o unitate de informatie cand sursa poate furniza unul din doua mesaje echiprobabile.


Considerand un eveniment s, cu probabilitatea de realizare p(s), atunci, prin definitie, cantitatea de informatie obtinuta este :


(1.3)


Simbolurile care compun alfabetul sursei pot fi de natura foarte diferita (litere, cifre, ansamblu de idei, imagini etc.), in functie de sursa luata concret in studiu.


Fie o sursa cu N simboluri. Informatiile care se obtin la furnizarea fiecarui simbol s1, s2, , sN sunt i(s1), i(s2), , i(sN) si definesc o variabila aleatoare discreta, ce va fi notata cu I, si are distributia:


                     (1.4)


Definitia 1.2. Valoarea  medie a variabilei aleatoare discrete I se numeste entropia sursei S, si se va nota cu H(S).


In baza definitiei 1.2, se poate scrie relatia de calcul a entropiei unei surse discrete si fara memorie:


(1.5)


Entropia este informatia medie pe simbol sau, altfel formulat, este incertitudinea medie asupra simbolurilor sursei S.


Limba vorbita sau scrisa este o sursa de informatie discreta cu memorie. Aceasta pentru ca dupa anumite litere, din cauza regulilor ortoepice ale limbii, urmeaza numai anumite litere stabilite de gramatica fiecarei limbi. De exemplu, in limba romana:

inainte de consoanele b, d, g si v se scrie z;

inainte de l, m, n se scrie s;


Daca un text este considerat ca o sursa fara memorie, atunci entropia este maxima. Intrucat, de cele mai multe ori, probabilitatea de aparitie a unei litere este conditionata de una sau mai multe litere scrise anterior, textul literar sau tehnico-stiintific trebuie modelat ca o sursa cu memorie.


Ordinul sursei cu memorie difera de la o limba la alta, si duce la scaderea entropiei, deci aparitia unei redundante. Redundanta unei limbi, deci folosirea unui surplus de litere pentru a transmite informatie putina, are avantajul protectiei transmiterii informatiei impotriva perturbatiilor, cand, desi unele litere nu se aud sau nu se inteleg, cuvantul in ansamblu se poate intelege. Limba vorbita sau scrisa este redundanta pentru ca unele cuvinte se repeta, in mod inutil uneori, o idee (informatie) continuta in sensul altor cuvinte pronuntate anterior. Ideal, entropia unei limbi este de 1 bit/litera.


Definitia 1.3 Debitul de informatie al unei surse discrete, complete si fara memorie, este cantitatea medie de informatie furnizata in unitatea de timp.

Daca ti este durata necesara transmiterii simbolului si atunci durata medie de emisie a unui simbol este :


                  (1.6)


Debitul de informatie Ht(S) al sursei S este:


(1.7)


Definitia 1.4: Eficienta unei sursei discrete este raportul dintre entropie si valoarea maxima a entropiei:

(1.8)



Definitia 1.5: Redundanta unei surse discrete de informatie este diferenta dintre valoarea maxima posibila a entropiei si valoarea curenta:


[bit simbol (1.9)



Exista posibilitatea de a defini si o redundanta relativa dupa relatia:


                                             (1.10)


1.3. Desfasurarea lucrarii


1.     Se considera un fisier text oarecare, cu un numar de maxim 20 linii. Se scrie un program pentru stabilirea modelului informational al sursei ce a furnizat fisierului text. Se determina numarul de simboluri distincte si frecventa de aparitie a simbolurilor.

2.     Vom prezenta in continuare programul in Matlab plus pseudocodul acestuia, program ce satisface cerintele punctului 1 si anume determinarea numarului de simboluri si frecventa lor de aparitie.



Pseudocod

Exemplu( partial) in Matlab



Program identificare sursa




#1: Citeste fisierul.

f=textread('sursa.txt','%s','delimiter','n','whitespace','');

#2: Defineste:

s _ 1=char(f);

vectorul de intrare, txt;

[m,m1]=size(s _ 1);

numarul de simboluri,Ns;

txt=[];

vectorul de frecventa,freq;

for i=1:m,txt=[txt s _ 1(i,:)];


end;

#3: Initializeaza:


alfabetul:S(1)=txt(1);

Ns=length(txt);S=[txt(1)];F=[1];

freq[1]=1;

for i=2:Ns,


new=1;

#4:PENTRU fiecare char α din text,

N=length(S);

#4.1: Caut caracterul α in alfabet.

for j=1:N,

#4.2: DACA α este in alfabet

if S(j)==txt(i),

ATUNCI

F(j)=F(j)+1;new=0;

cresc frecventa lui cu 1

break;

ALTFEL

end;

il adaug la alfabet

end;


if new==1,


S=[S txt(i)];F=[F 1];


end;

#5: Scrie datele in fisier.

end;


P=F./sum(F)

END

N=length(S)


S


Exemplu:


2.1.sursa.txt='ana _ are _ mere _ mari'


txt=ana _ are _ mere _ mari

S=[an _ remi]

F=[4 1 3 3 3 2 1]


2.2.sursa.txt='astazi _ este _ o _ zi _ frumoasa _ de _ primavara _ dar _ tot _ nu _ este _ ca _ o _ zi _ de _ vara'

txt=astazi _ este _ o _ zi _ frumoasa _ de _ primavara _ dar _ tot _ nu _ este _ ca _ o _ zi _ de _ vara

S=[astzi _ eofrumdpvnc]

F=[11 4 4 3 4 15 6 4 1 5 2 2 3 1 2 1 1]



3.     Sursa studiata se considera ca fiind o sursa discreta si fara memorie. Sa se calculeze entropia , eficienta  si redundanta sursei.




Contact |- ia legatura cu noi -| contact
Adauga document |- pune-ti documente online -| adauga-document
Termeni & conditii de utilizare |- politica de cookies si de confidentialitate -| termeni
Copyright © |- 2024 - Toate drepturile rezervate -| copyright