1. Structuri de date. Clasificarea și caracteristica generală

O structura de date este un set de operatii, care poate fi caracterizate ca un lucru, o entitate noua. O structură de date este o metodă sistematică de stocare a informațiilor șidatelor într-un calculator, în așa fel încât ele să poată fi folosite în mod eficient.O structura de date este un set de operatii, care poate fi caracterizate ca un lucru, o entitate noua. SD-1. SD liniare 2. SD neliniareSD liniare- *tablou(uni-dimensional; multidimensional); *structura, record, inregistrare; *liste lantuite liniare[unidimensionale(stiva- stack, coada-quene) multidimensionale]SD neliniare-*liste lantuite neliniare multi-directionale; *graf[arbore(arbori de gradul m>2; arbori binari)]O lista liniara este un set finit de elemente ordonate liniar, adica exista unelement considerat primul in lista, un element considerat ultimul si pentru orice altelement din lista exista un element precedent si un element urmator. Principalele operatii cu liste sunt:−accesarea sau modificarea unui element din lista−inserarea unui element in lista−eliminarea unui element din listaModul in care aceste operatii sunt efectuate depinde de modul in care suntreprezentate listele. Exista doua feluri de reprezentari: secventiala si inlantuita

2. Structura de date, tipul de date și tipul de date abstract Tip de date reprezinta un set de valori si operatiuni asupra lor. Tipurile de date în C pot fi împărţite în două categorii: simple (elementare) şi compuse (structurate) Sunt 2 tipuri de date:

*Tipuri de date predefinite*Tipuri de date definite de programator utilizind conceptia tipului de date abstract

Tipul abstract de date reprezinta un model matematic al structurii de date studiate si operatiuni asupra datelor.Structura este un grup de variabile de tipuri diferite reunite sub acelasi nume, ce pune la dispozitia utilizatorului un mod convenabil de pastrare a informatiilor legate intre ele.Declararea unei structuri creeaza un nou tip de date ce poate fi folosit pentru a crea variabile de acel tip. Variabilile unei structuri, pot fi denumite campuri,membri sau elemnte sunt identificate prin nume simbolice, denumite selectori. Campurile unei structuri pot fi de orice tip, simplu sau derivat, dar nu void sau functie. Declararea structurilor se face folosind cuvantul cheie struct: struct nume_generic{ // struct-cuvint rezervat numele tipului de date; nume_generic-numele dat noului tip de date,optional;tip nume_membru1;//tip-orice tip de data admis de C;tip nume_membru2;//nume_membru_i-numele membrului structurii.................................tip nume_membrun;}lista_variabile;//o lista de variabile de tip nume_generic daca apare sau anonim daca nu apare, este optionala; nume_generic saulista_variabile pot lipsi, dar nu simultan.

3. Etape de implementare a tipului de date abstract în limbajul CEtapele implementarii TDA in limbajul C:1.Crearea fisierului cu extensia (.h) care contine:descrierea proprietatilor SD 2.prototipurile functiilor pentru operatiuni asupra datelor 3.Crearea fisierului cu extensia (.cpp)

care contine main-ul.

4. Implementarea tipului de date abstract „Tablou de structuri” în limbajul CStructurile la fel ca si celelalte tipuri de date pot fi aranjate in tablouri. De ex urmatoarea declaratie creeaza un tablou unidimensional CARTE[20] de structuri de tip carte, ce contin 20 elemente:Pentru a accesa o anumita structura din tablou, numele tabloului trebuie indexat.CARTE[0]-permite accesul la prima componenta a tabloului de structuri, sauCARTE[19]-permite accesul la ultima componenta a tabloului de structuri.Pentru a accesa un cimp al unei anumite structuri din tablou, indexul trebuie urmat de punct si de numele cimpului dorit. De exemplu:gets(CARTE[3].nume_autor);CARTE[3].data_ap=1998;

5. Liste înlanțuite. Clasificarea și caracteristica generală

O lista circulara este o lista in reprezentarea inlantuita care are proprietatea ca ultimul nod pointeaza la primul nod al listei in loc sa aiba drept componenta pointerul NULL. Info adresa info adresa

...

Listele inlantuite se clasifica in: Liste liniare dublu inlantuite si Liste circulare. O lista liniara dublu inlantuita este caracterizata prin faptul ca pe multimea elementelor sunt definite doua relatii de ordine totala inverse una alteia (inainte si inapoi). Rezulta doua secventializari ale listei Ordinea elementelor pentru o astfel de lista este specificata prin doua cimpuri de informatie care sunt parte componenta a fiecarui element si indica elementul urmator si respectiv elementul precedent, conform cu relatiile de ordine definite pe multimea elementelor listei. O lista circulara simplu/dublu inlantuita este o lista liniara simplu/dublu inlantuita modificata astfelincat ultimul element pointeaza spre primul element din lista.

6. Lista simplu înlanțuită. Implementarea tipului de date abstract „Lista simplu înlanțuită” în limbajul C

Lista simpla inlantuita este o SD in care elementele (nodurile) sunt legate printr-un singur cimp ce reprezinta adresa elementului urmator. Elementele sunt definite in diferite locatii in memorie. Primul element al listei este numit corpul listei-head. Spre deosebire de masive, listele nu sunt alocate ca blocuri omogene de memorie, ci ca elemente separate de memorie. Pentru accesarea listei trebuie cunoscuta adresa primului elemen; elementele urmatoare sunt accesate parcurgand lista. Typedef struct lelement {Int info;Struct element *next;}element;Element *head=NULL;

7.Doubly Linked List. Lista dublu înlanțuită. Implementation of abstract data type „Doubly Linked

List” in C language Implementarea tipului de date abstract „Lista dublu înlanțuită” în limbajul C

Lista este dublu inlantuita daca intre nodurile ei sunt definite doua relatii de ordine. In general, o lista este n-inlantuita daca intre nodurile ei sunt definite n relatii de ordine. Listele dublu inlantuita sunt alcatuite din date la care se adauga atit legaturi cu urmatorul articol, cit si cu precedentul .

Aceasta figura indica modul de dispunere al acestor legaturi. Existent a doua legaturi in locul uneia singure prezinta mai multe avantaje, din care poate cel mai important rezida in faptul ca lista poate fi citita in ambele directii. Construirea unei liste dublu inlantuite este un process asemanator celui de alcatuire a unei liste simplu inlantuite, cu deosebirea ca sunt necesare doua legaturi. Structura trebuie sa asigure spatiu pentru ambele. Ca modalitate de implementare, putem defini un tip de date inregistrare in care partile dinamice vor fi pointeri catre acelasi tip, pentru a retine adresa nodului din stanga, respectiv adresa nodului din dreapta si vor fi numite in continuare "st", respectiv "dr" iar partea statica va fi numita "info":

struct nod{< tip> info;nod *st, *dr;};typedef struct nod *NOD;

8.Queue. Coada. Implementation of abstract data type „Queue” in C language Implementarea tipului de date abstract "Coada" în limbajul CO coada este o lista liniara in care stergerea si accesarea unui element se potface numai pe la un capat al cozii, numit front, iar inserarea se face la celalalt capat alcozii, numit rear. Se poate face o analogie intre o coada folosita in programare si, deexemplu, o coada pentru tiparirea mai multor fisiere text. Pentru tiparirea unui noufisier va trebui sa asteptam pana cand toate fisierele sunt tiparite in ordinea in carecomenzile de tiparire au fost efectuate.Cozile se mai numesc si liste FIFO (first in/first out) deoarece primul elementcare este extras din coada este primul introdus

#define DimMax 100           //numarul maxim de elemente din coada

typedef int Coada[DimMax];   //tipul coada implementat ca vector

Coada C;                     //coada

int Inc, Sf;                 //inceputul si sfarsitul cozii

9.Stack. Stiva. Implementation of abstract data type „Stack”  in C language Implementarea tipului

de date abstract "Stiva" în limbajul C

Stiva este o lista liniara in care inserarile si stergerile din lista se pot facenumai pe la un capat al listei, numit varful stivei. Singurul element care poate fiaccesat la un moment dat este cel din varful stivei. Se poate face o analogie intre ostiva folosita in programare si o stiva de carti. Adaugarea unei carti se poate facenumai in varful stivei de carti, peste cartile existente si singura carte ce poate fiaccesata, eventual eliminata din stiva este cea din varful stivei.Stivele se mai numesc si liste LIFO (last in/first out) deoareceprimul element care este extras din stiva este ultimul introdus in stiva.

10.Trees. Arbori. Classification and general characteristics Clasificarea și caracteristica generală

Un graf neorientat conex fara cicluri se numeste arbore . Un tip special de arbore il constituie un arbore, o structura arborescenta, similara cu un arbore din natura sau cu un arbore genealogic, in care se pune in evidenta un nod, numit radacina . Deci putem spune ca un arbore este o multime de noduri legate intre ele prin muchii ce indica relatiile dintre noduri, relatii de tip tata-fiu, similare arborilor genealogici. Nodurile sunt arajate pe nivele. Pe nivelul 0 se afla un singur nod, radacina. Nodurile fiecarui nivel al aborelui sunt fii nodurilor nivelului precedent. Un nod care are fii se numeste tata. Fii cu acelasi tata se numesc frati. Se numeste inaltime a unui arbore lungimea celui mai lung drum de la radacina la un nod terminal din arbore Arbori pot fi: binari...Un arbore in care orice nod nu are mai mult de 2 fii se numeste arbore binar.Arborii binari pot fi de mai multe tipuri: a.b. adecvat si a.b.perfect

11.Different forms of tree representation in the memory of computer Diferite forme de reprezentare

a unui arbore în memoria calculatorului

Reprezentarea cu ajutorul vectorilor de tip tata Reprezentarea cu ajutorul a doi vectori: stang si drept . Pentru fiecrare nod i  stang[i] retine

numarul de ordine al nodului stang subordonat de i, iar drept[i] retine numarul de ordine al nodului drept subordonat de i. Daca nu exista nod subordonat, retine 0. 

12.Binary Tree. Arbore binar. Implementation of  abstract data type „Binary Tree” in C language

Implementarea tipului de date abstract "Arbore binar" în limbajul C

Un arbore binar este un arbore in care orice nod are cel mult doi descendenti facandu-se distincatie clara intre descendentul drept si descendentul stang. Radacina unui arbore binar are doi subarbori, subarborele stang, cel care are drept radacina fiul stang si subarborele drept, cel care are ca radacina fiul drept. Orice aubarbore al unui arbore binar este el insusi arbore binar. Reprezentarea secventiala Pentru fiecare nod al arborelui se precizeaza informatia si descendentii directi ca elemente a trei vector diferiti, INFO[i], ST[i] si DR[i], unde i este indicele asociat unui nod. Cei trei vectori au dimensiunea egala cu numarul de noduri din arbore. Reprezentarea inlantuitaPentru fiecare nod al arborelui se precizeaza informatia si descendentii directi ca elemente ale unei structuri definita astfel:

struct nodarbore{

T info;struct nodarbore *stang;

struct nodarbore *drept;};typedef struct nodarbore NODARB;unde T este presupus definit anterior (eventual printr-o definitie typedef), stang este pointer la subarborele stang al nodului, iar drept este pointer la subarborele drept al nodului. Pentru identificarea radacinii arborelui vom defini NODARB rad; drept un pointer la radacina arborelui. Daca unul din subarbori este vid, atunci pointerul la acel subarbore este NULL

13.Binary Tree  level by level and recursive traversals Arbore binar. Parcurgeri pe niveluri și

parcurgeri recursive

Parcurgerea pe niveluri S-D; D-SParcurgeri recursive:

o in preordine: intai vizitam radacina arborelui, apoi subarborele stang urmat de subarborele drept

o in inordine (simetrica): intai vizitam subarborele stang, , apoi radacina arborelui si apoi subarborele drept

in postordine: intai vizitam subarborele stang si subarborele drept si ultima data radacina arborelui

14.Binary Search Tree and its implementation  in C language Arbore binar de

căutare.Implementarea tipului de date abstract"Arbore binar de căutare" în limbajul C

In domeniul calculatoarelor un arbore binar de cautare (ABC) este o structura de datenumita arbore, si care detine urmatoarele proprietati:* Fiecare nod are o valoare.* Ordinea totala este definita pe aceste valori.* Sub-arborele stang al unui nod oarecare contine numai valorile mai mici decat valoarenodului respectiv.* Sub-arborele drept al unui nod oarecare detine numai valorile mai mari sau egale cunodul respectiv.Avantajul major al arborilor binari de cautare consta in relatarea algorimilor de sortare sialgoritmilor de cautare care folosesc metoda traversarii arborilor in ordine, poate fi foarteeficienta.Toate operatile intr-un arbore binar realizeaza mai multe operatii ce se folosesc de uncomparator, care este o subrutina care calculeaza ordinea totala a oricaror doua valori.Inimplementatiilre simple a arborilor binari de cautare, un program de cele ami multe oritrimite un raspuns catre comparator cand acesta creeaza un arbore, sau altfel explicand, inlimbajele de programare care suporta tipul polimorfism parin folosirea valorilor ca fiindde tip comparabil.

15. Crearea arborelui binar de căutare. Algoritm pentru inserarea unui nod

Prin crearea unui arbore de cautare intelegem de fapt crearea radacinii, restul nodurilor fiind adaugate prin operatia de inserare.

16.Algorithms for searching a node and determining the maximal /minimal node of Binary Search

Tree Arbore binar de căutare. Algoritmi pentru căutarea unui nod și pentru determinarea nodului

max/min

Cautarea unei valori date intr-un arbore binar de cautare este un proces care poate firealizat recursiv in ordinea valorilor care sunt stocate.Se incepe prin axaminarea noduluiradacina.Daca valoarea care este cautata este egala cu valoare nodului radacina, atunciinseamna ca valoarea exista in arbore.Daca valoarea ce trebuie cautata este mai micadecat valoarea nodului radacina, atunci aceasta trebuie sa fie in sub-

arborele stang, astfel printr-o cautare recursiva se va cauta valoarea in structura acestui sub-arborestang.Asemenator,daca valoarea care trebuie cautata este mai mare decat valoareadetinuta de nodul radacina, atunci aceasta trebuie sa fie in structura sub-arboreluidrept.Daca procedura de cautare a ajuns la un nod curent si valoarea cautata nu s-a gasit,atunci valoarea nu se afla in arbore.O compararatie ar putea fi executata cu o cautare binara, care efectueaza o cautarea a valorii printr-o metoda foarte asemanatoare, insaabordeaza un acces aleator in tabloul valorilor prin urmarirea legaturilor.

17. Arbore binar de căutare. Algoritm pentru ștergerea unui nod

Se caută nodul de şters şi se şterge nodul. Subarborele drept este avansat în locul nodului şters, iar subarborele stâng este mutat ca fiu al celui mai mic element din subarborele drept

18.Sequantial and binary search algorithms for 1-D arrays Algoritmi de căutare secvențială și binară

pentru tabloul unidimensional

Cautarea binara (logaritmica)Se aplica pentru tablouri ordonate, principiul ei constind in injumatatirea repetata a intervalului in care se cauta elementul dorit. Aceasta tehnica are avantajul rapiditatii: numarul de comparatii necesare este cel mult log2(N). Necesitatea ca tabloul sa fie ordonat implica faptul ca elementele sale au o componenta (cheie) ce apartine unui tip scalar, iar cautarea se face dupa aceasta component.Cautarea secventiala- urmăreşte să verifice apartenenţa unui element la un şir de elemente de aceeaşi natură, în speţă a unui număr la un şir de numere. Pentru aceasta se parcurge şirul de la un capăt la celălalt şi se compară numărul de căutat cu fiecare număr din şir. În cazul în care s-a găsit corespondenţă (egalitate), un indicator flag este poziţionat. La sfârşitul parcurgerii şirului, indicatorul ne va arăta dacă numărul căutat aparţine sau nu şirului.

19.Sorting algorithms. Algoritmi de sortare. Classification and general characteristics Clasificarea şi caracteristica generalSortare- Se doreşte ca pornind de la o secvenţă de înregistrări conţinând fiecare o cheie, secvenţa să fie reordonată astfel încât cheile să fie într-o anumită relaţie de ordine. Pentru chei numerice poate fi crescătoare sau descrescătoare, iar pentru chei alfanumerice poate fi ordinea alfabetică. Sortarea este un mijloc ajutător pentru căutare, permiţând astfel ca ieşirile de la calculator să poată fi adaptate cerinţelor umane. 0 caracteristică importantă a unui algoritm de sortare este stabilitatea. Este util ca o metodă de sortare sa fie stabilă în cazul unei duble sau multi sortări. De exemplu, dacă avem o secvenţă de înregistrări conţinând un câmp nume şi un câmp nota, secvenţa fiind sortată după nume, şi dacă sortăm secvenţa şi după nota, atunci în secvenţa finală pentru o sortare stabilă înregistrările cu aceeaşi valoare a câmpului notă vor fi încă în ordine alfabetică.0 a doua caracteristică importantă a unei metode de sortare este naturaleţea. 0 metodă de sortare este naturală dacă timpul de execuţie scade odată cu creşterea gradului de sortare iniţială.Prin calculul de complexitate, care se va face pentru fiecare algoritm, se înţelege analiza algoritmului din care să reiasă o dependenţă între dimensiunea datelor de intrare şi timpul de execuţie. Se pot defini diferite măsuri (metrică) pentru intrare, dar pentru problema sortării cea mai naturală măsură este dată de numărul de elemente de sortat.

20.Selection sort algorithm for 1-D array and its modifications Algoritmi de sortare prin selecţie și

prin selecție și interscimbări

Considerăm un vector de elemente comparabile între ele şi dorim să le ordonăm crescător. Pentru aceasta comparăm primul element cu toate elementele care urmează după el. Dacă găsim un element mai mic decât primul atunci le interschimbăm pe cele două. Apoi continuăm cu al doilea element al şirului,

pe care, de asemenea îl comparăm cu toate elementele care urmează după el şi în caz de inversiune interschimbăm cele două elemente. Apoi procedăm la fel cu al treilea element al şirului iar procesul continuă astfel pâna la penultimul element al şirului care va fi comparat cu ultimul element din şir.

21.Insertion sort and bubble sort algorithms for 1-D array Algoritmi de sortare ”bubble” și prin

inserție

Succesul algoritmului este asigurat de trecerea succesivă prin tablou, până când acesta este sortat, cu specificaţia că, la fiecare trecere, elementele succesive i şi i+1 pentru care a[i]>a[i+1], vor fi interschimbate. Metoda poate fi imbunătăţită dacă, după fiecare trecere, se va reţine ultima poziţie din tablou în care a avut loc o interschimbare, iar trecerea următoare se va efectua doar pină la acea poziţie. În cazul în care la o trecere nu a avut loc nici o interschimbare algoritmul se va incheia. Pentru o şi mai bună optimizare se poate înlocui trecerea prin tablou într-un sens cu trecerea în dublu sens. În acest caz, dacă la două treceri succesive, între două elemente i şi i+1 nu a avut loc o interschimbare, atunci nici la trecereile următoare nu se vor înregistra interschimbări. Cu toate optimizările aduse acestei sortari, ea se dovedeşte a fi cu mult mai lentă decât sortarea prin inserţie, fiind însă preferată de unii datorită simplităţii, ce nu ridică probleme de implementare. Pentru valori suficient de mari ale dimensiunii vectorului ce urmează a fi sortat se recomandă utilizarea unor algoritmi ce au o complexitate mai redusa şi, prin urmare, oferă un timp de calcul mai mic.- Inserţia directă. Este cea mai simplă implementare a algoritmului şi se face în felul următor: Se consideră că primele i elemente al vectorului sunt deja sortate. Pentru elementul al (i+1)-lea, din tabloul iniţial, se va găsi poziţia în care trebuie inserat printre primele i elemente. Toate elementele tabloului de la această poziţie şi până la i vor fi deplasate cu o poziţie mai la dreapta iar poziţia eliberată va fi ocupată de elementul i+1. - Inserarea rapidă. Deoarece vectorul destinaţie este un vector ordonat crescător, căutarea poziţiei în care va fi inserat a[i] se poate face nu secvenţial (ca în cazul inserării directe) ci prin algoritmul de căutare binară. Subvectorul destinaţie este împărţit în doi subvectori, se examineazărelaţia de ordine dintre elementul de la mijlocul subvectorului şi elementul a[j] şi se stabileşte dacă elementul a[i] va fi inserat în prima jumătate sau în a doua jumătate. Operaţia de divizare a subvectorului continuă până se găseşte poziţia în care urmează să fie inserat a[i].

22.Shaker and Shell sort algorithms for 1-D array Algoritmi de sortare ”shaker” și Shell

Elementul cheie al algoritmului ˆıl reprezint˘a alegerea valorilor pasului h.Pentru alegeri adecvate ale secvent¸ei hk se poate obt¸ine un algoritm de complexitate mai mic˘a (de exemplu O(n3/2) ˆın loc de O(n2) cum este ˆın cazul algoritmului clasic de sortare prin insert¸ie). O astfel de secvent˘a de pa¸si este hk= 2k−1 pentru 1 ≤ k ≤ IlgnI.Sortarea prin interschimbarea elementelor vecine asigur˘a, la fiecare pas al ciclului exterior, plasarea cˆate unui element (de exemplu maximul din subtabloul tratat la etapa respectiv˘a) pe pozit¸ia final˘a. O variant˘a ceva mai eficient˘a ar fi ca la fiecare etap˘a s˘a se plaseze pe pozit¸iile finale cˆate dou˘a elemente (minimulrespectiv maximul din subtabloul tratat la etapa respectiv˘a). Pe de alt˘a parte prin ret¸inerea indicelui ultimei interschimb˘ari efectuate, atˆat la parcurgerea de la stˆanga la dreapta cˆat ¸si de la dreapta la stˆanga se poate limita regiunea analizat˘a cu mai mult de o pozit¸ie atˆat la stˆanga cˆat ¸si la dreapta (cˆand tabloul cont¸ine port¸iuni deja sortate). Aceast˘a variant˘a (cunoscut˘a sub numele de”shaker sort”)

23.Merge sort recursive algorithm for 1-D array Algoritm de sortare prin interclasare (mergesort)

Aceasta metoda de ordonare are la baza interclasarea a doi vectori: fiind dati doi vectori ordonati se obtine un al treilea vector ordonat care va contine elementele din cei doi vectori. In cazul sortarii prin interclasare vectorii care se interclaseaza sunt doua secvente ordonate din acelasi vector Sortarea prin interclasare utilizeaza metoda Divide et Impera: -se imparte vectorul in secvente din ce in ce mai mici., astfel incat fiecare secventa sa fie ordonata la un moment dat si interclasata cu o alta secventa din vector corespunzatoare.-practic interclasarea va incepe cand se ajunge la o secventa formata din doua elemente. Aceasta odata ordonata se va interclasa cu o alta corespunzatoare. Cele doua secvente vor alcatui in subsir ordonat din vector mai mare care la randul lui se va interclasa cu subsirul corespunzator samd.

24. Algoritm de sortare rapidă (quicksort)

Quicksort este un celebru algoritm de sortare, dezvoltat de C. A. R. Hoare și care, în medie, efectuează   comparații

pentru a sorta n elemente. În cazul cel mai rău, efectuează   comparații. De obicei, în practică, quicksort este mai rapid decât

ceilalți algoritmi de sortare de complexitate   deoarece bucla sa interioară are implementări eficiente pe majoritatea

arhitecturilor și, în plus, în majoritatea implementărilor practice se pot lua, la proiectare, decizii ce ajută la evitarea cazului când

complexitatea algoritmului este de  . Quicksort efectuează sortarea bazându-se pe o strategie divide et

impera. Astfel, el împarte lista de sortat în două subliste mai ușor de sortat. Pașii algoritmului sunt:

1. Se alege un element al listei, denumit pivot

2. Se reordonează lista astfel încât toate elementele mai mici decât pivotul să fie plasate înaintea

pivotului și toate elementele mai mari să fie după pivot. După această partiționare, pivotul se află în

poziția sa finală.

3. Se sortează recursiv sublista de elemente mai mici decât pivotul și sublista de elemente mai mari

decât pivotul.

O listă de dimensiune 0 sau 1 este considerată sortată.

25.Heap Tree and Priority Queue algorithms Arbore binar heap şi coada de prioritate

Heap-ul, este un arbore binar care respectă proprietăţile de structură şi de ordonare. Fiecare nod al arborelui trebuie să conţină o valoare asociată numită cheie şi poate conţine alte informaţii suplimentare. Cheia trebuie să permită definirea unei relaţii de ordine totală pe mulţimea nodurilor. În funcţie de obiectivul urmărit, heap-ul poate fi organizat sub formă de max-heap sau min-heap. Cele două tipuri de heap sunt echivalente. Transformarea unui max-heap în min-heap, sau invers, se poate realiza prin simpla inversare a relaţiei de ordine.Structura heap este preferată pentru multe tipuri de aplicaţii. Cele mai importante utilizări sunt: implementarea cozilor de prioritate utilizate pentru simularea pe bază de evenimente sau algoritmi de alocare a resurselor; implementarea selecţiei în algoritmi de tip greedy cum ar fi algoritmul lui Prim pentru determinarea arborelui de acoperire minimă sau algoritmul lui Dijkstra pentru determinarea drumului minim; sortarea masivelor utilizând algoritmul HeapSortCozile de prioritate sunt structuri de date care suportă următoarele două operaţii de bază: inserarea unui element cu o prioritate asociată; extragerea elementului cu prioritate maximă. Cele mai importante aplicaţii ale cozilor de prioritate sunt: simularea bazată pe evenimente, gestionarea resurselor partajate (lăţime de bandă, timp de procesare) şi căutare în spaţiul soluţiilor.

Structura de date de tip Heap este una dintre cele mai eficiente modalităţi de implementare a cozilor de prioritate. Prioritatea elementelor este dată de relaţia de ordine existentă între valorile asociate nodurilor.

26.Priority Queue and Heap sort algorithms for 1-D array Algoritmi de sortare utilizînd coada de

prioritate și arbore binar heap

O altă aplicaţie a structurii heap este implementarea algoritmului de sortare Heapsort. Sortarea presupune extragerea elementelor din heap şi stocarea acestora, în ordine inversă, la sfârşitul masivului utilizat pentru memorarea structurii.Algoritmul de filtrare presupune parcurgerea următoarelor etape, începând cu nodul rădăcină:◦ se determină maximul dintre nodul curent, fiulstânga şi fiul dreapta (dacă există);◦ dacă maximul se află în nodul curent, atuncialgoritmul se opreşte;◦ dacă maximul se află într-unul dintre fii, atunci se interschimbă valoarea din nodul curent cu cea dinfiu şi se continuă execuţia algoritmului cu nodul fiu.

27.Standard functions queue( ) and bsearch( ) in C language Funcţii standard qsort ( ) şi bsearch

( ) în limbajul C

qsort - sorteaza un masiv

bsearch - cautare binara într-un masiv sortat

#include <stdlib.h>

void qsort(void *base, unsigned nel,

unsigned size, int (*comp)

(const void *, const void *));

void *bsearch(const void *key, const void

*base, unsigned nel, unsigned size, int

Functia qsort sorteaza un masiv de nel elemente, fiecare de marime size. Argumentul base indica spre începutul masivului.Elementele masivului sunt sortate în ordine crescatoare în concordanta cu functia de comparare referita de comp, apelata cu doua argumente care indica spre obiectele ce se compara. Functia de comparare trebuie sa returneze un întreg mai mic decât, egal cu, sau mai mare decât zero daca primul argument este considerat a fi mai mic decât, egal cu, respectiv mai mare decât al doilea. Daca cele doua elemente comparate sunt egale, ordinea în masivul sortat este nedefinita.Functia bsearch cauta într-un masiv de nel elemente, fiecare de marime size, un membru care coincide cu obiectul indicat de key. Argumentul base indica spre începutul masivului.Continutul masivului trebuie sa fie sortat crescator în concordanta cu functia de comparare referita de comp, apelata cu doua argumente care indica spre obiectele ce se compara. Functia de comparare se defineste ca în cazul qsort. Primul argument este adresa cheii, al doilea este adresa unui element din masiv.

Valoare returnataFunctia bsearch returneaza un pointer la un membru al masivului care coincide cu obiectul indicat de key, sau NULL daca nu se gaseste nici un membru. Daca exista mai multe elemente care coincid cu key, poate fi returnat oricare element cu aceasta proprietate.

28.Algorithm techniques. Tehnici de programare. Classification and general characteristics

Clasificarea şi caracteristica generală

O clasificare a cunoasterii importanta pentru programare în general se refera la continutul acesteia, existând urmatoarele trei categorii: cunoastere procedurala, declarativa sitacita. Cunoasterea procedurala se refera la a sti cum sa faci ceva, adica a sti mijloacele pentru a ajunge la un anume rezultat Cunoasterea declarativa se refera la a sti daca un enunt este adevarat sau fals (o asemenea cunoastere ar trebui sa se foloseasca în justitie!). Cunoasterea tacita (denumita uneori si neconditionata, datorata inconstientului) este cunoasterea ce nu poate fi exprimata prin limbaj (un exemplu de acest fel este cunoasterea privind mersul pe bicicleta).Tehnici de programare:Clasa limbajelor procedurale se bazeaza pe notiunea de algoritm. Acesta este o metoda de a rezolva o problema într-un numar finit de pasi, folosind o multime finita de operatii (instructiuni) cunoscute, care executate într-o ordine bine stabilita, pornind de la un set de valori (intrarile), produc în timp finit un alt set de valori (iesirile).Limbajele imperative sau orientate pe instructiune (în engleza ”statement-oriented”) au ca o caracteristica esentiala aceea ca programul este un sir de instructiuni - comenzi, precizândcalculatorului operatiile pe care trebuie sa le execute la momente succesive de timp. Aceste limbaje au fost dezvoltate pentru a elibera programatorul de lucrul în cod masina si în acest sens au fost prevazute cu facilitati privind manipularea variabilelor, operatiile de atribuire si asigurarea repetarii unor secvente.Programarea functionala este centrata pe notiunea de functie. Aici programul este vazut ca o functie, care se obtine din compunerea mai multor functii simple, fie functii sistem, fie definite de utilizator.O alta trasatura pe care au dorit sa o realizeze limbajele functionale este asa numitatransparenta referentiala. Aceasta este o caracteristica a limbajului folosit în matematica si care nu a fost respectata în limbajele imperative. Ea se refera la faptul ca întelesul unui întreg este complet determinat de întelesul partilor, neputând apare efecte parazite datorita combinarii partilor sau unor relatii de ordine dintre ele.

29.Divide and conquer algorithm technique. Tehnica de programare „Forța brută ” și tehnica de

programare „ Divide et empera”. Examples Exemple

Divide et impera este o clasă de algoritmi care funcționează pe baza tacticii divide et impera. Divide et impera se bazează pe principiul

descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține

combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași

tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit

rezolvare imediată.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin "divide et impera"

este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este:

"ce se întâmplă la un nivel, se întâmplă la orice nivel" (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et

impera se elaborează astfel: la un anumit nivel avem două posibilități:

1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;

2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme,

pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare

subproblemă, fie la final, înaintea revenirii din apel.

30.Dynamic programming algorithm technique. Tehnica de programare Backtracking și

programarea dinamică.Examples Exemple

Deseori în practica trebuie să rezolvăm probleme care au un numar foarte mare de soluţii posibile. De cele mai multe ori însa, nu ne intereseaza toate soluţiile, ci numai o parte dintre ele, care îndeplinesc anumite condiţii specifice problemei.Pentru astfel de probleme este indicată folosirea metodei backtracking care evită generarea soluţiilor inutile. Backtracking este numele unui algoritm general de descoperire a tuturor soluțiilor unei probleme de

calcul, algoritm ce se bazează pe construirea incrementală de soluții-candidat, abandonând fiecare candidat

parțial imediat ce devine clar că acesta nu are șanse să devină o soluție validă.[1][2][3]

Exemplul de bază folosit în numeroase manuale de liceu și de nivel universitar este problema reginelor, care

cere să se găsească toate modurile în care pot fi așezate pe o tablă de șah opt regine astfel încât să nu se

atace. În abordarea backtracking, candidatele parțiale sunt aranjamente de câte k regine pe primele k rânduri

ale tablei, toate pe rânduri și coloane diferite. Orice soluție parțială ce conține două regine care se atacă

poate fi abandonată, deoarece în mod clar restul de regine nu pot fi așezate într-o soluție validă.

Tehnica backtracking se poate aplica doar pentru probleme ce admit conceptul de „candidat parțial de

soluție” și oferă un test relativ rapid asupra posibilității ca un astfel de candidat să fie completat către o soluție

validă. Când se poate aplica, însă, backtrackingul este adesea mult mai rapid decât căutarea prin metoda

forței brute prin toți candidații, întrucât este capabilă să elimine dintr-un singur test un mare număr de

candidați.

Backtrackingul este util la rezolvarea unor probleme de satisfacere a constrângerilor, cum ar fi cuvintele

încrucișate, jocuri de sudoku și alte probleme similare. Ea stă la baza unei serii de limbaje de programare

logică, cum ar fi Icon, Planner și Prolog.

Programarea dinamică rezolvă problemele prin descompunerea lor în subproblemeşi prin combinarea rezolvărilor acestora. Programarea dinamică se aplică în general problemelor de optimizare, atunci când dorim să determinăm rapid soluţia optimă pentru o problemă. De fapt, aplicând această tehnică determinăm una din soluţiile optime, problema putând avea mai multe soluţii optime.

Aplicarea acestei tehnici de programare poate fi descompusă în următoarea secvenţă de paşi:1. Descoperirea structurii şi "măsurii" pe care o are o soluţie optimă.2. Definirea recursivă a valorii care caracterizează o soluţie optimă.3. Calcularea "de jos în sus" a acestei valori.4. Construirea soluţiei optime pornind de la calculele efectuate anterior