bda_20040323

8/8/2019 bda_20040323

1/219

RODIAN SCNTEIE

BAZE DE DATE I ALGORITMIPENTRU CI DE COMUNICAIE

EDITURA SOCIETII ACADEMICE MATEI-TEIU BOTEZ

IAI - 2003S A T B

8/8/2019 bda_20040323

2/219

RODIAN SCNTEIE

BAZE DE DATE I ALGORITMIPENTRU

CI DE COMUNICAIE

Editura Societii Academice Matei-Teiu Botez

Iai - 2003

8/8/2019 bda_20040323

3/219

Refereni:prof.univ.dr.ing. Gabriela VIOREL

prof.univ.dr.ing. Cornel JIVA

Descrierea CIP a Bibliotecii Naionale a RomnieiSCNTEIE, RODIAN

Baze de date i algoritmi pentru ci de comunicaii / RodianScnteie. - Iai : Editura Societii Academice "Matei - Teiu Botez", 2003Bibliogr.ISBN 973-86343-3-4

625.7(075.8)

Copyright 2003, Toate drepturile asupra acestei ediii aparin autorului

8/8/2019 bda_20040323

4/219

i

CUPRINS

CAPITOLUL 1......................................................................................................................... 1INTRODUCERE N MANAGEMENTUL ASISTAT DE CALCULATOR..................... 1

1.1.INTRODUCERE ......................................................................................................... 11.2.OBIECTUL CURSULUI .............................................................................................. 3

1.3.DATE, INFORMAII, CUNOTINE........................................................................... 3Datele............................................................................................................. 4Informaia ......................................................................................................5Cunotinele................................................................................................... 8

1.4.VALOAREA DATELOR, INFORMAIILORI CUNOTINELOR................................ 9

1.5.UTILIZAREA DATELOR.......................................................................................... 11

1.6.BIBLIOGRAFIE ....................................................................................................... 12

CAPITOLUL 2.......................................................................................................................14STRUCTURI DE DATE ....................................................................................................... 14

2.1.ARTICOLUL ........................................................................................................... 14

2.2.TIPURI ABSTRACTE DE DATE ................................................................................ 15

2.3.SETUL..................................................................................................................... 17

2.4.TABLOUL ............................................................................................................... 182.5.LISTA NLNUIT ................................................................................................ 19

2.6.URNE ...................................................................................................................... 21

2.7.TABELE DE DISPERSIE (HASH TABLES)................................................................. 21

2.8.STIVE ..................................................................................................................... 22

2.9.COZI....................................................................................................................... 24

2.10.ARBORI ................................................................................................................ 27 Arbori binari................................................................................................ 28

Arbori binari de cutare ......................................................................................29Arbori rou-negru................................................................................................30

8/8/2019 bda_20040323

5/219

ii

Arbori b........................................................................................................ 30

2.11.BIBLIOGRAFIE ..................................................................................................... 31

CAPITOLUL 3.......................................................................................................................33BAZE DE DATE, PREZENTARE GENERAL............................................................... 33

3.1.ISTORICUL BAZELOR DE DATE.............................................................................. 33

3.1.BAZE DE DATE COMPUTERIZATE.......................................................................... 35Sisteme de prelucrare a fiierelor ............................................................... 36Sisteme integrate de procesarea datelor ..................................................... 36

3.2UTILIZAREA BAZELOR DE DATE ............................................................................ 38

3.3CARACTERISTICILE BAZELOR DE DATE ................................................................ 40Independena fizic...................................................................................... 40Independena logic.................................................................................... 41Utilizarea datelor de ctre neinformaticieni............................................... 41Eficacitatea accesului la date...................................................................... 41Administrarea centralizata datelor .......................................................... 41Eliminarea redundanei datelor .................................................................. 42Coerena datelor.......................................................................................... 42 Partajarea datelor ....................................................................................... 42Securitatea datelor ...................................................................................... 42

3.4MODELE DE BAZE DE DATE.................................................................................... 42Structura bazei de date................................................................................ 43

3.5.ARHITECTURA BAZELOR DE DATE ....................................................................... 44

3.6CONCEPTE AVANSATE DE BAZE DE DATE.............................................................. 46SGBD cu procesare paralel....................................................................... 46 Baze de date distribuite ............................................................................... 47Baze de date orientate pe obiect.................................................................. 48Tendine viitoare.......................................................................................... 51

3.7.AVANTAJE I DEZAVANTAJE................................................................................. 51Avantajele utilizrii bazelor de date ...................................................................51Dezavantajele utilizrii bazelor de date ..............................................................52

3.8. BIBLIOGRAFIE........................................................................................................ 52

CAPITOLUL 4.......................................................................................................................54MODELE DE DATE UTILIZATE......................................................................................54

4.1.DEFINIII ............................................................................................................... 54

4.2.MODELE DE DATE ................................................................................................. 55

Modelul entitate-relaie ............................................................................... 56Entitatea ..............................................................................................................56Atributele ............................................................................................................57

8/8/2019 bda_20040323

6/219

iii

Relaiile...............................................................................................................57 Diagrame entitate relaie.....................................................................................58 Atribute ale relaiei .............................................................................................59Reprezentarea atributelor....................................................................................60

4.3.DEZVOLTAREA BAZELOR DE DATE....................................................................... 61Nivele ale arhitecturii bazelor de date ........................................................ 61Modele de baze de date ............................................................................... 62

Modelul ierarhic..................................................................................................62Modelul reea ......................................................................................................63Modelul de date relaional ..................................................................................63Consideraii practice ...........................................................................................64

4.4.BIBLIOGRAFIE ....................................................................................................... 64

CAPITOLUL 5.......................................................................................................................66ALGEBRA RELAIONALI LIMBAJE DE BAZE DE DATE.................................. 66

5.1.ALGEBRA RELAIONAL ...................................................................................... 66

5.2.LIMBAJUL DE BAZE DE DATE SQL ....................................................................... 70

5.3.SQLLIMBAJ DE MANIPULARE A DATELOR....................................................... 71Comanda SELECT....................................................................................... 71

Sintaxa comenzii SELECT .................................................................................71Operatori n expresia logic de condiionare ......................................................73Ordonarea rezultatelor ........................................................................................74

Gruparea rezultatelor ..........................................................................................74Lucrul cu jonciuni..............................................................................................75 Jonciuni externe.................................................................................................76Utilizarea interogrilor imbricate........................................................................76

Operaii de asamblare................................................................................. 77Operatorul UNION .............................................................................................77Operatorul INTERSECT.....................................................................................78Operatorul EXCEPT...........................................................................................78

Adugarea de date ntr-o tabel.................................................................. 79Adugarea de linii prin valoare...........................................................................79Adugarea de linii obinute dintr-o interogare....................................................80

Modificarea datelor dintr-o tabel.............................................................. 81Eliminarea datelor dintr-o tabel............................................................... 81Funcii utilizate n interogri ...................................................................... 82

5.4.SQLLIMBAJ DE DEFINIRE A DATELOR.............................................................. 83Crearea tabelelor ........................................................................................83

Sintaxa comenzii CREATE TABLE ..................................................................83Crearea de tabele cu copierea datelor .................................................................84Tipuri de date n tabelele bazelor de date ...........................................................84Expresii de restricie ...........................................................................................86

Crearea unei viziuni .................................................................................... 88Creareai utilizarea indecilor................................................................... 89Modificarea tabelelori a bazei de date .....................................................89tergerea componentelor bazei de date...............................................................90

8/8/2019 bda_20040323

7/219

iv

tergerea datelor dintr-o tabel ...........................................................................90Redenumirea unei tabele.....................................................................................90Eliminarea unor coloane dintr-o tabel...............................................................90Adugarea unei coloane ntr-o tabel .................................................................91

Modificarea unei coloane....................................................................................915.5.SQLLIMBAJ DE CONTROL A DATELOR............................................................. 91

Atribuirea privilegiilor ................................................................................ 92 Retragerea privilegiilor............................................................................... 92Controlul tranzaciilor................................................................................. 93

5.6.BIBLIOGRAFIE ....................................................................................................... 94

CAPITOLUL 6.......................................................................................................................96BAZE DE DATE DIN MANAGEMENTUL INFRASTRUCTURII................................ 96

6.1.NECESARUL DE DATE ............................................................................................ 97Tipuri de date necesare ............................................................................... 97Necesarul de date la diferite niveluri de decizie ....................................... 100

6.2.LOCUL BAZELOR DE DATE N AGENIA DE ADMINISTRARE .............................. 101Paii de bazn dezvoltarea unei baze de date pentru ntreinerea

infrastructurii transporturilor ........................................................... 103

6.3.IMPLEMENTAREA BAZELOR DE DATE N TRANSPORTURI..................................105AND - Banca centralde date tehnice rutiere .......................................... 105

6.4.BIBLIOGRAFIE .....................................................................................................108

CAPITOLUL 7.....................................................................................................................109ALGORITMI N MANAGEMENTUL INFRASTRUCTURII ...................................... 109

7.1.NOIUNI FUNDAMENTALE................................................................................... 109

7.2.DESCRIEREA ALGORITMILOR............................................................................. 112Diagramele logice ..................................................................................... 112 Limbajul pseudocod................................................................................... 113

7.3.EFICIENA ALGORITMILOR................................................................................ 113Complexitatea algoritmilor ....................................................................... 113Structuri ciclice .........................................................................................114Recursivitatea............................................................................................ 115

7.4.ANALIZA COMPLEXITII ALGORITMILOR....................................................... 118Metode de analiz...................................................................................... 118Notaia asimptotic................................................................................... 119

Notaia (theta mare) ......................................................................................120Notaia O (O mare) ...........................................................................................120Notaia (Omega mare) ..................................................................................121Notaia o (o mic)...............................................................................................121Notaia (omega mic)......................................................................................121

8/8/2019 bda_20040323

8/219

v

Consideraii practice................................................................................. 121Exemple de calcul a complexitii............................................................. 123Clase de complexitate................................................................................ 124

Clasa P de complexitate....................................................................................124Clasa NP de complexitate.................................................................................124Clasa de probleme NP-complete.......................................................................125

7.5.TEHNICI DE PROIECTARE A ALGORITMILOR..................................................... 125Reducerea la probleme cunoscute............................................................. 125Abordarea egoist..................................................................................... 126Divide i cucerete..................................................................................... 126Programare dinamic............................................................................... 128

7.6.BIBLIOGRAFIE .....................................................................................................128

CAPITOLUL 8.....................................................................................................................130SORTAREA I CUTAREA.............................................................................................130

8.1.SORTARE..............................................................................................................130 Sortarea cu bule .................................................................................... 130Sortarea cu inserare.................................................................................. 132Sortarea cu selecie ................................................................................... 133Sortarea Shell ............................................................................................ 134Sortarea rapid(QuickSort)...................................................................... 136Sortarea cu combinare (merge sort) ......................................................... 138

Sortarea cu numrare (counting sort)....................................................... 139Sortarea radix............................................................................................ 140Sortarea cu grmezi (bucket sort)............................................................. 141

8.2.CUTAREA...........................................................................................................141 Cutarea datelor neordonate .................................................................... 141Cautare binar.......................................................................................... 142

8.3.BIBLIOGRAFIE .....................................................................................................143

CAPITOLUL 9.....................................................................................................................144GRAFURI I PROBLEME PE GRAF..............................................................................144

9.1.ELEMENTE DE TEORIA GRAFURILOR................................................................. 144Definiii ...................................................................................................... 144Gradul unui nod ........................................................................................146Definiii suplimentare................................................................................ 147

9.2.REPREZENTAREA GRAFURILOR......................................................................... 147Reprezentarea grafic............................................................................... 147Reprezentarea prin structuri de date......................................................... 151

9.3.ARBORI ................................................................................................................153 Arborele de acoperire................................................................................ 153Problema arborelui de acoperire minimal................................................ 154

8/8/2019 bda_20040323

9/219

vi

Algoritmul lui Prim pentru arborele minimal de acoperire ..............................154Algoritmul lui Kruskal......................................................................................155

9.4.PARCURGEREA GRAFURILOR.............................................................................157

9.5. PROBLEME DE ACOPERIRE PE REELE ............................................................... 157Podurile din Knigsberg ........................................................................... 157Fleurys Algorithm............................................................................................158

Problema potaului chinez....................................................................... 159Ciclu Hamiltonian ..................................................................................... 159Problema vnztorului ambulant.............................................................. 160

9.6.BIBLIOGRAFIE .....................................................................................................160

CAPITOLUL 10...................................................................................................................161PROBLEME DE MINIM I MAXIM PE REEA.......................................................... 161

10.1.INTRODUCERE ................................................................................................... 161

10.2.DRUMUL CEL MAI SCURT .................................................................................. 162Abordri ale problemei drumului cel mai scurt n ci de comunicaie ....163Algoritmul lui Dijkstra ............................................................................. 163 Algoritmul Bellman-Ford .......................................................................... 165

10.3.CELE MAI SCURTE KDRUMURI PE GRAF.......................................................... 166Introducere ................................................................................................ 166 Diferite metode de tratare ......................................................................... 168

Metoda Bock, Kantner, Haynes........................................................................168Metoda drumului cel mai scurt .........................................................................168Metoda lui Bellman i Kalaba ..........................................................................169

Algoritmi cu corecia etichetei (label-correcting)..................................... 169Forma de baz a algoritmului cu corecia etichetei ..........................................170Algoritm cu indicator de modificare (alteration flag AF)..............................170Algoritmul cu list de secvene (sequence list SL)........................................170Algoritmul cu dubl baleiere (double-sweep DS) .........................................171

Algoritmul cu fixarea etichetei (label-setting LS) .................................. 171

10.4.BIBLIOGRAFIE ...................................................................................................172

CAPITOLUL 11...................................................................................................................174ELEMENTE DE TEORIA COZILOR..............................................................................174

11.1.INTRODUCERE ................................................................................................... 174Notaia Kendall ......................................................................................... 175Procesul Poisson .......................................................................................177 Proprieti ale cozilor de ateptare........................................................... 179

Rata de ocupare.................................................................................................179Legea lui Little..................................................................................................179Proprietatea PASTA..........................................................................................180

11.2.ANALIZA COZILOR DE ATEPTARE................................................................... 181

8/8/2019 bda_20040323

10/219

vii

Modele de cozi de ateptare ...................................................................... 181Distribuia probabilitilor n stare stabil............................................... 182

11.3.COADA DE ATEPTARE (M/M/1) ....................................................................... 183

11.4.COADA DE ATEPTARE (M/M/C)....................................................................... 185Comparaie: un sistem cu doucozi (M/M/1) i o coad(M/M/2)...........187

11.5.COZI DE ATEPTARE CU CAPACITATE FINIT.................................................. 190Sisteme cu Cozi de ateptare (M/M/1/1) ................................................... 190Sisteme cu Cozi de ateptare (M/M/1/N)................................................... 191Caracteristici generale (M/M/c/N)............................................................ 193Cozi de ateptare (M/M/c/c)...................................................................... 194

11.6.COZILE DE ATEPTARE DE TIPUL (M/G/1) ....................................................... 195

11.7.ANALIZA COZILOR DE TIPUL (M/G/-/-/N) ........................................................ 198

11.8.COZI DE ATEPTARE CU PRIORITATE............................................................... 199Noiuni generale ........................................................................................ 199Cozi de ateptare cu proritate i ntrerupere ............................................200

11.9.REELE CU COZI DE ATEPTARE ...................................................................... 203

11.10.BIBLIOGRAFIE .................................................................................................204

8/8/2019 bda_20040323

11/219

viii

8/8/2019 bda_20040323

12/219

Scnteie Rodian Baze de date i algoritmi pentru ci de comunicaieISBN 973-86343-3-4 Editura Societii Academice Matei-Teiu BotezIai 2003

1

INTRODUCERE N MANAGEMENTULASISTAT DE CALCULATOR

1.1. INTRODUCERE

Infrastructura transporturilor reprezint o avuie public de o valoare imenscare trebuie transmis ntr-o stare mulumitoare ctre generaiile viitoare.Responsabilitatea factorilor de decizie este cu att mai mare cu ct de bunafuncionare a cilor de comunicaie depinde desfurarea normal a ntregii activitieconomice a rii, securitatea colectiv i, bineneles, sigurana participanilor latrafic.

Meninerea n stare de funcionare a infrastructurii depinde de modul n careadministratorul reelei efectueaz aciuni de intervenie. Pentru ca aceste aciuni s fieeficiente trebuie cunoscut n amnunt situaia calitativ i funcional a

componentelor. Pentru aceasta sunt necesare programe sistematice de inventariere,inspecie i evaluare. Scopul unor astfel de programe este de a stabili capacitateaactuali de perspectiv a infrastructurii de a face fa cerinelori scopului pentrucare a fost realizat.

Pe baza datelor existente se pot stabili strategii, programe, proiecte, soluiietc. Pentru realizarea lor sunt necesare fonduri substaniale. Suma valorii tuturor

proiectelor reprezint bugetul necesar pentru administrare. Practica a demonstrat cfondurile disponibile nu sunt niciodat suficiente nicieri n lume. Deoarece pentruaceleai fonduri concureaz mai multe proiecte, administratorii trebuie s aleag ntre

acestea. Ei trebuie s aleag ntre proiecte localizate n diverse situri dar i ntrevariante de proiect pentru aceeai locaie.

8/8/2019 bda_20040323

13/219

Capitolul 1 Introducere n managementul asistat de calculator

2

Decizia este dificil deoarece n cele mai multe cazuri este necesar prediciaefectelor diferitelor proiecte. n final trebuie selectate acele proiecte care aduc celemai mari beneficii. Prin beneficii trebui s nelegem nu numai valoarea bneasc ci i

de alt natur cum ar fi timp, consum de combustibil i piese de schimb etc. Studiulsistematic al mecanismelor matematice i logice de descriere a comportrii reelei iutilizatorilor, combinat cu dezvoltarea i utilizarea de algoritmi de predicie, poateajuta la eliminarea sau ntrzierea apariiei unor fenomene negative sau se potminimiza efectele lor nc nainte de apariie.

Simultan cu programele de ntreinere a infrastructurii trebuie iniiate i parcurse permanent programe de culegere de date pentru a putea cunoate starea ievoluia sistemului. O cunoatere mai profund implic utilizarea unui numr ct maimare de variabile de descriere. Numrul combinaiilor posibile devine astfel tot mai

mare i mintea uman poate tot mai greu s le cuprindi s le controleze integral. nconsecin, se impune o gndire sistemic i o abordare algoritmic. Complexitateatot mai mare a algoritmilor i dimensiunea crescnd a bazelor de date n care sestocheaz datele impun utilizarea calculatoarelor ca mijloc de lucru.

A fost conceput un cadrul general care include instrumente eficiente deevaluare, analiz economic, metode moderne de management. Termenul generic estemanagement asistat de calculator. Scopul unui astfel de mecanism este de a obine un

beneficiu maxim din utilizarea resurselor disponibile.

Managementul infrastructurii rutiere se confrunt cu o permanent obligaie

de a lua decizii. Aceste decizii se refer la alocarea de resurse, fie ele materiale,financiare, umane sau de echipament. n contextual actual de desfurare a proceseloralocarea este irevocabil.

Avem aici cteva noiuni ce necesit o explicaie. Irevocabil i decizie vor fireinui cu nelesul exprimat de R.A. Howard (1966) [12]:

... irevocabil n sensul c este imposibil sau extrem de costisitor s revenimla situaia care exista nainte de luarea deciziei. De aceea pentru scopul

propus decizie nu este hotrrea mintalde a urma o anumit linie de aciune

ci mai degrabducerea la ndeplinire a aciunii n conformitate cu hotrrea.

Procesul decizional este unul complex afectat frecvent de subiectivism i deincertitudine. O dat cu ptrunderea calculatorului electronic n majoritateadomeniilor vieii i managementul infrastructurii transporturilor rutiere trebuie s

beneficieze de avantajele utilizrii noilor tehnologii. Viteza de calcul deosebit,capacitatea de stocare a datelor i procedurile sofisticate de prelucrare permitspecialistului n inginerie civil s fac analize pertinente, multicriteriale care s

permit luarea de decizii corecte, documentate i argumentate.

8/8/2019 bda_20040323

14/219

Baze de date i algoritmi pentru ci de comunicaie

3

1.2. OBIECTUL CURSULUI

Acest curs va trata modul n care datele, informaiile i cunotinele pot fiobinute, stocate, regsite i prelucrate pentru a fi utilizate n managementul

infrastructurii transporturilor. Un accent deosebit se va pune pe metodele algoritmicede procesare cu scopul lurii deciziilor.

n capitolele urmtoare vom face doar o trecere n revisti o introducere nmijloacele moderne de analiz care transpuse n programe rulate pe calculatoarelemoderne pot oferi sprijin n procesul decizional al managementului infrastructuriitransporturilor. Considerm c este de o importan deosebit cunoaterea unornoiuni de baz privind:

Definirea, reprezentarea i gruparea datelor;

Achiziionarea, stocarea, regsirea i actualizarea datelor n baze de date;Prelucrarea datelor pe baza algoritmilor pentru obinerea de informaii;Aplicaii ale utilizrii bazelor de date i a algoritmilor n managementul

infrastructurii transporturilor;Modelarea i simularea n vederea prelucrrii datelor .

Studierea i aprofundarea acestor noiuni permite colaborarea facil cu ceilalispecialiti implicai n colective multidisciplinare care trateaz probleme de trafic,administrarea infrastructurii, sisteme informaionale integrate, dirijareatransporturilor, cercetri operaionale etc.

Acest curs NU se va ocupa de: limbaje de programare, arhitectur hardware,arhitectur software sau de problematica proiectrii i implementrii de programe decalcul. Acestea sunt doar tangenial abordate. Chiar dac nu este absolut necesar,cunoaterea unui limbaj de programare va facilita buna nelegere a noiunilor cu carene vom confrunta.

Acest curs NU se ocup de teoria i practica managementului cu aplicare nreeaua infrastructurii transportului rutier. Este totui strns interconectat, logica imetodele de raionament nsuite n cadrul acestui curs putnd fi aplicate nrezolvarea nevoilor managementului.

1.3. DATE, INFORMAII, CUNOTINE

n managementul infrastructurii rutiere, de altfel ca n multe alte domenii ica n viaa nsi, exist o activitate susinuti permanent de culegere, prelucrare,generare i transmitere a datelor, informaiilori cunotinelor.

La nivelul elementar putem spune urmtoarele:

Datele reprezint elemente simbolice de baz, crmida n construcia

cunoaterii;

8/8/2019 bda_20040323

15/219


4

Informaia reprezint datele prelucrate pentru a corespunde unui scop icare rspunde la ntrebrile: Cine? Ce? Unde? Cnd? Ct?

Cunotinele aplicaia datelor i informaiilor i rspunde la ntrebarea:

Cum? nelegerea apreciaz: De ce? nelepciunea apreciaz nelegerea?

Pentru a asigura o bun nelegere a conceptelor cuprinse n aceast lucrare ia desfurrii proceselor decizionale care decurg la diferitele niveluri alemanagementului infrastructurii transporturilor vom insista asupra noiunilor de date,informaii i cunotine. Celelalte depesc limitele pe care ni le-am impus i pot fiabordate ntr-o eventual lucrare de filozofia cunoaterii.

Informaiile i cunotinele se obin din prelucrarea datelor dup o schem

principial prezentat n figura urmtoare.

DATE

Prelucrare

INFORMAII

Aplicare Raionamente, experimente

CUNOTINE

Fig. 1 Procesul de transformare a datelor n cunotine [13]DATELE

Activitatea specialitilor din domeniu este caracterizat prin entiti facticeexprimate fie sub form de valori numerice, fie ca percepii i observaii numerice.Aceste entiti faptice independente i neevaluate, existente n numr mare, se numescdate [13].

Datele sunt o reprezentare a observaiilor, faptelor, conceptelor sauinstruciunilor ntr-o manier formal adaptat comunicrii, procesrii i interpretriide ctre om sau cu mijloace automatizate.

Date sunt toate acele valori numerice, caracter, sau de alt natur ce pot fipstrate separat sau grupate pentru a fi stocate, regsite, transmise, prelucrate etc.pentru a obine informaii.

8/8/2019 bda_20040323

16/219


5

Datele reprezint elementul de baz, materia prim, n procesul decizional.Pot avea diferite reprezentri i pot fi utilizabile sau nu. Ele pot exista n variateforme: numere, texte, mulimi, colecii etc., dar nu au semnificaie prin ele nsele.

Datele pot fi de patru tipuri (Floridi-1999 [10]):Date primare datele brute culese din teren, stocate n bazele de date sau

nscrise n cri, simple niruiri de valori care nu au suferit o prelucrareprealabil sau procesul de prelucrare a fost sumar. Sistemele de gestiune ainformaiilor sunt proiectate, n fapt, s manipuleze n special astfel de date.

Metadate sunt date secundare care ofer indicaii i descriere privind naturadatelor primare. Ajut sistemele de gestiune a bazelor de date s-indeplineasc sarcina prin descrierea proprietilor eseniale ale datelor

primare: localizare, format, actualizare, disponibilitate, drepturi de autor,

etc.Date operaionale sistemele de gestiune a bazelor de date monitorizeazi

colecteaz date privind propria funcionare, despre funcionarea sistemuluide calcul sau a performanelor implementrii. Aceste date pot asigurafeedback-ul, bucla de control, pentru identificarea i corectareaeventualelor erori de funcionare, a greelilor de proiectare sau aneconcordanelor cu necesitile utilizatorului;

Date derivate sunt acele date care pot fi deduse sau extrase din tipurileanterioare cnd acestea sunt utilizate pentru comparaii i analize

cantitative.Ca toate produsele societii umane datele au o un ciclu de via. Funcie de

durata lor de via datele pot fi:

Volatile: date care se obin, se prelucreaz, se utilizeaz n generareainformaiilor sau altor tipuri de date i a cror valoare nu se pstreaz, sau

Persistente: date stocate pe un suport de informaie cum ar fi hrtie, benzi perforate, mijloace magnetice (benzi, dischete, discuri), mijloace optice(compact discuri) etc.

INFORMAIADatele obinute n cadrul activitilor de proiectare, execuie, investigaie,

mentenan etc. constituie un material informaional brut care poate fi ordonat iprelucrat, avnd n vedere diferite obiective. n urma acestui proces de transformare adatelor, se obin informaii, care reprezint o interpretare a datelor n conformitate cuanumite situaii particulare sau cu nelegerea de ctre mintea uman n general.

Informaia este trecerea de la valoare la semnificaia care se ataeaz datei.nelesul care se ataeaz datelor depinde de locul, modul i scopul obinerii lor.Aceast semnificaie poate fi util dar acest lucru nu este obligatoriu.

8/8/2019 bda_20040323

17/219


6

Exist numeroase ncercri de a defini informaia. Fiecare este adevrat pedomenii limitate dar nici una nu este suficient de general. Studii de sintez fcute de-a lungul timpului nu au gsit la autorii citai o unitate de vedere (Braman 1989 [3],

Losee 1997 [15], Machlup 1983 [17], NATO 1974 [21], 1975 [22], 1983 [23],Schrader 1984 [25], Wellisch 1972 [32], Wersig i Neveling 1975 [33]). Dei pare onoiune simpl, conceptul de informaie este greu de cuprins ntr-o singur definiie i

poate fi explicat n moduri diferite funcie de categoria de cerine i deziderate careorienteaz teoria (Bar-Hillel i Carnap 1953 [1], Szaniawski 1984 [29], Shannon 1993[27]).

Dintre definiiile date i comentariile fcute putem reine:

Informaia reprezint datele care au fost procesate ntr-o form inteligibilpentru receptor (Davis i Olson 1985 [6]);

Datele reprezint materia prim care este procesati rafinat pentru a obineinformaia (Silveri Silver 1989 [28]);

Informaie egal date plus semnificaie (Checkland i Scholes 1990 [5]);Informaia este setul de date care a fost interpretat i neles de receptorul

mesajului (Lucey 1991 [16]);Datele trebuie interpretate sau prelucrate pentru a deveni informaie

(Warner 1996 [31]).

Noiunea de informaie este adesea utilizat intuitiv pentru a desemnaconinutul semantic non-mental, independent de utilizator, declarativ inclus n

implementri fizice precum baze de date, enciclopedii, locaii internet, programe tv.(Buckland 1991 [4]), care pot fi colectate, accesate sau prelucrate (Floridi 2002 [9]).

Se pune problema coninutului de adevr a informaiei. Care este situaiaentitilor care sunt privite drept informaie dar care n fapt nu conin valoare deadevr. Unii autori consider c informaia fals este pseudo-informaie(Floridi 2002 [9]). Ali autori sunt i mai categorici: informaia fals nu este un tipinferior de informaie; ea pur i simplu nu este informaie (Grice 1989 [11]);informaia fals sau informaia greit nu sunt tipuri de informaie(Dretske 1981 [8]).

Pornind de la cele subliniate mai sus i pe baza abordrii metodologicedezvoltate n logica situaional de Barwise i Perry 1983 [2]; Israel i Perry 1990[14]; Devlin 1991 [7], Luciano Floridi 2002 [9] d urmtoarea definiie semantic

pentru elementul individual de informaie:

este informaie obiectiv, semantic daci numai dac:

const ntr-un set D nevid de date ( d);datele din D sunt bine formatate;datele din D au semnificaie;datele d din D sunt veridice.

8/8/2019 bda_20040323

18/219


7

S-a utilizat termenul veridic n loc de adevrat cu sensul dereprezentnd sau transmind un coninut cu grad de adevr despre o situaie dat.Toate discuiile ulterioare i referirile la noiunea de informaie din aceast lucrare in

cont de aceast definiie.Informaia reprezint un element fundamental al activitii n orice

ntreprindere (Punescu et al. 1985 [24]). Ea prezint caracteristici similare celor pecare le au bunurile materiale: se produce, se stocheaz i se prelucreaz, este

perisabil n timp i are un pre de cost exprimat prin suma cheltuielilor ocazionatede obinerea, prelucrarea, memorarea sau difuzarea ei.

Indicii de calitate ai informaiei sunt: precizia, oportunitatea, completitudinea.

Precizia este definit prin cantitatea de informaie corect n raport cuntregul volum de informaii produs ntr-o anumit perioad de timp. Exist un raportdirect ntre acest indice de calitate i datele pe care se fundamenteaz informaiilerespective; pentru a crete valoarea acestui indice este necesar un volum mai mare dedate. n acelai timp ns obinerea informaiilor dintr-o cantitate mare de date impuneun volum mai mare de prelucrri care, n anumite situaii, poate veni n contradiciecu alt indice de calitate i anume cu oportunitatea.

Relevana sau actualitatea exprim faptul c o informaie este util ntr-unanumit moment, legat de desfurarea n timp a unor fenomene. Obinereainformaiilor, care privesc aceste fenomene, dup depirea unor etape ale evoluieilor reduc sau anuleaz valoarea acestor informaii. Corelat cu precizia apare oanumit contradicie, a crei soluionare depinde de natura i specificul activitii ncauz. Fenomenul de perisabilitate n timp a informaiilor se face simit prindiminuarea valorii informaiei n raport cu preul de obinere al acestora.

Completitudinea exprim necesitatea de a dispune de ct mai multe sau chiarde totalitatea informaiilor referitoare la un domeniu al activitii umane.

Obinerea informaiilor cu calitile menionate anterior este condiionat attde datele care le genereaz, ct i de mijloacele de prelucrare disponibile. Dac datelefolosite n procesul de obinere a informaiilor sunt inexacte, incomplete sau perimate,

informaiile care rezult sunt de valoare redus. Orice informaie trebuie s reduc dinincertitudine i s conduc la o mai bun nelegere a anumitor situaii sau fenomene.

Potrivit lui Zadeh (1997 [34]) informaiile disponibile se pot grupa n treicategorii:

Informaii factice care sunt numerice i bazate pe msurtori (ex. nlimeagrinzii este de 82,5 cm);

Informaii pseudo-numerice i bazate pe pseudo-msurtori (ex. ne ntlnimla trei);

Informaii bazate pe percepii care sunt n special aprecieri lingvistice (ex.cineva este cinstit i artos).

8/8/2019 bda_20040323

19/219


8

Aceste grupe difer ntre ele prin gradul de incertitudine.

Cnd exist incertitudine n aprecierea unui fenomen se poate definicantitatea de informaie care nltur aceast incertitudine. Informaia este n acest caz

numiti entropie i este reprezentat de numrul minim de ntrebri ce trebuie pus nmedie pentru a elimina incertitudinea.

Numeric, informaia poate fi estimat cantitativ funcie de probabilitateastrilor. Astfel, considernd un numr de stri: nxxx ,...,, 21 a cror probabilitate de

apariie este dat de ( )ixP , cantitatea de informaie se calculeaz cu formula:

( ) ( )=i

ii xPxPI 2log (1)

Logaritmul n baza doi implic msurarea informaiei n bii. Trebuie fcutconvenia ( ) 00log0 2 = , adic o stare cu probabilitatea 0 nu aduce informaie nsistem. Se poate observa c i existena unei stri cu probabilitate 1 conduce lainformaie 0.

CUNOTINELEInformaiile constituie baza raionamentelor, experimentrilor imaginate de

mintea uman, n scopul obinerii de noi cunotine.

Cunotinele reprezint esena ce rezid n spatele datelori informailor ntr-un domeniu de activitate. Cunotinele se obin prin cercetare tiinific i sunt unrezultat al sintezei procesrii datelor, informaiilori experienei.

Cunotinele acumulate faciliteaz aprecierea relaiilor dintre atributele unuielement, obiect, sistem, proces. Relaiile pot fi: procedurale, temporale, structurale,spaiale, logice, semantice, etc. Pe baza nelegerii relaiilor se poate lua o decizie ntr-un context dat.

Capacitatea de a lua decizii corecte este influenat de disponibilitatea datelori de aptitudinea de a anticipa consecinele aciunii. Capacitatea de a prezice ntr-unmod raional consecinele lucrrilor de intervenie constituie cunotina n domeniulmanagementului patrimoniului: cu ct este mai bogat corpul cunotinelor cu att estemai puternic instrumentul de administrare; cu ct mai mare numrul de opiuni cu attdecizia va avea o acuratee mai ridicat.

Analiza mai multor variante i managementul bazat pe cunotine estealegerea logic i totui prea puine persoane sau compartimente de planificareefectueaz analize explicite i complete. Chiari atunci cnd se consider mai multeopiuni, judecata este superficiali se oprete dup civa pai. Procesul decizionaleste prezentat n figura urmtoare.

8/8/2019 bda_20040323

20/219


9

Mediulfizic,social,politic,

ti

inific

Colectarea datelor

Performane

Soluii alternative

- Selecie -

Luarea deciziilor

Realizare

Analiz

Modele

Politici

Buget

Cunotine

Fig. 2 Procesul decizional (dup[26])Exist dou cauze pentru care oamenii nu iau decizii bazate pe cunotine: (1)

deficien n cunoatere i (2) comportament inadecvat.

1. pentru a utiliza cunotinele este necesar ca acestea s existe, s fiedisponibile i s fie incluse n instrucia personalului;

2. interese personale sau de grup, ineria sau indiferena pot perturba procesul dedecizie.Pornind de la cele prezentate mai sus este necesar cercetare tiinific pentru

a furniza administratorului metode extinse de colectare i interpretare a datelor,modele corespunztoare i algoritmi decizionali eficieni. Opiunile trebuieorganizate, clasificate i corect evaluate.

1.4. VALOAREA DATELOR, INFORMAIILOR I CUNOTINELOR

ntr-o lume cu magistrale informaionale datele, informaiile i cunotinele

au devenit mrfuri a cror comercializare cere sau se bazeaz pe metode de evaluare(Mowshowitz 1994 [20]).

8/8/2019 bda_20040323

21/219


10

n acest sens unii autori sunt extrem de categorici:

Pentru a fi informaie, informaia trebuie s aib o valoare, trebuie s poatfi utilizat n procesul decizional i s fie proiectat s conduc la o aciune... Ea

trebuie s reduc incertitudinea celor care o obin (Machlup i Mansfield 1983 [18],citat de Meadow i Yuan, 1997 [19]).

Exist mai multe raiuni privind studierea valorii datelor, informaiilor icunotinelor:

Motivaia educativ-instructiv studierea valorii poate conduce laidentificarea acelor entiti care trebuie luate n consideraie n procesul deadministraie fie prin utilizarea de ctre persoanele fizice implicate, fie

prin includerea lor n sisteme automate, informatizate de luare a deciziei.

Motivaia metodologic metodele de evaluare a valorii informaiei icunotinelor ajut la evaluarea sistemelor decizionale stabilite n urmacercetrii sau experienei practice. Selecia ntre diferite tipuri de sistemede inteligen artificial utilizate n rezolvarea problemelor se poate face

prin msurarea valorii cunotinelor utilizate, generate i manipulate.

Motivaia organizatoric se leag de funcionarea sistemelor complexe nmedii integrate, fie ele instituionale sau artificiale. Cnd mai multemodule/compartimente sunt n competiie pentru rezolvarea unei sarcini,evaluarea cunotinelor poate face identificare celui mai potrivit.

La nivelul actual, n administrarea infrastructurii transporturilor, dei nu serecunoate, s-a fcut prea puin pentru a stabili n mod tiinific detaliile legate decolectarea datelor anume: cantitatea, precizia, frecvena i chiar scopul. Cele maiimportante rmn ns timpul i costul i aici probabil s-a fcut cel mai puin. Pe dealt parte, industria transporturilor are o dinamic deosebit. Elementele de detaliucare trebuie msurate i prelucrate se schimb destul de des. Colectarea datelor devineastfel o int n continu micare.

Probabil c singurul domeniu care este reglementat din punctul de vedere alinformaiei i unde datele se culeg n continuu, dup proceduri bine stabilite, esteindustria transporturilor aeriene, dar i aici erorile, omisiunile, imprecizia afecteaz

procesul, rezultatele fiind uneori catastrofale.

n domeniul administrrii infrastructurii terestre s-au fcut pai prea puini i prea mici ca importan n vederea stabilirii raportului cost-beneficiu n ceea ceprivete colectarea datelor. Fiind un proces pe termen lung, factorii de decizie careinvestesc n programe de colectare a datelor investesc probabil n ceva din care ei nuobin nici un beneficiu. Majoritatea datelor rmn motenire succesorilor. De aceea,de multe ori, factorii politici nici nu iau n calcul proiecte care presupun culegerea dedate, urmrirea comportamentului n timp etc.

8/8/2019 bda_20040323

22/219


11

Pentru prelucrarea datelor i extragerea de informaii semnificative suntnecesare programe statistice performante. Acestea au n general preuri mari, dar

programele statistice de scar larg, care se preteaz la prelucrarea datelor din

infrastructura transporturilor, au costuri exorbitante. Fiind finanate de la buget,majoritatea ageniilor de administrare nu dispun de fondurile necesare pentruachiziionarea i meninerea unor asemenea programe. n plus, justificarea necesitiicheltuielilor pentru colectarea datelor ori nsi colectarea datelor este deficitar. Demulte ori nu se argumenteaz relevana datelor colectate i implicaiile cunoaterii.

Conceptul de relevan i msurarea acesteia sunt deosebit de delicate.Tate-Glass .a. (2000 [30]) compar msurarea relevanei cu statul la focul de tabr:

prea departe de flacra politic riti s fii tratat cu rceal, o poziie prea apropiatprezint riscul de a te arde din cauza cheltuielilor inutile.

Fundamental n rezolvarea problemei este anticiparea necesarului de date.Proiectele de statistic n infrastructura transporturilor, ca i n alte domenii, sunt 5%statistic i 95% logistic, ele fiind exerciii complexe de organizare i planificare.Elementul esenial este n mai mic msur competena n analize statistice ctabilitatea de a anticipa politicile i nevoile de planificare n viitor.

Cnd problemele de planificare sau de strategie ajung la MinisterulTransporturilor spre studiu este deja prea trziu s ncepem colectarea de date. n

planificri strategice trebuie s se lucreze cu acele date care sunt imediat disponibile.

Atunci cnd datele sunt cerute, conform Tate-Glass (2000 [30]), profesionitiiinformaiei pot rspunde n:

trei minute, cnd datele sunt pe raft;trei ore, dac trebuie cutat prin baza de date sau dosare;trei zile, cnd datele trebuie prelucrate;trei sptmni, dac trebuie fcut ceva programare sau modificat programul;trei luni, cnd este necesar prelucrarea complet a datelor;trei ani, dac este necesar colectarea de noi date.

De aceea sunt necesare programe proactive de colectare a datelor care s vin

n ntmpinarea viitoarelor analize de politici n transporturi.

1.5. UTILIZAREA DATELOR

Domeniul managementului infrastructurii rutiere este un domeniu intensiv nutilizarea datelor, informaiilor i cunotinelor. Date de teren, de structur, demateriale, de reea, informaii de evoluie, despre origine destinaie, cunotine desprecomportamentul agenilor umani implicai n trafic, al vehiculelori echipamentelor.Iat doar cteva elemente care trebuie tratate de administratorii infrastructurii

transporturilor.

8/8/2019 bda_20040323

23/219


12

Pentru a avea la dispoziie date, informaii i cunotine corecte i complete ntimp util administratorii infrastructurii transporturilor trebuie s aib n vedereurmtoarele aciuni:

Identificarea necesitilor de date;Crearea unui sistem de reprezentare a datelor;Implementarea i evaluarea unui sistem de colectare a datelor;Crearea i administrarea unui sistem de stocare i regsire a datelorImplementarea sistemului de transmitere a datelor;Identificarea algoritmilor utili n mecanismul decizional;Identificarea, implementarea i evaluarea unor proceduri de prelucrare a

datelor;Analiza rezultatelor n conformitate cu scopul urmrit

Evaluarea sistemului de management a datelor.Lucrarea de fa urmrete i trateaz aceti pai, sau cel puin ncearc s o

fac. Totodat se ncearc s se prezinte laolalt noiunile i metodele de procesarenecesare pentru dezvoltarea unui sistem integrat de management a infrastructurii.

1.6. BIBLIOGRAFIE

[1] Bar-Hillel Y., Carnap R.:An Outline of a Theory of Semantic Information, 1953, rep. inBar-Hillel 1964.

[2] Barwise J., Perry J.: Situations and Attitudes; MIT Press, Cambridge Mass. 1983.[3] Braman S.:Defining Information; Telecommunications Policy 13, pp.233-242., 1989.[4] Buckland M.: Information as Thing; Journal of the American Society of Information

Science (42.5), pp.351-360, 1991.[5] Checkland P. B., Scholes J.: Soft Systems Methodology in Action; John Wiley & Sons,

New York 1990.[6] Davis G. B., Olson M. H.: Management Information Systems: Conceptual Foundations,

Structure, and Development; 2nd ed., McGraw-Hill, New York 1985.[7] Devlin K.:Logic and Information; Cambridge University Press, Cambridge 1991.[8] Dretske F.:Knowledge and the Flow of Information; MIT Press, Cambridge Mass. 1981,

rep. Stanford: CSLI, 1999.[9] Floridi Luciano: Is Information Meaningful Data ?; Electronic Conference on

Foundations of Information Science (FIS 2002)[10] Floridi Luciano: Philosophy and Computing An Introduction; London New York:

Routledge, 1999.[11] Grice P.: Studies in the Way of Words; Harvard University Press, Cambridge Mass. 1989.[12] Howard R.A.:Decision Analysis: Applied Decision Theory; in Proceedings of the Fourth

International Conference on Operational Research, D. B. Hertz and J. Melese, eds.,Wiley, New York, 1966, pp. 55-71.

[13] Ionescu Constantin, Scnteie Rodian: Informational Flows in Bridge Engineering; inIoani A., Chira C., Manea D. (editors) Proceedings of the International Conference,

Constructions 2003, Volume 4 Road, Bridges and Railways, pp. 209-216,Argonaut&Napoca Star, Cluj-Napoca, Romania, May 2003.

8/8/2019 bda_20040323

24/219


13

[14] Israel D., Perry J.: What is Information?; in P. Hanson (ed.), Information, Language andCognition, pp.1-19, University of British Columbia Press, Vancouver 1990.

[15] Losee R. M: A Discipline Independent Definition of Information; Journal of theAmerican Society for Information Science, 48.3, 254-269, 1997.

[16] Lucey T.: Management Information Systems; 6th ed. DP Publications Ltd, London 1991.[17] Machlup F.: Semantic Quirks in Studies of Information; in Machlup, F. And Mansfield,

U. eds.. The Study of Information: Interdisciplinary Messages, pp. 641-671 JohnWiley, New York, 1983.

[18] Machlup Fritz, Mansfield Una: The Study of Information: Interdisciplinary Messages;John Wiley, New York, 1983.

[19] Meadow C. T., Yuan, W.: Measuring the impact of information: defining the concepts;Information processing and management. Vol. 33, no. 6, pp. 697-714, 1997.

[20] Mowshowitz A.:Information as a commodity: assessment of market value; In Yovits, M.C., editor, Advances in Computers, Vol. 38, pages 247316, London. Academic Press.,

1994.[21] NATO 1974, Advanced Study Institute in Information Science, Champion, 1972. Information Science: Search for Identity; ed. by A. Debons (New York: MarcelDekker).

[22] NATO 1975, Advanced Study Institute in Information Science, Aberystwyth, 1974.Perspectives in Information Science, ed. by A. Debons and W. J. Cameron. (Leiden:Noordhoff).

[23]NATO 1983, Advanced Study Institute in Information Science, Crete, 1978.InformationScience in Action: Systems Design, ed. by A. Debons and A. G. Larson. (Boston:Martinus Nijhoff).

[24] Punescu, F., Badea-Dinc, N., Stcu., E., Informatizarea societii: un fenomen

inevitabil?, Ed. iinifici Enciclopedic, Bucureti, 1985.[25] Schrader, A.:In Search of a Name: Information Science and its Conceptual Antecedents;

Library and Information Science Research 6, pp.227-271, 1984.[26] Scnteie Rodian: Decision Making Process in Highways Structures Management; in

Ioani A., Chira C., Manea D. (editors) Proceedings of the International Conference,Constructions 2003, Volume 4 Road, Bridges and Railways, pp. 287-294,Argonaut&Napoca Star, Cluj-Napoca, Romania, May 2003.

[27] Shannon, C. E.: Collected Papers; ed. N. J. A. Sloane & A. D. Wyner, Los Alamos, CA,IEEE Computer Society Press, 1993.

[28] Silver G. A., Silver M. L.: Systems Analysis and Design; Addison Wesley, Reading MA,

1989.[29] Szaniawski, K.: On Defining Information; 1984, rep. in Szaniawski 1998.[30] Tate-Glass Martha J., Bostum Rob, Witt Greg: Data, Data, DataWheres the Data?;

TRB Millennium Papers, National Research Council, Transportation ResearchBoard, Washington, D.C., USA, January 2000.

[31] Warner T.: Communication Skills for Information Systems; Pitman, London 1996.[32] Wellisch, H., From Information Science to Informatics; Journal of Librarianship 4,

pp.157-187, 1972.[33] Wersig G., Neveling U.: The Phenomena of Interest to Information Science; Information

Scientist 9, 127-140, 1975.[34] Zadeh LA: Toward a Theory of Fuzzy Information Granulation and its Centrality in

Human Reasoning and Fuzzy Logic; Fuzzy Sets and Systems, vol. 90, No.2, pp.111-127, 1997.

8/8/2019 bda_20040323

25/219


14

STRUCTURI DE DATE

Rezolvarea problemelor cu ajutorul calculatorului presupune analiza,gruparea i structurarea datelor pentru a obine eficien maxim. Utilizareastructurilor de date este impus pe de o parte de nelegerea facil a problemei i pe dealt parte de necesitatea implementrii practice a procedurilor de rezolvare a

problemei pe mainile fizice.Structurile de date reprezint o cale sistematic de organizare i accesare a

datelor [36].

Reprezentarea datelor i a structurilor de date depind n mare msur deconstrucia calculatoarelor fizice i de implementrile limbajelor de programare.Totui pe majoritatea calculatoarelor i n majoritatea limbajelor apar urmtoarelestructuri de date: setul, articole (nregistrarea), tablouri, liste, urne (buckets), stive,cozi, arbori i reele.

n prezenta lucrare suntem preocupai mai puin de reprezentarea efectiv adatelor n memorie sau de tipurile implicite oferite de limbajul de programare. Deaceea prima structur tratat este articolul sau nregistrarea. Aceasta este baza pentrutoate celelalte reprezentri de tipuri de date abstracte.

2.1. ARTICOLUL

Articolul sau nregistrarea este o structur neomogen reprezentnd reuniuneaunui numr fix de componente numite cmpuri care constituie logic o unitate.Cmpurile din structur sunt caracterizate prin tipul lor care poate fi unul primar,

oferit de limbajul de programare, sau unul complex, definit de ctre proiectant (deci larndul su un articol). Gruparea cmpurilor se face din considerente de procesare dar

8/8/2019 bda_20040323

26/219


15

n cele mai multe cazuri sunt grupate atribute comune ale unei entiti care trebuietratat. Lungimea total a articolului este dat de suma lungimilor cmpurilor

( =i

iLAL )( ) (vezi Fig. 3).

Articol A

Cmp_1 Tip_cmp_1 L1

Cmp_2 Tip_cmp_2 L2

Cmp_3 Tip_cmp_3 L3

Cmp_i Tip_cmp_i Li

Cmp_n Tip_cmp_n Ln

Fig. 3 Structura unui articolRegsirea cmpului se face cu ajutorul unui identificator asociat la definire.

Pentru regsirea unui cmp cnd exist mai multe articole se utilizeaz numelearticolului i al cmpului mpreun.

Implementrile moderne ale obiectelor pot genera articole cu structurvariabil. Chiar dac unele dintre variante au lungimi diferite, articolul n ansambluva avea lungimea celei mai lungi dintre variante i aceasta este cantitatea de memoriecare va fi rezervat de fiecare dat cnd se creeaz un nou articol.

2.2. TIPURI ABSTRACTE DE DATE

O categorie special de structur de date derivat din articol este obiectul. Unobiect, denumit n unele implementri recente clas, ncapsuleaz ntr-o structurunic att datele ct i un set de proceduri i funcii care efectueaz prelucrarea de

baz a datelor respective. Astfel de proceduri, ataate n momentul definirii, eliminambiguitatea i ofer sigurana c prelucrarea i rezultatele obinute se refer strict la

setul de date coninut de obiect.Procedurile definite n interiorul obiectului ajut proiectantul s nu se mai

gndeasc la procesul complicat de referire a cmpurilor i regsire a datelor careapare cnd acestea sunt cutate din exterior. Modalitile efective de definire aobiectelori a procedurilori funciilor ataate depind de limbajul de programare ales.Definirea unor noi obiecte se poate face pe baza unora deja existente. Noile obiectemotenesc structura de date i proprietile de la cele anterioare. Ele pot defini noielemente sau le pot modifica pe cele anterioare.

ncapsularea componentelor i motenirea permit un anumit grad deabstractizare a datelor (a abstractiza cu sensul de a distila un sistem complicat pn

8/8/2019 bda_20040323

27/219

Capitolul 2 Structuri de date

16

la conceptele sale fundamentale). Aceasta implic identificarea componentelor idescrierea funcionalitii lor. Datele sunt organizate modulari exist posibilitatea cadetaliile interne de implementare s fie ascunse utilizatorilor, iar comunicarea s se

fac numai prin acea parte a datelori funciilor care sunt declarate publice. Se obineastfel un grad ridicat de libertate pentru analiti i programatori.

Aplicnd paradigma abstractizrii la proiectarea structurilor de date obinemtipuri abstracte de date - TAD.

Tipul abstract de date este un model matematic prin care se definesc tipurilede date ce pot fi stocate ntr-o structuri metodele disponibile s proceseze datele.Se definete deci o interfa. Interfaa este un contract prin care ni se garanteazdisponibilitatea unor elemente, fr s ni se ofere detalii privind implementareaintern [36].

Tip Abstract de Date = Interfa + Implementare (2)

Interfaa definete proprietile logice ale TAD i n special profilul sausemntura operaiilor sale.

Implementarea definete reprezentarea structurii de date i algoritmii deimplementare a operaiilor.

Un TAD este realizat printr-un pachet, cel mai adesea un pachet generic.Particularizrile se fac prin definirea de descendeni care preiau (motenesc)

caracteristicile tipului iniial.Specificaiile pachetului sunt reprezentate de interfa. Structura de date este

declarat ca o zon privat. Operaiile sunt declarate sub forma unor subprograme ceau cel puin un parametru.

Partea privat a specificaiilor i a corpului pachetului reprezintimplementarea TAD. Tot aici este inclusi reprezentarea structurii de date.

Exemple de tipuri de operatori [48]:

Constructori crearea i iniializarea unui obiect.Selectori furnizeaz informaii despre starea obiectului.Modificatori altereaz starea unui obiect.Destructor distruge obiectul.Iteratori (engl. iterators; franc. parcoureurs, itrateurs) acceseaz toate

prile unui obiect compus i aplic o anumit aciune fiecruia dintre ele.

Studiu de cazUn exemplu de limbaj de programare ce permite declararea i lucrul cu tipuri

abstracte de date este i dialectul de Pascal al mediului de programare Delphi

dezvoltat de Borland.

8/8/2019 bda_20040323

28/219


17

typeTNewObject = class(TOldObject)private{ Private declarations }

protected{ Protected declarations }

public{ Public declarations }

end;

Fig. 4 Declararea claselor n Delphi PascalUn membru (element) privat (engl.private) este invizibil n afara unitii de

programare sau modulului n care clasa a fost declarat. Prin plasarea declaraiilor

claselor legate ntre ele n acelai modul putei s oferii claselor acces una laresursele alteia fr ca elementele respective s fie vzute din afar de alte clase sauproceduri.

Un membru protejat (engl.protected) este vizibil n modulul n care clasa afost declarat i n oricare clas descendent, indiferent de modulul n care aceastaapare. Se intenioneaz ca aceste elemente s fie caracteristici generale pentru toidescendenii.

Un membru public este vizibil oriunde clasa este vizibili poate fi referit.

Un membru publicat (engl. published) are aceeai vizibilitate ca oricemembru public. Diferena const n faptul c pentru aceste elemente se genereazinformaii suplimentare pe timpul rulrii (RTTI runtime type information). Prinaceasta se pot asocia metode specifice cu proprieti specifice (de ex. proceduri detratarea evenimentelor cu evenimente particulare).

2.3. SETUL

Setul sau mulimea reprezint o colecie finit de elemente{ }nmmmM ,,, 21 K= . Deoarece, prin definiie, este finit, setul poate fi imaginat ca un

vector. Deoarece componena sa este aprioric definiti cunoscut, reprezentarea cavector de tipul ( )nmmm ,,, 21 K nu ar aduce informaii relevante. Este mult maiimportant s reprezentm un sub-set Sce poate fi definit pe mulimea iniial.

Pentru aceasta vom defini o funcie de apartenen }1,0{: MA , astfel:

( )

==

Sm

SmmAa

i

iii cnd

cnd

,0

,1 (3)

Acum sub-setul poate fi reprezentat prin vectorul valorilor funciei deapartenen ( )nS aaav ,,, 21 K= .

8/8/2019 bda_20040323

29/219


18

Operaiile ce trebuie s fie create pe un sub-set sunt:

Inserare, pentru a introduce un element n sub-set [Insert(e,S)eS];

Eliminare, care scoate elementul din sub-set [Suppress(e,S)eS];Aparine, funcie care face cunoscut apartenena unui element la sub-set;

Vid, indic faptul c sub-setul nu conine nici-un element;

Alte operaii ce se pot defini sunt: complementul, reuniunea, intersecia, diferena,

diferena simetric.

2.4. TABLOUL

Tabloul reprezint, n esen, o mulime de date de acelai tip care segrupeaz n poziii succesive n aa fel nct s poat fi regsite prin utilizarea unorindici de poziie.

Astfel aplicaia:

{ } { } { } Mnnnf k ,,2,1,,2,1,,2,1: 21LLLL

(4)care ataeaz fiecrui k-uplu de indici ( )kiii ,,, 21 L un element

Mmkiii,,, 21 L definete un tablou k-dimensional. Pentru cazul particular 1=k se

obine un vector. Reprezentarea fizic a tablourilor se face prin rezervarea de locaiisuccesive ntr-o zon contigu de memorie.

Identificarea unui anumit element din tablou se face prin numele tabloului isetul de indici corespunztori elementului. Aa cum spuneam la nceput tabloul seregsete ca o structur omogeni oricare dintre operaiile definite se aplic oricrui

element din tablou. Pe astfel de structuri se pot lesne aplica proceduri repetitive.Implementrile moderne ale tablourilor permit definirea unor seturi de indici care nu

pornesc obligatoriu de la 1 sau 0, lucru ce d mai mult flexibilitate n programare.

Elementele din tablou pot fi de tip simplu oferite de ctre limbajul deprogramare (ntregi, reali, iruri de caractere etc.) dari tipuri complexe definite dectre utilizator (ex. articole, obiecte etc.).

n principiu, lungimea unui tablou este fixi deci numrul de elemente esteconstant. n general, pentru a simula un numr variabil de elemente se contorizeaz

ntr-o variabil extern numrul de elemente ocupate sau se utilizeaz tablouri depointeri pentru care se aloc ulterior articole sau obiecte.

8/8/2019 bda_20040323

30/219


19

2.5. LISTA NLNUIT

Lista este o structur de date care are lungime variabil. n multe cazuri, nu se poate cunoate din momentul proiectrii programului care va fi numrul exact al

elementelor utilizate n calcul.Alocarea unui anumit spaiu fixat n faza de programare poate conduce la

dou situaii neplcute: fie se aloc spaiu insuficient i problema rmne nerezolvat,fie se aloc prea mult spaiu care rmne neutilizat i se consum inutil din resurselecalculatorului blocnd celelalte programe. Soluia propus a fost de a aloca dinamicmemorie pe msur ce nevoia o impune. n structura articolelor, pe lng informaiautil, se pstreaz referine ctre alte articole similare care pot fi create pe msur ce

programul este rulat. Se creeaz astfel o nlnuire care are o lungime variabil,programul utiliznd atta memorie ct este necesar.

Date de calcul Referine(date de legtur)

Fig. 5 Structura unui obiect dintr-o listnlnuirea de articole similare care conin referine unul despre altul pstrnd

un singur nivel de legturi se numete list (Fig. 6).

DAT_1 REF_1 DAT_2 REF_2 DAT_N-1 REF_N-1 DAT_N NIL

BAZA

Fig. 6 nlnuirea n listLista este accesat din interiorul programului prin intermediul unei adrese de

baz (o referin, un pointer etc.), elementul din list care este referit fiind capul delist. Se observ c datele referin din ultimul element din list sunt vide (NIL),acesta fiind unul dintre indicatorii de terminare a nlnuirii.

Din punct de vedere matematic, lista reprezint o secven de zero sau maimulte elemente de un anumit tip dat. Numrul n de elemente ce se regsesc n listreprezintlungimea listei. Cnd lungimea este 0 adresa de baz este vid (NIL).

Elementele pot fi identificate prin poziia lor n list. Din considerente ce inde reprezentarea numerelor ntregi n formatul binar este uzual a se spune c primulelement ocup poziia 0.

Dac ultimul element conine o referin ctre capul de list avem o listcircular. nlnuirea poate fi simpl, dar se poate ca fiecare element s coninreferine att ctre succesor ct i ctre predecesor. n acest caz nlnuirea este dubl.

8/8/2019 bda_20040323

31/219

8/8/2019 bda_20040323

32/219


21

Mai jos prezentm cteva exemple de implementri de operaii pe liste.

Proc Inser( x : DataType, L: ListType )

x.Next

8/8/2019 bda_20040323

33/219


22

Prezentm n continuare un exemplu de tabel de dispersie cu dimensiunea 5.

200 25 10 -

211 1 61

2 -2

26 -

3 -

94 54 -

Fig. 10Tabelde dispersieCazul cel mai defavorabil este dat de situarea tuturor elementelor ntr-osingur list nlnuit.

Un asemenea caz este dat sau evitat de forma funciei de repartiie. Dacfuncia de repartiie este uniform atunci lista iniial se subdivide n priaproximativ egale. Pentru aceasta se utilizeaz diverse tipuri de funcii:

Restul mpririi la M (operaia modulo M). Cheia considerat pentru fiecareelement se mparte la dimensiunea tabelei. Restul rezultat se utilizeaz caindex pentru poziionarea n tabel.

Se alege M s fie numr prim. Se asigur o uniformitate mai bun.

O tabel de dispersie, ca structur de stocare a datelor are un constructor itrei metode:

Creare / Init creeaz tabela i iniializeaz cmpurile la valoarea implicit;Insereaz(M) / Insert(M) calculeaz indexul )(Mindexi = cu ajutorul

funciei de dispersie i introduce elementul n lista adresat de poziia i dintabel;

Caut(M) / Find(M) calculeaz indexul )(Mindexi = cu ajutorul funcieide dispersie i caut elementul n lista adresat de poziia i din tabel; dacnu este gsit se returneaz Nil sau se genereaz o eroare;

Elimin(M) / Remove(M) calculeaz indexul )(Mindexi = cu ajutorulfunciei de dispersie, caut elementul n lista adresat de poziia i dintabel i elimin obiectul; dac nu este gsit se returneaz Nil sau segenereaz o eroare;

2.8. STIVE

Stivele reprezint structuri de date care au o singur cale de acces att pentruintroducere ct i pentru extragere de date: vrful stivei. Pentru ele se aloc iniial o

8/8/2019 bda_20040323

34/219


23

zon static, fix a crei coninut este vid (numrul de elemente este 0). Pe msur cenoi date trebuie pstrate ele se depun n stiv numrul elementelor fiind incrementat(Fig. 11). Cnd se dorete utilizarea datelor salvate singura modalitate de acces

permis este scoaterea elementului din stiv (cu decrementarea numrului deelemente) (Fig. 12).

Element nou

a) b)

L

L+1

Fig. 11Stiva nainte i dupintroducerea unui element

Element ce se elimin

a) b)

L

L-1

Fig. 12Stiva nainte i dupextragerea unui element

Modul de lucru al acestor structuri este ultimul intrat primul ieitLIFO (lastin - first out). Pentru o corect funcionare, n general, se aloc un tablou cu elementede tipul cerut i o variabil n care se pstreaz un indicator de stiv. Valoarea 0 aindicatorului semnalizeaz stiva goal. Valoarea indicatorului egal cu lungimeastivei semnalizeaz stiva plin. Verificarea acestor dou stri cade n sarcina

programatorului nainte de a efectua extragerea i respectiv depunerea.La adugarea unui nou element valoarea indicatorului crete cu unu

( 1+LL ) n timp ce la scoaterea unui element valoarea indicatorului de stivdescrete cu unu ( 1LL ).

Pe o asemenea structur se pot defini urmtoarele operaii minimale:

Sterge(S) / Clear(S): elimin toate datele din stiv i aduce indicatorul npoziia iniial.

Adauga(x,S) / Push(S): introduce elementul x n vrful stivei. Indicatorul este

incrementat. Dac stiva este deja plin genereaz o eroare.

8/8/2019 bda_20040323

35/219


24

Extrage(S) / Pop(S): extrage elementul din vrful stivei i l ntoarce carezultat. Indicatorul este decrementat corespunztor. Dac stiva este goalgenereaz un mesaj i se returneaz elementul vid.

Varful(S) / Top(S): verific elementul din vrful stivei fr a-l ndeprta.EsteVida(S) / IsEmpty(S): verific dac stiva este goali ntoarce valoarealogic (boolean) corespunztoare.

O implementare facil a stivei pentru tipuri complexe de articole se poaterealiza prin utilizarea unei liste nlnuite. Descrierea n limbaj pseudocod se face nfigura urmtoare (Fig. 13).

DecType DataTypeAs Record......

EndRecordDecType LinkedRecordAsRecord

Data : DataTypeNext : ^LinkedRecord

EndRecord

Declare HeapAs LinkedRecordProc Push( x : DataType )

tmp

8/8/2019 bda_20040323

36/219


25

primul intrat primul ieit FIFO (first in - first out). Reprezentarea intuitiv amodului de lucru este prezentat n Fig. 14 i Fig. 15.

Element nou

a) b)

L

L+1

Fig. 14Coada nainte i dupintroducerea unui element


a) b)

L

L-1

Fig. 15Coada nainte i dupextragerea unui elementn fapt, pentru implementarea unei cozi se poate utiliza tot un tablou care se

aloc cu o lungime fix de n elemente i dou variabile care pstreaz doi indicatori:unul privind sfritul cozii (Ia) i unul pentru vrful cozii (Ie) (vezi Fig. 16).


Element ce se adaug

Ie

Ia

n

Fig. 16Implementarea practica cozilor

PresupunndIaiIe indici n tablou, utilizmIa pentru adugare iIe pentruextragere. Dup adugarea unui nou element se incrementeazIa ( 1+IaIa ).

8/8/2019 bda_20040323

37/219


26

DacIa depete dimensiunea tabloului Ia ia valoarea bazei tabloului (pentrusimplitate s presupunem 0). Cnd se extrage un element se incrementeaz Ie ( 1+IeIe ) i, n mod similar, dacIe depete dimensiunea tabloului atunci ia

valoare bazei tabloului. Dac IeIa = atunci coada este vid, dac( )( )nIaIe mod1+ atunci coada este plin. Este datoria programatorului s facverificarea nainte de fiecare extragere i adugare respectiv.

Pentru cozi se pot defini urmtoarele operaii minimale:

Sterge(Q) / Clear(Q): elimin toate datele din coadi aduce indicatorii Ia iIe n poziia iniial.

Adauga(x,Q) / Enqueue(x,Q): Introduce elementul x la sfritul cozii.Indicatorul Ia este incrementat. Cnd coada este deja plin genereaz o

eroare fr s mai adauge elementul.Extrage(Q) / Dequeue(Q): extrage elementul din vrful cozii i l ntoarce carezultat. Indicatorul Ie este incrementat corespunztor. Dac coada estegoal genereaz un mesaj i se returneaz elementul vid.

Varful(Q) / Top(Q): verific urmtorul element din coad fr a-l ndeprta.EsteVida(Q) / IsEmpty(Q): verific dac coada este goali ntoarce valoarea

logic (boolean) corespunztoare.EstePlina(Q) / IsFull(Q): verific dac coada este goali ntoarce valoarea

logic (boolean) corespunztoare.

Operaiile de mai sus pot fi simplu descrise utiliznd limbajul pseudocod.Prezentm mai jos cteva dintre funcii pentru implementarea cu ajutorul tabloului.

Declare QAs array of OTypeDeclare Ia, IeAs IntegerProc Enqueue(x)

Ia

8/8/2019 bda_20040323

38/219


27

Reprezentarea cozii prin liste nlnuite:

DecType DataTypeAs Record

......EndRecord

DecType LinkedRecordAsRecordData : DataTypeNext : ^LinkedRecord

EndRecord

DecType QueueAs RecordHead, Tail: ^LinkedRecord

EndRecord

Declare Q As ^QueueFunct IsEmpty( Q ) :

If Q = NilThen return TrueElse Return False

EndFunctProc enqueue(Q, x)

tmp new LinkedRecordtmp.data xtmp.next NilIf Q.Head = Nil

Then Q.Head tmpElse (Q.Tail).Next p

Q.Tail pEndProcFunct dequeue( Q )

If IsEmpty(Q) then Error

Tmp Q.HeadTmpX Tmp.DataQ.Head Tmp.NextIf Q.Head = Nil Then Q.Tail NilFree TmpReturn TmpX

EndFunctFig. 18Reprezentarea cozilor prin liste nlnuite

2.10. ARBORI

Considerm o mulime finit de elemente (fie ele articole sau obiecte) pe carele vom denumi noduri. Aceast mulime se va numi arbore dac :

exist un nod special denumit rdcin;celelalte noduri sunt grupate n submulimi care la rndul lor sunt arbori.

Elementele arborelui sunt nodurile i legturile care se stabilesc ntre acestea.

8/8/2019 bda_20040323

39/219


28

R=N0

N1

N1,1 N1,j1 ... N1,n1...

Ni

Ni,1 Ni,ji ... Ni,ni...

Nn

Nn,1 Nn,in ... Nn,nn...

Ni,ji,1 Ni,ji,kji ... Ni,ji,nji...

... ...

Fig. 19Arbore

Rdcina constituie nivelul 0 i are referiri ctre un numr de noduri careconstituie nivelul 1, fiecare dintre nodurile acestui nivel au referiri ctre nodurile unuial doilea i aa mai departe. Fiecare nod este direct subordonat doar unui singur altnod. Orice nod este printe pentru subordonaii si care, la rndul lor suntdescendenipentru acesta. Orice nod fr descendeni este nod terminalsaufrunz.

nlimea (sau adncimea) unui arbore este dat de numrul de niveluriierarhice prezente.

Structura de date trebuie deci s conin pe lng datele utile i referine ctretoi descendenii i eventual ctre printe.

Date de calcul REF 1 REF 2 ... REF nPrinte

Fig. 20Structura unui nod dintr-un arboreMai sus prezentm schematic structura unui nod al unui arbore. Referinele

ctre printe nu sunt obligatorii. Nu se fac referiri ctre noduri cuprinse n ali sub-arbori ai aceluiai arbore. Dac exist descendeni sau nu exist suficieni care scompleteze spaiul lsat pentru referine, locaiile excedentare se completeaz cu NIL(entitatea care identific lista vid). Dac referina PRINTE existi este egal cu

NIL avem de-a face cu rdcina.

ARBORI BINARIReprezint o categorie special de arbori. Fiecare dintre noduri are doar

maxim doi descendeni: un sub-arbore stnga i un sub-arbore dreapta. Poziia celordoi este foarte important spre deosebire de arborii normali la care ordinea fiilor nuconteazi era suficient s se cunoasc cine este descendentul cui.

Pentru arborii binari trebuie cunoscut att descendena ct i poziia corect.

Cei doi sub-arbori nu sunt interschimbabili.

8/8/2019 bda_20040323

40/219


29

Structura de date a unui arbore binar este prezent n figura urmtoare:

Date de calcul Stnga DreaptaPrinteFig. 21Structura unui nod dintr-un arbore binar

Dac unul sau ambii descendeni lipsesc locaia se completeaz cu NIL.

Arborii binari sunt foarte populari n implementarea mecanismelor de cutarea datelor ordonate.

Cteva definiii se impun n acest context:

Arbore strict binar un arbore binar n care fiecare nod care nu este frunzare ambii descendeni;

Arbore binar complet arbore n care toate frunzele sunt la acelai nivel;

Arbore binar de cutare arbore binar care nodurile sunt ordonate pentru afacilita operaia de cutare.

Arbori binari de cutare

Este un tip special de arbore binar n care datele sunt aranjate cu respectareaunor reguli. Presupunnd c valoarea unui nod oarecare dintr-un arbore binar decutare este m, urmtoarele proprieti sunt ntlnite [37]:

Toate valorile mai mici dect m sunt n stnga,Toate valorile mai mari dect m sunt n dreapta.

Spre exemplu, dac avem 7 numere ele vor fi aranjate ntr-un arbore binar decutare astfel:

4

2 6

1 3 5 7

Fig. 22Reprezentarea datelor ntr-un arbore binar de cutarenlimea arborelui din exemplul precedent este 3. se poate observa faptul c

dac vom cuta o valoare n arbore vom gsi dup maxim 3 pai.

Se poate observa c valorile sunt aezate n mod regulat n aa fel nct s seobin un echilibru. Aceste echilibru menine o eficien maxim n utilizarea

8/8/2019 bda_20040323

41/219


30

arborelui de cutare. Spre deosebire de exemplul de mai sus n figura urmtoare avemreprezentat un arbore dezechilibrat.

1

2

3

4

5

Fig. 23Reprezentarea datelor ntr-un arbore dezechilibratAcest arbore este binar de cutare, el respectnd toate regulile impuse. Din

nefericire toate valorile au fost depuse n descendenii de pe un singursens. Pentrudoar cinci valori s-a obinut o nlime a arborelui de cinci ceea ce face cutareaineficient.

Din aceste considerente s-a impus utilizarea altor tipuri de arbori.

Arbori rou-negru

Sunt arbori binari de cutare n care se dorete o balansare ct mai bun adatelor. Numele vine de la faptul c nodurile se coloreaz cu dou culori: rou inegru. Aceste culori sunt atribuite dup reguli care determin echilibrarea arborelui.

Arborii rou-negru au urmtoarele proprieti [37]:

Fiecare nod este colorat sau n negru sau n rou;Orice frunz este un nod NIL i se coloreaz n negru;Dac un nod este rou atunci ambii descendeni sunt negri;Orice cale simpl de la un nod la o frunz descendent conine acelai numr

de noduri negre.Numrul de noduri colorate n negru de pe o cale poart numele de

adncime neagr sau nlime neagr.

ARBORI BArborii B (Knuth 1998 [43], Cormen 1998 [37], Aho 1983 [35]) reprezint o

alt cale de implementare a unui mecanism de meninere echilibrat a arborilor decutare. El reprezint o garanie a faptului c arborele va rmne din construcie cu o

nlime mic. Acest tip de arbore se preteaz la implementarea dicionarelor.

8/8/2019 bda_20040323

42/219


31

Un arbore B de ordin m este un arbore poziional care are urmtoareleproprieti:

Toate nodurile au cel mult m descendeni;

Toate nodurile cu excepia rdcinii au cel puin m/2 descendeni;Un nod care are m descendeni notai cu D0, D1, ... , Dm-1 are i m-1 chei

notate cuK1, K2, ... , Km-1 cu proprietatea cK1

8/8/2019 bda_20040323

43/219


32

[44] Knuth, Donald. E.: Tratat de programarea calculatoarelor. Algoritmi fundamentali;Editura Tehnic, Bucureti, 1974.

[45] Knuth, Donald. E.: Tratat de programarea calculatoarelor. Sortare i cutare; EdituraTehnic, Bucureti, 1976.

[46] Microsoft: Microsoft Windows Architecture for Developers; Course Number 794A,Microsoft Press 1997.

[47] Shaffer Clifford A.:A Practical Introduction to Data Structures and Algorithm Analysis,Java Edition, Prentice Hall 1998.

[48] Strohmeier Alfred:Algorithms and Data Structures; http://lglwww.epfl.ch, Swiss FederalInstitute of Technology in Lausanne, Department of Computer Science, SoftwareEngineering Laboratory, March 2000.

[49] Vogel Andreas, Keith Duddy: Java Programming with CORBA; Second Edition, JohnWiley & Sons, New York 1998.

[50] Williams Peter M.:Data Structures; University of Sussex, UK, 2002.

8/8/2019 bda_20040323

44/219


33

BAZE DE DATE,PREZENTARE GENERAL

3.1. ISTORICUL BAZELOR DE DATE

Stocarea i procesarea datelor nu este o invenie i o caracteristic a ereimoderne. Din totdeauna omenirea a cutat s pstreze informaiile pentru aducereaminte sau pentru posteritate. Iniial pe scoara copacilori pe pereii peterilor apoi

pe tblie de lut, suluri de papirus, pergament, hrtie i acum pe computere. Stocareai pstrarea sistematic a datelor, catalogarea, ordonarea i regsirea lor cu scopul

prelucrrii i are originea n vechile biblioteci i arhive. Multe dintre principiilefundamentale ale bazelor de date au fost descoperite i nvate la acea vreme,ignorarea lor ducnd la repetarea inutil a unor greeli de proiectare i implementare.

Cnd calculatoarele electronice au devenit accesibile publicului s-a pus

problema utilizrii lor pentru stocarea de date. n anii 1960 s-au depus eforturi pentrua standardiza acest proces i au rezultat dou modele: modelul reea (CODASYL) imodelul ierarhic (IMS). Accesul la date se fcea nc ntr-un mod greoi prin operaiide nivel sczut. Adugarea unui nou cmp impunea modificarea schemei de accesdeoarece predominant era preocuparea pentru definirea nregistrrilori nu structurasistemului. Erau necesare cunotine de structur intern pentru scrierea programelor.

Cu toate aceste minusuri nceputul era fcut i procesul nu mai putea fi oprit.Astfel propunerea lui E.F. Codd din 1970 privind modelul relaional al bazelor dedate a venit firesc. El desprea n dou probleme distincte descriere

bda_20040323

Documents

Transcript of bda_20040323