Lucrarea de faţă prezintă o aplicaţie practică în domeniul reunirii unor date care fac parte din acelaşi tip, interclasarea optimă a n şiruri de date memorate ordonat. În practică ne întâlnim deseori cu probleme în care dându-se nişte mai multe mulţimi ordonate trebuie să le interclasăm (aranjarea în ordine alfabetică a tuturor persoanelor culese pe judeţe pe întreaga ţară, şamd).
Programele de acest fel permit experimentarea unor situaţii, care ar fi dificil sau imposibil de realizat în practică. Simulările pot fi mai instructive atunci când sunt utilizate pentru a ilustra idei şi experimente explorate în prealabil prin alte mijloace - idei, teste, discuţii, chestionare, etc.
Aceste programe pot fi de asemenea utilizate în statistici ale unor date la anumite nivele, în realizarea unor reuniri care sunt prea costisitoare, complicate sau mari consumatoare de timp.
Acest tip de programe asigură simularea unor situaţii, modele, în care rezultatele finale să fie obţinute din deciziile proprii ale utilizatorului aplicându-se la orice nivel.
Ghidaţi după datele furnizate de program, se pot selecta anumite opţiuni sau alege anumite situaţii şi apoi se obţin rezultatele deciziilor.
O utilizare în creştere o au programele prin care se caută anumite statistici a diferitelor procese şi fenomene, păstrându-se interacţiunea dintre utilizator şi calculator.
Programul va rezolva interclasarea mai multor mulţimi ordonate într-un mod optim.
2. Arbori
2.1. Noţiuni introductive
Există mai multe moduri echivalente de definire a arborilor. Din punctul de vedere al teoriei grafurilor numim arbore un graf neorientat conex şi fără cicluri. Dacă graful este aciclic, dar nu este conex îl vom numi pădure.
De exemplu,
Fig. 1.
a. este arbore, b. este pădure, nefiind conex, iar c. nu este nici arbore, nici pădure, deoarece conţine cicluri.
Se numeşte gradul vârfului unui arbore numărul de muchii legate la acel nod.
Se numeşte înălţimea unui arbore binar numărul de nivele pe care-l are.
2.1.1. Proprietăţi ale arborilor
Teorema 1
Orice arbore cu n vârfuri are n-1 muchii.
Teorema 2
Fie G (V, U) un graf neorientat. Următoarele afirmaţii sunt echivalente:
1) G este arbore.
2) Oricare două vârfuri din G sunt unite printr-un lanţ simplu unic.
3) G este conex minimal (dacă suprimăm o muchie, graful obţinut este neconex).
4) G este conex şi are - V- -1 muchii.
5) G este aciclic şi are - V- -1 muchii.
6) G este aciclic maximal (dacă adăugăm o muchie, graful obţinut conţine cicluri).
Teorema 3
Numerele întregi 0 < d1 d2 dn (n 2) sunt gradele vârfurilor unui arbore dacă şi numai dacă d1d2 dn 2.n-2.
Demonstraţia acestei teoreme oferă şi o soluţie constructivă pentru obţinerea unui arbore cu secvenţa gradelor dată.
Vom reţine gradele vârfurilor într-un vector d de dimensiune n, ordonat crescător, cu suma componentelor egală cu 2.n-2.
Arborele va fi reprezentat prin matricea muchiilor, o matrice a cu două linii şi n-1 coloane, în care pentru fiecare muchie din arbore vom reţine extremităţile.
Spre deosebire de ideea din demonstraţie, pentru a conserva ordinea în vectorul d, la fiecare pas al algoritmului gradul care va fi decrementat va fi primul grad mai mare ca 1 şi nu ultimul.
De exemplu, pentru n 11 şi şirul gradelor:
1 2 3 4 5 6 7 8 9 10 11
1 1 1 1 1 1 1 2 3 4 4
obţinem arborele din figura 2.
Fig. 2
Acest procedeu sugerează o metodă foarte eficientă de reprezentare a arborilor. Dacă An este un arbore cu vârfurile x1, x2, , xn, suprimăm vârful terminal cu cel mai mic indice şi muchia incidentă cu acesta şi reţinem a1, vârful adiacent cu vârful terminal suprimat. Am obţinut astfel un subgraf cu n-2 muchii conex şi aciclic, deci un arbore An-1. Repetăm procedeul pentru arborele An-1, determinând un al doilea vârf, a2, adiacent cu vârful terminal de indice minim ce va fi eliminat din An-1 împreună cu muchia incidentă cu el ş.a.m.d., până când se obţine un arbore A2 cu două vârfuri adiacente.
B. Pătruţ, M. Miloşescu, Informatică (cls a IX-a), ed. Teora, 1999
Tudor Sorin, Turbo Pascal (cls a IX-a), ed. L&S Infomat
Internet
Turbo Pascal 6.0, Ghid de utilizare, ed.Microinformatica
Cornelia Ivaşc, Mona Prună, Bazele informaticii (cls a X-a) ed. Petrion, Bucureşti, 1995
Tudor Sorin, Informatică (cls a XI-a), ed. L&S Infomat
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.
