Arbori de selectie

Previzualizare atestat:

Cuprins atestat:

1. Introducere 3
2. Arbori 4
2.1. Notiuni introductive 4
2.1.1. Proprietati ale arborilor 4
2.1.2. Reprezentarea arborilor 6
2.2. Arbori binari 8
2.2.1. Proprietati ale arborilor binari 11
2.2.2. Parcurgerea arborilor binari 12
3. Aplicarea temei in informatica 14
3.1. Generalitati 14
3.2. Notiuni despre program 15
3.3. Resurse utilizate 16
4. Concluzii finale 18
5. Programul sursa 19
6. Bibliografie 23
7. Cuprins 24

Extras din atestat:

Lucrarea de fata prezinta o aplicatie practica in domeniul reunirii unor date care fac parte din acelasi tip, interclasarea optima a n siruri de date memorate ordonat. In practica ne intalnim deseori cu probleme in care dandu-se niste mai multe multimi ordonate trebuie sa le interclasam (aranjarea in ordine alfabetica a tuturor persoanelor culese pe judete pe intreaga tara, samd).

Programele de acest fel permit experimentarea unor situatii, care ar fi dificil sau imposibil de realizat in practica. Simularile pot fi mai instructive atunci cand sunt utilizate pentru a ilustra idei si experimente explorate in prealabil prin alte mijloace - idei, teste, discutii, chestionare, etc.

Aceste programe pot fi de asemenea utilizate in statistici ale unor date la anumite nivele, in realizarea unor reuniri care sunt prea costisitoare, complicate sau mari consumatoare de timp.

Acest tip de programe asigura simularea unor situatii, modele, in care rezultatele finale sa fie obtinute din deciziile proprii ale utilizatorului aplicandu-se la orice nivel.

Ghidati dupa datele furnizate de program, se pot selecta anumite optiuni sau alege anumite situatii si apoi se obtin rezultatele deciziilor.

O utilizare in crestere o au programele prin care se cauta anumite statistici a diferitelor procese si fenomene, pastrandu-se interactiunea dintre utilizator si calculator.

Programul va rezolva interclasarea mai multor multimi ordonate intr-un mod optim.

2. Arbori

2.1. Notiuni introductive

Exista mai multe moduri echivalente de definire a arborilor. Din punctul de vedere al teoriei grafurilor numim arbore un graf neorientat conex si fara cicluri. Daca graful este aciclic, dar nu este conex il vom numi padure.

De exemplu,

Fig. 1.

a. este arbore, b. este padure, nefiind conex, iar c. nu este nici arbore, nici padure, deoarece contine cicluri.

Se numeste gradul varfului unui arbore numarul de muchii legate la acel nod.

Se numeste inaltimea unui arbore binar numarul de nivele pe care-l are.

2.1.1. Proprietati ale arborilor

Teorema 1

Orice arbore cu n varfuri are n-1 muchii.

Teorema 2

Fie G ? (V, U) un graf neorientat. Urmatoarele afirmatii sunt echivalente:

1) G este arbore.

2) Oricare doua varfuri din G sunt unite printr-un lant simplu unic.

3) G este conex minimal (daca suprimam o muchie, graful obtinut este neconex).

4) G este conex si are - V- -1 muchii.

5) G este aciclic si are - V- -1 muchii.

6) G este aciclic maximal (daca adaugam o muchie, graful obtinut contine cicluri).

Teorema 3

Numerele intregi 0 < d1 ? d2 ? ? dn (n ? 2) sunt gradele varfurilor unui arbore daca si numai daca d1?d2? ?dn ? 2.n-2.

Demonstratia acestei teoreme ofera si o solutie constructiva pentru obtinerea unui arbore cu secventa gradelor data.

Vom retine gradele varfurilor intr-un vector d de dimensiune n, ordonat crescator, cu suma componentelor egala cu 2.n-2.

Arborele va fi reprezentat prin matricea muchiilor, o matrice a cu doua linii si n-1 coloane, in care pentru fiecare muchie din arbore vom retine extremitatile.

Spre deosebire de ideea din demonstratie, pentru a conserva ordinea in vectorul d, la fiecare pas al algoritmului gradul care va fi decrementat va fi primul grad mai mare ca 1 si nu ultimul.

De exemplu, pentru n ?11 si sirul gradelor:

1 2 3 4 5 6 7 8 9 10 11

1 1 1 1 1 1 1 2 3 4 4

obtinem arborele din figura 2.

Fig. 2

Acest procedeu sugereaza o metoda foarte eficienta de reprezentare a arborilor. Daca An este un arbore cu varfurile x1, x2, , xn, suprimam varful terminal cu cel mai mic indice si muchia incidenta cu acesta si retinem a1, varful adiacent cu varful terminal suprimat. Am obtinut astfel un subgraf cu n-2 muchii conex si aciclic, deci un arbore An-1. Repetam procedeul pentru arborele An-1, determinand un al doilea varf, a2, adiacent cu varful terminal de indice minim ce va fi eliminat din An-1 impreuna cu muchia incidenta cu el s.a.m.d., pana cand se obtine un arbore A2 cu doua varfuri adiacente.

Bibliografie:

B. Patrut, M. Milosescu, Informatica (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 Ivasc, Mona Pruna, Bazele informaticii (cls a X-a) ed. Petrion, Bucuresti, 1995

Tudor Sorin, Informatica (cls a XI-a), ed. L&S Infomat

Download atestat

Primești atestatul în câteva minute,
cu sau fără cont

Alte informații:
Tipuri fișiere:
doc
Diacritice:
Da
Nota:
9/10 (1 voturi)
Anul redactarii:
2004
Nr fișiere:
1 fisier
Pagini (total):
24 pagini
Imagini extrase:
24 imagini
Nr cuvinte:
3 348 cuvinte
Nr caractere:
17 395 caractere
Marime:
50.77 KB (arhivat)
Nivel studiu:
Liceu
Tip document:
Atestat
Materie:
Informatica
Data publicare:
18.09.2017
Structură de fișiere:
  • Arbori de selectie.doc
Predat:
Grup Şcolar Bicaz
Profil:
Real
Profesorului:
Vancea Ioan

Ai gasit ceva în neregulă cu acest document?

Te-ar putea interesa și:
Notiunea de arbore: Se numeste arbore un graf neorientat care este conex si nu contine cicluri....
Lucrarea de fata prezinta o aplicatie practica in domeniul constructiei arborilor partiali de...
Lucrarea de fata prezinta o aplicatie practica in domeniul matematicii si informaticii deoarece...
1.Analiza functionala, constructiva si tehnologica a produsului. Stabilirea principala a...
2.Definirea matricei de proprietati de materiale candidate si ierarhizarea acestora si aprecierea...
Sus!