Arbori asociati expresiilor aritmetice

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. Arbori asociati expresiilor matematice 9
3. Aplicarea temei in informatica 15
3.1. Generalitati 15
3.2. Notiuni despre program 16
3.3. Resurse utilizate 17
4. Concluzii finale 19
5. Programul sursa 20
6. Bibliografie 26
7. Cuprins 27

Extras din atestat:

Lucrarea de fata prezinta o aplicatie practica in domeniul matematicii si informaticii deoarece rolul oricarui compilator este de a transforma programele scrise intr-un limbaj de programare oarecare intr-un cod echivalent, scris in limbaj de asamblare sau in limbaj masina. in aceasta lucrare ne punem problema translatarii expresiilor aritmetice dintr-un limbaj de programare cum ar fi de exemplu limbajul Pascal in limbaj de asamblare. In practica ne intalnim deseori cu probleme de acest fel in programare.

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.

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.

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

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

George Daniel Mateescu, Pavel Florin Moraru, Informatica (cls XI), Ed. Niculescu

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):
27 pagini
Imagini extrase:
27 imagini
Nr cuvinte:
3 358 cuvinte
Nr caractere:
18 289 caractere
Marime:
58.64 KB (arhivat)
Nivel studiu:
Liceu
Tip document:
Atestat
Materie:
Informatica
Data publicare:
18.09.2017
Structură de fișiere:
  • Arbori asociati expresiilor aritmetice.doc
Predat:
Grup Şcolar Bicaz
Profil:
Real
Profesorului:
Vancea Ioan

Ai gasit ceva în neregulă cu acest document?

Te-ar putea interesa și:
1.1.ASPECTE GENERALE LEGATE DE TEMA LUCRARII . DOMENIUL (N CARE SE (NCADREAZA LUCRAREA (n...
<< Ideile, si daca sunt abstracte si daca nu, ca sa le poti manui, tebuie sa le ai ....
o Arbori Numim arbore un graf neorientat conex si fara cicluri. Aceasta nu este singurul mod in...
MICROBIOLOGIA PRODUSELOR ALIMENTARE Microbiologia produselor alimentare, stiinta microbiologica...
Cap 1 INTRODUCERE IN LIMBAJUL C 1.1 Scurt istoric 1.2 Forma unui program C 1.3 Compilarea unui...
Sus!