Termenul “OOP” (“Object Oriented Programming”) desemnează disciplina programării obiectuale (orientate-obiect). Această disciplină care are la bază ideea unificării datelor cu modalităţile de prelucrare a acestora şi manevrează entităţi reprezentate sub formă de obiecte (obiect=date+cod de tratare a acestor date).

Aşa cum s-a subliniat în capitolul 1.3., rezolvarea unei probleme se poate face pe 3 direcţii:

q  Rezolvarea orientată pe algoritm (pe acţiune), în care organizarea datelor este neesenţială;

q  Rezolvarea orientată pe date, acţiunile fiind determinate doar de organizarea datelor;

q  Rezolvarea orientată obiect, care combină tendinţele primelor două abordări.

Programarea obiectuală oferă posibilităţi de modelare a obiectelor, a proprietăţilor şi a relaţiilor dintre ele, dar şi posibilitatea de a descompune o problemă în componentele sale (soft mai mentenabil, adaptabil, reciclabil). Câteva exemple de limbaje de programare orientată obiect: SIMULA(1965), SIMULA-2(1967), Smalltalk, C++, Java (în plus, Java poate fi considerat un limbaj de programare orientată eveniment).

Facilităţile oferite de programarea orientată obiect (conform lui Pascou) sunt:

1. abstractizarea datelor;
2. moştenirea;
3. încapsularea (ascunderea)  informaţiei;
4. legarea dinamică (“târzie”).

9.2.  ABSTRACTIZAREA DATELOR

Obiectele sunt componente software care modelează fenomene din lumea reală. În general, un fenomen implică tipuri diferite de obiecte. Obiectele care reprezintă aceeaşi idee sau concept sunt de acelaşi tip şi pot fi grupate în clase (concrete sau abstracte). Clasele implementează tipuri de date (aşa cum s-a subliniat în capitolul 2, un tip de date înseamnă o mulţime de valori pentru care s-a adoptatat un anumit mod de reprezentare şi o muţime de operatori care pot fi aplicaţi acestor valori), deci şi operatorii destinaţi manipulării acestora: Clasă = Date + Operaţii.

De exemplu, programatorul îşi poate defini tipul (clasa) matrice şi operatorii care pot fi aplicaţi matricilor (* pentru înmulţirea a două matrici, + pentru adunarea a două matrici, – pentru scăderea a două matrici, etc). Astfel, el poate folosi tipul matrice în mod similar unui tip predefinit:

matrice A, B;

matrice C=A+B;

Tipul unui obiect (şablon al obiectului) este o clasă. O clasă se caracterizează prin: numele clasei, atribute, funcţii şi relaţii cu alte clase.

Instanţa este un obiect dintr-o clasă (A, B, C sunt obiecte, instanţe ale clasei matrice) şi are proprietăţile definite de clasă. Pentru o clasă definită, se pot crea mai multe instanţe ale acesteia. Toate obiectele au o stare şi un comportament. Starea unui obiect se referă la elementele de date conţinute în obiect şi la valorile asociate acestora (datele membre). Comportamentul unui obiect este determinat de care acţiunile pe care obiectul poate să le execute (metodele).

Atributele specificate în definiţia unei clase descriu valoric proprietăţile obiectelor din clasă, sub diferite aspecte. Cele mai multe limbaje orientate obiect fac următoarea distincţie între atribute:

q  atribute ale clasei (au aceeaşi valoare pentru toate instanţele clasei);

q  atribute ale instanţei (variază de la o instanţă la alta, fiecare instanţă având propria copie a atributului).

În limbajul C++ atributele se numesc date membre. Toate datele membre sunt atribute instanţă. Atributele de clasă se pot obţine în cazul datelor membre statice (aceeaşi adresă de memorare pentru orice instanţă a clasei).

Metode (funcţii membre). La definirea unei clase se definesc şi metodele acesteia (numite şi funcţii membre). Fiecare obiect are acces la un set de funcţii care descriu operaţiile care pot fi executate asupra lui. Metodele pot fi folosite de instanţele clasei respective, dar şi de instanţele altor clase (prin mecanismul moştenirii).

Clasa conţine atât structurile de date necesare descrierii unui obiect, cât şi metodele care pot fi aplicate obiectului. Astfel, gradul de abstractizare este, mult mai ridicat, iar programele devin mult mai uşor de înţeles, depanat sau întreţinut.

La crearea unui obiect, alocarea memoriei se poate fi face static sau dinamic (cu ajutorul unor funcţii membre speciale, numite constructori). Eliberarea memoriei se realizează cu ajutorul unor funcţii membre speciale, numite destructori, în momentul încheierii existenţei obiectului respectiv.

9.3.  MOŞTENIREA

Moştenirea este o caracteristică a limbajelor de programare orientate obiect, care permite refolosirea codului şi extinderea funcţionalităţii claselor existente. Între două clase pot exista multe diferenţe, dar şi multe asemănări. Este bine ca informaţia comună unor clase să fie specificată o singură dată (conceptul de clasă/subclasă, superclasă/clasă în OOP). Mecanismul moştenirii permite crearea unei ierarhii de clase şi trecerea de la clasele generale la cele particulare. Procesul implică la început definirea clasei de bază care stabileşte calităţile comune ale tuturor obiectelor ce vor deriva din bază (ierarhic superioară)(figura 9.1.). Prin moştenire, un obiect poate prelua proprietăţile obiectelor din clasa de bază.

9.3.1.  MOŞTENIREA UNICĂ

În cazul moştenirii unice, fiecare clasă are doar o superclasă. Există două modalităţi de specializare a unei clase de bază:

q  introducerea de extra-atribute şi extra-metode în clasa derivată (particulare doar clasei derivate);

q  redefinirea membrilor în clase derivate (polimorfism).

9.3.2.  MOŞTENIREA MULTIPLĂ

În situaţia moştenirii multiple, o clasă are mai multe superclase. Astfel, moştenirea clasei va fi multiplă (rezultând o structură de reţea).

Moştenirea multiplă este utilă, dar poate crea ambiguităţi (când pentru acelaşi atribut se moştenesc valori diferite). Există mai multe strategii de rezolvare a conflictului (părintele cel mai apropiat, cel mai depărtat, etc.). Deasemenea, este posibilă o moştenire repetată, în care o clasă ajunge să moştenească de la aceeaşi clasă, pe drumuri diferite în reţea (vezi figura 9.3., în care clasa E moşteneşte de la aceeaşi clasă A, pe drumurile A-B-E, A-C-E) . Aşa cum vedea în capitolele următoare, în aceste situaţii, limbajul C++ oferă programatorului două strategii: 1) clasa E poate avea două copii ale lui A, una pentru fiecare drum; 2) clasa E are o singură copie, iar A este clasă virtuală de bază şi pentru C şi pentru B. Ideea moştenirii multiple poate duce la utilizarea unor clase pentru care nu există instanţe, care să ajute doar la organizarea structurii (reţelei) de moştenire. În plus, limbajul C++ permite un control puternic asupra atributelor şi metodelor care vor fi moştenite.

9.4.  ÎNCAPSULAREA (ASCUNDEREA) INFORMAŢIEI

Încapsularea (ascunderea) informaţiei reflectă faptul că atributele instanţă şi metodele unui obiect îl definesc doar pe acesta. Vom spune că metodele şi atributele unui obiect sunt “private”, încapsulate în obiect. Interfaţa cu obiectul relevă foarte puţin din ceea ce se petrece în interiorul lui. Obiectul deţine controlul asupra atributelor instanţă, care nu pot fi alterate de către alte obiecte. Excepţia de la această observaţie o reprezintă doar atributele de clasă care nu sunt încapsulate, fiind partajate între toate instanţele clasei. Această tehnică de “plasare” a valorilor în datele membre private ale obiectului, reprezintă un mecanism de ascundere a datelor.

În limbajul C++ încapsularea poate fi forţată prin controlul accesului, deoarece toate datele şi funcţiile membre sunt caracterizate printr-un nivel de acces (rezultând astfel o mare flexibilitate). Nivelul de acces la membrii unei clase poate fi (figura 9.4.):

În limbajul C++, nivelul de acces poate preciza şi tipul de moştenire (capitolul 12).

q  Publică, unde în clasa derivată nivelul de acces al membrilor este acelaşi ca în clasa de bază;

q  Privată, unde membrii protected şi public din clasa bază devin private în clasa derivată.

9.5.  LEGAREA DINAMICĂ (“TÂRZIE”)

Obiectele unei clase părinte trebuie cunoscute în momentul compilării. Efectul combinat al moştenirii poate determina ca o anumită metodă să fie specializată diferit (prin redefinire), pentru subclase diferite. Polimorfismul reprezintă comportamente diferite ale unei metode în raport cu tipul unui obiect. Selectarea unei metode redefinite poate fi realizată în faza de compilare (legarea iniţială), sau în momentul execuţiei (legare târzie). În limbajul C++, legarea dinamică se poate realiza prin implementarea de:

q  funcţii virtuale (pot fi redefinite polimorfic);

q  funcţii virtuale pure (doar declarate, nu definite).

9.6.  ALTE ASPECTE

q  Comunicarea între obiecte

În limbajele de programare orientate obiect, obiectele comunică între ele prin mesaje, ceea ce conduce la accentuarea conceptului de încapsulare. Un obiect poate “stimula” un altul să activeze (declanşeze) o metodă, trimiţându-i un mesaj. După primirea mesajului, metoda respectivă este apelată cu parametrii furnizaţi, asigurând comportarea corespunzătoare a obiectelor. Metodele sunt invocate prin trimiterea de mesaje.

În limbajul C++ funcţiile membre (metodele) sunt accesate în mod similar oricarei funcţii, cu deosebirea că este necesară specificarea obiectului căruia îi corespunde metoda.

q  Pseudovariabile

Limbajele de programare orientate obiect posedă două variabile (numite pseudo-variabile) care diferă de variabilele normale prin faptul că nu li se pot atribui valori în mod direct, de către programator. În general, pseudovariabilele sunt o formă scurtă pentru “obiectul curent ” şi pentru “clasa părinte a obiectului curent”. În limbajul C++ există doar una din aceste pseudovariabile, numită ”this” (pointer către obiectul curent).

q  Metaclasele

Metaclasele reprezintă “clase de clase”. O clasă este, de fapt, o instanţă a unei metaclase. Diferenţele dintre clase şi metaclase sunt:

q  Clasa defineşte caracteristici (atribute şi metode) ale instanţelor de acel tip. Metodele pot fi folosite doar de obiectele clasei, nu şi de însăşi clasa (restricţie).

q  Metaclasele furnizează un mijloc prin care variabilele clasă pot fi implementate: în unele limbaje OOP, variabilele clasă sunt instanţieri ale unei metaclase.

Limbajul C++ nu include explicit metaclasele, dar suportă variabilele clasă sub forma datelor statice. Aşa cum funcţiile membre obişnuite sunt încapsulate înăuntrul fiecarei instanţe, pentru o funcţie membru statică a unei clase, se foloseşte o singură copie, partajată de către toate instanţele clasei. O asemenea funcţie nu este asociată unei anumite instanţe.

q  Persistenţa

Persistenţa reprezintă timpul de viaţă al unui obiect (între crearea obiectului şi ştergerea sa). Instanţele unei clase au un timp de viaţă dat de execuţia unei metode sau a unui bloc, de crearea sau ştergerea specificată explicit în program sau de durata întregului program. Persistenţa obiectelor este importantă în special în aplicaţiile de baze de date.

q  Supraîncarcarea operatorilor.

Limbajul C++ furnizează modalităţi de supraîncarcare a operatorilor (overloading): acelaşi operator are semnificaţii diferite, care depind de numărul şi tipul argumentelor.

8.1 Noţiuni generale

Orice algoritm lucrează cu date (numere întregi, reale, şiruri de caractere etc.). Referitor la acestea, în informatică, s-au cristalizat anumite concepte fundamentale, pe care le vom prezenta în continuare.

Printr-un tip de dată  înţelegem o mulţime cu elemente numite valori.

Exemplu:{-32768, 32767, …….0,1,……..32767} este omulţime de numere întregi. Atunci cînd nu există posibilatea de confuzie, putem nota mulţimea de mai sus astfel: [-32768,32767]. Un element al acestei mulţimi este 7 (valoarea 7). În Turbo Pascal un astfel de tip se numeşte integer. Şi este predefinit (este cunoscut de limbaj, nu trebuie definit de programator).

Pe mulţimea valorilor unui tip se definesc operaţiile asociate tipului.

Exemplu: Pentru tipul integer se definesc operaţiile de adunare, scădere, înmulţire etc.

Pentru fiecare tip se defineşte modul în care se valorile sale.

Exemplu: Pentru tipul integer valorile se memorizează utilizînd codul complementar şi se folosesc 2 octeţi consecutivi.

Pentru a lucra cu date de un anumit tip se folosesc variabile.

O variabilă se caracterizează prin: tip (natura datelor şi modul de memorare), nume (prin care aceasta se adresează) şi adresă (număr de ordine al primului octet în care se reţin datele, memoria internă fiind privită ca o succesiune de octeţi numerotaţi).

Tipuri de date pot fi simple (mulţimile care alcătuiesc nu sunt rezultate ca produs cartezian a altor mulţimi) şi stucturate în caz contrar. Exemplu:tipul integer este simplu, iar tipul record este structurat.

Limbajele de programare evoluate utilizează din plin tipurile de date. Mai mult, unele din ele permit programului, folosind tipurile existente, să definească noi tipuri de date. Limbajul Turbo Pascal este un exemplu în acest sens.

Noţiunea de tip de date este strânsă legată de un anumit limbaj de programare. În situaţia în care se renunţă la această legătură, se ajunge la o altă noţiune mult utilizată şi anume cea de structură de date.

Exemplu: Mulţimea este o structură de date (după cum vom arăta). În limbajul Turbo Pascal există tipul mulţime (set). Alte limbaje (de exemplu C) nu cunosc acest tip. Aceasta nu înseamnă că în C nu vom putea lucra cu mulţimi. Sarcina noastră este să înţelegem structura de date numită mulţime şi să o implementăm în orice limbaj de programare dorim.

Un curs de algoritmi trebuie să fie independenţi de orice limbaj. Fapt că în aceasta lucrare algoritmii se implementează în Turbo Pascal nu înseamnă că ei pot fi folosiţi numai în acest limbaj. Din acest motiv, orice curs de algoritmi va utiliza noţiunea de structură de date.

Structurile de date se clasifică în două mari categorii:statice şi dinamice.

Criteriul de clasificare este dat de modul de alocare a memoriei interne.

Astfel, pentru structurile statice memoria se alocă la începutul execuţiei programului şi rămăne alocată pînă cînd se încheie execuţia acestuia. Pentru structurile dinamice se alocă memorie în timpul execuţiei programului, iar cînd nu mai este necesară, memoria se eliberează.Modalitatea prin care se poate realiza aceasta în Turbo Pascal va fi arătată chiar în acest capitol.

8.1.1 Structuri statice

Aceste structuri ne sunt deja binecunoscute. În acest capitol le vom prezenta în mod sistematic şi, pe cît posibil, formalizat.

1)  Tabloul

Fie Ani={1,2,….ni} mulţimea primelor ni numere naturale.

Fie M=An1 x An2  x…..x Ank   produsul cartezian a k astfel de mulţimi.

Se numeşte tablou o funcţie f:M→T, unde T este o mulţime oarecare.

Numărul k este dimensiunea tabloului. Dacă k=1 tabloul se mai numeşte şi vector. Vectorul are n1 componente. Dacă k=2 tabloul se mai numeşte şi matrice. Matricea are n1xn2 elemente.

Atenţie! Frecvent se confundă numărul componentelor cu dimensiunea tabloului.

De exemplu, despre un vector cu n componente se spune că este de dimensiune n (cînd, de fapt, toţi vectorii au dimensiunea 1).

Majoritatea limbajelor de programare evoluate au implementat tipul tablou (array în Turbo Pascal). Pentru a identifica elementele unui tablou se folosesc indici (aceştia sunt elemente ale produsului cartezian pe care este definită funcţia).

2)       Articolul

Fie A1, A2,….An n mulţimi finite. În general, natura elementelor acestor mulţimi poate fi diferită. De exemplu, A1 poate fi alcătuită din numere întregi, A2 poate fi alcătuită din caractere etc. Fie A=A1xA2x…xAn produsul cartezian  a celor n mulţimi. Un articol reţine un element al mulţimii A. Un cîmp reţine un element al mulţimii Ai. Majoritatea limbajelor de programare  evaluate  cunosc tipul structurat articol (record în Turbo Pascal). Oricare cîmp poate fi, la rîndul său, articol (record în record).

3)       Mulţimea

Fie A o mulţime finită. Ea poate fi privită ca o structură de date. Puţine dintre limbaje  (Turbo Pascal) admit chiar un tip de date numit mulţime (set). Însă şi aici numărul elementelor unei mulţimi nu poate fi mai mare decît 255 (avantajul este că sunt predefinite operaţiile cu mulţimi ). În ipoteza că programatorul doreşte să implementeze  algoritmi care lucrează cu mulţimi, indiferent de limbaj, se poate folosi vectorul caracteristic. Astfel , pentru o mulţime cu n elemente, orice submulţime a sa (v) va fi definită cu ajutorul unui vector cu n componente, în care fiecare componentă poate lua doar două valori 0 şi 1.

¥ i Є{1..n} avem v(i)=

În acest caz, este sarcina programatorului să stimuleze diversele operaţii cu mulţimi.

4)       Stiva alocată static

Structura de date numită stivă a fost prezentată şi este binecunoscută cititorului. Nu ne rămîne decît să precizăm faprul că, pînă acum, a fost impementată ca structură statică, cu ajutorul vectorilor . modul în care s-a realizat implementarea ne este clar, cu ajutorul unui vector (ST l-am numit) şi a unei variabile k (indică vîrful ei). Principalul dezavantaj al unei astfel de implementări este dat de faptul că, deşi ca structură de date nu are limitat numărul nivelelor (putem folosi oricîte), practice, numărul acestora nu poate fi mai mare decît numărul componentelor vectorului. Acest dezavantaj se reduce simţitor în cazul cînd în care stivă este implementată dinamic, însă, din cauza limitării memoriei interne, se menţine totuşi.

5)       Coada alocată static

Coada este acea structură de date în care toate înserările sunt făcute la unul din capetele cozii, iar toate ştergerile (în general, prelucrările) sunt făcute la celălalt capăt.

Este cu totul nerecomandabilă utilizarea vectorilor pentru stimularea cozii (alocarea statică). Facem această precizare deoarece, în această situaţie are loc un fenomen de migraţie a datelor de la dreapta la stînga în cadrul vectorului.

Să presupunem că stimulăm o coadă cu ajutorul unui vector cu zece componente, care reţin numere întregi. Presupunem de asemenea că niciodată în coadă nu vom mai avea mai  mult bde 4 elemente. Introducem în coadă numerele 1,2,3,4. pentru a avea unde să introducem şi alte completăm vectorul de la dreapta la stînga.

Dacă scoatem din coadă pe 1 şi introducem în coadă pe 5, coada va arăta astfel:

Scoatem din coadă pe 2 şi obţinem pe 6:

Se observă acest fenomen de migraţie a datelor, de la dreapta spre stînga.

O altă soluţie ar fi ca, după fiecare stocare de date din coadă, să deplasăm întregul şir de date cărte dreapta, însă în acest caz se consumă mult timp.

O soluţie mai bună de implementare a cozii este să folosim un vector pe care îl privim ca fiind “circular” (facem convenţia ca după ultima componentă să urmeze prima). Adresa componentei de început a cozii va fi reţinută de altă variabilă, iar adresa componentei de sfîrşit va fi reţinută de o altă variabilă. Un astfel de procedeu poate fi folosit, dar nu este recomandabil atît timp cît există alocarea dinamică a memoriei (aşa se lucra prin anii 70, când limbajele “la modă” Fortan şi Cobol nu putea aloca memoria dinamic).

Din cele prezentate nu rezultă în nici un fel la ce foloseşte această structură de date. Deşi are numeroase utilizări (rol fundamental în informatică) pentru moment nu putem da exemple (ne lipsesc condiţiile necesare). Vezi parcurgerea în lăţime a arborilor oarecare.

8.1.2. Alocarea dinamică a memoriei în Turbo Pascal

Din punct de vedere al unui programator, memoria calculatorului se prezintă ca o succesiune de octeţi, fiecare octet avînd o adresă binară bine stabilită. Aceşti octeţi sunt identificaţi prin numere cuprinse între 0 şi n-1. convenim să numim adresă numărul de ordine al unui octet. Un octet este format din 8 biţi. Fiecare bit poate memora fie cifra binară 1, fie cifra binară 0, diversele tipuri de date cunoscute pînă acum (INTEGER, REAL) ocupă 2 sau mai mulţi octeţi consecutive. Pentru fiecare tip de dată cunoscut există o anumită logică potrivit căreia se face memorarea efectivă a conţinutului. De exemplu, pentru tipul INTEGER memorarea se face în COD COMPLEMENTAR. Nu ne propunem să prezentăm modul de reprezintare a datelor. Ne mărginim numai să atragem atenţia că o variabilă folosită de noi în program are un nume (simbolic), o valoare şi o adresă la care o găsim memorată (adresa primului octet din cei p octeţi consecutive ocupaţi de variabilă). În general, în limbajele evaluate nu este necesar ca programatorul să cunoască adresa la care se găsesc variabilele cu care lucrează.

Se cunosc două forme de alocare a memoriei de către programator în cadrul limbajului PASCAL: statică şi dinamică.

• Utilizînd forma de alocare statică, variabilele se declară utilizînd cuvîntul cheie VAR la începutul programului.
• Utilizînd forma de alocare dinamică, în timpul rulării programului, în funcţie de necesităţi, se alocă memorie suplimentară sau se renunţă la ea.

Pentru alocarea dinamică utilizăm tipul de date referinţă. Se consideră secvenţa de program:

type  ref=^inr;

inr=record

nr:integer;

adrurm:ref

end;

var c:ref;

Aici variabila c este o variabilă de tip referinţă. Ea reţine adrese de înregistrări. La rîndul ei, o înregistrare are două cîmpuri: nr, care conţine un număr întreg (informaţia utilă) şi adrurm (adresa următoare), care conţine adresa unei alte înregistrări.

Procedura NEW (c) rezervă spaţiu (un număr de octeţi cosecutivi) pentru o înregistrare, adresa primului octet fiind depusă în variabila c. Presupunem că variabila c conţine adresa unei înregistrări.

Procedura DISPOSE (c) eliberează spaţiul de memorie afectat acelei înregistrări care avea adresa în c. Cuvîntul cheie NIL are semnificaţia ” nici o adresă”.

Observaţii:

1)    c se referă la adresa care se găseşte în variabila c;

2)    c^.nr se referă la cîmpul numeric al înregistrării care are adresa memorată în variabil c;

3)    c^.adrurm semnifică adresa de înregistrare care se găseşte memorată în cadrul înregistrării care are adresa c;

4)    c^.adrurm.nr  semnifică variabila nr care se găseşte în înregistrarea care care adresa plasată în cîmpul adrurm al înregistrării cu adresa c.

Observaţie foarte importantă: spaţiul necesar variabilelor alocate dinamic se rezervă într-o zonă de memorie, special destinată numită HEAP (pentru PC compatibile i.B.M.).

8.2 Structuri dinamice.

8.2.1 Listă liniară simplu înlănţuită

O listă liniară simplu înlănţuită este o structură de forma:

adr1                                                   adr2                                                                       adrn

Semnificaţia notaţiilor folosite este următoarea:

• adr1, adr2,…,adrn reprezintă adresele din memorie ale celor n înregistrări;
• in1, in2,…, inn reprezintă informaţiile utile din cele n înregistrări (altele decît cele de adresă pentru înregistrarea următoare ).

Denumirea “simplu înlănţuită”  provine din faptul că fiecare element  al listei conţine o singură adresă, şi anume adresa elementului următor din listă. Aici avem o excepţie pentru ultimul element, care are în cîmpul de adresă cuvîntul cheie  NIL (semnificînd “nici o adresă”). Operaţiile pe care le putem face în legătură cu această structură de date sunt următoarele:

1)    creare;

2)    listare;

3)    adăugare;

4)    ştergere;

În programul care urmează aceste operaţii sunt realizate de   procedurile cu acelaşi nume (facem precizarea că, în program, informaţiile utile sunt date de numere 1,2,…,n). Am recurs la această cale din dorinţa de a simplifica pe cît posibil prezentarea.

1) Creare

Se cere numărul n de înregistrări. Se creează o primă înregistrare avînd ca informaţie utilă numărul 1. Variabila b de tip referinţă reţine adresa primei înregistrări din listă. Pentru fiecare i cuprins între 2 şi n se adaugă cite o nouă înregistrare listei. Variabila d reţine adresa ultimei înregistrări deja create pentru a-i completa cîmpul de adresă. Se procedează astfel pentru că în momentul în care am creat o înregistrare nu se cunoaşte adresa înregistrării care urmează.

2) Listare

Am precizat faptul că b reţine adresa primei înregistrări. Pentru a nu deteriora această valoare, o vom memora în variabila c . Atît timp cît nu am ajuns  la sfîrşitul listei, tipărim informaţia utilă şi încărcăm  în c adresa înregistrării următoare.

3) Adăugare

Operaţia de adăugare a unui nou element la listă comportă cunoaşterea a două informaţii:

• Informaţia utilă a elementului (înregistrării) din listă după care urmează  să se facă adăugarea;
• Informaţia utilă a elmentului care urmează să fie adăugat.

Adăugarea propriu-zisă constă în următoarele:

• Poziţionarea pe înregistrarea  după care urmează să adăugăm noua înregistrare;
• Alocarea spaţiului pentru noua înregistrare;
• Completarea informaţiei utile pentru aceasta;
• Completarea adresei următoare a noii înregistrări, care va fi adresa următoare a înregistrării pe care suntem poziţionaţi;
• Cîmpul de adresă al înregistrării pe care suntem poziţionaţi va lua ca valoare adresa noii înregistrări.

Observaţie:

- Aşa cum este concepută procedura, nu se poate adăuga  o primă înregistrare listei. Propunem ca exerciţiu modificarea ei în acest sens.

4) Ştergerea

Pentru a şterge o înregistrare este necesar  să cunoaştem informaţia utilă

a acesteia. Vom proceda în mod diferit pentru situaţiile în care se şterge  prima înregistrare sau una diferită de prima.

În cazul în care ştergem prima înregistrare, efectuăm operaţiile:

• Se salvează în variabila c adresa primei înregistrări (cea care urmează a fi ştearsă);
• Variabila b (care reţine adresa primei înregistrări) va lua ca valoare adresa următoare primei înregistrări;
• Se eliberează spaţiul rezervat înregistrării şterse;

În situaţia în care ştergem o altă înregistrare decît prima, procedăm în felul următor:

• Se face poziţionarea pe înregistrarea care urmează a fi ştearsă;
• Cîmpul  de adresă al înregistrării precedente capătă valoarea cîmpului de adresă al înregistrării curente;
• Eliberăm spaţiul rezervat înregistrării curente.

program 11n;

type ref=^inr;

inr=record

nr:integer;

adrurm:ref

end;

var b,c,d:ref;

n,i: integer;

procedure creare;

begin

write (‘n=’); readln(n);

new ( c); c^.nr:=1;

b:=c; d:=c;

for i:=2 to n do

begin

new ( c);

c^.nr:=i;

d^.adrurm:=c;

d:=c

end;

procedure listare;

begin

c:=b;

while c< >nil do

begin

writeln( c^.nr);

c:=c^.adrurm

end

end;

procedure ştergere;

begin

write (‘i=’); readln(i);

if  i=1 then

begin

c:=b;

b:=b^.adrurm;

dispose (c)

end

else

begin

c:=b;

while  c^.nr< >i do

begin

d:=c;

c:=c^.adrurm

end;

d^.adrurm:=c^.adrurm;

dispose ( c)

end

end;

procedure adăugare;

begin

write(‘i=’); readln(i);

write(‘n=’); readln(n);

c:=b;

while c^.nr< >i do c:=c^.adrurm;

new (d );

d^.nr:=n;

d^.adrurm:=c^.adrurm;

c^.adrurm:=d

end;

begin

creare;

listare;

adăugare;

listare;

ştergere;

listare

end.

În continuare ne propunem să construim şi să tipărim o listă liniară simplu înlănţuită, utilizînd tehnici recursive.

Funcţia lista are sarcina de a construi lista liniară înlănţuită. La început se cere informaţia utilă. În situaţia în care aceasta este diferită de 0 (valoare care semnifică faptul  că nu mai avem de adăugat nici un element), se rezervă un spaţiu pentru noua înregistrare, se completează informaţia utilă, iar cîmpul adrurm va lua valoarea funcţiei  de tip lista care se autoapelează. În încheiere lista va lua valoarea c a cîmpului care reţine adresa noului element.

Este interesant să observăm că iniţial se creează lista simplu înlănţuită fără a completa cîmpul adresa, această completare urmînd să se facă la revenirea în procedură.

Să ne imaginăm că rulînd acest program dorim să creăm o listă cu două înregistrări care au informaţiile  utile 1 şi 2.

Rularea decurge astfel:

• Apelăm procedura;
• Citim valoarea lui n şi anume 1;
• Se alocă spaţiu pentru prima înregistrare;
• Completăm informaţia utilă;
• Pentru a completa adresa următoare înregistrării curente, se apelează din nou funcţia;
• Citim valoarea lui n şi anume 2;
• Alocăm spaţiu pentru a doua înregistrare;
• Completăm informaţia utilă cu 2;
• Se apelează din nou funcţia;
• Se citeşte 0;
• Funcţia ia valoarea NIL;
• Se revine din apel şi se continuă de acolo de unde am rămas;
• Cîmpul de adresă al celei de a doua înregistrări va lua valoarea NIL;
• Funcţia capătă valoarea adresei înregistrării 2,
• Se revine din apel;
• Cîmpul de adresă al primei înregistrări ia valoarea celei de-a doua înregistrări;
• Funcţia ia  valoarea adresei primei înregistrări;
• Se revine în programul principal.

Observăm că valoarea variabilei c a programului principal va fi după rulare adresa primei înregistrări.

Propunem ca exerciţiu construirea listei utilizînd o procedură recursivă. Putem defini recursiv lista astfel:

• O mulţime vidă de înregistrări este o listă;
• Dacă la o listă se adaugă o înregistrare, se obţine o listă.

Recursiv putem tipări informaţia utilă din listă în două moduri:

• În ordinea în care a fost creată;
• În ordinea inversă celei în care a fost creată.

Lăsăm pe seama cititorului analiza acestor două proceduri.

program 11r;

type ref=^inr;

inr=record

nr:integer;

adrurm:ref

end;

var n:integer;

c:ref;

function lista:ref;

var c:ref;

begin

write(‘n=’); readln(n);

if n< >0

then

begin

new(c);

c^.nr:=n;

c^.adrurm:=lista;

lista:=c;

end

else lista:nil

end;

procedure tipard(c:ref);

begin

if c< >nil

then

begin

writeln(c^.nr);

tipard (c^.adrurm)

end

end;

procedure tipari(c:ref);

begin

if c< > nil tfen

begin

tipari (c^.adrurm);

writeln(c^.nr)

end

end;

begin

c:=lista;

tipard©;

writeln(‘————’);

tipari©

end.

Aplicaţie (Sortare topologică)

Presupunem că dorim sortarea numerelor. 1, 2, ….., n, numere care se găsesc într-o ordine oarecare, alta decît naturală. Pentru a afla relaţia în care se găsesc numerele, introducem un număr finit de perechi (i,j). O astfel de pereche ne spune că, în relaţia de ordine considerată, i se află înaintea lui j.

Exemplu 1: n=3 şi citim perechile (3,1) şi (3,2). Numărul 3 se află înaintea lui1 şi 3 se află înaintea lui 2. Apar două soluţii posibile: 3,1,2 şi 3,2,1, întucît nu avem nici o informaţie asupra relaţiilor dintre 1şi 2. Tragem de aici concluzia că o astfel de problemă poate avea mai multe soluţii.

Exemplu 2: n=3 şi citim (1,2), (2,3), (3,1). În acest caz nu avem soluţie.di primele două relaţii rezultă că ordinea ar fi 1,2,3 iar a-3-a contrazice această ordine.

În concluzie, problema ar avea sau nu soluţie, iar dacă are poate fi sau nu unică.

Algoritmul pe care îl prezentăm în continuare furnizează o singură soluţie atunci cînd problema admite soluţii. În caz contrar specifică faptul că problema nu admite soluţie.

Vom exemplifica funcţionarea algoritmului pe exemplu următor: n=4 şi se citesc perechile (3,4), (4,2), (1,2), (3,1).

Pentru fiecare număr între 1 şi n trebuie să avem următoarele informaţii:

• Numărul predecesorilor săi;
• Succesorii săi;

Pentru aceasta folosi doi vectori:

• contor, vector care reţine numărul predecesorilor fiecărui k, cu k Є {1..n}.
• a, care reţine adresele de început ale listelor de succesori ai fiecărui element.

Pentru fiecare element există o listă simplu înlănţuită a succesorulor săi. Fiecare înregistrare din aceste liste conţine două elemente:

• succesorul;
• adresa următorului element din listă.

Iniţial, în dreptul fiecărui element în vectorul „contor” se trece 0, iar în vectorul „a” se trece NIL.

Citirea unei perechi (i,j) înseamnă efectuarea următoarelor operaţii:

• mărirea cu 1 a cîmpului contor (j) (j are un predecesor, şi anume pe i);
• adăugarea lui j la lista succesorului lui i.

Pentru exemplu nostru, lucrurile decurg astfel:

CONTOR

A

În continuare se procedează astfel:

• toate elementele au 0 în cîmpul lui contor se reţine într-un vector c;
• pentru fiecare element al vectorului c se procedează astfel:
  • se tipăreşte;
  • se marchează cu -1 cîmpul său de contor;
  • pentru toţi succesorii săi (aflaţi în lista succesorilor) se scade cu 1 din cîmpul contor (este normal, întrucît aceştia au un predecesor mai puţin).
  • Se reia algoritmul dacă nu este îndeplinită una din condiţiile următoare:

v   Au fost tipărite toate elementele, caz în care algoritmul se încheie cu succes;

v   Nu avem nici un element cu 0 în cîmpul contor, caz în care relaţiile au fost incoerente.

.

tipăresc 3, scad 1 din predecesorii lui 4 şi 1, cu -1 contorul lui 3;

Observaţie:

Algoritmul are mai multe aplicaţii, ca de exemplu:

• Ordonarea unor activităţi, atunci cînd ele sunt condiţionate una după alta;
• Ordonarea unor termeni care se cer explicaţi pentru a-i putea explica prin alţi deja prezentaţi.

Program stoop;

type ref=^inr;

inr=record

succ:integer;

urm:ref

end;

vector=array [1..100] of integer;

vectad=array [1..100]of ref;

var n, m, i, j, k:integer;

contor, c:vector;

a:vectad;

gasit:boolean;

procedure adaug  (i,j:integer);

var c,d:ref;

begin

contor [j]:=contor [j]+1;

c:=a[i];

new (d);

d^.urm:=nil;

d^.succ:=j;

if c=nil

then a[i]:=d

else

begin

while c^.urm< >nil do c:=c^.urm;

c^.urm:=d

end

end;

procedure actual (i:integer);

var c:ref;

begin

c:=a[i];

while c < >nil do

begin

contor [c^.succ]:=contor[c^.succ]-1;

c:=c^.urm

end

end;

begin

write (’n=’); readln(n);

for i:=1 to n do

begin

contor [i]:=0;

a[i]:=nil

end;

while i< >0 do

begin

write (’tastati i,j=’);

readln (i,j);

if i< >0 then adaug (i,j)

end;

m:=n;

repeat

k:=1;

gasit:false;

for i:=1 to n do if contor [i]=0

then

begin

gasit:=true;

m:=m-1;

c[k]:=1;

k:=k+1;

contor [i]:=-1

end;

for i:=1 to k-1 do

begin

actual (c[i]);

writeln (c[i]);

end;

until (not gasit) or (m=0);

if m=0

then writeln (’totul e ok’)

else writeln (’relatii contradictorii’)

end.

8.2.2 Lista liniară dublu înlănţuită

O listă dublu înlănţuită este o structură de date de forma:

adr1                                                           adr2                                                            adrn

Operaţiile pe care le putem face cu o listă dublu înlănţuită sunt următoarele:

1)    Creare;

2)    Adăugare la dreapta;

3)    Adăugare la stînga;

4)    Adăugare în interiorul listei;

5)    Ştergere din interiorul listei;

6)    Ştergere la sînga listei;

7)    Ştergere la dreapta listei;

8)    Listare de  la sînga la dreapta;

9)    Listare de la dreapta  la sînga;

1)    Creare

O listă dublu înlănţuită se creează cu o singură înregistrare. Pentru a ajunge la numărul de înregistrări dorit, utilizăm proceduri de adăugare la stînga sau la dreapta. În programul de faţă acest lucru este realizat de procedura creare. Această procedură realizează operaţiile următoare:

• Citirea informaţiei utile;
• Completarea înregistrării cu informaţia utilă;
• Completarea adreselor de legătură la stînga şi la dreapta cu NIL;
• Variabilele tip referinţă b şi s vor căpăta valoarea adresei acestei prime înregistrări (b semnfică adresa înregistrării cea de mai din stînga, s adresa ultimei înregistrări din dreapta).

2) Adăugarea la dreapta

Această operaţie este realizată de procedura addr. Pentru adăugarea unei înregistrări se realizează următoarele operaţii:

• Citirea informaţiei utile;
• Alocarea spaţiului pentru înregistrare;
• Completarea adresei la dreapta cu NIL;
• Completarea adresei din stînga şcu adresa celei mai din dreapta înregistrări (reţinute în variabila s);
• Modificare cîmpului de adresă la dreapta a înregistrării din s cu adresa noii înregistrări;
• s va lua valorile noi înregistrări, deoarece va fi cea mai din dreapta.

3)    Adăugarea la stînga

Această operaţie o propunem ca exerciţiu.

4)    Adăugare în interiorul listei

Această operaţie este realizată de procedura includ, care realizează următoarele operaţii:

ü Parcurge lista de la stînga la dreapta căutînd înregistarea cu informaţia utilă m, în dreapta căreia urmează să introducem noua înregisrare;

ü Citeşte informaţia utilă;

ü Alocă spaţiu pentru noua înregistrare;

ü Completează informaţia utilă;

ü Adresa stîngă a noii înregistrări ia valoarea adresei înregistrării de informaţie utilă m;

ü Adresa dreaptă a noii înregistrări ia valoarea adresei dreapta a înregistrării de informaţia utilă m;

ü Adresa dreaptă a înregistrării cu informaţia utilă m ia valoarea noii înregistrări;

Observaţie:

Propunem ca exerciţiu realizarea unei proceduri de adăugare în interiorul listei a unei înregistrări la dreapta înregistrării cu informaţia utilă m.

5)    Ştergere din interiorul listei

Această operaţie este realizată de procedura sterg. Operaţiile efectuate de această procedură următoarele:

ü Se parcurge lista de la stînga la dreapta pentru a ne poziţiona pe înregistrarea care urmează a fi ştearsă;

ü Cîmpul de adresă dreapta al înregistrării care o precede pe această şi va lua valoarea cîmpului de adresă dreapta al înregistrării care va fi ştearsă;

ü  Cîmpul de adresă stînga al înregistrării care urmează înregistrării care va fi ştearsă va lua valoarea cîmpului de adresă stînga al înregistrării pe care o ştergem;

ü Se eliberează spaţiul de memorie rezervat înregistrării care se şterge.

6)-7) Ştergere la sînga şi la dreapta  listei

Aceste două operaţii sunt propuse cititorului ca exerciţiu.

8) Listare de  la sînga la dreapta

Această operaţie este realizată de procedura listare, procedură care realizează următoarele operaţii:

v Porneşte din stînga listei;

v Atît timp cît nun s-a ajuns la capătul din dreapta al listei, se tipăreşte informaţia utilă şi se trece la înregistrarea următoare.

9)    Listare de la dreapta  la sînga

O propunem ca exerciţiu.

Program 1di;

type ref=^inr;

inr=record

as:ref;

nr:integer;

ad:ref

end;

var b,s,c:ref;

n,m,i:integer;

procedure creare (var b,s:ref);

begin

write (‘n=’); readln (n);

new (b); b^.nr:=n;

b^.as:=nil; b^.ad:=nil;

s:=b

end;

procedure addr (var s:ref);

var  d:ref;

begin

write (‘n=’); readln (n);

new (d); d^.nr:=n;

d^.as:=s; d^.ad:=nil;

s^.ad:=d; s:=d

end;

procedure listare (b:ref);

var d:ref;

begin

d:=b;

while d< >nil do

begin

writeln (d^.nr);

d:=d^.ad

end

end;

procedure include (m:integer; b:ref);

var d,e:ref;

begin

d:=b;

while d^.nr< >m do d:d^.ad;

write (‘n=’); readln (n);

new (e);

e^.nr:=n;

e^.as:=d;

d^.ad^.as:=e;

e^.ad:=d^.ad;

d^.ad:=e

end;

procedure sterg (m:integer; b:ref);

var d:ref;

begin

d:=b;

while d^.nr< >m do d:=d^.ad;

d^.as^.ad:=d^.ad;

d^.ad^.as:=d^.as;

dispose (d)

end;

begin

writeln (‘creare lista cu o singura inregistrare’);

creare (b, s);

write (‘cite inregistrari se adauga?’);

readln (m);

for i:=1 to m do addr (s);

writeln (‘acum listez de la stinga la dreapta’);

listare (b);

writeln (‘includem la dreapta o inregistrare’);

write (‘dupa care inregistrare se facec includerea?’);

readln (m);

include (m,b);

writeln (‘acum listez de la stinga la dreapta’);

listare (b);

writeln (‘Acum stergem o inregistrare din interior’);

write (‘Ce inregistrare stergem?’);

readln (m);

sterg (m,b);

writeln (‘Acum  listez de la stinga la dreapta’);

listare (b)

end.

8.2.3 Lista circulară

Se consideră o listă liniară. Dacă, ultima înregistrare, adresa următoare va fi înregistrării, am definit o listă circulară. În cazul în care lista iniţială este simplu înlănţuită, listă circulară va fi simplu înlănţuită, iar dacă listă iniţială este dublu înlănţuită şi lista ciculară va fi dublu înlănţuită.

Întucît operaţiile care se efectuează cu aceasta sunt asemănătoare cu cele prezente anterior, ne oprim cu explicaţiile în acest punct.

8.2.4 Stiva

O stivă poate fi definită şi ca o listă liniară  simplu înlănţuită în care toate intrările şi ieşirile se fac la un singur capăt al ei.

În acest caz, elementul de pe nivelul k al stivei va reţine adresa elementului de pe nivelul k-1.

În versiunile anterioare ale acestei cărţi am prezentat stiva ca  fiind o listă liniară dublu înlănţuită, fapt pentru care am fost criticat. Motivul? Prezentînd stiva ca o listă dublu înlănţuită, am avantajul că o pot folosi în mai multe aplicaţii (de exemplu, pentru backtracking, unde pentru a valida un element era necesară comparaţia sa cu cele aflate în stivă pe nivelele inferioare). Desigur, chiar folosind pentru stiva actuala definiţie (prezentă în toate lucrările de specialitate) putem realiza toate aplicaţiile făcute pînă în acest moment, însă mai greu (recursiv, cu pierdere de timp). Chiar modul de lucru standart cu stiva calculatorului (în limbaj de asamblare) permite accesul la elemente ale stivei care nu se află pe ultimul nivel.

Datorită celor prezentate, vom implementa stiva tot ca listă liniară dublu înlănţuită. Cititorul, dacă nu este de acord cu aceasta, îşi poate scrie propriile rutine.

Fiecare înregistrare corespunzătoare stivei conţine trei informaţii: adresa înainte (a elementului următor), adresa înapoi şi informaţia utilă care se diferă de la caz la caz.

Pentru a lucra cu o astfel de stivă sunt suficiente două proceduri: adaug şi scot, cu rolul de a adăuga şi, respectiv, de a scoate o informaţie din stivă. Modul de alcătuire al acestora îl putem analiza din programul următor:

Program stivă;

type ref=^inr;

inr=record

adrurm, adrinap:ref

end;

var  v:ref;

n:integer;

procedure adaug (var v:ref);

var c:ref;

n:integer;

begin

write (‘n=’); readln (n);

new (c);

c^.nr:=n;

c^.adrurm:=nil;

c^.adrinap:=v;

if v< >nil then v^.adrurm:=c;

v:=c

end;

procedure scot (var v:ref);

var c:ref;

begin

if v=nil

then

writeln (’Stiva este vida’)

else

begin

writeln (v^.nr);

c:=v;

v:=v^.adrinap;

dispose (c)

end

end;

begin

adaug (v);  adaug (v);

scot (v);  scot (v); scot (v)

end.

Spre deosebire de stimularea stivei prin intermediul vectorilor, aici avem avantajul că stiva nu este limitată la cele n componente alocate vectorului. Principalul dezavantaj al acestui mod de stimulaqre a stivei este faptul că pe lîngă informaţia utilă se reţin informaţii de adresă, fapt care duce la consum de memorie.

8.2.5 Coada

Structura de coadă a fost deja prezentată (nu şi exemplificată). Reamintim faptul că toate intrările se fac la un capăt şi toate ieşirile se fac la celălalt capăt. Coada nu se poate implementa dinamic cu mare uşurinţă. Astfel va fi implementată ca o listă simplu înlănţuită (sau, pentru a uşura anumite operaţii, chiar dublu înlănţuită). O variabilă de tip referinţă va reţine o adresă de început a cozii, iar alta de acelaşi tip va reţine adresa de sfîrşit. Exerciţiu: scrieţi un program care creează o coadă cu două, trei elemente, apoi le scoate. La sfîrşit se va da mesajul coadă vidă (asemănător cu programul care exemplifică stiva).

8.2.6 Structuri arborescente

8.2.6.1 Arbori binari

Vom defini arborii binari ca un set finit T de unul sau mai multe noduri, astfel încît:

• există un nod cu destinaţie specială numită tulpina (rădăcina) arborelui;
• Celelalte noduri sunt repartizate în două seturi disjuncte şi fiecare din aceste seturi este la rîndul lui un arbore.

Observaţii:

• Cei doi arbori subordonaţi tulpinei poartă denumirea de subarbore stîng şi subarbore drept,
• Definiţia este recursivă, acest lucru fiind de mare folos în continuare,
• În cele ce urmează, pentru tulpină vom folosi  şi termenul de vîrf,
• Dacă un nod nu subordonează arbori, îl vom numi nod terminal, în caz contrar îl vom numi nod neterminal.

Ne propunem să construim un program care generează în memorie un arbore binar. Pentru aceasta, fiecare nod va fi o înregistrare care conţine trei cîmpuri: informaţia utilă, adresa subarborelui stîng şi adresa subarborelui drept. Modul recursiv de definire a arborilor binari ne conduce la ideea de a folosi o funcţie recursivă şi chiar de a utiliza metoda DIVIDE ET IMPERA conform acestei metode se procedează astfel:

Se citeşte informaţia utilă pentru un nod;

Se alocă spaţiu în memorie pentru aceasta;

Se completează informaţia utilă;

Se costruieşte subarborele stâng;

Se costruieşte subarborele drept;

Exact în acest mod se procedează funcţia arb de tip referinţă. Aici, este de remarcat modalitate de trecere la construcţia subarborilor stâg şi drept. Atunci cînd trebuie completate cîmpurile de adresă, acestea primesc ca valoare funcţiei, ceea ce duce autoapelarea ei. Semnalizarea faptului că nu avem subarbore stîng sau drept se face completînd 0 pentru informaţia utilă.

În principal se folosesc trei metode de parcurgere a arborilor.

• Stînga, vîrf, dreapta sau inordine, în care se parcurg mai întîi                                                               subarborele stîng, rădăcina şi apoi subarborele drept;
• Vîrf, stînga, dreapta saunpreordine, în care se parcurg mai întîi rădăcina, subarborele stîng şi apoi subarborele drept;
• Stînga, dreapta, vîrf sau postordine, în care se parcurg mai întîi subarborele stîng, subarborele drept şi apoi rădăcina.

Fie arborele de mai jos:

Datele se introduc astfel:

1240050800360079001000.

Parcurgerea în inordine înseamnă:

4 2 5 8 1 6 3 9 7 10.

Parcurgerea în preordine înseamnă:

1 2 4 5 8 3 6 7 9 10.

Parcurgerea în postordine înseamnă:

8 5 2 6 9 10 7 3 1.

Parcurgerile arborului binar sunt realizate de procedurile: svd ( Stînga, vîrf, dreapta), vsd (Vîrf, stînga, dreapta), sdv (Stînga, dreapta, vîrf).în comentariul pe care îl facem acestor proceduri ne mărginim  să precizăm că sunt realizate utilizînd tehnica DIVIDE ET IMPERA.

Program arbori;

type  ref=^inr;

inr=record

st,dr:ref;

nr:integer

end;

var  c:ref;

function arb:ref;

var n:integer;

c:ref;

begin

write (‘n=); readln (n);

if n< >0

then

begin

new (c);

arb:=c;

arb^.nr:=n;

arb^.st:=arb;

arb^.dr:=arb

end

else arb:=nil

end;

procedure svd (c:ref);

begin

if c< >nil

then

begin

svd (c^.st);

writeln (c^.nr);

svd (c^.dr)

end

end;

procedure vsd (c:ref);

begin

if c< >nil

then

begin

writeln (c^.nr);

vsd (c^.st);

vsd (c^.dr)

end

end;

procedure sdv (c:ref);

begin

if c< >nil

then

begin

svd (c^.st);

svd (c^.dr);

writeln (c^.nr)

end

end;

begin

c:=arb;

writeln (‘Parcurg stinga virf dreapta’);

svd(c);

writeln (‘Parcurg virf stinga dreapta’);

vsd (c);

writeln (‘Parcurg  stinga dreapta virf’);

sdv (c)

end.

Aplicaţie. Forma poloneză

Se dă o expresie aritmetică. Să se construiască forma poloneză asociată acesteia.

Acest exerciţiu l-am rezolvat utilizînd diagramele de sintaxă. În acest capitol îl vom rezolva cu ajutorul arborilor binari. Tehnica de programare folosită va fi DEVIDE ET IMPERA.

Expresiile aritmetice pot fi reprezentate utilizînd arbori binari, respectînd următoarele reguli:

• Fiecare operaţie corespunde unui nod neterminal, avînd ca informaţie utilă operaţia respectivă;
• Fiecare nod terminal este etichetat cu o variabilă sau cu o constantă;
• Pentru fiecare nod neterminal subarborele din stînga şi cel din dreapta reprezintă, în această ordine, cei doi operanzi;
• Rădăcina corespunde ultimei operaţii executate la evaluarea expresiei.

Exemplu: Expresiei (a+b)*c-d/e i se asociază arborele binar din figura de mai jos. Parcurgerea acestui arbore în postordine va da chir forma poloneză: ab+c*de/-. Utilizînd cele spuse, pentru rezolvarea problemei, vom proceda în felul următor:

• Construim arborele binar asociat, expresiei aritmetice;
• Îl parcurgem în postordine pentru a obţine forma poloneză.

Parcurgerea arborelui a fost deja prezentată, problema principală rămînînd construirea acestuia.

Pentru  aceasta vom acorda priorităţi operatorilor şi operanzilor (mai puţin parantezelor), după cum urmează:

• Prioritatea iniţială a operatorilor ‘+’, ‘-’ este  1;
• Prioritatea iniţială a operatorilor ‘*’, ‘/’ este 10;
• La prioritatea unui operator se adună 10 pentru fiecare pereche de paranteze între care se găseşte;
• Prioritatea unui operand este 1000.

În program acest lucru se realizează astfel:

• Se citeşte expresia aritmetică în variabila e;
• Se utilizează o variabilă j care indică ce număr se adaugă la prioritatea iniţială a unui operator (la întîlnirea unei paranteze deschise j creşte cu 10, iar la întîlnirea unei paranteze închise j scade cu 10);
• Se parcurge expresia caracter cu caracter şi se pun în vectorul p priorităţile acestor operatori şi operanzi (mai puţin ale parantezelor);
• În efp se construieşte  expresia fără paranteze (la expresia aritmetică iniţială lipsesc parantezele), iar în pfp se obţine vectorul priorităţilor, din care, spre deosebire de p, lipsesc componentele corespunzătoare parantezelor (acestea nu aveau nici o valoare).

Utilizînd efp şi pfp ,cu ajutorul funcţiei arb, se construieşte arborele ataşat expresiei aritmetice. Un nod al acestui arbore are ca informaţie utilă un operator sau un operand.

Conform tehnicii DIVIDE ET IMPERA, funcţia arb procedează în felul următor:

• de la limita superioară către limita inferioară (limite corespunzătoare subşirurilor de caractere tratate din efp) caută operatorul sau operandul cu prioritate minimă, reţinînd poziţia acestuia;
• acesta constituie informaţia utilă din nod, care va fi completată;
• în situaţia în care limita inferioară este diferită de limita superioară, pentru completarea adresei subarborelui din stînga şi a arborelui din dreapta se reapelează funcţia, iar în caz contrar aceste cîmpuri capătă valoarea NIL.

Pentru listarea în postordine se utilizează procedura parc .

program fp;

type ref=^inr;

sir=array [1..30] of char;

vector=array [1..30] of integer;        inr=record

as, ad:ref;

op:char

end;

var e, efp:sir;

pfp, p:vector;

i, j, n:integer;

c:ref;

a:char;

function arb (1i,1s:integer; var efp:sir; var pfp:vector):ref;

var c:ref;

i, j, min: integer;

begin

min:=pfp [1s];

i:=1s;

for j:= 1s downto 1i do

if pfp [j]<min
then

begin

min:=pfp [j];

i:=j

end;

new ( c);

arb:=c;

arb^.op:=efp [i];

if 1i=1s

then

begin

arb^.as:=nil;

arb^.ad:=nil

end

else

begin

arb^.as:=arb(1i, i-1, efp, pfp);

arb^.ad:=arb(i+1, 1s, efp, pfp)

end

end;

procedure parc (c:ref);

begin

if c< >nil

then

begin

parc ( c^.as);

parc (c^.ad);

write (c^.op)

end

end;

begin

j:=0;

read (a);

n:=1;

while a< >’.’ do

begin

e [n]:=a;

n;=n+1;

read (a )

end;

n:=n-1;

for I;=1 to n do

case e[i] of

‘)’:j:=j-10;

‘(‘:j:=j+10;

‘+’,’-‘:p[i]:=j+1;

‘*’,’/’:p[i]:=j+10

else p[i]:=1000

end;

j:=1;

for i:=1 to n do

if  (e[i] < >’)’) and ( e[i]< >’(‘)

then

begin

efp[j]:=e[i];

pfp[j]:=p[i];

j:=j+1

end;

c:=arb (1,j-1, efp,pfp);

parc ( c);

writeln

end.

Aplicaţie. Arbori de căutare

Se numeşte arbore de căutare un arbore binar ale cărui noduri au o cheie de identificare ( mulţimea cheilor asociate nodurilor este o mulţime bine ordonată – între oricare două elemente distincte ale acestei mulţimi a şi b avem sau a>b sau a<b=, iar pentru fiecare nod avem proprietăţile următoare:

• Orice cheie asociată unui nod al subarborelui stîng este mai mică decît cheia asociată nodului;
• Orice cheie asociată unui nod al subarborelui drept este mai mare decît cheia asociată nodului.

Orice nod al arborelui are asociate trei informaţii

• Cheia de identificare (NR);
• Adresa subarborelui stîng (AS);
• Adresa subarborelui drept (AD).

Arborii de căutare au fost creaţi pentru regăsirea rapidă a informaţiei.

Aplicaţiile care creează şi actualizează un arbore de căutare, care reţine numerele naturale citite (acestea var fi şi chei asociate noduri).

Vor fi prezentate următoarele funcţii:

• Inserarea şi căutarea;
• Listarea;
• Ştergerea;

Inserarea şi căutarea

Crearea arborilor de căutare se face aplicînd de un număr de ori operaţia de inserare. Regula de inserare este următoarea:

• se compară cheia asociată a unui nod cu numărul de inserat;avem trei posibilităţi:
  • cheia coincide cu numărul – se renunţă la inserarea acelui număr;
  • cheia este mai mare decît numărul – se încearcă inserarea în subarborele stîng;
  • cheia este mai mic decît numărul – se încearcă inserarea în subarborele drept.

Inserarea propriu-zisă se realizează atunci cînd subarborele stîng, respectiv drept, este vid, altfel se reia.

Mecanismul descris este tipic tehnicii DIVIDE ET IMPERA.

Pornim de la un arbore de căutare vid. Inserăm numărul 10.

Inserăm 5. Acest număr se inserează în subarborele sting.

Inserăm 7. Acesta este mai mic decît 10. Se trece la subarborele stîng. Se compară cu 5, faţă de care este mai mare. Se inserează în subarborele drept.

Se inserează 15; cum acesta este mai mare decît 10 vom avea:

Iată cum arată arborele după inserarea numerelor 3, 9, 12, 30.

Operaţia de căutare este asemănătoare cu cea de inserare. Cheia căutată se compară cu cheia asociată vîrfului. În caz de egalitate imformaţia a fost găsită. Dacă este mai mică decît cheia asociată nodului, se caută în subarborele stîng iar dacă este mai mare se caută în subarborele drept. Dacă în procesul de căutare s-a ajuns să se caute cheia într-un subarbore vid, înseamnă că nodul cu cheia respectivă lipseşte.

Programul care urmează conţine o procedură de inserare (C_I). Când cheia pentru care se încearcă inserarea lipseşte se execută inserarea, altfel se dă un mesaj corespunzător.

Transmiterea parametrului c se face prin referinţă. Adresa de alocare (obţinută prin NEW) va fi trecută automat părintelui, ca adresă de subarbore stîng sau drept (după caz).

Odată creat, un arbore de căutare permite regăsirea mai rapidă a informaţiei decât în cazul în care ar fi memorate secvenţial. Odată analizată informaţia ataşată prin nod, în caz de inegalitate se trece la subarborele stâng (sau drept) caz în care informaţiile cu cheile din subarborele drept (sau stâng) nu se mai ia în calcul. Numărul de comparaţii este mai mic sau egal cu numărul de niveluri ale arborelui de căutare. De exemplu, pentru regăsirea unei imformaţii, în cadrul arborelui din figură se fac cel mult 4 comparaţii. Dacă pentru memorizare se utilizează o listă simplu înlănţuită, în cazul cel mai defavorabil trebuie de efectuate 8 comparaţii.

Există totuţi o problemă care poate duce la scăderea eficienţei de căutare. În cazul în care cheile sunt introduse în ordine strict crescătoare sau în ordine descrescătoare, arborele degenerează într-o listă liniară (fiecare nod are un singur subarbore nevid). Putem aprecia că introducerea numerelor în această ordine este improbabilă.

Listarea informaţiei

Informaţia se poate lista utilizând oricare din metodele cunoscute pentru parcurgerea arborilor. Dacă dorim listarea imformaţiilor în ordinea strict crescătoare a cheilor, se utilizează metoda stânga-vârf-dreapta (inordine), întucât pentru orice nod avem următoarele:

• cheile nodurilor din subarborele stâng sunt mai mici decât cheia asociată nodului;
• cheile nodurilor din subarborele drept sunt mai mari decât cheia asociată nodului.

Vom lista arborele stâng,informaţia din nod şi informaţiile din subarborele drept (SVD).

Ştergerea

După ştergerea unui nod care are o anumită cheie, arborele rămas trebuie să fie de căutare. Nodul care urmează a fi şters se caută după metoda de acum binecunoscută. Se disting 4 situaşii posibil:

a)     nodul care urmează a fi şters este nod terminal – în acest caz se face ştergerea  având grijă ca la părintele lui să înlocuim adresa către el cu NIL;

b)    nodul care urmează a fi şters subordonează un singur subarbore – cel drept – caz în care părintelui i se va înlocui adresa către el cu adresa subarborelui drept, iar nodul respectiv se va şterge;

c)     nodul care urmează a fi şters subordonează un singur subarbore – cel stâng – caz în care părintelui i se va înlocui adresa către el cu adresa subarborelui stâng, iar nodul respectiv se va şterge;

d)    nodul care urmează a fi şters (după cum vom vedea, acesta se va şterge numai logic) subordonează doi subarbori, caz în care se fac operaţiile:

• se identifică cel mai din dreapta nod al subarborelui stâng corespunzător nodului care urmează a fi şters (acesta va fi şters ăn mod efectiv, ni înainte de a muta informaţiile sale la nodul care se şterge logic);
• cheia acestuia şi alte informaţii utile conţinute de el (altele decât cele de adresă) se mută lanodul care urmează a fi şters;
• subarborele stâng care se va şterge fizic se leagă:
  • în stânga nodului care se va şterge logic (dacă nodul identificat ca cel mai din dreapta din subarborele stâng este descendentdirect al nodului care se va şterge logic)
  • în dreapta tatălui nodului care se va şterge fizic (în caz contrar);

se şterge fizic nodul care a fost identificat şi ale cărui informaţii au fost mutate (cu cheia cea mai mare din suarborele stâng).

Exemlu: pentru cazul d):

Fie arborele din figura de mai jos la care se şterge nodul 6:

• se identifică nodul cel mai din dreapta pentru subarborele stâng (5);
• el nu este descendent direct al nodului care se şterge (6);
• informaţia sa se trece nodului şi se obţine:

• subarborele stâng al nodului care se şterge fizic este dat de nodul 4;
• acesta se leagă în dreapta tatălui nodului care se şterge fizic (3);
• se execută ştergerea fizică şi se obţine:

Ştergerea unui nod este realizată de procedura ŞTERG. Pentru situaţia în care un nod care urmează a fi şters subordonează doi arbori, se apelează procedura CMMD.

Mecanismul de transmitere al parametrilor prin referinţă face ca această procedură să fie exterm de scurtă. Astfel, căutarea nodului cel mai din dreapta pentru subarborele stâng (adresa F) se face recursiv, ce procedura a fost apelată pentru primul nod al subarborelui stâng. În situaţia în care acesta este subordonat direct nodului care se şterge, procedura nu se autoapelează, iar după transferul informaţiilor adresa subarborelui stâng (F^.AS) trece ca adresă în stînga nodului care se şterge logic. În caz contrar, datorită faptului că procedura s-a autoapelat, F^.AS trece ca adresa în dreapta pentru părintele nodului care se şterge fizic.

Întrebarea la care trebuie să răspundem în continuare este următoarea: de ce, dacă se şterge în acest mod un nod, arborele rămîne în căutare? Ştergerea unui nod se face în mod distinct pentru fiecare din cele 4 cazuri arătate. Datorită simplităţii prelucrării, primele 3 cazuri nu necesită comentarii. În cazul 4 se identifică nodul cel mai din dreapta din arborele stâng (care este cu cheia cea mai mare din aceste subarbore). Cheia acestuia trece în locul cheii nodului care se şterge. Aceasta este mai mică decât cheia iniţială (pentru că se găseşte în subarborele stâng), este în acelaşi timp cea mai mare cheie din subarborele stâng care este cea mai mică decât cheia care se şterge. Iată motivul pentru care aceasta trece în locul cheii şterge logic.

program c;

type ref=^inr;

inr=record

nr:integer;

as, ad:ref

end;

var  v, man:ref;

k:integer;

opt:char;

procedure c_i (var  c:ref;  k:integer;);

begin

if c< >nil

then

if c^.nr=k

then

writeln (‘nr deja inserat’)

else

if  c^.nr<k

then

c_i(c^.ad,k)

else

c_i(c^.as,k)

else

begin

new (c);

c^.as:=nil;

c^.ad:=nil;

c^.nr:=k

end;

end.

procedure svd (c:ref);

begin

if c< >nil then

begin

svd (c^.as);

writeln (c^.nr);

svd( c^.ad)

end;

end;

procedure cmmd (var  c,f:ref);

begin

if f^.ad< >nil

then

cmmd (c,f^.ad)

else

begin

c^.nr:=f^.nr;

man:=f;

f:=f^.as;

dispose (man);

end;

end;

procedure sterg;

var f:ref;

begin

if c< >nil

then

if c^.nr=k

then

begin

if (c^.as=nil) and (c^.ad=nil)

then

begin

dispose (c);

c:=nil

end

else

if c^.as=nil

then

begin

f:=c^.ad;

dispose (c);

c:=f;

end

else

if c^.ad=nil

then

begin

f:=c^.as;

dispose (c);

c:=f;

end

else

cmmd  (c, c^.as)

end

else

if c^.nr<k

then

sterg (c^.ad, k)

else

sterg (c^.as, k)

else

writeln (‘numar absent – tentativa esuata ‘)

end;

begin

v:=nil;

repeat

write (‘optiunea’);

readln (opt);

case opt of

’i’:    begin

write (‘k=’); readln (k);

c_i (v, k)

’l’:   svd (v);

’s’:   begin

write (‘se va sterge numarul  ‘);  readln (k);

sterg  (v, k)

end;

end  {case}

until   opt=’t’

end.

Teoria regăsirii informaţiei este deosebit de importantă pentru viaţa practică. Reţinem faptul că se pot crea arbori de căutare (echilibraţi) în care toate nodurile terminale se găsesc numai pe două niveluri consecutive. Aceasta conduce la o căutare rapidă (puţine operaţii).

8.2.7   Arbori oarecare

Vom defini arbori oarecare după D.E.   KNUTH. Se numeşte arbore oarecare un set finit T de unul sau mai multe noduri astfel încât:

• există un nod cu destinaţie specială numit tulpina arborelui;
• celelalte noduri sunt repartizate în m≥0 seturi disjunctive T1,T2, …, Tm unde fiecare din aceste seturi la rândul său este un arbore.

Am folosit această definiţie recursivă întrucît ne este de mare folos în scrierea programului care creează un arbore oarecare.

În programul care urmează construim un arbore oarecare în care fiecărui nod i se subordonează cel mult trei subarbori.

Pentru un nod se completează informaţia utilă (un număr întreg) precum şi un vector de adrese ale subarborilor subordonaţi nodului respectiv. Am utilizat tehnica DIVIDE ET IMPERA atât la creare cât şi la parcurgere.

Fie arborele oarecare din figura de mai jos:

Pentru a crea acest arbore vom introduce informaţiile în ordinea următoare:

1 2 3 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0.

Vom prezenta două dintre cele mai uzuale metode de parcurgere a arborilor oarecare:

1) Parcurgerea în adâncime (realizată de procedura padinc), în care se utilizează întâi tulpina, apoi subarborii de la stânga la dreapta (pentru arboreledin figura de mai sus avem: 1 2 3 4 5 6);

program arbg;

type ref=^inr;

vectad=array [1..3] of ref;

inr=record

nr:integer;

a:vectad

end;

var  c:ref;

function arb:ref;

var  c:ref;

n, i:integer;

begin

write (‘n=’); readln (n);

if n< >0

then

begin

new (c);

arb:=c;

arb^.nr:=n;

for i:=1 to 3 do arb ^.a[i]:=arb

end

else arb:=nil

end;

procedure padinc (c:ref);

var i:integer;

begin

if c< >nil then

begin

writeln (c^.nr);

for i:=1 to 3 do padinc (c^.a[i])

end

end;

begin

c:=arb;

padinc (c)

end.

2)    Parcurgerea în lăţime.

În acest caz, fiecare element al listei liniare care constituie coada va fi o înregistrare care cuprinde în general două câmpuri: adresa înapoi şi informaţia utilă. Dacă variabilele de tip referinţă b şi v vor reţine adresa utimului element introdus în coadă şi adresa elementului care poate fi scos din coadă.

Lucrul cu coada se poate face utilizînd trei proceduri:

1)    crearea cozii;

2)    adăugarea la coadă;

3)    scoaterea (prelucrarea) din coadă.

1)                Crearea cozii

Această operaţie este realizată de procedura ccoada. Crearea cozii constă în:

• alocarea spaţiului pentru o înregistrare;
• completarea informaţiei utile;
• completarea informaţiei îapoi prin NIL.

2)                Adăugarea la coadă

Operaţia de adăugare la coadă este realizată de procedura adcoada. Parametrii ei sunt: t (informaţia utilă) şi b (adresa ultimului element introdus în coadă). Pentru aceasta se realizează următoarele operaţii:

• alocarea spaţiului pentru noua înregistrare;
• completarea informaţiei utile;
• completarea câmpului de adresă înapoi a înregistrării de la b cu adresa noii înregistrări;
• b va lua valoarea adresei noii înregistrări.

3)                Scoaterea din coadă

Această operaţie este realizată de procedura scoada. În acest sens se realizează operaţiile:

• se reţine adresa elementului care urmează a fi scos din coadă;
• se şterge înregistrarea acestui element;
• v va lua valoarea adresei înregistrării plasate înaintea celei şterse.

O aplicaţie foarte importantă a structurii de coadă este parcurgerea în lăţime a arborilor oarecare.

Pentru arborele din figura de mai sus, ordinea de parcurgere a vârfurilor este următoarea:

1 2 5 6 3 4.

În exemplul care urmează, această parcurgere este realizată de procedura tipari. Ideea de lucru este următoarea:

• se porneşte cu o coadă care conţine numai rădăcinile arborelui;
• pentru fiecare element din vârful cozii procedăm astfel:
• îl listăm;
• îi încărcăm toţi succesorii în coadă;
• algoritmul se încheie când coada este vidă.

Recomandăm cititorului analizarea cu  atenţie a acestei proceduri.

program arbg;

type ref=^inr;

vectad=array [1..3]of ref;

inr=record

nr:integer;

a:vectad

end;

refl=^inr1;

inr1=record

inreg:inr;

inapoi:ref1

end;

var  c:ref;

b, v:ref1;

function  arb:ref;

var  c:ref;

n,i:integer;

begin

write (‘n=’);

readln (n);

if n< >0

then

begin

new (c);

arb:=c;

arb^.nr:=n;

for i:=1  to  3  do  arb^.a[i]:=arb

end

else  arb:=nil

end;

procedure ccoada;

var  d:ref1;

i:integer;

begin

new (d);

d^.inreg:=c^;

d^.inapoi:=nil;

b:=d;

v:=d

end;

procedure adcoada (t:inr;  var  b:ref1);

var  d:ref1;

begin

new (d);

d^.inapoi:=nil;

d^.inreg:=t;

b^.inapoi:=d;

b:=d

end;

procedure scoada  (var  v:ref1);

var  d:ref1;

begin

d:=v;

dispose (v);

v:=d^.inapoi

end;

procedure  tipari (var  b, v:ref1);

var  d:ref;

t:inr;

i:integer;

begin

while  v< >nil do

begin

writeln (v^.inreg.nr);

for  i:=1  to  3  do  begin

d:=v^.inreg.a[i];

if d< >nil

then

begin

t:=d^;

adcoada (t,b)

end

end;

scoada (v)

end

end;

begin

c:=arb;

ccoada;

tipari  (b, v)

end.

Aplicaţie. Partiţia determinată de o relaţie de echivalenţă.

Un arbore oarecare poate fi memorat utilizînd o legătură de tip tată. Pentru aceasta este necesar un singur vector v, în care, pentru fiecare nod i, v(i) are semnificaţia de tatăl lui i. Avem v(i)=0 dacănodul lui i este vârf.

Observaţii:

- această formă de memorare este extrem de economică din punct de vedere al memoriei folosite (un nod poate avea mai multe noduri subordonate, dar numai un nod tată, deci avem o singură informaţie de adresă).

-parcurgerea arborilor reprezintanţi astfel de greoaie, fiind consumat mult timp.

Din matematică este cunoscută relaţia de echivalenţă. Aici o vom reaminti. O relaţie de echivalenţă ‘≈’ este o relaţie între elementele unei mulţimi, care satisface următoarele trei proprietăţi:

1)    x≈x (reflexivitate);

2)    dacă x≈y avem şi y≈x (simetrie);

3)    dacă x≈y şi y≈z, atunci x≈z (tranzitivitate).

Pentru că formează o submulţime aparte a mulţimii considerate, toate elementele sunt echivalente între ele. Cum fiecare element este cel puţin echivalent cu el însuşi, înseamnă că o relaţie de echivalenţă determină pe mulţimea considerată o partiţie.

Se consideră mulţimea primilor n numere naturale {1, 2, …, n}. Se dau un număr neprecizat de perechi echivalente de forma x≈y şi se cere  partiţia determinată de această relaţie de echivalenţă.

Exemplu:

Fie n=4 şi perechile 1≈3, 1≈4, 3≈4.

În acest caz relaţia 3≈4 ar putea fi dedusă dinprimele două relaţii:anume din 1≈4 rezultă 4≈1 (simetrie), iar din 4≈1 şi 1≈3 rezultă 4≈3 (tranzitivitate), deci 3≈4 (simetrie). Partiţia determinată de această relaţie de echivalenţă este {1,3,4}, {2}.

Pentru rezolvare, considerăm o pădure cu arbori oarecare, cu nodurile elemente ale mulţimii considerate, reprezintaţi într-un vector cu n, componente, utilizând legătura de tip ‘tată’.

Iniţial, fiecare element constituie un arbore aparte, deci componentele vectorului v au valoarea 0.

Aplicăm soluţia următoare: toate elementele echivalente între ele (care vor alcătui o submulţime aparte a partiţiei) formează un arbore oarecare. Deci la citirea unei perechi j≈k se pune v(j) =k (adică tatăl lui j este k). Există posibilitatea ca j să fie subordonat unui alt părinte (v(j)≠0). În această situaţie j va lua valoarea lui v(j); raţionamentul continuă pînă când v(j) va fi 0 (se ajunge la tulpina arborelui construit pentru această submulţime). În acest moment v(j) va lua valoarea lui k, ceea ce înseamnă că întreg arborele se subordonează lui k. preluăm un exemplu al lui D.E. KNUTH.

Fie n=9 şi perechile citite: 1≈5, 6≈8, 7≈2, 9≈8, 3≈7, 4≈2, 9≈3.

Iniţial vectorul v va arăta astfel:

indici      1  2  3  4  5  6  7  8  9

v            0  0  0  0  0  0   0  0  0

arbori      1  2  3  4  5  6  7  8  9

indici      1  2  3  4  5  6  7  8  9

v             5  0  0  0  0  0  0  0  0            am citit 1=5

arbori      2   3   4   5   6  7  8  9

indici      1  2  3  4  5  6  7  8  9

v             5  0  0  0  0  8  0  0  0             am citit 6=8

arbori       2   3    4  5    7   8   9

1        6

indici      1  2  3  4  5  6  7  8  9

v             5  0  0  0  0  8  2  0  0            am citit 9=8

arbori        2  3  4      5  7    8

indici      1  2  3  4  5  6  7  8  9

v              5  0  7  2  0  8  2  0  8         am citit 3=7

arbori             2   4  5       8

indici      1  2  3  4  5  6  7  8  9

v             5  0  7  2   0  8  2  0  8       am citit 4=2

arbori            2         5      8

indici      1  2  3  4  5  6  7  8  9

v              5  0  7  2  0  8  2  3  8        am citit 8=3arbori

Se obţine partiţia {2,7,4,3,8,6,9} şi {5,1}.

Observaţie:

- Algoritmul nu înregistrează relaţii de forma j≈j sau, dacă a înregistrat j≈k, nu înregistrează k≈j. Pentru listare utilizăm procedura tipar. Precizăm faptul că, în acest algoritm nu sunt permise ca intrări informaţii redundante.

Exemplu:(1,2),  (2,3),  (3,1).  Modificarea algoritmuui în acest sens este propusă ca exerciţiu.

program rechiv;

type  vector=array [1..100]  of integer;

var  v:vector;

n, j, k:integer;

procedure adaug (var j, k:integer; var  v:vector);

begin

while v[j]< >0  do  j:=v[j];

if  (j< >k)  and  (v[k]< >j)  then  v[j]:=k

end;

procedure tipar  (j:integer);

var  i:integer;

begin

for  i:=1  to n do  if  v[i]=j

then

begin

if j=0  then writeln (‘——-clasa——-‘);

writeln (i);

tipar (i);

end

end;

begin

write (‘n=’); readln (n);

for j:=1  to  n  do  v[j]:=0;

while  j< >0 do

begin

write (‘j k’);

readln   (j, k);

if  j< >0  then adaug (j, k, v)

end;

tipar (0)

end.

Probleme propuse

1)    Se citesc n numere naturale, distincte. Să se sorteze crescător, utilizînd lista liniară simplu înlănţuită, după următorul algoritm

• iniţial lista va conţine numai primul număr;
• dacă al doilea este mai mare decît primul, se va pune în coada listei, altfel va fi primul element din listă;
• orice număr se aşează în listă înaintea celui mai mic număr care este mai mare decît el (dacă există un astfel de număr), sau la sfîrşitul listei, în caz contrar.

În final, se listează conţinutul listei liniare simplu înlănţuită. (sortare prin inserţie).

2)    Să se rezolve una din problemele propuse la capitolul 1 utilizînd stiva implementată dinamic.

3)    Să se creeze un obiect numit LLSI – lista liniară simplu înlănţuită – care conţine numere naturale. Acesta va cuprinde metode pentru adăugarea la sfîrşitul listei, ştergerea unui element ş.a.m.d. (în general toate operaţiile care se fac cu liste liniar simplu înlănţuite).

4)    Utilizînd obiectul creat la problema anterioară să se construiască un descendent al acestuia, numit NUMĂR_MARE, în care fiecare element al listei reţine o cifră între 0 şi 9 (în ansamblu o astfel de listă va reţine un număr cu mai multe cifre). Obiectul va fi înzestrat cu metode pentru citarea şi tipărirea numărului.

5)    Să se scrie o procedură care poate aduna două ’’numere mari’’.

6)    Să se scrie o procedură care înmulţeşte două ’’numere mari’.

7)    Pentru realizarea unui curs în care se explică conţinutul a n noţiuni, se citesc p perechi de cuvinte de forma (ni, nj). Fiecare cpereche citită are semnificaţia următoare: noţiunea i foloseşte în definirea noţiunii j. Se cere să se precizeze ordinea de prezentare a noţiunilor în curs.

8)    În jurul arbitrului sunt aşezaţi în cerc N jucători, numerotaţi în sens orar. Arbitrul, începînd de la jucătorul K, numără pînă la M. persoana la care sa oprit numărătoarea este eliminată din cerc. Arbitrul se poziţionează pe următoarea persoană şi repetă procedeul pînă cînd în cerc rămîne un singur jucător (L).

Să se scrie un program care:

• Citind M, N şi K, să-l determuine pe L;
• Citind M, N şi L, să-l determuine pe K.

9)    Să se sorteze n numere naturale cu ajutorul arborilor de căutare.

10)               Evidenţa produselor aflate în stocul unui magazin se ţine pe baza unui arbore de căutare. Pentru fiecare produs se reţine:

• denumirea;
• preţul;
• cantitatea existentă (buc.).

În fiecare seară arborele estev actualizat prin comenzi de forma:

i – se introduc produsele primite de la depozit (Atenţie! Un astfel de produs poate să mai existe în stoc);

s – se şterg produsele vândute în ziua respectivă;

De asemenea, programul acceptă şi comenzile:

v – se tipăreşte valoarea tuturor produselor aflate în stoc;

l – se tipăreşte o listă completă a produselor aflate în stoc, în ordine alfabetică. Pentru fiecare produs se va tipări şi numărul de bucăţi.

11)           Problema jocurilor între doi parteneri, în care unul din jucători este calculatorul. Pentru a putea juca, calculatorul îşi construieşte un arbore corespunzător situaţiilor care pot apărea.

Pentru a exemplifica vom considera un joc simplu, numit ’GRUNDY’. Se consideră o stivă de n monede. Unul din cei doi parteneri o împarte în două părţi inegale. Celălalt partener împarte una din cele două stive de monede rămase în două părţi inegale ş.a.m.d.. Pierde acel jucător care nu mai poate face o astfel de împărţire.

Vom considera cazul n=5. În această situaţie calculatorul îşi construieşte arborele din figura de mai jos:

O primă problemă care se pune este dacă într-o anumită situaţie, presupunînd că trebuie să mute calculatorul, acesta dispune sau nu de strategie sigură de cîştig. Această problemă se poate rezolva utilizînd algoritmul MINI-MAX. Aplicarea acestui algoritm presupune următoarele:

• analiza nodurilor terminale ale arborelui, unde pot apărea două situaţii:
• trebuie să mute calculatorul, caz în care nodul se etichetează cu 0;
  • trebuie să mute partenerul uman, caz în care nodul se etichetează cu 1;
• analiza nodurilor neterminale ale arborelui, unde apar din nou două situaţii:
  • mută calculatorul, situaţie în care nodul se etichetează cu maximul dintre etichetele nodurilor subordonate acestuia;
  • mută partenerul uman, situaţie în care nodul se etichetează cu minimul dintre etichetele nodurilor subordonate acestuia.

Acest mod de etichetare îşi găseşte explicaţia în faptul că, la mutarea efectuată de calculator, acesta va alege o mutare convenabilă (se va duce într-un nod etichetat cu 1), iar la mutarea efectuată de partenerul uman se presupune că acesta va alege o mutare  convenabilă lui (va face o mutare care îl va duce într-un nod etichetat 0).

Scrieţi un program cu ajutorul căruia calculatorul va juca Grundy cu dumneavoastră.

1.1. GHID DE LUCRU

Rezolvarea unei probleme cu ajutorul calculatorului presupune parcurgerea următoarelor faze:

‑ precizarea completă a problemei de rezolvat;

‑ proiectarea algoritmului de rezolvare a problemei;

‑ programarea propriu‑zisă (implementarea);

‑ testarea programului obţinut;

‑ exploatarea şi întreţinerea programului.

Aceste faze constituie ciclul de viaţă al programului.

De foarte multe ori, atunci când beneficiarul discută cu executantul despre problema care trebuie rezolvată, acesta dă un enunţ vag, incomplet, dacă nu chiar inexact sau contradictoriu, pentru problema de rezolvat. Urmează mai multe discuţii, uneori întinse în timp, în urma cărora se ajunge la un enunţ relativ complet şi exact al problemei. Întrucât problemele propuse sunt luate din domeniul matematicii sarcina noastră va fi mult mai uşoară.

După enunţarea problemei urmează modelarea matematică şi căutarea unei metode de rezolvare a ei. Uneori sunt posibile mai multe moduri de rezolvare, caz în care se va alege metoda considerată cea mai potrivită scopului urmărit. Modelarea matematică şi alegerea unei metode de rezolvare se îmbină aproape întotdeauna cu conceperea algoritmului, fiind greu să se separe una de cealaltă. Activităţile de mai sus constituie ceea ce numim proiectarea programului.

Pe toată durata proiectării trebuie menţionate în scris toate deciziile luate, întrucât este posibil ca ulterior să fie necesară o reproiectare şi deci, să se revină asupra acestor decizii. Documentaţia realizată este necesară în primul rând pentru următoarea fază a ciclului de viaţă al programului, implementarea. De asemenea, în faza de întreţinere a programului este posibilă modificarea unor module, modificare în care sunt necesare să fie cunoscute şi aceste decizii. E bine ca proiectarea să fie astfel făcută încât să permită o întreţinere cât mai uşoară.  Faza următoare, implementarea sau codificarea, constă în traducerea algoritmului într‑un limbaj de programare. Evident, prima decizie ce trebuie luată constă în alegerea limbajului de programare în care va fi scris programul. În cele ce urmează vom folosi în acest scop limbajul Pascal. De multe ori se vor folosi mai multe limbaje pentru această activitate. De exemplu, pot exista unele module a căror scriere se poate face numai în limbajul de asamblare. Urmează testarea programului elaborat, care uneori pune în evidenţă erori grave de programare, erori care au dus în unele situaţii la refacerea (parţială sau integrală) a activităţilor anterioare. Sigur că este de dorit să nu se ajungă la astfel de situaţii şi, dacă proiectarea şi implementarea au fost făcute corect, în faza de testare nu ar trebui să întâlnim erori.

Următoarea fază din viaţa programului constă în exploatarea propriu-zisă a acestuia, fază în care execuţia se face cu date reale. Această activitate se întinde în timp pe mai mulţi ani şi cere adeseori schimbări în program, motiv pentru care este cunoscută sub numele de întreţinerea programului. Este faza cea mai costisitoare şi cea mai importantă din viaţa unui produsul real. Toată activitatea de realizare a programului trebuie să ţină seama de acest fapt şi programul să fie astfel conceput încât să se permită modificări în ceea ce face programul cu un număr minim de modificări în textul acestuia. Documentarea programului presupune elaborarea unor materiale scrise în care se precizează toate informaţiile utile despre programul realizat. Pentru proiectarea algoritmilor vom folosi limbajul Pseudocod. Avantajele folosirii acestui limbaj pentru proiectarea algoritmilor constau în faptul că permit programatorului să-şi îndrepte complet atenţia asupra logicii rezolvării problemei şi să uite de restricţiile impuse de limbajul de programare şi calculatorul folosit. În această fază este necesară o analiză atentă a problemei în vederea găsirii unui algoritm corect proiectat.

De asemenea, proiectarea algoritmului permite evitarea duplicării unui grup de instrucţiuni în mai multe părţi ale programului. Identificarea unui astfel de grup permite definirea lui ca un singur subalgoritm şi folosirea acestui subalgoritm ori de câte ori este necesar.

În descrierea unui algoritm deosebim următoarele activităţi importante:

- specificarea problemei;

- descrierea metodei alese pentru rezolvarea problemei;

- precizarea denumirilor şi semnificaţiilor variabilelor folosite;

- descrierea algoritmului propriu-zis.

Astfel, dacă ni se cere să calculăm radicalul de ordinul 2 din x, în partea de specificare a problemei vom menţiona:

Se dă un număr real nenegativ, notat prin x.

Se cere să găsim un alt număr pozitiv r astfel încât r²=x.

Pentru un informatician este clar că un astfel de număr nu se poate găsi în general prin nici un procedeu finit. Este însă posibil să găsim o aproximare oricât de bună a lui r. Deci specificarea făcută nu este corectă, neputând găsi un algoritm care să rezolve problema în forma enunţată. Vom modifica această specificaţie, cerând să se calculeze aproximativ r cu o eroare ce nu depăşeşte un număr real eps oricât de mic.

Specificaţia problemei este:

DATE eps,x;                                                                                                    {eps,xR,  eps>0 şi x0}

REZULTATE r;                                                                                                          {r-rad(x)<eps}

unde prin rad(x) am notat radicalul de ordinul 2 din x definit în matematică.

Urmează să precizăm metoda de rezolvare a problemei. Se ştie că există cel puţin două posibilităţi de a calcula pe r:

- ca limită a unui şir (definit printr-o relaţie de recurenţă) convergent la r;

- prin rezolvarea ecuaţiei r²=x.

Precizăm că-l vom calcula pe r rezolvând ecuaţia r²=x. Dar şi rezolvarea acestei ecuaţii se poate face prin mai multe metode. Decidem că o vom rezolva prin metoda njumătăţirii. Această metodă constă în njumătăţirea repetată a intervalului [a,b] care conţine rădăcina r la intervalul [a',b'], care este jumătatea stângă, sau jumătatea dreaptă a intervalului [a,b], cea care conţine rădăcina.

Variabilele folosite în descrierea algoritmului sunt:

- a şi b = capetele intervalului în care se află rădăcina;

- m mijlocul intervalului (a,b). În momentul în care b-a<eps,

m va fi chiar valoarea căutată pentru r.

Algoritmul propriu-zis este descris în continuare:

*Iniţializează pe a şi b;

REPETĂ

FIE m:=(a+b)/2;

* Dacă rădăcina se află în [a,m] atunci b:=m altfel a:=m.

PNĂCND b-a<eps SF-REPETĂ

FIE r:=(a+b)/2;

În textul de mai sus apar două propoziţii nestandard care sugerează însă foarte bine ce acţiuni trebuiesc întreprinse. Prima stabileşte intervalul iniţial în care se află rădăcina, care depinde de mărimea lui x: (x,1) când x este mai mic decât 1 sau (1,x) în caz contrar. Deci ea se va transcrie în propoziţia standard

DACĂ x<1 ATUNCI ATRIBUIE  a:=x;  b:=1

ALTFEL ATRIBUIE  a:=1;  b:=x

SF-DACĂ

A doua propoziţie înjumătăţeşte intervalul. Condiţia ca rădăcina să se afle în jumătatea stângă a intervalului este (a²-x)*(m²-x)<0. Se ajunge la următoarea variantă finală:

ALGORITMUL RADICAL ESTE:                                                       {Calculează radical din x}

DATE eps,x;                                                                                                     {eps,xR, eps>0 şi x0}

DACĂ x<1 ATUNCI FIE  a:=x;  b:=1                                                   {Iniţializează pe a şi b}

ALTFEL FIE  a:=1;  b:=x

SF-DACĂ

REPETĂ

DACĂ (a²-x)*(m²-x)<0 ATUNCI b:=m                                                   {rădăcina în stânga}

ALTFEL a:=m                                                                       {rădăcina în dreapta}

SF-DACĂ

PNĂCND b-a<eps SF-REPETĂ

FIE r:=(a+b)/2;

REZULTATE r;                                                                                                          {r-rad(x)<eps}

SF-ALGORITM

Programul Pascal corespunzător este dat în continuare.

PROGRAM RADICAL;                                                                {Programul 1.1. Calculează radical din x}

VAR eps,                                                                                               {eps= precizia cu care se calculează}

x,                                                                                                                       {radical din x, eps>0 si x>=0}

r,                                                                                                                                 {valoarea radicalului x}

a,b,                                                                                                   {capetele intervalului ce conţine pe r}

m : REAL;                                                                                                           {mijlocul intervalului [a,b]}

BEGIN

WRITELN(‘Se calculează radical din x cu precizia eps:’);

WRITE(‘eps=’);   READLN(eps);

WRITE(‘ x =’);   READLN(x);

IF x<1 THEN BEGIN a:=x;  b:=1 END                                                                     {Iniţializează pe a si b}

ELSE BEGIN a:=1;  b:=x END;

REPEAT

m:=(a+b)/2;

IF (a*a‑x)*(m*m‑x)<0

THEN b:=m                                                                                                       {rădăcina în stânga}

ELSE a:=m;                                                                                                       {rădăcina in dreapta}

UNTIL b‑a<eps;

r:=(a+b)/2;

WRITELN;  WRITELN;

WRITELN(‘Radical(‘,x:6:1,’) = ‘,r:6:3);                                                                                     {r‑rad(x)<eps}

READLN

END.

1.2. NUMERE PITAGORICE.

Numerele a,b,c, se numesc pitagorice dacă

Specificarea problemei este:

DATE n;                                                                               {nN; pentru n<12 nu există triplete}

REZULTATE toate tripletele de numere pitagorice (a,b,c) cu proprietatea

0<a<b<c şi a+b+cn.

Vom nota prin S suma a+b+c. Se ştie că (3,4,5) este primul triplet de numere pitagorice. În acest caz S ia valori de la 12 la n. Întrucât  3a<S variabila a ia valori de la 3 la S/3. Apoi 2b<S-a deci b va lua valori de la a+1 la (S-a)/2. Algoritmul pentru rezolvarea problemei este dat în continuare :

Algoritmul NRPITAGORICE este :

Date n;                                                                                                {nN; pentru n<12 nu există triplete}

Dacă n<12

atunci Tipăreşte “Nu există numerele cerute”

altfel Pentru S=12,n execută

Pentru a=3,S/3 execută

Pentru b=a+1,(S-a)/2 execută

Fie c:=S-a-b;

Dacă c=a+b atunci Tipăreşte(a,b,c) Sf-dacă

Sf-pentru

Sf-pentru

Sf-pentru

Sf-dacă

Sf-algoritm.

Programul Pascal corespunzător este dat în continuare.

PROGRAM  NRPITAGORICE;                                                         {Programul 1.1.2. Numere pitagorice}

VAR n,                                                                                                                             {    nN;  a+b+cn        }

S,                                                                                                                                   {    S  =  a+b+c          }

a,b,c,                                                                                                   {(a,b,c) triplet de numere pitagorice}

{  0 < a < b < c          }

k     : integer;                                                                                                                                    { contor }

BEGIN

WRITELN(‘Se tipăresc tripletele(a,b,c) de numere pitagorice’);

WRITELN(‘cu proprietatea: a+b+c<=n, pentru n dat’);

WRITE(‘Daţi valoarea lui n:’); READLN(n);

For k:=1 to 4 do writeln;

k:=0;

IF n<12

THEN WRITELN(‘Nu exista numerele cerute’)

ELSE FOR S:=12 TO n DO

FOR a:=3 TO S DIV 3 DO

FOR b:=a+1 TO (S‑a) DIV 2 DO

BEGIN

c:=S‑a‑b;

IF c*c=a*a+b*b THEN BEGIN

k:=k+1;

WRITELN(‘Tripletul (a,b,c)’,k:3,’= ‘,a:3, b:3,c:3);

END {IF}

END;

READLN;

END.

68 de pagini de probleme rezolvate si teorie in Pascal

Însă un matematician utilizează aceleaşi cuvinte – „variabilă aleatoare”, punînd în sensul acestor cuvinte ceva bine determinat. Într-adevăr, spune un matematician, noi nu ştim ce valoare va primi variabila aleatoare în cazul dat concret, dar noi putem determina ce valori poate primi această variabilă, şi putem calcula care este probalilitate de apariţie a evenimentelor.

Pe baza acestor date noi nu putem să anticipăm care ar fi rezultatul unui experiment legat de această mărime, dar noi putem să ştim care ar fi rezultatul unei serii întregi de experimente. Cu cît este mai mare numărul de experimente cu atît mai exact putem să prezicem care va fi rezultatul.

Pentru a defini o variabilă aleatoare, trebuie să indicăm ce valori ar putea lua această variabilă şi care sunt probabilităţile de apariţie ale acestor valori.

Există două tipuri de variabile aleatoare: continue şi discrete.

§1. Variabile aleatoare continue

Variabile aleatoare, valorile căreia aparţin unui interval, se numeşte continuă.

În cazuri particulare acesta poate fi nu un singur interval, dar reuniunea a mai multor intervale. Intervalele pot fi finite, parţial finite sau infinite, de exemplu:  (a; b], (–µ ; a), [b;µ), (–µ; µ).

În general variabila aleatoare continuă este o abstractizare. Вообще непрерывная случайная величина – это абстракция. Obuzul, lansat de un proectil, poate să parcurgă o distanţă cuprinsă între 5 şi 5,3 km, dar nimănui nu-i va veni în gînd să măsoare această distanţă cu exactitatea de pînă la milimetri, nemaivorbind de exactitatea absolută. În practică această distanţă va fi o variabilă aleatoare discretă, la care fiecare valoare a variabilei se deosebeşte de alta cel puţin cu distanţa de un metru.

La descrierea unei variabile aleatoare continue principial nu pot fi scrise şi numerotate toate valorile pe care le poate lua această variabilă, care aparţin unui interval destul de îngust. Aceste valori formează o mulţime nenumărabilă, care se numeşte „”continuu”.

Dacă x este o variabilă aleatoare continuă, atunci egalitatea x = х reprezintă în sine, ca şi în cazul variabilei aleatoare discrete, un careva eveniment aleator, dar pentru variabila aleatoare continuă acest eveniment poate fi legat cu o probabilitate egală cu zero, ceea ce nu indică că evenimentul este imposibil. Aşa de exemplu, putem spune, că obuzul va parcurge distanţa de 5245,7183m cu probabiliatea zero, sau, că diametrului unei piese deviază de la cel ideal cu 0,001059 milimetri. În aceste cazuri este greu să ne dăm seam  - avut loc experimentul sau nu, deoarece măsurarea acestor mărim se efectuiază cu o careva eroare, şi în calitate de rezultat pot fi doare indicate limitele între care se va afla mărimea dată.

Valorilor variabilelor aleatoare le este specifică o careva nedeterminare. De exemplu, nu are sens distingem două valori care se abat de la valoarea matematic ideală cu 0,5mm şi 0,5000025mm. Probabilitatea, diferită de zero, poate fi legată doar cu nimerirea  mărimii în intervalul dat, chiar dacă este destul de îngust.

Fie x – o variabilă aleatoare continuă. Vom cerceta pentru un careva număr х probabilitatea inegalităţii  х < x < х + Dх

P(х < x < х + Dх).

Aici Dх – mărimea unui interval îngust.

Evident, că dacă  Dх ® 0, atunci P(х < x < х + Dх) ® 0. Notăm prin р(х) limita raportului P(х < x < х + Dх) la Dх , cînd Dх ® 0, dacă această limită există:

Funcţia р(х) se numeşte densitatea de repartiţie a variabilea aleatoare. Di for formula (1) rezultă egalitatea, care este adevărată pentru valori foarte mici lae lui Dх şi care poate fi considerată definirea funcţiei  р(х):

P(х < x < х + Dх)

Evident, că funcţia p(x) este o funcţie nenegativă. Pentru definirea probabilităţii, că variabila aleatoare x va lua valori din intervalul [a, b] de lungime finită, vom alege pe acest interval numerele arbitrare x₁, х₂,¼,  х_n care satisfac condiţiei а=х₀<х₁<x₂<¼<x_n<b=x_n+1. Aceste numere impart intervalul [a, b] în n+1 părţi, care nu sunt altceva decît tot nişte intervale [х₀, х₁), [х₁, х₂), ¼,[х_n, b]. Introducem notaţiile:

Dх₀= х₁ – х₀, Dх₁= х₂ – х₁, ¼, Dх_n = b – х_n,

şi formăm suma

teza_var_aleatoare

Un sistem de numeraţie poziţional este caracterizat de baza sa. Numărul cifrelor defineşte baza sistemului de numeraţie. Pentru un sistem de numeraţie poziţional este justă următoarea egalitate:

X(q)=a_nqⁿ+a_n-1q^n-1+…+a₁q¹+a₀q⁰+a_-1q^-1+…+a_-mq^-m,          (1)

unde q – baza sistemului poziţional de numeraţie, un număr întreg; X(q) – un număr arbitrar reprezentat în sistemul de numeraţie poziţional cu baza q; a_i – coeficienţii şirului (cifrele sistemului de numeraţie); n, m – numărul de clase întregi şi fracţionare. În practică se utilizează forma prescurtată de reprezentare a numerelor, adică X(q)=a_na_n-1…a₁a₀a_-1…a_-m.

Egalitatea (1) se utilizează şi pentru conversia numerelor reprezentate într-un sistem poziţional de numeraţie cu baza q în echivalentul său zecimal.

Conversia numărului zecimal X₁₀ în echivalentul său în baza q se efectuează conform următoarelor reguli:

Întrucât 8=2³, conversia binar – octală şi octal – binară se poate face direct. Orice cifră octală se reprezintă prin trei cifre binare, numită triadă:

0 = 000           4 = 100

1 = 001           5 = 101

2 = 010           6 = 110

3 = 011           7 = 111.

Dacă se consideră un număr octal, pentru conversia în binar se va scrie fiecare cifră octală prin trei cifre binare.

Dacă se consideră un număr binar, pentru conversia în octal se vor grupa cîte trei cifre binare, pornind de la poziţia virgulei spre stînga pentru partea întreagă, respectiv dreapta pentru partea fracţionară, găsind corespondentul octal. Pentru completarea unui grup de trei cifre binare, zerourile din faţa numărului, respectiv după ultima cifră a părţii fracţionare nu modifică semnificaţia numărului.

Într-un mod similar se procedează şi în cazul sistemului hexazecimal, baza căruia 16=2⁴. Orice cifră hexazecimală se reprezintă prin 4 cifre binare, numită tetradă:

0 = 0000               8 = 1000

1 = 0001               9 = 1001

2 = 0010               A = 1010

3 = 0011               B = 1011

4 = 0100               C = 1100

5 = 0101               D = 1101

6 = 0110               E = 1110

7 = 0111               F = 1111.

teza_sisteme

sistem de calcul – algoritmică – programare

La baza acestei interdependenţe se află conceptul de algoritm, concept ce a construit  pentru om o nouă filosofie: gândirea algoritmică. Această gândire algoritmică a facut posibilă apariţia şi dezvoltarea Tehnologiei Informaţiei (IT) ce reprezintă de fapt implementarea filosofiei procesării, gestionării şi comunicării informaţiilor.

Întâmplător sau nu, deceniul 7 al sec. XX a fost deceniul marilor schimbări în domeniul informaticii şi al sistemelor de calcul:

Toate aceste aspecte au fost şi sunt într-o interdependenţa continuă ţinând seama de particularitatea informaticii care oferă sisteme de calcul performante şi produse-program competitive în rezolvarea problemelor. Utilizarea eficientă a sistemelor de calcul şi a produselor-program reclamă o instruire continuă, atât pentru informaticieni-programatori, cât şi pentru utilizatori.

Gîndirea algoritmică trebuie să se aiba în vedere în instruire, şi atunci când se invaţă algoritmică (metode şi tehnici), şi atunci când se invaţă programarea (limbaje de programare). Practica instruirii elevilor şi studenţilor a demonstrat că invăţarea unui limbaj de programare este, în general, mai uşoară decat invăţarea elaborarii algoritmilor (algoritmică). Acest lucru se poate justifica prin faptul că elaborarea unui algoritm este echivalentă cu implementarea (reprezentarea) raţionamentelor (procese demonstrative) deduse din metode şi tehnici utilizate în rezolvarea unei probleme. Rezolvarea problemelor necesită nu numai cunoştinţe clare şi precise, dar şi capacitate de sinteză şi control şi mai ales capacitate de creaţie. Dacă vrem să facem o analogie, un programator poate fi compozitorul ce realizează o lucrare muzicală.

Succesele unui programator depind de cunoaşterea foarte bine a programării într-un limbaj de programare modern, dar mai ales depind de bogatia şi stapanirea cunoştinţelor în elaborarea algoritmilor. Şi mai este ceva: experinţa acumulată în activitatea de rezolvare a problemelor prin formarea unei gândiri algoritmice solide şi consistente.

teza_congruenta

3 Þ 4

Notăm cu n numărul de vîrfuri şi cu m numărul de muchii din graf.

Pentru a demonstra că orice graf conex minimal are n-1 muchii vom demonstra prin inducţie completă după n că  m £ n-1. Cum în orice graf conex m ³ n-1, deducem m = n-1.

P(1)                 Dacă n = 1, atunci m = 0 Þ  m = n-1.

P(2)                 Dacă n = 2, atunci  m =1 Þ  m = n-1.

P(n)                 Presupunem că într-un graf conex minimal cu cel mult n vîrfuri numărul de muchii este strict mai mic decît numărul de vîrfuri.

P(n+1)             Demonstrăm că într-un graf conex minimal cu n+1 vîrfuri, numărul de muchii este cel mult egal cu n.

Fie G conex minimal cu n+1 vîrfuri şi m muchii. Eliminînd o muchie oarecare din graf obţinem un graf G’ cu m-1 muchii şi două componente conexe C₁ şi C₂ cu n₁, respectiv n₂ vîrfuri (n₁+n₂ = n+1) şi m₁, respectiv m₂ muchii (m₁+m₂ = m-1). Subgrafurile C₁ şi C₂ sînt conexe minimale, altfel graful G nu ar fi conex minimal. Din ipoteza inductivă rezultă că m₁ £ n₁-1, m₂ £ n₂-1; dar m₁+m₂ = m-1 £ n₁+n₂ = n-2 Þ m £ n-1. Deci G conex minimal implică G conex cu n-1 muchii.

4 Þ 5

Fie G un graf conex cu n-1 muchii. Să demonstrăm că G este aciclic.

Presupunem prin reducere la absurd, că graful G conţine un ciclu C format din  vîrfurile v₁, v₂, …, v_k.

Să considerăm subgraful parţial G_k = (V_k, U_k) constînd  din ciclul C. Deci V_k = {v₁, v₂ ,…, v_k}, iar U_k = {[v₁,v₂)], [v₂,v₃],…,[v_k-1,v_k], (v_k,v₁]} (½V_k½=½U_k½= k). Dacă  ½V_k½<½V½, atunci  $v_iÎV_k şi v_k+1ÎV-V_k astfel încît [v_i, v_k+1]ÎU, graful G fiind conex.

Construim G_k+1 = (V_k+1, U_k+1) în modul următor: V_k+1 = V_k È{v_k+1};     U_k+1=U_kÈ{[v_i,v_k+1]} şi ½U_k+1½=½V_k+1½=k+1.

Cît timp k+1 < n, aplicăm acelaşi procedeu pînă cînd obţinem un graf  G_n = (V, U_n), cu ½U_n½= n, U_n Í U; deci ½U½ ³ n, contradicţie cu ipoteza ½U½= n-1.

5 Þ 6

Presupunem că graful G este aciclic cu n-1 muchii, să demonstrăm că G este aciclic maximal.

Fie C₁, C₂,…, C_p cele p componentele conexe ale grafului G, avînd respectiv n₁, n₂,…, n_p vîrfuri şi m₁, m₂,…, m_p muchii fiecare. Evident că n₁+n₂+…+n_p = n  şi m₁+m₂+…+m_p = n-1.

Cum graful G este aciclic, deducem că fiecare componentă conexă este un arbore. Deoarece am demonstrat că 1 Þ 5, rezultă că m _i= n_i-1, “iÎ{1, 2, …, p}. Înlocuind în relaţia de mai sus, obţinem  n-p = n-1 Þ  p = 1, deci G conex. Dacă G este conex şi aciclic, conform definiţiei G este arbore. Dar am demonstrat că 1 Þ 2, deci oricare două vîrfuri din G sînt unite printr-un lanţ simplu. Astfel, adăugînd orice muchie obţinem un ciclu.

6 Þ 1

Presupunem că graful G este aciclic, dar dacă am mai adăuga o muchie s-ar obţine un ciclu. Să demonstrăm că G este conex.

Fie u şi v două vîrfuri neadiacente din graf, arbitrar alese. Deoarece adăugînd muchia [u, v] se obţine un ciclu, rezultă că u şi v sînt unite printr-un lanţ ale cărui muchii aparţin grafului G. Cum u,v au fost alese arbitrar, deducem că graful G este conex.

Q.E.D.

Teorema 2

Numerele întregi 0 < d₁ £ d₂ £ …£ d_n (n ³ 2) sînt gradele vîrfurilor unui arbore dacă şi numai dacă d₁+d₂+…+d_n = 2n-2.

Demonstraţie:

Necesitatea Condiţia este necesară, deoarece orice arbore cu n vîrfuri are n-1 muchii, iar suma gradelor vîrfurilor oricărui graf este de două ori numărul de muchii. Deci d₁+d₂+…+d_n = 2n-2.

Suficienţa Fie 0 < d₁ £ d₂ £…£ d_n astfel încît d₁+d₂+…+d_n = 2n-2.

Să demonstrăm că există un arbore cu gradele vîrfurilor d₁, d₂,…, d_n. Vom proceda prin inducţie.

P(2)                 Dacă d₁+d₂ = 2, atunci d₁ = d₂ = 1 , arborele fiind cel din figura de mai jos:

Fig. 3

P(n)                 Presupunem acum că proprietatea este adevărată pentru orice secvenţă de n numere naturale 0 < d₁ £ d₂ £ …£ d_n, astfel încît d₁+d₂+…+d_n = 2n-2.

P(n+1)             Să demonstrăm că pentru orice secvenţă 0 < d’₁ £ d’₂ £…£ d’_n £ d’_n+1 astfel încît d’₁+d’₂+…+d’_n+1 = 2n, există un arbore cu n+1 vîrfuri cu secvenţa gradelor d’₁, d’₂, …, d’_n+1.

Observăm că există măcar un nod terminal x₁ cu gradul d’₁=1, altfel dacă  d_i ³ 2,”iÎ{1, 2,…, n+1} Þ d’₁+d’₂+…+d’_n+1 ³ 2(n+1), ceea ce contrazice ipoteza. În mod analog, observăm că există măcar un nod neterminal  x_n+1, cu gradul d’_n+1 > 1, altfel dacă d’_i = 1,”iÎ{1, 2, …, n+1} Þ d’₁+d’₂+…+d’_n+1 = n+1 < 2n .

Să considerăm următoarea secvenţă de n numere întregi d’₂,…, d’_n, d’_n+1-1 cu proprietatea că d’₂+…+d’_n+d’_n+1 = 2n-2. Din ipoteza inductivă există un arbore A_n cu n vîrfuri şi secvenţa gradelor d’₂,…, d’_n, d’_n+1-1. Adăugăm la arborele A_n un vîrf pe care îl unim printr-o muchie cu vîrful avînd gradul d’_n+1-1. Obţinem un arbore A_n+1 cu gradele vîrfurilor d’₁, d’₂,…, d’_n+1.

Q.E.D.

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 2n-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.

Capit1

Capit2_partea1

Capit2_partea2

Să considerăm, una din cele mai simple probleme. Se dă un vector cu n componente. Se cere sa se calculeze maximul dintre componentele sale.

Reamintim, pe scurt algoritmul:

Timpul de calcul depinde, în primul rînd, de lungimea(mărimea) datelor de  intrare, pe care o vom nota cu n.

Exemple:

Pentru a calcula timpul de calcul ar trebui inventariem toate instrucţiunile programului şi să ştim d cîte ori se execută fiecare din ele(în funcţie de n).Mai mult, ar trebuie să cunoaştem cît durează execuţia fiecărui tip de instrucţiune.

Observaţie 1.

Exemplu. Pentru calculul maximului, nu putem şti de cîte ori se execută atribuirea max:=v[i]. Cu toate acestea putem considera că există o proporţionalitate între valoarea n şi numărul de execuţii.

Observaţia 2.

Datorită acestor considerate vom proceda astfel.

Se alege o operaţie numită operaţie de bază, şi se vede de cîte ori se execută aceasta. Cerinţa pentru operaţia de bază este ca aceasta să se execute de un număr de ori, numărul care să poată calcula de la început pornind de la n.

Exemplu.

În astfel de cazuri(cînd avem de ales între mai multe operaţii de bază), vom alege acea operaţie care corespunde cît mai bine scopului propus.

Astfel, dacă analizăm un algoritm de generare a permutării comparativ cu altele de aceeaşi natură vom alege ca operaţie de bază comparaţia.

În cazul în care analizăm un algoritm oarecare, în care soluţia este sub formă de permutare, putem considera ca operaţie de bază permutarea. Problema se spune în felul următor: dacă căutăm soluţia printre toate permutările pe care se pot genera vom avea n! căutări(un număr imens !), oare nu se poate altfel?

Exemple de probleme la care se foloseşte un astfel de raţionament: problema comis voiajorului, problema celor n dame.

Timpul estimat de calcul se trece sub formă aproximativă astfel:

O(număr estimat de execuţii ale operaţiei de bază)

Exemplu de exprimare a timpului.

Dacă un algoritm efectuiază 3n²+7n+5 operaţii de bază, vom spune că aceasta este un algoritm cu O(n²).

Exemple.

În cazul de faţă operaţia aleasă este cea de comparare. Pentru un vector cu n componente se fac n-1 comparaţii. Aceasta înseamnă că dacă vectorul are o sută de componente se fac 99 de comparaţii ş.a.m..d.. Se poate demonstra faptul că un algoritm mai bun nu există!

2.  Pentru generarea permuntărilor(în cazul în care se consideră ca operaţie de bază generarea unei permutări) timpul estimat de calcul este O(n!).

În anumite cazuri nu putem preciza nici macar numărul de execuţie ale operaţiilor de bază.

Exemplu. Sortarea prin interschimbare(vezi 6.2.1). În cazul în care vectorul este sortat se execută n-1 comparaţii (se parcurge vectorul o singură dată), dacă vectorul este sortat invers se execută n(n-1)/2 operaţii de bază (se parcurge vectorul de n ori).

În astfel de cazuri se poate considera:

De fiecare dată cînd se trece timpul estimat se precizează despre care este vorba (minim, mediu, maxim). În practică, prezintă interes timpul madiu sau maxim.

Dacă timpul estimat este sub forma O(n^k), k=N*, spunem că algoritmul este în timp polinomial.

Exemlu. Sortarea prin interschimbare are timpul (mediu, maxim) polinomial şi anume O(n²).

Un algoritm în O(n) se numeşte algoritm liniar.

Dacă un algoritm are un timp estimat O(2ⁿ), O(3ⁿ).. spunem că algoritmul este în timp exponenţial.

Un algoritm în timp O(n!) este asimilat unui algoritm în timp exponenţial.

n!=1x2x…n<2x2x….x2=2^n-1.

În practică nu sunt admişi decît algoritm în timp polinomial, deşi nu este deloc indiferent gradul polinomului.

Şi totuşi pentru ce tot acest efort de estimare a timplui de calcul? Oare viteza de lucru a unui calculator nu este atît de mare, în cît abstracţie făcînd de cîteva minute de calcul, în plus sau în minus, să renunţăm la estimarea lui? Răspunsul la această la această întrebarea este categoric negativ. Mai mult timpul de calcul este esenţial dacă este prea mare algoritmul nu are nici un fel de valoare practică. Să ne imaginăm un algoritm care are un timp de calcul O(2ⁿ). Dacă n este de 10, calculatorul va efectua aproximativ 1024 operaţii elementare. Dacă n este 100 acesta va trebui să efectueze 1024^*1024^*…^*1024 operaţii elementare, adică un număr mai mare decît 1000^*1000^*…^*1000 adică 1000000…0000 (de treizeci de ori). Aceasta este un număr imens. Dar dacă n este 1000? pentru un n nu foarte mare, nici cel mai modern calculator din lume nu scoate rezultatul decît în sute sau în mii de ani. De astfel ce înseamnă în asemenea cazuri un calculator modern? Să presupunem că un sistem PENTIUM are o viteză de circa 25 de ori mai mare decît un sistem XT. Să presupunem că avem un program care are un timp de calcul de ordinul O(2ⁿ). Se cere să rezolvăm o problemă pentru n=30. Fie că timpul necesar rulării acestei probleme pe un XT. Această problemă va fi rulată pe PENTIUM în timpul t/25. Dorim să rezolvăm problema pe PENTRIUM pentru n=35 (n a crescut numai cu 5). Dar 2³⁵=2^30*2⁵=32^*2³⁰. Deci dacă n a crescut cu 5, vom avea nevoie de mai mult timp de lucru să rezolvăm problema pe PENTIUM decît timpul pentru rezolvarea ei pentru n=30 pe XT.

Vă daţi seama ce înseamnă un timp de calcul de ordinul O(2ⁿ)? Sporul lui n cu o singură unitate duce la dublarea timpului de calcul.

Ce concluzie tragem de aici? De cîte ori avem de rezovat o problemă căutăm pentru aceasta un algoritm în timp polinomial (polinomul va avea gradul minim). Mai mult căutăm un algoritm care să rezovle problema în timp polinomial de grad minim.

analiza timpului de calcul

În regimul text fiecare caracter ce apare la ecran este păstrat în memoria calculatorului în doi octeţi, unul cuprinde codul ASCII al caracterului, iar al doilea culorile, iluminarea, culoarea fonului şi clipirea. În regimul grafic memoria ecranului are un cod pentru fiecare pixel prin care se determină culoarea pixelui.

Zona de memorie ecran pentru memorarea unui ecran se numeşte pagină video. Pagina video care apare la un moment dat pe ecran se numeşte pagină vizibilă. Prelucrarea informaţiei grafice în Pascal este susţinută de modulul Graph.

Modulul Graph pune la dispoziţie circa 90 de proceduri şi funcţii păstrate în fişierul graph.tpu. Utilizarea procedurilor şi funcţiilor grafice este posibilă dacă în partea declarativă uses vom declara modulul graph. Fiecare regim grafic are driver-ul său specific. Tabelul  următor conţine lista regimurilor grafice posibile pentru diferite adaptoare grafice. În prima coloniţă sunt indicare  tipurile de drivere, în a doua – numărul de pixeli de pe ecran, în coloniţa a treia este indicată palitra de culori a regimului dat, în ultima coloniţă sunt indicate numărul de pagini video care se pot încărca simultan în memoria videoadaptorului.

Orice program Turbo Pascal ce conţine prelucrarea informaţiei grafice trebuie să cuprindă:

Iniţializarea regimului grafic se relizează prin procedura InitGraph cu formatul:

InitGraph(var GraphDriver:integer; {tipul adaptorului}

var GraphMode:integer; {regimul grafic}

var DriverPath:string); {calea spre driver}

De exemplu:

procedure ini;

var gd, gm:integer;

begin

gd:=detect;

initgraph(gd,gm,’c:\tp\bgi’);

if graphresult<>grok then halt(1);

end;

2. Detecţia rezoluţiei

Funcţia GetMaxX întoarce un numar întreg reprezentând numărul maxim de pixeli (rezoluţia), după direcţia orizontală.

Function GetMaxX:integer;

Funcţia GetMaxY determină numărul maxim de pixeli (rezoluţia), dupa direcţia verticală.

Function GetMaxY:integer;

Funcţia GetMaxColor determină numărul maxim de culori cu care se poate desena pe ecran. În mod convenţional, “culoarea” 0 este cea neagră, astfel încât numărul de culori “de lucru” se află în gama 1..GetMaxColor.

Function GetMaxColor:word;

Cele 3 funcţii sunt necesare pentru scrierea de programe ce folosesc modul grafic şi care pot rula pe orice calculator, indiferent de tipul monitorului şi a placii grafice.

3. Ecranul în modul grafic

Dimensiunea unui element de imagine (pixel) pe direcţia orizontală diferă, în general, de dimensiunea lui pe verticală. Doar adaptoarele mai noi (cum ar fi VGA, VESA) consideră pixelul că având dimensiunile egale pe cele două direcţii.

Raportul între dimensiunea pe orizontală şi dimensiunea pe verticală a unui pixel se numeşte “aspect ratio” (factor/raport de forma).

Procedura prin care se poate afla factorul de forma este GetAspectRatio.

PROCEDURE GetAspectRatio(Var xasp,yasp:word );

Parametrii xasp şi yasp reprezintă numărul de pixeli pe direcţie orizontală şi verticală necesari pentru a obţine o dimensiune “reală”.

Procedura complementară cu GetAspectRatio este SetAspectRatio, ce modifică factorul de forma la valorile dorite. Parametrii xasp, yasp au semificaţie identică cu cei ce apar în procedura GetAspectRatio.

Function SetAspectRatio(xasp,yasp:word):word;

4. Noţiunea de cursor grafic

O noţiune specifică modului grafic este cursorul grafic sau “curent pointer”, notat CP. El este similar cu conceptul de cursor din modul text, dar, spre deosebire de acesta, cursorul este invizibil în mod grafic. Poziţia acestui cursor este importantă la trasarea liniilor, scrierea de text etc.

Pentru a determina poziţia curentă a cursorului grafic se folosesc funcţiile GetX pentru coordonata orizontală şi GetY pentru coordonata verticală.

Initializare_grafica_pascal

Un modul este un element simplu şi autonom, care însă poate intra în calitate de componentă într-un ansamblu mai complex.

Se numeşte curs multimedia instructiv (CMI) o reţea de module, create pe baza tehnologiilor multimedia, reprezentînd informaţii multimedia, pentru acumularea cunoştinţelor în orice domeniu disciplinar.

La elaborarea unui curs instructiv asistat de calculator trebuie de pacurs următoarele etape:

După cum s-a meţionat mai sus una din priorităţile instruirii asistate de calculator este aplicarea elementelor multimedia: imagini grafice, imagini 3D, elemente de sunet (voce, mizică), clipuri-video, filme, animaţie. Ele oferă posibilitatea explicării proceselor complexe prin adăugarea efectelor ilustrative multimedia.

Obietivul de bază al implementării lecţiilor electronice, incluse în cursurile multimedia instructive este asistarea şi înlocuirea patţială a materiei studiate în mod tradiţional. Deaceea la crearea cursurilor de instruire electronice autorul trebuie să selecteze minuţios temele ce vor fi incluse în curs. Cursul creat trebuie să fie consecutiv şi integru.

Utlizarea tehnologiilor informaţionale asigură instruirea computerizată cu acomodarea la viteza de asimilare a informaţiei pentru fiecare utilizator în parte.

Modulele cursului multimedia elaborat trebuie să conţină un număr suficient de obiecte de navigare, hottascuri (combinaţii de taste), pauze, posibilităţi de anulare (ESC) a unor acţiuni etc. Modumele informaţionale şi paginile cursului pot fi legate prin cuvinte-cheie, legături definite de autor.

E necesar să oferim posibilitatea alegerii de către utilizator a oricărei teme pentru strudiere. Trebuie să asigurăm ieşirea către începutul programului (meniul de bază), cît şi către pagina primară a oricărui modul…

Sugestii şi recomadări de creare a cursului:

Este bine de folosit nu mai mult de trei culori pe o pagină. Alte efecte pot fi obţinute prin schimbarea temporară a culorii fragmentului, care apoi revine la culoarea iniţială.

Documentele grafice sunt informaţii în formă de imagini fixe reprezentînd grafice, schiţe tehnice, desene, imagini foto. Utilizarea imaginilor la crearea unui curs multimedia insctructiv îl face mai explicit, mai interesant, mai captivant

Secvenţele video sunt informaţii în formă de imagini în mişcare – filme etc. Pregătirea benzilor animate este un proces mai complicat, dar în unele cazuri poate fi necesar. O deosebire clară între video-clipuri şi animaţie nu este reliefată. Cu filme sunt reflectate imagini din lumea reală, iar cu animaţii şi vedeo-clipuri – imagini din lumea virtuală.

Există mai multe forme de proiectare a unui dialog. Din cele mai cunoscute tipuri de dialog sunt:

- selectarea cu ajutorul mause-lui a opţiunii necesare din meniu;

- înscrierea opţiunii necesare, sau a abrevierii acesteia;

- activarea unei taste corespunzătoare funcţiei date.

Cea mai eficientă este selectarea cu ajutorul mouse-lui.

Secvenţele audio sunt informaţii în formă acustică: voce, muzică,sunet, etc. În cadrul creării unui curs multimedia instructiv sunetul reprezintă un mijloc eficient de influenţare. Cu ajutorul sunetului putem contribui la focalizarea atenţiei către un obiect de pe ecran. Secvenţele audio ocupă un volum mare, deaceea se vor utiliza doar în caz de strictă necesitate.

O valoare psihologică înaltă o are maniera sau tonul de expunere a informaţiei de studiu. Pentru ca expunerea informaţiei să fie mai accesibilă este necesar să fie ales un ton agreabil. O abordare aproblemei de-o manieră autoritară va avea o expunere severă şi neatractivă, deaceea poate duce la plictiseală şi la scăderea interesului faţă de studiu, pînă la abandonarea cursului. Folosirea binevoinţei, nuanţelor de umor contribuie la stabilirea unui feedback (conexiune inversă)sănătos între utilizator şi CMI

Download Tipul de date string