Licenta informatica 2014. Programare, baze de date si retelistica.

5/23/2018 Licenta informatica 2014. Programare, baze de date si retelistica.

1/32

Tematica pentru examenul de licen,Specializarea: Informatic

2013

Partea I: Programare:1. Caracteristici algoritmilor. Etapele elaborarii algoritmilor. Metode de proiectarea algoritmilor.

Top-down, Bottom Up.

Definiie: n !lgoritm "informatic# reprezint o $ec%en finit &i ordonat de reguli clare, a crorparcurgere ne permite ca, pornind de la o mulime de date de intrare, $ o'inem (n mod eficientrezultatele corecte ale pro'lemei)

Proprietile algoritmilor:Caracteristici algoritmilor*rice algoritm informatic %erific urmtoarele proprieti:

1) +eneralitate un algoritm nu rezol% o $ingur pro'lem, ci o cla$ de pro'leme de acela&i tip)2) -initudine aciunile algoritmului tre'uie $ $e termine dup un numr finit de operaii, acea$ta pentru

orice $et de date %alide

3) .laritate aciunile algoritmului tre'uie $ fie clare, $imple &i riguro$ $pecificate/) .orectitudine algoritmul tre'uie $ produc un rezultat corect "date de ie&ire# pentru orice $et de date

de intrare %alide) ficien algoritmul tre'uie $ fie eficient pri%ind re$ur$ele utilizate, &i anume $ utilizeze memorie

minim &i $ $e execute (ntrun timp minim)n funcie de tipurile de reguli pe care le conine, un algoritm poate fi:

!lgoritm liniar conine doar reguli de tipul 1,2,/ !lgoritm ramificat conine cel puin o regul de tipul 3 !lgoritmi repetiti%i "ciclici# o $ec%en de reguli $e repet de un numr finit de ori)

Etapele elaborarii algoritmilor.

a. Analiza problemei) Pro'lemele reale cu care ne confruntm nu $unt formulate (ntotdeauna (ntrun $til clar,preci$) De cele mai multe ori, pro'lemele $unt formulate incomplet, am'iguu, l$4nd programatorului $arcinade a determina corect: ce $e cunoa&te din pro'lem &i rezultatele cerute) tapa de analiz a pro'lemei $efinalizeaz prin identificarea celor dou elemente e$eniale ale formulrii unei pro'leme: datele de intrare &idatele de ie&ire)

b. Proiectarea algoritmuluipoate fi con$iderat etapa de creati%itate a programrii, (n care folo$indu$e decuno&tinele &i experiena do'4ndite, programatorul %a identifica metoda de rezol%are a pro'lemei date &i %adez%olta algoritmul core$punztor) -inalitatea ace$tei etape o con$tituie un algoritm de$cri$ clar (ntruna dintre%ariantele de reprezentare algoritmic "$c5eme logice, p$eudocod, $au c5iar lim'a6 de programare (n cazul (ncare pro'lema e$te de dificultate mic#)

c. Traducerea n limbaj de programare (implementarea):e$te etapa (n care $e %a efectua o 7traducere8 (nlim'a6 de programare a de$crierii algoritmului rezultat (n etapa de proiectare) .unoa&terea (n detaliu a regulilor$intactice ale lim'a6ului ale$, experiena &i $tilul programatorului $unt ingredientele nece$are &i $uficiente aleace$tei etape)

d. Traducerea n cod main, execuia i tetarea. Traducerea (n cod ma&in $e realizeaz automat cua6utorul a dou componente ale mediului de programare: compilatorului &i a editorul de legturi) Te$tarea

programului con$t (n execuia $a repetat pentru o mulime de date de intrare "date de te$t# &i %erificareacorectitudinii rezultatelor oferite) 9ezultatele incorecte ne $emnaleaz o eroare logic de proiectare &i nece$it ore%izuire a algoritmului &i reparcurgerea etapelor programrii)

e. !ntreinereae$te ultima etap a programrii &i con$t din aciuni de actualizare a produ$ului final &i dea$i$ten oferit 'eneficiarului)Dintre toate ace$te etape, cea care e$te mai $olicitant e$te etapa de proiectare)

1


2/32

xi$ta doua metode generale de proiectare a algoritmilor, a caror denumire pro%ine din modul de a'ordare

a rezol%arii pro'lemelor: metoda de$cendenta $i metoda a$cendenta)

Proiectarea decendenta (top"do#n)porne$te de la pro'lema de rezol%at, pe care o de$compune in parti

rezol%a'ile $eparat) De o'icei ace$te parti $unt $u'pro'leme independente, care la randul lor pot fi de$compu$e in

$u'pro'leme) a prima de$compunere accentul tre'uie pu$ pe algoritmul "modulul# principal nu a$upra

$u'pro'lemelor) a ace$t ni%el nu ne intere$eaza amanunte legate de rezol%area $u'pro'lemelor, pre$upunem ca le

$tim rezol%a, e%entual ca a%em de6a $cri$i $u'algoritmi pentru rezol%area lor) rmeaza $a con$ideram pe rand

fiecare $u'pro'lema in parte $i $a proiectam "in acela$i mod# un $u'algoritm pentru rezol%area ei) In final, $e %a

de$crie $u'algoritmul de rezol%are al fiecarei $u'pro'leme, dar $i interactiunile dintre ace$ti $u'algoritmi $i ordinea

in care ei $unt folo$iti)

;otiunea de modul %a fi definita in $ectiunea urmatoare) Deocamdata intelegem prin modul orice

$u'algoritm $au algoritmul principal) egatura dintre module $e prezinta cel mai 'ine $u' forma unei diagrame

numita ar'ore de programare) -iecarui modul ii core$punde in ar'orele de programare un nod, ai carui de$cendenti

$unt toate modulele apelate direct) ;odul core$punzator algoritmului principal e$te c5iar nodul radacina)

In multe carti metoda topdoetoda =Di%ide et Impera= poate fi folo$ita nu numai la impartirea pro'lemei in $u'pro'leme ci $i la

impartirea datelor in grupe mai mici de date) n a$tfel de procedeu e$te folo$it de $u'algoritmul ?uic@$ort, care %a

fi prezentat in $ectiunea A)3)

$etoda acendenta (bottom"up)porne$te de la propozitiile lim'a6ului $i de la $u'algoritmi exi$tenti, pe

care ii a$am'leaza in alti $u'algoritmi pentru a a6unge in final la algoritmul dorit) .u alte cu%inte, in cazul metodei

a$cendente %a fi $cri$ mai intai $u'algoritmul apelat $i apoi cel care apeleaza) .a rezultat al proiectarii a$cendente$e a6unge la o multime de $u'algoritmi care $e apeleaza intre ei) $te important $a $e cunoa$ca care $u'algoritm

apeleaza pe care, lucru redat printro diagrama de $tructura, ca $i in cazul programarii de$cendente)

2


3/32

!cea$ta metoda are marele deza%anta6 ca erorile de integrare %or fi detectate tarziu, a'ia in faza de

integrare) Se poate a6unge a'ia acum la concluzia ca unii $u'algoritmi, de$i corecti, nu $unt utili)

De cele mai multe ori nu $e practica o proiectare a$cendenta $au de$cendenta pura ci o com'inare a lor, o

proiectare mixta)

2. Programarea structurata. Principii.

.re&terea complexitii aplicaiilor a impu$ la (nceputul anilor BA0 apariia unei noi paradigme (n programare :programarea $tructurat) Scopul era de a dez%olta noi te5nici de programare, care $ permit dez%oltarea unorprograme fia'ile, u&or de ela'orat (n ec5ip, u&or de depanat, de (ntreinut &i de reutilizat)

Principiile programarii $tructurate impun reguli $tricte (n ceea ce pri%e$te de$crierea in$tructiunilor admi$epentru fiecare din $tructurile definite:

oliniara "$ec%entiala#C

oalternati%aC

orepetiti%a)

n prim principiu al programrii $tructurare e$te modularizarea) Pentru proiectarea unor aplicaiicomplexe, e$te nece$ar de$compunerea pro'lemei care tre'uie rezol%at (n $u'pro'leme relati% independente,

pentru fiecare dintre ace$te $u'pro'leme $criindu$e module de program mai $imple) -iecare modul efectueazun $et de prelucrri $pecifice &i e$te relati% independent de celelalte module, cu care comunic prin intermediulunui $et de parametri, care con$tituie interfaa) !%anta6ele $unt multiple) .um la orice firm $e lucreaz (nec5ip, modulele de program pot fi implementate de mai muli programatori) >odificarea unui modul nuafecteaz celelalte module) -iecare modul poate fi implementat, te$tat, depanat, modificat, independent decelelalte)

n alt principiu fundamental e$te $tructurarea datelor &i a prelucrrilor)Programatorul are po$i'ilitatea de a&i grupa datele (n coleci, organizarea dup anumite reguli, denumite$tructuri de date)

Prelucrrile a$upra datelor $unt $tructurare $eparat) .onfotm teoremei de $tructur EmFacopini, oriceprelucrare poate fi de$cri$ prin compunerea a trei $tructuri fundamentale : $trucuta liniar "$ec%enial#cuprinde o $ucce$iune de operaii, reprezentate printrunul $au mai multe 'locuri procedurale, care $e execut$ec%enial "unul dup cellalt (n ordinea (n care $unt $cri$e#)$tructura alternati% cuprinde o operaie de decizie &i dou 'locuri procedurale aciune 1 &i aciune 2 dintre care$e execut numai unul : fie aciune 1 (n cazul (n care condiia e$te ade%rat, fie aciune 2 (n cazul (n care

condiia e$te fal$) .ele dou ramuri ale $tructurii alternati%e $e (nc5id apoi (n acela&i punct al $tructurii caredetermin continuarea algoritmuluicu operaiile din $tructura urmtoare $tructurii alternati%e)$tructura repetiti% una numit contor care $e folo$e&te pentru a numra de c4te ori $a executat repetat corpulciclului una numit numr de repetri care determin de c4te ori tre'uie $ $e execute repetat corpul ciclului)

3. lgoritmi elementari !c"imbarea #alorilor a doua #ariabile

$orma practic%&* can ro&ie conine ceai, iar una al'a$tr lapte) Se dore&te $c5im'area coninutului celor dou cni (ntre ele)

$orma matematic%&9eprezentarea a dou mrimi $e realizeaz folo$ind %aria'ile de di%er$e tipuri) -ie a, ' %aria'ilele care core$pundcelor dou cni &i %alorile lor numerice)

3


4/32

Deci aGc1 &i 'Gc2) Dar a G ' e$te fal$, atunci $ucce$iunea de operaii x Ga H ' &i G x a , z G x ' ne dau ' G &i a G z)

$orma algoritmic%&Jaria'ilele utilizate (n algoritmic au proprietatea de a&i modifica %aloarea dup fiecare operaie de atri'uire)Jalorile lor pot fi de di%er$e tipuri, caracter: 7ceai8 &i re$pecti% 7lapte8, numerice, logice) Pentru a putea realiza$c5im'ul %alorilor algoritmul:

Algoritm schimb ( a, b );

x : {Orice tip}x a;

a b;b x;

stop;

permite p$trarea %alorii lui a (n x, tran$ferul %alorii lui ' (n a &i apoi %aloarea lui a p$trat (n x trece (n ') !cea$t$c5im'are $e poate face indiferent de tipul %aria'ilelor)Dac %aria'ilele a &i ' $unt de tip numeric &i accept operaii de adunare &i $cdere atunci %aria'ilele matematice x, &i z nu mai $unt nece$are, iar algoritmul e$te:

Algoritm schimb_numeric ( a, b : numeric );

x : numeric;

a a + b;b a - b;

a a - b;stop;

xemplu: a G 1A, ' G 13, &i ta'elul de %erificare a celor trei pa&i:

Pa$ a G 1A ' G 131 30 132 30 1A3 13 1A

tran$miterea parametrilor prin adre$ "prin pointeri#)%oid inter$c5im'are"int Ka, int K'#Lint auxiliarCauxiliarGKaCKaGK'CK'GauxiliarCM

NN!pelul:int x,CxG1CxG2Cinter$c5im'are"Ox,O#NNfectulInainte de apel:

xG1G2

Dup apel:

xG2G1

/


5/32

Parcurgerea elementelor unei multimi$orma practic%&S $e efectueze o anumit operaie a$upra fiecrui element al unei mulimi)

$orma matematic%&Se &tie c, matematic, o mulime > e$te definit prin elemente di$tincte) *peraiile permi$e a$upra mulimilor $unt

reuniune, inter$ecie, apartenen, incluziune, produ$ cartezian, etc);umrul elementelor unei mulimi $e nume&te cartezianul mulimii &i $e noteaz cu M ) !ce$ta poate fi finit $au

infinit "numra'il $au nenumra'il#) Dac M G n, finit, atunci elementele mulimii pot fi parcur$e folo$ind notaiamatematic ni ,1= , i parcurge toate elementele mulimii L1,2,,nM)

Dac numrul elementelor nu $e cunoa&te atunci exprimarea elementelor unei mulimi $e face prin de$criereaproprietilor elementelor $ale, $u' forma:

> G Lx Q x %erific R.ondiiaMDe reinut c dintre mulimi doar cele cu numr finit de elemente pot face $tudiul pro'lemelor algoritmice)

$orma algoritmic%&Parcurgerea elementelor unei mulimi, a%4nd (n %edere c reprezint o operaie care repet o anumit $ec%en de un

numr de ori $e %a rezol%a algoritmic folo$ind $tructura repetiti%) Di$tingem dou cazuri:a# .4nd numrul de elemente e$te n)

Sec%ena de pa&i:

Pentrui = 1 , n, 1 execut

{Operaie asupra fiecrui e!ement}Sf pentru

Dintre pro'lemele cla$ice care $e (ncadreaz (n acea$t categorie: $uma $au produ$ul a n elemente, $ume definiteprin termen general, parcurgerea elementelor unui &ir "citirea, $crierea elementelor#)

'# .4nd numrul elementelor nu $e cunoa&te dar e$te finit &i exi$t o care permite parcurgereaelementelor)

Ct timp"c#n$iie% execut{Operaie asupra fiecrui e!ement}

Sf ct timp;

sau

Repet{Operaie asupra fiecrui e!ement}

pn cnd n#t "c#n$iie%;

i$ citire_mu!time(int ', int *n){int i;

printf($ati $imensiunea ./000:); scanf(2$,n);f#r(i=3;i"*n;i++)

scanf(2$, 4'i);}

'mplementarea cuanti$icatorilor matematici oricare si e(ista.$orma practic%&"!# S $e %erifice dac toate elementele unei mulimi %erific o anumit proprietate)"# S $e %erifice dac exi$t cel puin un element care %erific o proprietate dat)Jom numi ace$te tipuri de pro'leme, pro'leme cu cod de %alidare, 7cu 'ecule8)

$orma matematic%&Se cunoa&te exprimarea matematic a celor doi cuantificatori pentru o mulime > &i un predicat P"x#, P: > L-al$,

!de%ratM: "!# #", xPMx e$te ade%rat"# ,Mx a$tfel (nc4t P"x# $ fie ade%rat


6/32

$orma algoritmic%&De$crierea algoritmic pre$upune introducerea unei %aria'ile logice, cod,care $&i modifice %aloarea doar (n cazul

(n care nu $e certific proprietatea cerut) -ie condiia de parcurgere a elementelor mulimii &i

predicatul "proprietatea#, pentru care P" x # e$te ade%rat $au fal$)

"!# !lgoritm care permite implementarea cuantificatorului oricare85#$ '$e&rat;

Ct timp"c#n$itie% an$ c#$ executDacn#t "6% atunci

5#$ 7a!s;!$ c)t timpC

Dac c#$ atunci{Oricare e!ement &erific pr#prietatea}

altfel

{5e! puin un e!ement nu &erific pr#prietatea}sf dac

"# !lgoritm care permite implementarea cuantificatorului exi$t85#$ 7a!s;Ct timp"c#n$itie% an$ n#t c#$ execut

Dac"6% atunci5#$ '$e&rat;

Sf ct timp;

Dac c#$ atunci{8xist e!ement care &erific pr#prietatea}

altfel

{9u exist e!ement care s &erifice pr#prietatea}sf dac

*'$er%aii:1# .omplexitatea algoritmului e$te *"n#, deoarece (n cel mai defa%ora'il caz tre'uie parcur$e toate cele n elemente

ale mulimii)

Exemplul 1.S se determine dac un numr natural n, n>2, este prim.

'!#ritm prim ( n: numeric, c#$ : b##!ean );$ : numeric;

5#$ '$e&rat;d ;

Ct timp$ "= s


7/32

Metoda reed>etoda +reed e$te una din cele mai directe te5nici de proiectare a algoritmilor care $e aplic la o %arietate

larg de pro'leme) In general, acea$ta metoda $e aplica pro'lemelor de optimizare) Specificul ace$tei metodecon$ta in faptul ca $e con$truie$te $olutia optima pa$ cu pa$, la fiecare pa$ fiind $electat "$au Ving5ititV# in$olutie elementul care pare Vcel mai 'unV la momentul re$pecti%, in $peranta ca %a duce la $olutie optimaglo'ala)

!lgoritm +reed e$te: NN%arianta fr ordonarea mulimii !

Date de intrare: !Date de ie&ire: -ie GLM.4ttimp "!WX# &i "K nu e$te optim#

K!lege aidin !Dac LaiM Ke$te $oluie po$i'il atunci

G LaiM $au K ai(nlocuie&te un element din !G! Y L aiM

SfDacSf.4ttimp

Sf!lgoritm

!lgoritm +reed2 e$te: NN%arianta cu ordonarea mulimii ! dup un criteriuDate de intrare: !Date de ie&ire: -ie GLMK*rdoneaz mulimea !Pentru i de la 1 la n

Dac LaiM e$te $oluie po$i'il atunci G LaiM $au ai(nlocuie&te un element din

SfDacSfPentru

Sf!lgoritm

Metoda Bactracingac@trac@ing e$te numele unui algoritm general de de$coperire a tuturor $olu iilor unei pro'leme de

calcul, algoritm ce $e 'azeaz pe con$truirea incremental de $olu iicandidat, a'andon4nd fiecare candidat par ial imediat ce de%ine clar c ace$ta nu are an$e $ de%in o $olu ie %alid

Su'algoritm ac@trac@ing" @# e$te: NNtrateaz ni%elul @Pentru fiecare kk Ax

[ ] kxkStiva NNoperaia pu$5

Dac Jalid"@#G!de%arat atunciDac -inal"@#G!de%arat atunci

Tipre&te 7Soluie:8 Sti%a [ ] [ ]kStivaStiva ,)),1 !ltfel

.5eam ac@trac@ing" @H1# NNautoapelSfDac

SfDacSfPentru

SfSu'algoritm

*'$er%aie: n %arianta recur$i%, operaiile pop "re%enirea pe un ni%el inferior al $ti%ei $oluie# $e executautomat la re%enirile din apelurile $u'algoritmului)

Pentru furnizarea $oluiilor, $e %a apela:

A


8/32

.5eam ac@trac@ing "1#)

Metoda /i#ide et 'mpera

Su'algoritm Di%idetImpera "PZformal, nZformalC SZformal# e$te:Dac nZformalR n0 atunci

[rezol% imediat $u'pro'lema PZformal &i o'ine $oluia SZformal!ltfel

[(mparte pro'lema PZformal de dimen$iune nZformal (n:[ P1 de dimen$iunea n1,[ P2 de dimen$iune n2,)))[ P@ de dimen$iune [email protected] Di%idetImpera"P1,n1,S1#.5eam Di%idetImpera"P2,n2,S2#))).5eam Di%idetImpera"P@,n@,S@#[com'in $oluiile pariale S1,S2,))),S@ &i o'ine SZformal

SfDac

SfSu'algoritm

Programare dinamica

>etoda Programrii dinamice $e poate con$idera ca o (m'untire a te5nicii +reed) n cazul metodei+reed, alegerea unui element $e face pe 'aza unui criteriu de admi$i'ilitate, (n$ la Programarea dinamic,ace$t criteriu e$te cel al optimalitiiC folo$ind$e de un criteriu mai puternic, rezultatul final oferit de metoda

programrii dinamice e$te (ntotdeauna optimul glo'al).a &i metoda Di%ide et impera, programarea dinamic pre$upune (mprirea pro'lemei (n $u'pro'leme,

rezol%area &i com'inarea $oluiilor ace$tora pentru a o'ine rezultatul final) n $ituaia (n care $u'pro'lemeleo'inute prin de$compunere conin $u'pro'leme comune, e$te prefera'il aplicarea metodei Programriidinamice)* particularitate a metodei con$t (n con$truirea $i utilizarea unor ta'ele cu informaii)

Programarea dinamic e$te o metod de rezol%are a pro'lemelor de optimizare pentru care $oluia e$terezultatul unui &ir de decizii optime) Pro'lema de optimizare rezol%a'il prin metoda programrii dinamice e$teformulat a$tfel:

-ie un $i$tem care $e poate afla (ntruna din $trile:S0, S1, S2 , , Sn1, Sn&i fie &irul de decizii

D1, D2 , , Dn1, Dnprin care $i$temul e$te trecut prin $trile date:

n

n/

1n2

2/

1

1/

0 !!...!!!

Pro'lema %erific unul dintre principiile optimalitii:

Jarianta 1: Dac &irul de decizii D1, D2 , , Dn1, Dnduce $i$temul din $tarea iniial S0(n $tarea final Sn(nmod optim, atunci:

{ }nk ,))),2,1 , $ec%ena de decizii D@ , , Dn1, Dnduce $i$temul din $tarea S@1(n $tarea final Sn(n modoptim)

Jarianta 2: Dac &irul de decizii D1, D2 , , Dn1, Dnduce $i$temul din $tarea iniial S0(n $tarea final Sn(nmod optim, atunci:{ }nk ,))),2,1 , $ec%ena de decizii D1 , , D@1, D@duce $i$temul din $tarea iniial S0(n $tarea S@(n mod

optim)

\


9/32

n funcie de %arianta principiului optimalitii identificat din analiza pro'lemei, metoda de a'ordare apoate fi:

>etoda (nainte aplicat (n cazul %erificrii principiului optimalitii (n forma 1)>etoda (napoi aplicat (n cazul %erificrii principiului optimalitii (n forma 2)

$ena celor dou %ariante "(nainte $au (napoi# e$te aceia&i &i con$t (n identificarea &i rezol%area relaiilor derecuren referitoare la criteriul de optimizat $au la %aloarea ce $e calculeaz)

>etoda (nainte opereaz (n urmtoarele / faze:1) prin relaiile de recuren $e %or calcula optimele core$punztoare $trilor (ndeprtate de $tarea final (nfuncie de optimele core$punztoare $trilor apropiate de $tarea final "practic (n acea$t faz $ecompleteaz ta'ela de informaii intermediare#

2) $e determin deciziile care leag optimele determinate (n faza anterioar3) $e afl optimul total/) $e determin $oluia pro'lemei reprezentat de un &ir de decizii con$tituit prin compunerea deciziilor de

la etapa 2, (n mod directe, de la (nceput $pre $f4r&it "(nainte#

>etoda (napoi e$te dual metodei de$cri$e anterior &i opereaz (n urmtoarele / faze:

1) prin relaiile de recuren $e %or calcula optimele core$punztoare $trilor apropiate de $tarea final (nfuncie de optimele core$punztoare $trilor deprtate de $tarea final

2) $e determin deciziile care leag optimele determinate (n faza anterioar3) $e afl optimul total/) $e determin $oluia pro'lemei reprezentat de un &ir de decizii con$tituit prin compunerea deciziilor de

la etapa 2, (n mod in%er$, de la $f4r&it $pre (nceput "(napoi#

De&i pare o metod general de rezol%are a pro'lemelor de optim, aplica'ilitatea programrii dinamice e$tere$tr4n$ doar la acele pro'leme pentru care $e poate demon$tra principiul optimalitii)

. !tructuri de date

$tructuri neomogene "articol, fi$ier#Prin fi&ier $e (nelege colecie ordonat de elemente pe care le numim (nregi$trri) -i&ierele $unt p$trate pe

$uporturi externe reutiliza'ile: 5ard di$@, flopp di$@, etc) Prelucrarea fi&ierelor implic un numr de operaii$pecifice ace$tora:

1) .reare fi&ier2) De$c5idere fi&ier3) .itire din fi&ier/) !daugare $criere (n fi&ier

) !ctualizare fi&ierU) Poziionare (n fi&ierA) ]tergere fi&ier

*peraiile $pecifice fi&ierelor $e realizeaz prin intermediul unor funcii $tandard exi$tente (n 'i'liotecalim'a6ului .) xi$t dou ni%ele de tratare a fi&ierelor:

1) ;i%elul inferior face apel direct la $i$temul de operare2) ;i%elul $uperior face apel la proceduri $pecializate de prelucrare a fi&ierelor, care utilizeaz

$tructuri $peciale de tipul -I)

tablouri& operatii cu tablouri. Metode de sortare

Ta'lourile (n lim'a6ul . $unt %aria'ile cu indici) Pot fi de dou categorii, ta'louri unidimen$ionale "%ectori#$au multidimen$ionale) a ni%el a'$tract, un ta'lou unidimen$ional $e poate defini ca o li$t ordonat de n

^


10/32

%alori de acela&i tip: x1,x2, ,xn) -iecare poziie i din cadrul ta'loului conine elementul xi, re$pecti% o%aloare de tipul $pecificat)

Declararea unui ta'lou unidimen$ional (n lim'a6ul . $e face a$tfel:Rtip ;umeTa'lou _;umarlemente`C

nde Rtip e$te tipul de date al elementelor ta'loului, ;umarlemente e$te un numr natural $au o con$tantcu %aloare (ntreag poziti% prin care $e precizeaz numrul elementelor din ta'lou, ;umeTa'lou e$te unidentificator prin care e$te denumit %ectorul)

9eferirea unui element al ta'loului $e folo$e&te numele ta'loului &i indicele core$punztor) Spre exemplu:int x_100`C Pentru a referi elementul de pe poziia i %om $crie x_i1`, dat fiind faptul c primul element al &irului e$te

x_0`) Ta'lourilor li $e a$ociaz locaii de memorie con$ecuti%e, de aceea&i lungime (n care $unt $tocate %alorile

fiecrui element) *'$er%aie: numele ta'loului "$pre ex) x# e$te o %aria'il a crei %aloare e$te adre$a de memorie a primului

element din &ir "pointer#)

Declararea ta'lourilor ndimen$ionale:Rtip ;umeTa'lou _;1` _;2` _;n`C

nde ;1, ;2 ;n reprezint numrul de elemente pe fiecare dimen$iune) 9eferirea unui element al ta'loului multidimen$ional $e face prin identificatorul ta'loului "numele# &i

$pecificarea poziiei pe fiecare dimen$iune: ;umeTa'lou _i1` _i2` _in`)xemplu:int !_20` _30`CNNdeclararea unei matrice "ta'lou 'idimen$ional# de 20 linii $i 30 coloane)

Primul element al ta'loului 'idimen$ional declarat mai $u$ e$te !_0`_0`, iar numele ta'loului conineadre$a primului element memorat)

1.!ortarea prin inserie-ie x1,x2,))),xnun %ector de n elementePrincipiul ace$tei te5nici e$te acela de a pri%i ta'loul ca fiind (mprit (n dou $u'ta'louri: x1,))),xi1&ixi,))),xn) Se pre$upune c primul $u'ta'lou e$te de6a ordonat &i $e urmre&te in$erarea elementului x i(n$u'ta'loul ordonat a$tfel (nc4t dup efectuarea in$eriei $u'ta'loul rezultat $ rm4n ordonat) !ce$t

procedeu $e %a continua pri%ind ta'loul iniial ca dou $u'ta'louri : x1,))),xi&i xiH1,))),xn) .uno$c4nd cprimul $u'ta'lou e$te de6a ordonat "neam a$igurat de ace$t lucru la operaia de in$erare precedent#, $e%a continua cu in$erarea elementului x iH1(n x1,))),xi&i o'inerea $u'ta'loului ordonat x1,))),xiH2) Procedura$e repet p4n c4nd nu mai $unt elemente de in$erat (n $u'ta'loul $t4ng)

Sortarea prin $elecie-ie x1,x2,))),xnun %ector de n elemente)

Principiul e$te acela de a con$idera $u'%ectorul xi,,xn&i de a determina minimul din acea$t $ec%en,urm4nd ca minimul rezultat $ $e inter$c5im'e cu elementul xi) Procedeul $e %a repeta pentru oricare iG1,,n2) lgoritm !ortare!eleciee$te:

.ite&te n, x1,x2,))),xnPentru i de la 1 la n1

NNdetermin poziia &i %aloarea minimului $u'%ectorului xi,,xnpozminGiminGxiPentru 6 de la iH1 la n

Dac x6Rmin atunci

pozminG6minGx6SfDac

$fPentru

10


11/32

NNinter$c5im'are xicu minxpozminGxixiGmin

SfPentruSf!lgoritm

3.!ortarea prin intersc"imbare Bubble!ort4

>etoda $ortrii prin inter$c5im'are con$t (n parcurgerea repetat a %ectorului &i compararea pe r4nd a

perec5ilor de elemente con$ecuti%e urmat de inter$c5im'area %alorilor ace$tora (n $ituaia (n care relaia deordine dorit nu e$te %erificat)a fiecare parcurgere $e %a pre$upune c %ectorul e$te ordonat "marcarea ace$tei pre$upuneri $e face printr

un cod#, (n$ la determinarea unei perec5i de elemente con$ecuti%e care nece$it inter$c5im'are, pre$upunereae$te anulat)

!lgoritmul $e %a termina (n condiiile (n care la o parcurgere anterioar, complet a %ectorului, pre$upunerea$a do%edit ade%rat)

!lgoritm SortareInter$c5im'are e$teNNordonare cre$ctoare dup %alorile elementelor

.ite&te n, x1,x2,))),xn

9epet*rdonatG!de%ratPentru i de la 1 la n1

Dac xixiH1atunci.5eam Inter$c5im'are"xi,xiH1#*rdonatGfal$

SfDacSfPentru

P4nc4nd "*rdonatG!de%rat#Sf!lgoritm

*. !ortare rapid% 5uic!ort4.!lgoritmul de $ortare rapid e$te un exemplu tipic de algoritm Di%ide etImpera) -iind dat un %ector oarecare de n elemente $e cere ordonarea cre$ctoare a %ectorului dup %alorileelementelor)

Ideea de 'az a $ortrii rapide con$t (n (mprirea %ectorului (n doi $u'%ectori cu proprietatea c toateelementele primului $unt mai mici dec4t un element pi%ot &i elementele celui deal doilea $u'%ector $unt maimari dec4t pi%otul) !legerea pi%otului rm4ne (n $arcina programatorului, exi$t4nd trei %ariante plauzi'ile:

pi%otul e$te elementul median al $u'%ectorului mane%rat, pi%otul e$te elementul de pe prima poziie, re$pecti%,pi%otul e$te ale$ ca elementul de pe ultima poziie din $u'%ector) n de$crierea urmtoare, pi%otul e$te ale$ cafiind elementul de pe poziia median)

) Sortarea prin intercla$are e$te o te5nic de ordonare a unui %ector) Principiul de 'az e$te acela al (mpririi%ectorului iniial (n dou pri egale "$u'%ectori#, prin $ortarea prilor rezultate &i ulterior intercla$area celor

doi $u'%ectori ordonai, rezult4nd %ectorul glo'al ordonat) -iecare dintre cei doi $u'%ectori o'inui la o(mprire precedent, la r4ndul lor pot fi (mprii fiecare (n dou pri, urm4nd ca $u'%ectorii de dimen$iunemai mic $ fie $upu&i aceluia&i mecani$m de ordonare prin intercla$area &i $ o'inem $u'%ectori ordonai, dedimen$iuni mai mari)

liste inlantuitei$ta reprezint o mulime de dimen$iune %aria'il, format din elemente de acela&i tip) nelegem prin li$t

o mulime dinamic &i omogen, a crei dimen$iune $e modific (n timpul rulrii programului)>emorarea $tructurilor de date de tip li$t $e poate face (n dou maniere:

1) $ec%enial elementele li$tei $unt memorate la adre$e con$ecuti%e2) (nlnuit elementele li$tei nu ocup adre$e con$ecuti%e, fiecare element conine pe l4ng informaia

propriuzi$ &i o legtur $pre urmtorul element)i$te (nlnuite pot fi: $implu, du'lu $au multiplu (nlnuite) .la$ificarea li$telor $e face (n funcie denumrul legturilor din compunerea unui element)

*peraiile principale cu li$te $unt urmtoarele:

11


12/32

1) parcurgere2) creare3) di$trugere "&tergere#/) adugare nou element) &tergere element

ar'ori 'inari de cautaren caz particular de ar'ori 'inari $unt ar'orii 'inari de cutare) n plu$ fa de a$pectele menionate la

prezentarea ar'orilor 'inari, un ar'ore de cutare prezint o caracteri$tic $uplimentar: fiecare nod al $u

conine o c5eie "c4mp cu %alori unice pentru nodurile ar'orelui# &i: toate nodurile din $t4nga nodului re$pecti% au %alorile c5eilor mai mici dec4t c5eia noduluicurent

toate nodurile din dreapta nodului re$pecti% au %alorile c5eilor mai mari dec4t c5eia noduluicurent

xemplu: -igura alturat ilu$treaz reprezentarea grafic a unui ar'ore 'inar de cutare "%aloarea c5eii e$teprecizat (n fiecare nod#:

6

*

7

2

31

8

9

Se poate o'$er%a o proprietate important a ar'orilor 'inari de cutare: la parcurgerea (n inordine $e o'ineli$ta nodurilor ordonate dup %aloarea c5eii) n plu$, operaia de cutare a unui nod $pecificat de %aloarea c5eiie$te $implificat "de aici &i denumirea ar'orilor de cutare#)

.utarea unui nod dup o c5eie dat nu nece$it parcurgerea (ntregului ar'ore) Datorit $pecificului ace$torar'ori, %aloarea c5eii e$te comparat cu c5eia coninut (n rdcin &i (n funcie de rezultatul comparaiei,cutarea $e %a continua doar (ntrunul dintre cei doi $u'ar'ori, cellalt $u'ar'ore fiind exclu$ din cutare)Procedeul $e %a continua (n mod $imilar pentru $u'ar'orele curent: $e compar %aloarea c5eii cutate cu c5eiardcinii $u'ar'orelui &i (n funcie de rezultatul comparaiei $e %a continua cutarea doar (ntrunul dintre$u'ar'orii $u'ar'orelui curent) .utarea $e %a (nc5eia (n momentul (n care un nod rdcin a $u'ar'oreluicurent conine c5eia cutat $au dac nu mai $unt noduri de parcur$ &i c5eia nu a fo$t g$it)

.utarea unei informaii (ntro $tructur de ar'ore 'inar de cutare e$te eficient, deoarece numrulnodurilor acce$ate $e reduce prin excluderea acelor $u'ar'ori a cror parcurgere ar fi inutil)

*peraiile de in$erare &i &tergere executate a$upra unui ar'ore 'inar de cutare %or produce de a$emenea un

ar'ore 'inar de cutare) !$tfel, (n definirea unor funcii $pecifice care opereaz a$upra ar'orilor de cutare $e%a ine cont de criteriul de ordine (ntre c5eile nodurilor ce formeaz ar'orele)

gra$e+raful e$te o perec5e ordonat de mulimi + G", #, unde e$te o mulime de %4rfuri, iar G b e$te o

mulime de muc5ii $au arce "pentru grafuri orientate#)* muc5ie de la %4rful x la %4rful e$te notata cu perec5ea ordonata "x, #, dac graful e$te orientat &i (n mod

uzual e$te folo$it termenul de arc, $i cu mulimea Lx, M, dac graful e$te neorientat) n reprezentarea grafic,arcele "x,# $unt marcate prin $gei de la extremitatea iniial x la cea final , iar muc5iile prin $egmente)

ntrun graf orientat, exi$tena unui arc de la %4rful x la %4rful nu pre$upune &i exi$tena arcului de la la x)n grafurile neorientate, dac exi$t muc5ie (ntre x &i , atunci acea$ta e$te &i muc5ie (ntre %4rfurile &i x)

J4rfurilor unui graf li $e pot ata&a informaii numite uneori %alori, iar muc5iilor li $e pot ata&a informaiinumite co$turi)

9. Programarea modulara. /e$inirea si parametri+area subalgoritmilor.12


13/32

Prin proiectare "programare# modular (nelegem metoda de proiectare "programare# a unui algoritmpentru rezol%area unei pro'leme prin folo$irea modulelor) >odulul e$te con$iderat o unitate $tructural de $ine$tttoare, fie program, fie $u'program, fie o unitate de program)

n modul poate conine $au poate fi coninut (ntralt modul $i poate fi format din mai multe $u'module)$te important ca fiecare modul $&i ai' rolul $u 'ine precizat, $ realizeze o funcie (n cadrul (ntregului

program "proiect#) n lim'a6ele de programare cu $tructur de 'loc "de exemplu (n Tur'o Pa$cal, # niturile potfi con$iderate module) a compilarea $eparat un grup de $u'programe compilate deodat con$tituie un modul,dar ace$t modul poate fi con$iderat ca o mulime de $u'module din care e$te compu$) >odulele $unt relati%

independente, dar cu po$i'iliti de comunicare (ntre ele)!$tfel, un modul nu tre'uie $ fie influenat de maniera (n care $e lucreaz (n interiorul altui modul)*rice modificare ulterioar (n $tructura unui program, dac funcia pe care o realizeaz un modul > (nc e$tenece$ar, ace$t modul tre'uie $ fie util &i folo$it (n continuare fr modificri)6. Programarea orientata obiect. Concepte si principii&

Clasa. bstracti+area

* cla$ reprezint un T!D (n care protecia datelor e$te a$igurat)

n acti%itatea de programare, identificarea cla$elor $e realizeaz (n etapa de analiz a pro'lemei &icore$punde proce$ului de a'$tractizare)Sinax: "definirea unei cla$e#cla$$ ;ume.la$ L

_R>odProptectie:` Ri$ta>em'rii_R>odProptectie:` Ri$ta>em'rii

_R>odProptectie:` Ri$ta>em'rii

MCnde:R>odProptectie:Gpri%ateQ protected Q pu'licRi$ta>em'rii:G

Ri$taDate>em'ruRi$ta-unctii>em'ru :biect. 'ncapsulare

*'iectul reprezint o in$tan a unei cla$e)!ce$ta poate fi pri%it pentru (nceput ca o dat de tipul de date a'$tract introdu$ prin intermediulcon$truc iei cla$$)

Propriet ile unui o'iect includ:numele $pecificat printrun identificatoratri'ute date mem're de un anumit tip ale cror %alori la un moment dat define$c $tarea o'iectuluimetode func ii mem're cla$ei prin intermediul crora pot fi acce$ate atri'utele o'iectului i e%entual

modificat $tarea ace$tuiaC $etul de metode define te comportamentul o'iectului) a in$tanierea unui o'iect $e produc urmtoarele:

datele mem're "atri'utele# $e aloc di$ctinct pentru fiecare o'iect in$taniat, cu excepia datelormem're $tatice

funciile mem'ru $e afl (ntrun $ingur exemplar oric4te in$tane ale cla$ei $ar produce tribute c)mpuri4

Tipul unui o'iect "$a'lon al o'iectului# e$te o cla$a) * cla$a $e caracterizeaza prin: numelecla$ei, atri'ute, functii $i relatii cu alte cla$e)In$tanta e$te un o'iect dintro cla$a "!, , . $unt o'iecte, in$tante ale cla$ei matrice# $i are

proprietatile definite de cla$a) Pentru o cla$a definita, $e pot crea mai multe in$tante aleace$teia) Toate o'iectele au o $tare $i un comportament) Starea unui o'iect $e refera laelementele de date continute (n o'iect $i la %alorile a$ociate ace$tora "datele mem're#).omportamentul unui o'iect e$te determinat de care actiunile pe care o'iectul poate $a le execute "metodele#)!tri'utele $pecificate (n definitia unei cla$e de$criu %aloric proprietatile o'iectelor din cla$a, $u' diferite

13


14/32

a$pecte) .ele mai multe lim'a6e orientate o'iect fac urmatoarea di$tinctie (ntre atri'ute:atri'ute ale cla$ei "au aceea$i %aloare pentru toate in$tantele cla$ei#Catri'ute ale in$tantei "%ariaza de la o in$tanta la alta,#.onform programrii o'i nuite $e poate face urmtoarea analogie:obiect e$te ec5i%alent cu o %ariabilclaa e$te ec5i%alent cu un tip de&init de utilizator

Metode operatii4

>etodele pot a%ea acce$ la $tarea o'iectului &i de aceea $e comport diferit, (n funcie de aciunea ace$toraa$upra $trii o'iectului)Constructori metode care creeaz noi in$tanieri ale cla$ei "adic noi o'iecte#) Spunem cs-a nscutun nou obiect atunci c4nd e$te folo$it con$tructorul unei cla$e) $te po$i'il $ creem o'iecte (n mai multemoduri, deoarece unei cla$e (i pot core$punde mai muli con$tructori)2. /estructori ; metode care elimin obiecte din memorie)3. !electori ; metode care nu modific starea obiectului, a$emntoare cu acce$ul read-only) Selectori potin%oca o'iecte din mai multe cla$e)*. Modi$icatori ; metode care modific starea obiectului, efectu4nd operaii de $criere la ni%elul dateloro'iectului)

;ece$itatea folo$irii unor funcii glo'ale friendapare (n $ituaiile (n care exi$t funcii externe cla$ei

care ar putea opera a$upra datelor mem're cla$ei re$pecti%e) Datorit proteciei datelor mem're "private $au protected# ace$t lucru e$te interzi$ (n mod

o'i&nuit) * po$i'il $oluie "dar ineficient# con$t (n refacerea codului &i tran$formarea funciei glo'ale (n

metod a cla$ei) Pentru a nu modifica codul de6a $cri$ &i pentru a permite de a$emenea acce$area $au modificarea datelor

mem're de ctre funciile glo'ale exi$tente $e recurge la o $oluie de compromi$: declararea funciilorca fiind prietene8 cla$ei a$upra creia %or aciona)

?4).on$tructorii &i de$tructorii nu $e mo&tene$c)*peratorii $e mo&tene$c)>etodele unei cla$e prietene cu cla$a de 'az, poate acce$a atri'utele cla$ei de 'az, dar nu &i atri'utele cla$eideri%ate)

1/


15/32

9elaia de a$ociereAsocierea e$te o conexiune (ntre cla$e, ceea ce (n$eamn o legtur $emantic (ntreo'iectele cla$elor implicate (n relaie) n mod normal e$te o relaie 'idirectional, ceea ce

pre$upune c dac un element e$te a$ociat cu altul, a$ocierea exi$t &i (n $en$ in%er$) .eamai (nt4lnit relaie de a$ociere e$te asocierea simpla. !$ocierea are un nume care de o'icei e$te un %er'C daca$ocierea e$te numai (ntrun $en$ $e %a folo$i o $geat pentru precizarea $en$ului)

Unidirecional% in$tan a cla$ei Studente$te legat de mai multe in$tane ale cla$ei isciplina) !relaia se

traverseaz "ntr-un singur sens#:

Bidirecional% 9ela ia reprezentat mai $u$ e$te tradu$ prin formularea: Profesorul pred ndiscipline i

le cunoa te i disciplina este predat de m profesori i "i cunoa te$ !relaia se traverseaz "n ambele sensuri#


16/32

mo&tenirea repetat (n cla$a deri%at a acelor atri'ute care $e reg$e$c (n dou $au mai multe cla$e de'az)

Polimor$ismul

Definiie: Polimorfi$mul reprezint mecani$mul prin care aceia&i form $intactic poate a%ea (nele$uridiferite (n funcie de contextul (n care e$te utilizat)>odalitate de realizare: polimorfi$mul e$te realizat (n lim'a6ul .HH prin:$upra$crierea "redefinirea metodelor aflate $u' relaia de deri%are#

funcii %irtuale "%ezi capitolul anterior#$upra(ncrcare "ex) $upra(ncrcarea operatorilor#

Partea a ''-a& Ba+e de date1. Principii generale.

a. Concepte de ba+%@* baz de date reprezint un an$am'lu de date integrat, anume $tructurat &i dotat cu o de$criere a ace$tei

$tructuri) De$crierea $tructurii poart numele de dicionar de date $au metadate &i creaz o interdependen (ntredatele propriuzi$e &i programe)

aza de date poate fi pri%it ca o colecie de fi&iere interconectate care conin nucleul de date nece$are unui$i$tem informatic) !$tfel, poate fi con$iderat drept un model al unor a$pecte ale realitii unei uniti economice,modelat prin intermediul datelor) Diferitele o'iecte din cadrul realitii, ce prezint intere$, $unt denumite clase $au

entiti) Pentru ace$te o'iecte $unt ac5iziionate &i memorate date referitoare la diferite caracteristici "atribute#) azade date $e con$tituie ca un an$am'lu intercorelat de colecii de date, prin care $e realizeaz reprezentarea uneirealiti)

atele con$tituie orice me$a6 primit de un receptor, $u' o anumit form)*nformaiile reprezint cantitatea de noutate adu$ de un me$a6 din exterior "realitate#)nfi+ier e$te un an$am'lu de "nregistrri fizice, omogene din punct de %edere al coninutului &i al prelucrrii)* "nregistrare fizic e$te o unitate de tran$fer (ntre memoria intern &i cea extern a calculatorului)* "nregistrare logic e$te unitatea de prelucrare din punct de %edere al programului utilizator)* (nregi$trare $e compune din c,mpuri "atribute# care de$criu anumite a$pecte ale realitii) .4mpurile $unt

(nregi$trri logice)* 'az de date tre'uie $ a$igure:

abtractizarea datelor"'aza de date fiind un model al realitii#, integrarea datelor "'aza de date e$te un an$am'lu de colecii de date intercorelate, cu redundan

controlat#, integritatea datelor"$e refer la corectitudinea datelor (ncrcate &i manipulate a$tfel (nc4t $ $e re$pecte

re$triciile de integritate#,1U


17/32

ecuritatea datelor"limitarea acce$ului la 'aza de date#,partajarea datelor"datele pot fi acce$ate de mai muli utilizatori, e%entual (n acela&i timp#,A independena datelor "organizarea datelor $ fie tran$parent pentru utilizatori, modificrile (n 'aza de

date $ nu afecteze programele de aplicaii#)

b. bordarea ba+elor de date@+e$tionarea datelor implic at4t ge$tionarea factorilor reprezentai de &iruri de 'ii pe medii magneticede memorare c4t &i ge$tionarea $emnificaiei ace$tor factori) Semnificaiile $unt ge$tionate prin

organizarea lor (n $tructuri logice de entiti)1. 1.oiuni =i termeni te"nici u+uali

a) * entitatee$te reprezentat din datele de acela&i tip ale unui o'iect $pecific) *'iectele pot fi fixate (ncla$e de o'iecte numite entiti asociate) n tip de entitate reprezint osemnificaie, pe c4nd oin$tan de entitate reprezintfapte)

') -iecare entitate e$te de$cri$ de o mulime de proprieti e$eniale numite atribute) c)n atri'ut $auo mulime de atri'ute pentru care %alorile a$ociate determin (n mod unic orice element al entitiire$pecti%e $e nume&te ceie)

c) d$ ;umim relaie (ntre entitile 1,2,,@ orice $u'mulime a produ$ului cartezian al

mulimilor elementelor celor kentiti, adic mulimi de elemente de forma "e 1,e2,))),e@#, unde e1e$te un element din 1, e2e$te un element din 2 &)a)m)d) k) De cele mai multe ori @G2, deci $elucreaz cu relaii binare)n cazul relaiilor 'inare, $e poate face o cla$ificare a lor (n funcie de c4te elemente core$pundfiecrui element dintro entitate (n cealalt entitate, dup cum urmeaz:1. relaie unu-la-unu"notat 1&1#, (n cazul (n care fiecrui element din prima entitate (i core$punde

cel mult un element din a doua entitate &i reciprocC2. relaie unul-la-mai-muli"notat 1, (n cazul (n care fiecrui element al primei entiti (i pot

core$punde mai multe elemente din a doua entitate, dar fiecrui element din a doua entitate (icore$punde cel mult un element din prima entitate)

3. relaie mai-muli-la-mai-muli"notat M, (n cazul (n care fiecrui element al primei entiti (i

pot core$punde mai multe elemente din a doua entitate &i reciproc)d) Informaiile pri%ind $tructura unei %ederi $unt $intetizate grafic (ntro diagram entitate-relaie, care

pune (n e%iden entitile ce inter%in, reprezentate prin dreptung5iuri, atri'utele a$ociate lorreprezentate prin elip$e, &i diferite relaii ce $e $ta'ile$c (ntre entiti reprezentate prin $gei "cu %4rfdu'lu ctre entitatea pe care pot aprea mai multe elemente (n relaie cu un element din cealaltentitate#)

xi$t dou forme de 'aze de date:a) a) baze de date fizice, care $unt reprezentri pe medii de memorare a entitilor, atri'utelor &i a

relaiilor dintre eleC') ') baze de date logice, care reprezint entiti, atri'ute &i relaiile independente de modul (n care

datele &i relaiile $unt reprezentate &i memorate (ntro 'az de date fizic)

xi$t trei categorii de modele de 'aze de date:1)modelul relaionalC2)modelul reeaC3)modelul ar'ore$cent "ierar5ic#)

c. i#ele de abstractie n !B/. Ba+a logic%. Ba+a conceptual%* 'aza de date poate fi pri%ita din mai multepuncte de vederecum $unt:

Punctul de %edere al utilizatorilor care pri%e$c anumite parti componente ale 'azei de date numite%ederi) Dederile $unt de$cri$e prin $u'$c5eme in $u'lim'a6e ale lim'a6ului de de$criere a datelor) De

a$emenea utilizatorii pot $a prime$ca ra$pun$uri la diferitele cereri formulate prin intermediul lim'a6ului deprelucrare a datelor)

1A


18/32

Punctul de %edere al admini$tratorului de 'aza de date care integreaza toate %ederile ce pri%e$c 'azade date intrun $ingur model numit sc"ema conceptuala) Sc5ema conceptuala con$tituie ni%elul logic al

'azei de date) Punctul de %edere al implementatorului 'azei de date "care de cele mai multe ori coincide cu

admini$tratorul 'azei de date# care pri%e$te 'aza de date ca o colectie de fi$iere memorate pe diferite mediiexterne cum $unt 'enzile $i di$curile magnetice) !ce$ta con$tituie ni#elul $i+ical 'azei de date fiind de fapt$ingurul ni%el exi$tent efecti%)

-iecare dintre cele trei ni%ele contine $u'ni%ele) De exemplu utilizatorii pot fi utilizatori o'i$nuiti, fara

cuno$tinte de programare $au programatori de aplicatii, organizarea %ederilor core$punzatoare lor fiinddiferita) a fel ni%elul fizic poate $a contina un $u'ni%el logic in care conteaza $emnificatia diferitelorcampuri din inregi$trarile fi$ierelor $i $tructurile de date a$ociate $i un $u'ni%el fizic in care e$ential e$tenumai modul de organizare $i ge$tionare a 'locurilor pe memoria externa)

Primele doua ni%ele $unt de$cri$e prin planuri ce con$tau in enumerarea tipurilor de entitati ceapar in 'aza de date, relatiile intre ace$te tipuri de entitati $i modul de trecere de la notiunile ace$tui ni%el lani%elul imediat urmator) In mod curent ace$te planuri $e nume$c sc"eme e(terne $au $u'$c5emeconceptuale $au %ederi pentru primul ni%el $i $c5eme conceptuale pentru al doilea ni%el) De$crierile la ni%elfizic $unt facute prin sc"eme interne sau sc"eme $i+ice)%roiectarea se poate face plecand de la modelul relational care permite o te&nologie de proiectaresi apoi se poate transforma rezultatul proiectarii in oricare dintre modele prin adaptarilecorespunzatoare.

2. Procesul de proiectare a ba+elor de date@a. Modelarea datelor logice@

Modelul de date reprezint an$am'lul de concepte &i in$trumente nece$are pentru a con$trui o $c5em a'azei de date) >odelarea datelor poate %iza totalitatea datelor din cadrul 'azei de date "$c5emaNar5itecturadatelor# $au o parte a ace$tora "$u'$c5eme ale 'azei de date#) Sc5ema &i $u'$c5ema 'azei de date $unt modelelelogice ale 'azei de date, care au a$ociate principii generale pentru ge$tionareaNdefinirea "$tructurarea# datelor,manipularea &i a$igurarea integritii datelor, fr a reflecta modul de reprezentare &i $tocare a ace$tor date pe$uportul de memorie "care $unt ele modelului fizic#)

Se cuno$c mai multe tipuri de 'aze de date dup modul de organizare, modul de di$punere pe $uport

magnetic a informaiei &i a elementelor componente: ^)aze de date

1\


19/32

modele primitive datele $unt organizate la ni%el logic (n fi&iere, $tructura de 'az e$te (nregi$trarea, maimulte (nregi$trri fiind grupate (n $tructuri de tip fi&ierC

baze de date ierarice legturile dintre date $unt ordonate unic, acce$ul $e face numai prin %4rfulierar5iei, un $u'ordonat nu poate a%ea dec4t un $ingur $uperior direct &i nu $e poate a6unge la el dec4t peo $ingur caleC

baze de date "n reea datele $unt reprezentate ca (ntro mulime de ierar5ii, (n care un mem'ru al ei poatea%ea oric4i $uperiori, iar la un $u'ordonat $e poate a6unge pe mai multe ciC

baze de date relaionale $tructura de 'az a datelor e$te aceea de relaie . tabel, lim'a6ul S?"Structured ?uer anguage# e$te $pecializat (n comenzi de manipulare la ni%el de ta'el) Termenulrelaional a fo$t introdu$ de un cercettor al firmei I>, dr) ) -) .odd, (n 1^U^, cel care a enunat cele13 reguli de 'az nece$are pentru definerea unei 'aze de date relaionale) aza de date relaionalreprezint o mulime $tructurat de date, acce$i'ile prin calculator, care pot $ati$face (n timp minim &i(ntro manier $electi% mai muli utilizatori) !cea$t mulime de date modeleaz un $i$tem $au un

proce$ din lumea real &i $er%e&te ca $uport unei aplicaii informaticeC baze de date distribuite $unt rezultatul integrrii te5nologiei 'azelor de date cu cea a reelelor de

calculatoare) Sunt 'aze de date logic integrate, dar fizic di$tri'uite pe mai multe $i$teme de calcul

b. Modelul conceptual entitate relatie

.ele treicomponenteale modelului relaional $unt:

a) componenta destructura datelor "relaii cu proprieti $peciale#C

') componenta de manipulare a datelor "operaii predefinite prin care te5nologia relaional folo$e&te unoptimizator inteligent pentru a g$i calea de acce$ la date#C

c) componenta de integritatea datelor "reguli nece$are proteciei datelor la efectuarea unor operaii incorecte#)

Principalul a%anta6 al modelului relaional e$te acela c nu e$te nece$ar utilizarea at4t a pointerilor c4t &i adatelor (n cadrul ta'elelor, folo$ind (n $c5im' relaiipentru a acce$a %alori core$pondente din mai multe ta'ele)

* relaiecon$t dintro a$ociere (ntre (nregi$trrile aflate (n dou ta'ele ce au acelea&i %alori ale atri'utelor)

Deoarece ta'elele relaionale nu conin pointeri, datele aflate (n a$tfel de ta'ele $unt independente de metodelefolo$ite de ctre $i$temul de ge$tiune al datelor (n lucrul cu (nregi$trrile ta'elelor)

*ntensiamodelului relaional e$te o $c5em relaional cu una $au mai multe $c5eme de relaie) -iecare $c5emde relaie are propriul nume &i propriile atri'ute)

/xtensiamodelului relaional e$te un ta'el ce nu permite (nregi$trri duplicat) -iecare $c5em de relaieintroduce un ta'el (n $c5ema relaional)

>odelul relaional ofer o interfa flexi'il ce e$te pre%zut cu cele mai potri%ite componente nece$areoricrui utilizator la toate ni%elele, oferind o mare independen a datelor "produ$ul o'inut e$te relati%independent de implementarea intern#)

1) 9elaiile $unt alctuite din dou pri:- in$tana un ta'el cu r4nduri &i coloaneC

- $c5ema $pecific numele relaiei (mpreun cu numele &i tipul fiecrei coloane)

Termenul de relaie e$te folo$it (n $en$ul $u matematic acceptat:

Se d o $c5em de relaie 9 G r"!1, ))), !n# pe un $et de domenii LD1, D2))), DnM) * relaie nar rreprezint un$u'$et al produ$ului cartezian al ace$tor domenii: D1x D2 x ))) x Dn)

Proprietile unei relaii $unt:

- relaiile $unt alctuite din r4nduri &i coloaneC

- (ntro relaie nu are importan ordinea de apariie a r4ndurilor $au coloanelorC

- (ntre ta'ele nu exi$t o a$ociere explicit "nici una %izi'il cui%a care acce$eaz datele#C

- fiecare (nregi$trare poate fi identificat (n mod unicC

1^


20/32

- fiecare r4nd din cadrul unui ta'el are acela&i $et de coloaneC

- fiecare coloan are un $ingur tip de dat "nu $unt acceptate redefiniri pentru diferite %alori#)c. Propriet%tile de+irabile si $unctionale !B/

n S+D tre'uie $ a$igure funciile: funcia de de$criere a datelor $e face cu a6utorul DD, realiz4ndu$e de$crierea atri'utelor din cadrul

$tructurii 'azei de date, legturile dintre entitile 'azei de date, $e define$c e%entualele criterii de %alidare adatelor, metode de acce$ la date, integritatea datelor) .oncretizarea ace$tei funcii e$te $c5ema 'azei de date)

funcia de manipulare e$te cea mai complex &i realizeaz actualizarea &i reg$irea datelor) funcia de utilizare a$igur mulimea interfeelor nece$are pentru comunicare a tuturor utilizatorilor

cu 'aza de date) funcia de admini$trare admini$tratorul e$te cel care realizeaz $c5ema conceptual a 'azei de date,

iar (n perioada de exploatare a 'azei de date autorizeaz acce$ul la date, reface 'aza (n caz de incident) funcia de protecie a 'azei de date an$am'lul de m$uri nece$are pentru a$igurarea integritii

"$emantic, acce$ concurent, $al%areNre$taurare# &i $ecuritii datelor "autorizare acce$, utilizare %iziuni,criptare#)

3. Maparea pe modelul relaional @$odelul relaional

e$te modelul folo$it de mine (n realizarea ace$tei 'aze de date &i reprezint cel mai utilizat model de $tocare adatelor, (n care datele $unt organizate $u' form de ta'ele (ntre care exi$t di%er$e legturiC modelul relaionale$te un model $implu, 'azat pe alge'ra relaional, care a fcut po$i'il dez%oltarea lim'a6elor relaionale $u'forma unui $oft


21/32

1 (i core$punde o $ingura entitate dinmultimea >2$i reciproc "figura 1)#)

igura -..9elatie de tip 1:1

21


22/32

ntro relatie 1:n "unalamaimulte#, unei entitati din >1(i core$pund 0, una $au mai multe entitati din >2,dar fiecarei entitati din >2(i core$punde o $ingura entitate din >1"figura 1)U#)

igura -./. 9elatie de tip 1:n

ntro relatie n:m "maimultelamaimulte#, unei entitati din >1(i core$pund 0, una $au mai multe entitati din>2, $i reciproc "figura 1)A#)

igura -.0. 9elatie de tip n:m

. lgebra relationala@a. C"ei primare si secundare. Constrngeri de integritate

1+ei relationaleSa mentionat faptul ca tuplurile unei relatii $unt unice, ceea ce (n$eamna ca fiecare tuplu poate fi identificat(n mod unic prin %alorile atri'utelor $ale) De o'icei, pentru identificarea unica a unui tuplu nu $unt nece$are

%alorile tuturor componentelor $ale, ci $unt $uficiente doar %alorile unui $u'$et al atri'utelor relatiei)

* c"eie candidate$te un atri'ut $au un $et de atri'ute care identifica (n mod unic un tuplu dininteriorul unei relatii)

Pentru o relatie pot exi$ta mai multe c5ei candidat) * a$tfel de c5eie poate fi simpla daca e$tecon$tituita dintrun $ingur atri'ut $au compusac4nd contine mai multe atri'ute)

n orice relatie exi$ta cu certitudine o c5eie, (n cel mai defa%ora'il caz c5eia fiind (ntregul tuplu) ncon$ecinta, pro'lema ga$irii unei c5ei $e reduce la determinarea $etului minimal de atri'ute care $ati$face

proprietatea de identificare unica)*rice atri'ut al unei relatii care face parte din cel putin o c5eie $e nume$te atribut prim) Toate

celelalte atri'ute ale relatiei $unt neprime)ntro relatie pot exi$ta mai multe c5ei candidat) Pentru fiecare relatie din cadrul unei 'aze de date $e

de$emneaza, dintre ace$tea, dupa anumite criterii, o c5eie pri%ilegiata numita c5eie primara)* c"eie primarae$te o c5eie candidat care e$te $electata pentru a identifica (n mod unic tuplurile din

cadrul unei relatii)!tunci c4nd o c5eie candidat nu e$te alea$a drept c5eie primara e$te con$iderata c"eie alternati#a

"secundara#)

2ntegritate relationalan model de date mai are (nca doua parti: o parte de manipularecare define$te tipurile de operatii permi$ea$upra datelor $i unset de regulide integritatecare a$igura corectitudinea datelor)

22


23/32

Din moment ce fiecare atri'ut are un domeniu a$ociat, exi$ta anumite con$tr4ngeri "denumite constr)ngeride domeniu# $u' forma de re$trictii impu$e multimii de %alori permi$e pentru atri'utele relatiilor) Pe l4ngaace$tea, exi$ta doua reguli de integritateimportante, care reprezinta con$tr4ngeri $au re$trictii ce $e aplicatuturor in$tantelor unei 'aze de date) Pentru modelul relational, cele doua reguli principale $unt cuno$cute $u'denumirile de integritate a entitatilor$i integritate re$erentiala)

n null reprezinta %aloarea unui atri'ut care e$te (n mod curent necuno$cuta $au nu e$te aplica'ila tupluluire$pecti%)

n null poate fi luat cu $en$ul de %aloare logica Vnecuno$cutaV) Poate (n$emna ca o %aloare nu e$te aplica'ilaunui anumit tuplu $au poate (n$emna doar ca, deocamdata, nu $a atri'uit nici o %aloare) ;ullurile reprezintao modalitate de tratare a datelor incomplete $au deo$e'ite) Totu$i, un null nu e$te acela$i lucru cu o %aloarenumerica egala cu zero $au cu un $ir de text completat cu $patiiC zerourile $i $patiile $unt %alori, pe c4nd unnull $emnifica a'$enta unei %alori) De exemplu, $e (nregi$treaza (n 'aza de date ac5izitia unui produ$, dar nu$e trece, deocamdata, numarul facturii, deoarece acea$ta nu a $o$it "marfa a fo$t (n$otita de a%iz de expeditie#)Jaloarea con$iderata pentru un atri'ut ;rZfactura %a fi null)

Prima regula de integritate $e aplica c5eilor primare ale relatiilor de 'aza) * relatie de 'aza core$punde uneientitati (n $c5ema conceptuala)

'ntegritatea entitatilorcon$ta (n faptul ca (ntro relatie de 'aza, nici un atri'ut al unei c5ei primare nu poate

fi null) Deci %alorile c5eilor primare tre'uie $a fie unice$i nenule)Prin definitie, o c5eie primara e$te un identificator minim, utilizat pentru identificarea unica a tuplurilor)!dmit4nd un null pentru orice parte a unei c5ei primare, acea$ta implica faptul ca nu toate atri'utele $untnece$are pentru a deo$e'i tuplurile, ceea ce contrazice definitia c5eii primare)

! doua regula de integritate $e aplica c5eilor $traine)

'ntegritatea re$erentialapre%ede faptul ca %aloarea unei c5ei $traine tre'uie ori $a coincida cu %aloarea uneic5ei candidat a unui tuplu (n relatia $a de 'aza, ori $a fie (n (ntregime null)

De exemplu, atri'utul ;r-il din relatia Per$onal e$te o c5eie $traina care tinte$te atri'utul ;r-il din relatia de'aza -iliala) ;u tre'uie $a fie po$i'ila crearea unei (nregi$trari de per$onal cu numarul de filiala 2, de

exemplu, dec4t daca exi$ta de6a o (nregi$trare core$punzatoare numarului 2 (n relatia -iliala "daca exi$taacea$ta filiala#) Totu$i, tre'uie $a exi$te po$i'ilitatea de a crea o noua (nregi$trare de per$onal cu un numar defiliala null) !cea$ta core$punde $ituatiei (n care un nou mem'ru al per$onalului a fo$t admi$ (n companie, faraa fi repartizat, deocamdata, la o anumita filiala)

n concluzie, orice S+D relational tre'uie $a realizeze urmatoarele trei principii:

principiul integritatii domeniului

principiul integritatii entitatii "$aual relatiei#

principiul integritatii re$erintei)

Constr)ngerile de ntreprindere$unt reguli aditionale $pecificate de catre utilizatorii $au admini$tratoriiunei 'aze de date) De exemplu, $e $ta'ile$te un numar maxim de 20 de mem'ri ai per$onalului pentru ofiliala)

n S+D e$te con$iderat total relationaldaca:

a$igura cele trei principii de integritate

furnizeaza utilizatorului un >D cel putin ec5i%alent ca putere de expre$ie cu alge'ra relationala)

9. Proiectarea $i+ic% a ba+elor de date relaionalea. 'nterogarea ba+elor de date !EHECT4

'nterogarea Iuer4e$te operatia prin care $e o'tin datele dorite dintro 'aza de date, $electate conform

unor criterii) Deoarece acea$ta operatie e$te cea mai importanta operatie, lim'a6ele de manipulare a datelor $untdenumite $i limba0e de interogare$

23


24/32

lgebra relationala relational algebra4, introdu$a de .odd (n 1^A0, define$te cadrul formal allim'a6elor relationale pentru 'aze de date)Algebra relationala introduce o colectie de operatori alge'rici care $eaplica relatiilor "ta'elelor#)Principalele in$tructiuni de manipulare a datelor $unt: S.T I;S9T PD!T DT

'nstructiunea !EHECTIn$tructiunea S.T e$te instructiunea de interogare a datelor din lim'a6ul S?) tilizarea ace$teiin$tructiuni genereaza o ta'ela %irtuala, numita vedere !1uery#) n 1uery $e rega$e$c toate informatiile dorite dinunul $au mai multe ta'ele ale 'azei de date)Sintaxa generala a in$tructiunii S.T e$te:!EHECT J/'!T'CTK c1, c2, ... , cn JF indica unu $au mai multe ta'ele ce contin datele dorite)Z .lauza h9 defin$te conditia $au conditiile ce tre'uie (ndepline de datele dinclauza S.T)

2/


25/32

Partea a '''-a&


26/32

caracteri$ticile ec5ipamentului extinderea re elei modul de admini$trare a re elei)Topologia Point-to-Point .ea mai $impl topologie din acea$t categorie e$te o legtur ";:in@# permanent (ntre dou

termina ii ";:endpoint#)Topologia Magistral% BU!4 Tipul de topologie de re ea (n care toate nodurile de a re elei $unt conectate la un mediu comun de

tran$mi$ie care are exact dou termina ii ";:endpoint$#, toate datele care $unt tran$mi$e (ntre noduri (n re ea e$te tran$mi$ (n cur$ul ace$tei parti comune de tran$port i de mediu (n a a m$ur ca $ fie

primite de ctre toate nodurile din re ea, aproape $imultan "fr a ine $eama de (nt4rzieri r$p(ndite#) #antaGele Topologiei BU! or de implementat i de extin$ ;ece$it mai pu in lungime de ca'lu dec(t re elele $tea Sunt 'ine adaptate pentru re ele temporare i mici care nu nece$it %iteze mari, (n plu$ $e poate u or de

configurat Sunt mai pu in co$ti$itoare deoarece $e folo$e te numai un ca'lu

Topologia !tarstea4

Tipul de topologie de re ea (n care fiecare din nodurile de re ea e$te conectat la un nod central, numit 5u' $au $


27/32

*. Modelul '!:-:!'>odelul de referin *SI "*pen S$tem Interconnection, Interconectarea Si$temelor De$c5i$e# propune criteriigenerale pentru realizarea comunicrii (n cadrul $i$temelor de calcul, a$tfel (nc4t ace$tea $ poat $c5im'ainformaii, indiferent de particularitile con$tructi%e ale $i$temelor "fa'ricant, $i$tem de operare, ar#) >odelulde referin *SI are aplicaii (n toate domeniile comunicaiilor de date, nu doar (n cazul reelelor decalculatoare) >odelul *SI di%ide pro'lema complex a comunicrii (ntre dou $au mai multe $i$temeinformatice (n &apte ni%eluri $au $traturi "laer$# di$tincte, (ntro ar5itecturierar5ic) -iecare ni%el are funcii 'ine determinate &i comunic doar cu ni%elurile adiacente) !ce$te &apte

ni%eluri formeaz o ierar5ie plec(nd de la ni%elul $uperior A !plicaie "!pplication# &i p4n la ultimul din parteade 6o$ a $ti%ei, ni%elul 1 -izic "P5$ical#)>odelul *SI include un $et de protocoale care (ncearc $ definea$c &i $ $tandardizeze proce$ulcomunicaiilor de date)>odelul *SI are &apte $traturi $au ni%eluri "laer$# &i anume:

aer A !pplicationaer U Pre$entationaer Se$$ionaer / Tran$portaer 3 ;et


28/32

i#elul sesiune $ta'ile$te $i intretine conexiuni "sesiuni# intre proce$ele aplicatie, rolul $au fiind acela de apermite proce$elor $a $ta'ilea$ca Vde comun acordV caracteri$ticile dialogului $i $a $incronizeze ace$t dialog)i#elul pre+entare realizeaza operatii de tran$formare a datelor in formate intele$e de entitatile ce inter%in intro conexiune) Tran$ferul de date intre ma$ini de tipuri diferite "nixD*S, de exemplu# nece$ita $i codificareadatelor in functie de caracteri$ticile ace$tora) ;i%elul prezentare ar tre'ui $a ofere $i $er%icii decriptareNdecriptare a datelor, in %ederea a$igurarii $ecuritatii comunicatiei in retea)i#elul aplicatie are rolul de Vferea$traV de comunicatie intre utilizatori, ace$tia fiind reprezentati de entitatileaplicatie "programele#) ;i%elul aplicatie nu comunica cu aplicatiile ci controleaza mediul in care $e executa

aplicatiile, punandule la di$pozitie $er%icii de comunicatie) Printre functiile ni%elului aplicatie $e afla:o identificarea partenerilor de comunicatie, determinarea di$poni'ilitatii ace$tora $i autentificarea loro $incronizarea aplicatiilor cooperante $i $electarea modului de dialogo $ta'ilirea re$pon$a'ilitatilor pentru tratarea eroriloro identificarea con$trangerilor a$upra reprezentarii dateloro tran$ferul informatieiPrimele trei ni%ele de la 'aza ierar5iei "fizic, legatura de date, retea# $unt con$iderate ca formand o subretea decomunicatie$

9. Modelul TCP'P6. Paralel% ntre :!' =i TCP

De&i modelul de referin *SI a fo$t creat pentru a$igurarea interopera'ilitii ec5ipamentelor de reea, modelulTCP'P a fo$t conceput pentru a oferi o referin pentru dez%oltarea de protocoale compati'ile) >odelul de referin T.PNIP &i $ti%a protocolului T.PNIP "T.PNIP protocol $tac@# au fcut po$i'ilcomunicarea (ntre dou computere aflate (n oricare parte a lumii, cu %iteza luminii)TCP Tranmission Control Protocol4 are rolul de (mprire a datelor (n pac5ete &i a$igur tran$mitereacorect a me$a6elor (ntre computere) Pac5etele $unt numerotate, put4ndu$e %erifica primirea lor (n forma (n care au fo$t tran$mi$e &irecon$tituirea me$a6elor lungi, formate din mai multe pac5ete)'P 'nternet Protocol4 a$igur li%rarea pac5etelor numai dac (n funcionarea reelelor nu apar erori) Dacun me$a6 e$te prea lung, IP cere fragmentarea lui (n mai multe pac5ete) Tran$miterea pac5etelor IP $e face (ntrecalculatoare gazd &i nu direct (ntre programele de aplicaie)Protocolul T.PNIP are a%anta6ul c nu depinde de configuraia 5ardTP D;S D;S T-TP T.P DP I;T9;T IP !; !lte !; I !;

De&i at4t *SI c4t &i T.P (ncearc $ definea$cNmodeleze acela&i lucru, &i anume proce$ul de comunicare (ntredou entiti, $e pune fire$c (ntre'area: care din ele e$te mai 'unj Din pcate, pe c4t de $impl e$te (ntre'area,

pe at4t de complicat &i contro%er$at e$te r$pun$ul) * do%ad BBmaterial== (n ace$t $en$ o con$tituie cartea2\


29/32

intitulat 778pen Systems 4et5orking' 9(P:*P and 8S*;; pu'licat (n cadrul pre$tigioa$ei edituri !ddi$one$le care dez'ate ace$t $u'iect pe parcur$ul a))) U00 pagini S (ncercm &i noi $ identificm, (ntrun $paiumult mai re$tr4n$, c4te%a dintre a$emnrile &i deo$e'irile care leag cele dou modele)* important a$emnare (ntre *SI &i T.PNIP o con$tituie faptul c am'ele $unt modele conceptuale ale

proce$ului de comunicare) Din pcate acea$t a$emnare $impl &i e%ident conine &i o prim deo$e'irefundamental: *SI e$te general, permi4nd explicarea oricrui proce$ de comunicare, (n timp ce T.PNIPul nureu&e&te $ modeleze perfect dec4t proce$ul de comunicare folo$it (n Internet)* alt important a$emnare (ntre cele dou modele o reprezint faptul c am'ele conin o $ti% de ni%eluri care

$unt legate (ntre ele prin noiunea deserviciu "ceea ce &tie $ fac un ni%el#, interfa "modul (n care $er%iciile$unt oferite ni%elui $uperior# &iprotocol "modul (n care $unt efecti% implementate $er%iciile#) Dac *SI reu&e&te$ fac o di$tincie clar (ntre ace$te trei elemente, pentru T.PNIP ele nu reprezint deloc un element %ital)nc o a$emnare ar mai putea fi identificat: am'ele modele $au 'ucurat de o r$p4ndire larg)Din punct de %edere te5nic o diferen e%ident dintre cele modele o reprezint faptul cni%elurile $uperioare prezente (n *SI $unt coma$ate (ntrunul $ingur la T.PNIP)* alt diferen tot de ordin te5nic o reprezint faptul c *SIul de$crie dou tipuri de protocoale, orientateconexiune &i fr conexiune, la ni%elul reea &i doar unul, cel orientat conexiune, pentru ni%elul tran$port)T.PNIPul merge exact (n direcia opu$, oferind doar un protocol fr conexiune la ni%el reea &i am'ele tipuride protocoale pentru ni%elul tran$port)* alt deo$e'ire de ordin te5nic care complic *SIul e faptul c anumite operaii, cum ar fi de exemplu

%erificrile de integritate, $unt realizate de mai multe ori (n cadrul unor ni%eluri diferite)8. Modelul TCP'P. Modelul de retea =i protocoalele 'EEE. ??? la punctul 6.

I e$te cea mai mare organizaie profe$ional din lume) Su' egida $a anual $e pu'licnumeroa$e re%i$te &i 6urnale te5nice, $unt organizate $eminarii &i conferine, I de%enind a$tfel unul dintrecele mai pre$tigioa$e forumuri pentru dez'ateri &tiinifice) >ulte dintre ace$te dez'ateri a6ung $ fieconcluzionate de grupurile de $tandardizare afiliate I) Principalul $et de $tandarde pentru reelele decalculatoare ela'orat de I poart numele de \02)x &i cuprinde $tandarde ca:

;r) $tandardului Denumirea\02)1 !;N>!; 'ridging\02)2 . ".ontrolul legturi logice#\02)3 .S>!N.D "t5ernet#\02)/ To@en u$\02) To@en 9ing\02)U DD? "Standard pentru >!;#\02)A road'and !;\02)10 !; uri %irtuale &i $ecuritate\02)11 irele$$ !;\02)1 luetoot5

7. Transportul datelor pe o legatura de date3egatura de date e$te un an$am'lu compu$ din elementele a doua ec5ipamente terminale de date, care $untcontrolate de un protocol $i care, prin intermediul circuitului de date ce le interconecteaza, permit, (mpreuna,

tran$ferul datelor) ;i%elul legatura de date e$te realizat pe conexiunea fizica a$igurata de un circuit "fie el $idintro retea#, pentru a furniza un $er%iciu de tran$fer de date fia'il ni%elului retea $au, direct, ni%eluluiaplicatie).ircuitul de date e$te an$am'lul format din doua canale de tran$mi$iune a$ociate pentru a a$igura tran$mitereadatelor (n am'ele $en$uri)Statia de date e$te o unitate functionala care furnizeaza date pentru tran$mi$iune, prime$te datele tran$mi$e $irealizeaza toate functiunile nece$are pentru comunicatia cu oalta unitate functionala)Protocolul legaturii de date e$te con$tituit dintrun $et de reguli care determina comportarea unitatilorfunctionale (n cur$ul comunicatiei, urmarind ca informatia tran$ferata $a fie receptionata $i interpretata corect)egatura de date poate fi con$iderata $u' doua a$pecte: "1# fizic, cu referire la circuitul de date $i tran$mi$iunea

datelor $i "2# logic)Pentru a a$igura tran$ferul $igur $i eficient al datelor protocolul legaturii de date tre'uie $a realizezeurmatoarele functiuni principale: controlul erorii, controlul fluxului, formatarea datelor (n cadre "'locuri#,identificarea $ur$ei $i de$tinatiei datelor "(n legaturile multipunct $i (n 'ucla#) De$igur, protocolul legaturii de

2^


30/32

date tre'uie $a ai'a (n %edere $i $ituatiile anormale de functionare care pot $ur%eni (n cur$ul tran$ferului datelor:(ntreruperi ale legaturii, $aturarea unei $tatii, erori frec%ente, etc)

10. Protecia datelor mpotri#a erorilorPrincipalele cauze ale erorilor (n tran$mi$iunile de date $unt: zgomotul, interferenta $im'olurilor $i fluctuatiatactului de $ondare) Influenta ace$tor cauze a$upra marimii coeficientului de eroare pentru un circuit datdepinde de mai multi factori, cum ar fi: tipulcircuitului, de'itul datelor, metoda de modulatie utilizata) n mod uzual coeficientul de eroare %ariaza (ntre10k/ $i 10kU, iar gruparea erorilor depinde de tipul circuitului) n functie de natura cauzelor erorilor, ace$tea

pot fi cla$ificate (n erori independente $i erori (n pac5ete) n cazul erorilor independente $im'olurile de date$unt afectate (n mod independent unul de altul $i pro'a'ilitatea unei grupari "model# oarecare de erori depindenumai de numarul lor)>etodele de protectie a datelor (mpotri%a erorilor introdu$e de canalul de tran$mi$iuneimplica folo$irea unui codor (n tran$mitator, a unui decodor (n receptor $i a unei $trategii de control al erorii)Strategia de utilizare a codorului $i decodorului depinde de an$am'lul $i$temului de comunicatii de datecon$iderat) !cea$ta $trategie poate fi o $impla detectie a erorilor, entitatea care prime$te datele fiind informatade$pre 'locurile de date receptionate cu erori) !lte $trategii urmare$c corectarea erorilor $i, pentru ace$tea, $edi$ting doua cazuri: "1# detectarea 'locurilor de date receptionate eronat $i corectarea erorilor prinretran$miterea ace$tor 'locuri $i "2# corectarea directa, la receptie, a erorilor

11. !isteme de operare n retea

Principala component $oft


31/32

13. Compresia datelor.ompre$ia datelor e$te un proce$ de codare prin care $e urmre&te mic&orarea redundanei me$a6ului generat deo $ur$, pentru a reduce re$ur$ele nece$are memorrii $au tran$miterii ace$tui me$a6) Deoarece, de regul,

pentru memorarea $au tran$miterea unui me$a6 $e folo$e&te, e%entual (ntro form intermediar, reprezentareaprin $im'oluri 'inare a ace$tuia, &i pentru c cele mai multe metode de compre$ie folo$e$c metode de codare'inar 'inar, putem $pune c o'iecti%ul compre$iei con$t (n reducerea numrului de $im'oluri 'inare nece$arpentru reprezentarea me$a6ului)Dup cum &irul $im'olurilor emi$e de $ur$ e$te (mprit, pentru codare, (n $u'&iruri de aceea&i lungime $au de

lungime %aria'il, &i dup lungimea, con$tant $au %aria'il, a cu%intelor de cod, codurile de compre$ie $ecla$ific (n 'loc 'loc, 'loc %aria'il, %aria'il 'loc &i %aria'il %aria'il, 'loc 'loc indic4nd aceea&i lungimepentru $u'&irurile $ur$ei &i cu%inte de cod de lungime fix, iar %aria'il %aria'il core$punz4nd unor lungimi%aria'ile ale $u'&irurilor &i ale cu%intelor de cod)!lgoritmii de compre$ie fr pierderi $unt re%er$i'ili, prin decompre$ie o'in4ndu$e me$a6ul original (ntocmai)!lgoritmii de compre$ie cu pierderi au ca rezultat diferene relati% mici (ntre me$a6ul rezultat prin decompre$ie&i cel original &i $unt utilizai (n compre$ia imaginilor &i a me$a6elor %ideo &i audio).odarea S5annon -ano &i codarea huffman $tatic,

1*. !., $u'ni%elul >!. a%4nd (n$a ofunctionalitate $pecifica mediului de tran$mi$iuneDin cauza limitarilor pri%ind ni%elul fizic "acoperire radio#, retelele fara fir care tre'uie $a acopere di$tantegeografice rezona'ile pot fi compu$e din 'locuri de 'aza) locul de 'aza e$te numit $etul $er%iciului de 'aza"SS#)

1) Securitatea in retele de calculatoare)

Importanta a$pectelor de $ecuritate (n retelele de calculatoare a cre$cut odat cu extinderea prelucrrilorelectronice de date $i a tran$miterii ace$tora prin intermediul retelelor) n cazul operrii a$upra unor informatiiconfidentiale, e$te important ca a%anta6ele de parta6are $i comunicare adu$e de retelele de calculatoare $ fie$u$tinute de facilitti de $ecuritate $u'$tantiale) !ce$t a$pect e$te e$ential (n conditiile (n care retelele de

calculatoare au a6un$ $ fie folo$ite inclu$i% pentru realizarea de operatiuni 'ancare, cumprturi $au plata unortaxe)

n urma implementrii unor mecani$me de $ecuritate (ntro retea de calculatoare, informatiile nu %or putea fiacce$ate $au interceptate de per$oane neautorizate "curioa$e $au, e%entual, c5iar ru intentionate# $i $e %a(mpiedica fal$ificarea informatiilor tran$mi$e $au utilizarea clande$tin a anumitor $er%icii de$tinate unorcategorii $pecifice de utilizatori ai retelelor)

Pro'lemele de a$igurare a $ecurittii retelelor pot fi grupate (n urmtoarele domenii interdependente:

confidentialiatea $e refer la a$igurarea acce$ului la informatie doar pentru utilizatorii autorizati $i

(mpiedicarea acce$ului pentru per$oanele neautorizateC integritatea$e refer la a$igurarea con$i$tentei informatiilor "(n cazul tran$miterii unui me$a6 prin retea,

integritatea $e refer la protectia (mpotri%a unor tentati%e de fal$ificare a me$a6ului#C

31


32/32

autentificareaa$igur determinarea identittii per$oanei cu care $e comunic "a$pect foarte important (ncazul $c5im'ului de informatii confidentiale $au al unor me$a6e (n care identitatea tran$mittorului e$tee$ential#C

ne-repudierea$e refer la a$umarea re$pon$a'ilittii unor me$a6e $au comenzi, la autenticitatea lor)!ce$t a$pect e$te foarte important (n cazul contractelor realizate (ntre firme prin intermediul me$a6elorelectronice: de exemplu, un contract N comand cu o %aloare foarte mare nu tre'uie $ poat fi ulteriorrepudiat"# de una din prti "$ar putea $u$tine, (n mod fraudulo$, c (ntelegerea initial $e referea la o$um mult mai mic#)

32

Licenta informatica 2014. Programare, baze de date si retelistica.

Documents

Transcript of Licenta informatica 2014. Programare, baze de date si retelistica.