Organizarea si structurarea datelor
Datele = un mod de reprez a inf accesibil unui processor (om sau calc) cu care se poate opera pt a obtine noi informatii despre fenomene, procese sau obiecte.
Datele sunt grupate in 2 mari categorii :
datele elementare
= entitati indivizibile atat in raport cu inf pe care o reprezinta cat si in raport cu procesul care o prelucreaza.
Poate fi privita dpdv logic sau fizic.
Pctu de vedere logic = pctu de vedere al procesorului uman. E formata din 3 parti : identificatori, atribute si valori.
Identificatorul = simbol sau nume care se asociaza datei pt a o distinge de alte date si pt a o putea referi in procesul de prelucrare.
Atributele precizeaza proprietati datei si determina modu 222g67c l in care ea va fi tratata in procesul de prelucrare. Pot fi de tip, pot preciza modul de alocare al mem (static/dinamic), pot preciza reprezentarea interna, eventual valorile initiale.
Valorile pot fi nr intregi, reale, complexe, logice, siruri de caractere. Pot fi precizate prin enumerare sau printr-o proprietate comuna. Dc pe parc procesului de prel, data isi pastreaza valoare => constanta, altfel => variabila.
Dpdv fizic (al calc), modelul coresp datei = o zona de mem de o an lungime situata la o an adresa absoluta in care sunt memorate pe o an per de timp si intr-o an forma specifica, valorile datei.
Datele se prezinta sub forma unor multimi (colectii) care necesita o an organizare. Dc intre elem unei colectii pot fi identify si introducse relatii, se obtine cel de-al doilea tip de date, structurile.
structurile de date
Relatiile pot fi relatii de ordine intre elem colectiei sau relatii de descriere a mecanismelor de acces.
O structura de date = entitate de sine statatoare individualizata prin nume ale carei comp isi mentin propriet. Comp unei SD pot fi individualizate sau selectate fie prin nume, fie prin pozitia pe care o ocupa in cadrul structurii conform cu relatia de ordine specificata.
Cladificarea SD :
dupa modul de selectare a comp : SD cu acces direct sau acces secvential
dupa suportul fizic in care sunt stocate : SD interne si externe(fisiere, BD)
dupa modul de alocare a memoriei :
SD statice, care isi pastreaza nr de componente pe parc prelucrarii
SD dinamice, care isi modifica structura pe parc prelucrarii
o cu cardinalitate finita (nr limitat de comp)
o cu cardinalitate infinita (nr de comp e nelimitat)
Asupra unei SD se pot efectua o multime de operatii cele mai uzuale fiind : creeare (memorarea str pe un support), actualizare (adaugare, modif, stergere), listare.
Alte operatii : ventilarea (desfacerea unei str in mai multe), fuzionarea (combinarea a 2/m multe str (ex. Interclasarea).
Tipurile de SD in memoria interna
sirul = o succesiune ordonata de elem. Lungimea lui e data de nr de elem. Tipul lui e dat de tipul elem.
Masivul = o colectie de date omogene cu cardinalitate finita. Are o str liniara si statica.
Inregistrarea = str de date eterogena, statica si cu cardinalitate finite. Comp ei sunt campuri si sunt indiv prin nume. Relatiile de ordine intre elem e ierarhica, ierarhia fiind precizata prin nr de nivel. Elem str pot fi date elementare sau SD. In memoria interna, reprezentarea articolului se face prin liniarizare intr-o zona compacta.
Liste = str dinamice liniare, recursive, cu comp omogene sau eterogene. Elem unei liste pot fi date elem/SD. Orice lista are doua capete numite baza si varf.
Toate elem unei liste mai putin baza si vf au det in mod unic elem precedent si eventual pe cel successor. Pot fi de 2 tipuri: liniare asimetrice (fiec elem I se cunoaste numai elem succ) si liniare simetrice (fiec elem I se cunoaste adr elem succ si al celui prec).
Parcurgerea listelor poate fi facuta in forma LIFO sai FIFO => listele pot fi de tip coada (FIFO) sau stiva (LIFO).
Arborii = str dinamice cu o rel de ordine ierarhica, elem str se numesc noduri sau
varfuri, referintele pleaca de la nodul tata la nodul fiu. In orice arbore exista un nod radacina care nu are tata si noduri frunze care nu au fii.
Arbori generali -> orice data poate sa aiba un nr nelimitat de fii
Arbori binari -> orice varf poate sa aiba maxim 2 descendenti
Arborii binari pot avea urmatoarele forme de reprezentare :
reprezentare standard
prin paranteze incluse
grafica
tata
Parcurgerea :
preordine (RSD)
inordine (SRD)
postordine (SDR)
- Structuri de date externe :
fisiere = colectie organizata de inregistrari. In functie de modalitatea de mem a inreg, exista m multe tipuri de metode de acc la fis.
Organizare secventiala => acc secvential
Organizare indexat secv => acc secv + direct
Organizare selectiva => acc direct, secv, dynamic
O categ speciala sunt fisierele inverse care se creeaza pe baza unor fis clasice prin inversarea rolului inreg cu cel al caract (campurilor). Se fol in cadrul org datelor in arhive sau cataloage de date in care se pune pb cautarii inreg carora le coresp o caract de o an valoare.
BD
Organizarea + structurarea datelor (continuare)
Factori care infl alegerea modului de org si str a datelor in cadrul act de dezvoltare soft
1.volumul datelor determina alegerea modului de stocare a datelor pe suport intern sau extern si implicit tipul de structura
2.operatiile de prelucrare si frecventa lor determina natura suportului de memorie, tipul de structura si modul de acces
3.indicele de activitate pe operatii este def ca un raport intre nr de comp a structurii utiliz intr-o operatie si nr de componente exploatate pt aceasta operatie. Acest fact infl tipul de acc, implicit suportul fizic
4.durata de viata a structurii. Dc se lucreaza in timp asupra datelor. Dc SD sunt temporare, nu cont modalitatea de stocare ci modul de org a datelor care sa permita un acc rapid la ele
5.utilizarea eficienta a spatiului de mem. Spatiul de mem conditioneaza stocarea datelor si implicit alegerea unor str de date (SD) in mem interna(MI)
6. complexitatea act de programe si lb de programare fol
7. asigurarea integritatii datelor
8. experienta programatorului
ALGORITMI
1)Notiuni generale privin alg
Algoritmul=sistem de reguli care, aplicat la o cls de pb de acelasi tip conduce de la o an inf initiala, la solutia finala cu ajutorul unor operatii succesiv ordonate si unic determinate. O inf initiala pt care un alg este aplicabil=inf admisibila. Totalitatea inf admisibile formeaza domeniul algoritmului. Alg poate fi definit: f:D->S
Obs! Nu orice metoda de calcul=alg. O met pt a fi alg tb sa indeplineasca 3 cond:
Compunerea si descompunerea alg
Compunerea se poate face prin:
-suprapunere - at cand alg f este compus din suprapunerea lui f1 peste f2: f=f1(f2), de ex min, max pe coloane
-succesiune - in care inf finala a lui f1 = inf initiala pt f2: f=f1*f2
-mixta
- o succ de suprapuneri
- o suprapunere de succ
Descompunerea se realiz prin spargerea unui alg intr-o combinatie de alg cu o str mai simpla numiti subalg.
Clasificarea alg
Dpdv al formei de reprezentare:
-alg liniari in care succ alg este liniara si nu se poate reveni la pasii anteriori
-alg cu ramificatii care includ struct alternativa si se det evolutia alg pe o ramura sau alta in fctie de rez unei conditii
-alg ciclici(iterativi) - pornind de la o val initiala a sol, imbunatatesc aceasta sol printr-un procedeu repetitiv
Dpdv al programarii:
-alg numerici - cu urm carac:
-maj datelor sunt numerice
-sunt org in siruri, liste, masive
-fol ca suport MI
-procesul de calcul este iterativ
-nr de operatii de calcul e mare
-pt programarea lor sunt fol lb procedurale
-alg de prelucrare - prezinta o pondere mare a datelor stocate pe suporti externi, org in fis sau BD. Specificul prel datelor impune o specializare a alg: alg pt creearea fis sau actualizarea lor. Deoarece prel datelor din fis se realiz la niv de inreg, alg vor avea str repetitive.
2. Tehnici de reprezentare a alg
Exista 2 mari categ:
2.1 repr grafica: scheme logice, diagrame arborescente, tabele de decizie
2.2 repr textuala: pseudocodul si reprez analitica
Obs!
-schema logica permite intelegerea mai clara a alg dar are dezav unui spatiu f mare ocupat si impos de a realiza o descompunere pe nivele a alg
-reprez analitica permite descrierea intr-un spatiu redus dar intelegerea semnif alg e f dificila
-diagrama arb are avant vizualizarii f clare a desc pe nivele a alg precum si a str fundam de control
-pseudocodul premite trecerea cu usurinta la lb de programare dar de asem spatiul ocupat este mare
2. diagr arb se parcurg de sus in jos si in cadrul aceluiasi niv de la st la dr. Exista 2 tipuri de diagr arborescente:
-tabourier(?)
-mills(asemanatoare cu prima numai k se elimina repr grafice: drept+romb
Pseudocodul poate fi in engleza sau in romana. El permite in plus si repr unor declaratii de datept care se poate utilize sintaxa unor anumite lb de programare.
|
