Arbori asociați expresiilor aritmetice

Previzualizare atestat:

Cuprins atestat:

1. Introducere 3
2. Arbori 4
2.1. Noţiuni introductive 4
2.1.1. Proprietăţi ale arborilor 4
2.1.2. Reprezentarea arborilor 6
2.2. Arbori binari 8
2.2. Arbori asociaţi expresiilor matematice 9
3. Aplicarea temei în informatică 15
3.1. Generalităţi 15
3.2. Noţiuni despre program 16
3.3. Resurse utilizate 17
4. Concluzii finale 19
5. Programul sursă 20
6. Bibliografie 26
7. Cuprins 27

Extras din atestat:

Lucrarea de faţă prezintă o aplicaţie practică în domeniul matematicii şi informaticii deoarece rolul oricărui compilator este de a transforma programele scrise într-un limbaj de programare oarecare într-un cod echivalent, scris în limbaj de asamblare sau în limbaj maşină. în această lucrare ne punem problema translatării expresiilor aritmetice dintr-un limbaj de programare cum ar fi de exemplu limbajul Pascal în limbaj de asamblare. În practică ne întâlnim deseori cu probleme de acest fel în programare.

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.

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.

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ă d1d2 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.

Bibliografie:

B. Pătruţ, M. Miloşescu, Informatică (cls a IX-a), ed. Teora, 1999

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

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

Descarcă atestat

Pentru a descărca acest document,
trebuie să te autentifici in contul tău.

Structură de fișiere:
  • Arbori asociati expresiilor aritmetice.doc
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.64KB (arhivat)
Publicat de:
Constantina Chirila
Nivel studiu:
Liceu
Tip document:
Atestat
Materie:
Informatică
Predat:
Grup Şcolar Bicaz
Profil:
Real
Profesorului:
Vancea Ioan
Sus!