Structuri de Date și Algoritmi (seria 1AB) laboratoare
http://elf.cs.pub.ro/sda-ab/wiki/
2026-04-17T11:18:13+00:00Structuri de Date și Algoritmi (seria 1AB)
http://elf.cs.pub.ro/sda-ab/wiki/
http://elf.cs.pub.ro/sda-ab/wiki/lib/tpl/dokuwiki/images/favicon.icotext/html2017-01-29T01:00:47+00:00Anonymous (anonymous@undisclosed.example.com)Laboratoare
http://elf.cs.pub.ro/sda-ab/wiki/laboratoare/home?rev=1485644447&do=diff
<pre>
@@ -3,2 +3 @@
{{indexmenu>.#1|navbar nocookie id#random}}
- {{indexmenu>.#2|navbar nocookie id#random}}
</pre>text/html2018-02-21T16:32:24+00:00Anonymous (anonymous@undisclosed.example.com)Laborator 01: Introducere
http://elf.cs.pub.ro/sda-ab/wiki/laboratoare/laborator-01?rev=1519223544&do=diff
<pre>
@@ -4,9 +4,9 @@
Mai multe detalii pot fi găsite pe pagina [[informaii-generale:notare|Reguli de notare]].
==== Reguli esenţiale pentru promovarea laboratorului====
- ----
+
* **MAXIM** 3 absenţe la laborator (**NU** se poate reface la alte grupe)
* **MINIM** jumătate din punctajul de laborator
</pre>text/html2018-02-25T22:02:45+00:00Anonymous (anonymous@undisclosed.example.com)Laborator 02: Algoritmi de sortare 1
http://elf.cs.pub.ro/sda-ab/wiki/laboratoare/laborator-02?rev=1519588965&do=diff
<pre>
@@ -53,8 +53,11 @@
Folosim notaţia O(n) pentru a indica:
*un număr de operaţii de ordinul lui n. În acest caz, spunem că avem "**complexitate de timp de ordinul lui n**"
*o dimensiune de ordinul lui n pentru memoria alocată. În acest caz, spunem că avem "**complexitate de spaţiu de ordinul lui n**"
+ <note important>
+ În acest material se face abuz de notaţie. **NU** confundaţi cu notaţiile **Big-O (O)**, **Big-Omega (Ω)**, **Big-Theta (θ)**. De fapt, notaţia din acest material "O(n)" se apropie ca semnificaţie de notaţia Big-Theta.
+ </note>
====2.3 Metodele de sortare folosite====
Fiecare algoritm se bazează pe o metodă de sortare:
</pre>text/html2018-02-25T22:13:27+00:00Anonymous (anonymous@undisclosed.example.com)Laborator 03: Liste
http://elf.cs.pub.ro/sda-ab/wiki/laboratoare/laborator-03?rev=1519589607&do=diff
<pre>
@@ -1,159 +1,75 @@
- ====== Laborator 03: Stive & Cozi ======
-
+ ====== Laborator 03: Liste ======
\\
=====1 Obiectivele laboratorului=====
- *Înțelegerea conceptului de funcționare si implementarea de stive și cozi.
- *Implementarea unor funcții individuale de lucru cu acestea.
+ *Înțelegerea conceptului de funcționare și implementarea unor liste dublu înlănțuite și circulare
+ *Implementarea unor funcții individuale de lucru cu aceste structuri de date.
\\
- =====2 Ce este o stivă?=====
+ =====2 Ce este o listă?=====
====2.1 Definiție====
- O stivă reprezintă o listă cu structuri de date de tipul: Last-In-First-Out (LIFO).\\
- Un exemplu comun ar fi un teanc de cărți: tot punem cărți pe o masă, dar în momentul când vrem să le ridicăm
- începem cu ultima, pusă deasupra teancului.
+ Listele sunt cele mai bune și cele mai simple exemple a unei structuri de date dinamice care folosește pointeri
+ la implementarea sa.în mod esențial, trebuie înțeles că listele funcționează ca un vector care se poate mări sau
+ micșora după nevoie, din orice punct al mulțimii sale de elemente.
- {{ :laboratoare:stack.jpg?300 |#poza stiva#}}
+ {{ :laboratoare:array_vs_list.png?400 |}}
- ====2.2 Operații cu stive====
+ Avantaje ale utilizării listelor:
+ *Elementele pot fi adăugate sau șterse din mijlocul listei
+ *Nu trebuie definită o mărime inițială, iar memoria se alocă pe rând, odată cu fiecare element adăugat
- Definim structura astfel:
+ Definirea nodului unei liste:
<file cpp>
- struct stack{
- int s[size];
- int top = -1;
- } st;
+ typedef struct {
+ int val;
+ node *next;
+ } node_t;
</file>
- * **Verificăm dacă stiva e plină sau goală**
- <file cpp>
- int st_full(){ //int st_empty{
- if(st.top>=size - 1) //if(st.top==-1)
- return 1;
- else
- return 0;
- }
- </file>
- * **Adăugarea**
- <file cpp>
- void push(int item){
- st.top++;
- st.s[st.top]=item;
- }
- </file>
- * **Ștergerea**
- <file cpp>
- int pop(){
- int item;
- if(st_empty()) //presupunem ca nu exista elemente
- return -1; //cu valoarea -1
- item = st.s[st.top];
- st.top--;
- return (item);
- }
- </file>
+ ====2.2 Clasificare====
+ * **Liste simplu înlănțuite** - Elementele au o singură legătură către următorul element introdus, iar ultimul
+ element pointează către NULL.
- **//Observații//**\\
- 1.Când introducem elemente într-o stivă,trebuie să incrementăm top-ul și apoi să adăugam elementul.\\
- 2.Când ștergem un element,trebuie întâi să ștergem elementul și apoi să decrementăm top-ul.\\
- 3.O stivă poate fi implementată cu ajutorul unui **vector** sau cu **liste înlănțuite**.\\
+ {{ :laboratoare:simplelist.png?500 | Liste simplu înlănțuite}}
- =====3 Ce este o coadă?=====
- ====3.1 Definiție ====
- O coadă este o structură de date ce modelează un buffer de tip First-In-First-Out (FIFO).Astfel, primul element introdus în coadă va fi și primul care va fi scos din coadă.
+ * **Liste dublu înlănțuite** - Elementele au dublă legătură către precedentul și antecedentul, capul listei pointând
+ spre NULL și ultimul element de asemenea
- {{ :laboratoare:fifoex.png?300 |#poza coada#}}
+ {{ :laboratoare:doublelist.jpg?500 |}}
- ====3.2 Operații cu cozi====
- Definim structura astfel:
- <file cpp>
- struct queue{
- int queue[size];
- int rear = -1;
- int front = 0;
- }Q;
- </file>
+ * **Liste circulare** - Pot fi simplu sau dublu înlănțuite cu proprietatea că ultimul element pointează spre primul.
- * **IsEmpty** - întoarce 0 dacă coada este goală;1 dacă are cel puțin un element.
- <file cpp>
- int Qempty(){
- if(Q.front > Q.rear)
- return 1;
- return 0;
- }
- </file>
- * **Enqueue / Adăugarea** - adaugă un element (entitate) în coadă.Adăugarea se poate face doar la sfârșitul cozii.
- <file cpp>
- void Qinsert(int item){
- Q.rear++;
- Q.queue[Q.rear] = item;
- }
- </file>
- * **Dequeue/ștergere** - șterge un element din coadă și îl returnează.Ștergerea se poate face doar la începutul cozii.
- <file cpp>
- int Qdelete(){
- int item;
- if( Qempty() ) //in acest caz, alegem o valoare de return
- return -1; // ce NU poate fi confundata cu un element
- //presupunem ca NU exista niciun element cu valoarea -1
- else {
- item = Q.queue[Q.front];
- Q.front ++;
- return item;
- }
- }
- </file>
+ {{ :laboratoare:circularlist.png?500 |#Poza lista circulare#}}
- ====3.3 Clasificare====
+ ====2.3 Operații cu liste:====
+ *Adăugare la începutul listei
+ *Adăugare la sfârsitul listei
+ *Adăugarea înainte sau după un element dat
+ *Ștergerea capului de listă
+ *Ștergerea unui element oarecare din listă
- * **Dequeue** - (sau coadă cu dublu acces) este o structură de tip coadă în care însă accesul (introducere/extragere de elemente) se poate realiza prin ambele capete.\\ \\
- De cele mai multe ori sunt implementate folosind liste dublu înlănțuite.\\ \\
- Dintr-un anume punct de vedere, se poate considera că atât stiva cât si coada clasică sunt specializări ale tipului abstract dequeue întrucât ambele se pot implementa folosind dequeue (și restrângând operațiile ce se realizează asupra sa).\\
- {{ :laboratoare:deque.png?800 |# poza #
- }}* **Priority queue** - Coada prioritară reprezintă un tip de coadă în care fiecare element are asociată o anume prioritate.\\
- În aceste condiții,operațiile de bază asupra cozii devin:\\
- * **Enqueue** - adaugă la coadă un element cu prioritatea specificată\\
- * **Dequeue** - extrage elementul cu cea mai mare prioritate\\
- * **Front** - examinează elementul cu cea mai mare prioritate fără a-l extrage din coadă.\\
+ =====3.Exerciții propuse pentru laborator=====
+ 1. Creați o listă circulară,dublu inlănțuită cu 6 angajați ai unei companii, care să conțină următoarele referințe: nume, nr de telefon, post.
+ * Scrieți funcțiile care să scrie urmatoarele:\\
+ * Să introducă un nou angajat după al treilea.\\
+ * Să introducă un nou angajat inainte de cel care e "mecanic".\\
+ * Să steargă angajatul cu un anumit număr de telefon introdus.\\
- =====4 Exerciții propuse =====
+ 2. Să se creeze o listă liniara simplu inlantuita care contine elemente intregi citite dintr-ul fisier text.
+ Se citeste apoi o valoare intreaga x. Sa se stearga primul nod care contine valoarea x.
+ Fișierul se va da ca parametru în linia de comandă.
- ==== 4.1 Exerciții clasice ====
- 1. **FIFO buffer**
- O coadă este o modalitate folositoare de a stoca date care provin in mod asincronic de la un microcontroler periferic, dar care nu pot fi citite imediat. Un bun exemplu ar fi stocarea de biți proveniți de la un UART (Universal asynchronous receiver/transmitter).\\
- Un buffer FIFO stochează date pe principiul "primul venit - primul servit".Structura de stocare este un spațiu alăturat de memorie.\\
- Datele sunt scrise in capul cozii și citite de la coadă.Dacă parcurgerea are loc de la coadă spre cap,buffer-ul este gol.Dar dacă parcurgerea este de la cap spre coadă, implementarea trebuie să defineascî dacă cea mai veche dată trebuie scoasă sau daca scrierea nu s-a terminat.
+ 3. Să se construiasca o lista liniara simplu inlantuita cu elemente numere intregi. Să se afișeze și apoi să se stearga din lista elementele pare.
- **Implementare generală**\\
- 1) Definite structură:head,tail,size,buffer.\\
- 2) Se realizează funcția de inițializare a cozii cu bufferul dat și marimea.\\
- 3) Se realizează funcția de citire a celor nbytes din coadă;nr. citit de biți se returnează\\
- 3.1 Pentru nbytes:se verifică dacă sunt date valabile (dacă coada e diferită de cap)\\
- 3.2 Daca da, se ia un byte din buffer și se incrementează coada.\\
- 3.3 Se verifica apoi dacă s-a terminat parcurgerea pentru a se reinițializa coada cu 0.\\
- 3.4 În cazul în care nu sunt date valabile se returnează nr. de bytes.\\
- 4) Se realizează funcția de scriere a celor nbytes din coadă.\\
- 4.1 Pentru nbytes:inițial se verifică dacă este spațiu în buffer (coadă).\\
- //[Bonus]// Generarea in mod random a datelor de intrare și prelucrarea lor cu ajutorul funcțiilor de mai sus;astfel valorile folosite vor fi introduse de la tastatură
-
- 2.Implementați pentru o structură de tip stivă funcţiile de inserare, extragere a unui nod, precum şi cele de afişare şi de semnalare a situaţiilor extreme (stivă goală au stivă plină).
-
- ====4.2 Exercitii alternative - schelet de laborator====
- Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab2-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.
-
- Pentru acest laborator sunt două exerciții, primul cu stive și al doilea cu cozi. Fiecare are mai multe task-uri. Urmăriți cu atenție comentariile din fișierele sursă.
-
- ===4.2.1 Linux===
- Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
-
- * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab2-skel.zip%%''
- * ''%%unzip lab2-skel.zip%%''
+ 4. Adunaţi 2 polinoame rare, reprezentând fiecare polinom printr-o listă înlănţuită, unde fiecare nod va conţine datele pentru un coeficient şi o putere (de exemplu: 5 x<sup>3</sup>, coeficient = 5, putere = 3).
+ 5. Pentru laboratorul de liste inlantuite vom porni de la o arhiva cu un schelet de laborator. Nu veti scrie codul de la zero ci veti implementa cateva functii in fisierul ''%%list.c%%''.
+ Descarcati arhiva de {{ :laboratoare:lab1-skel.zip |aici}} si dezarhivati-o. Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
<code bash>
- student@sda-ab-vm:~/Documents$ wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab2-skel.zip
- --2017-03-02 20:45:55-- http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab2-skel.zip
+ student@sda-ab-vm:~/Documents$ wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab1-skel.zip
+ --2017-03-02 20:45:55-- http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab1-skel.zip
Resolving elf.cs.pub.ro (elf.cs.pub.ro)... 141.85.227.116
Connecting to elf.cs.pub.ro (elf.cs.pub.ro)|141.85.227.116|:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 2368 (2,3K) [application/zip]
@@ -164,43 +80,24 @@
2017-03-02 20:45:56 (4,78 MB/s) - ‘lab1-skel.zip’ saved [2368/2368]
student@sda-ab-vm:~/Documents$ ls
lab1-skel.zip
- student@sda-ab-vm:~/Documents$ unzip lab2-skel.zip
- Archive: lab2-skel.zip
- creating: lab2_stive-si-cozi/
- creating: lab2_stive-si-cozi/1-stack/
- inflating: lab2_stive-si-cozi/1-stack/Makefile
- inflating: lab2_stive-si-cozi/1-stack/stack.c
- creating: lab2_stive-si-cozi/2-queue/
- inflating: lab2_stive-si-cozi/2-queue/Makefile
- inflating: lab2_stive-si-cozi/2-queue/queue.
- student@sda-ab-vm:~/Documents$ cd lab2_stive-si-cozi
- student@sda-ab-vm:~/Documents/lab2_stive-si-cozi$ ls -l
- total 0
- drwxrwxrwx 1 student student 248 mar 5 15:57 1-stack
- drwxrwxrwx 1 student student 248 mar 5 15:58 2-queue
-
- student@sda-ab-vm:~/Documents/lab2_stive-si-cozi$ cd 1-stack
- student@sda-ab-vm:~/Documents/lab2_stive-si-cozi/1-stack$ make
- student@sda-ab-vm:~/Documents/lab2_stive-si-cozi/1-stack$ make run
+ student@sda-ab-vm:~/Documents$ unzip lab1-skel.zip
+ Archive: lab1-skel.zip
+ inflating: list.c
+ inflating: list.h
+ inflating: Makefile
+ student@sda-ab-vm:~/Documents$ make
+ gcc list.c -o list -std=gnu99
+ student@sda-ab-vm:~/Documents$ make run
</code>
- Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi comanda ''%%make run%%''.
-
- * Pentru exercițiul ''1-stack'', executabilul rezultat în urma comenzii ''%%make%%'' se numește ''%%stack%%''.
- * Pentru exercițiul ''2-queue'', executabilul rezultat în urma comenzii ''%%make%%'' se numește ''%%queue%%''
-
- ===4.2.2 Linux + Github===
- [[https://github.com/mateiuli/sda-ab_laboratoare|Aici]] puteți găsi repository-ul de pe GitHub unde se află scheletul de cod pentru fiecare laborator.
-
- Dacă sunteți familiari cu git puteți clona repo-ul local folosind comanda ''%%git clone https://github.com/mateiuli/sda-ab_laboratoare%%''.
- ====4.3 Opţional - de interviu====
+ Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi fie **''%%./list%%''** fie comanda ''%%make run%%''.
- 1. Implementaţi o stivă folosind două cozi.
+ ====Probleme opţionale - de interviu====
- 2. Implementaţi o coadă folosind două stive.(utilizarea apelurilor recursive ale unor funcţii se contorizează ca folosirea unei stive)
+ 1. Se dă o listă simplu înlănţuită(primiţi doar un pointer către primul element). Verificaţi dacă lista conţine o buclă. (o listă simplu înlănţuită conţine o buclă => niciun element nu are legătura NULL)
- 3. Implementaţi o stivă cu valori întregi şi o funcţie care obţine valoarea maximă din stivă. Pentru interviu se cere ca funcţia să aibă complexitate de timp constantă => O(1).
+ 2. Se dau două liste(pentru fiecare listă - pointer către primul element) în formă de Y(listele se intersectează, ultimele k elemente sunt comune). Aflaţi valoarea lui k.
- 4. Se dă un vector cu n întregi și un număr k. Aflați valoarea maxima pentru fiecare grupare de k numere de pe poziții consecutive.
+ 3. Se dă o listă cu 2n+1 elemente, fiecare element conţine câte un întreg. Toate valorile întregi apar de două ori în listă, excepţie facând una singură. Aflaţi acea valoare.
</pre>text/html2018-02-25T22:34:48+00:00Anonymous (anonymous@undisclosed.example.com)Laborator 04: Stive & Cozi
http://elf.cs.pub.ro/sda-ab/wiki/laboratoare/laborator-04?rev=1519590888&do=diff
<pre>
@@ -1,275 +1,208 @@
- ====== Laborator 04: Arbori ======
+ ====== Laborator 04: Stive & Cozi ======
\\
=====1 Obiectivele laboratorului=====
- *Înțelegerea noțiunii de arbore și a structurii unui arbore binar
- *Citirea unei expresii matematice și construirea arborelui binar asociat
- *Înțelegerea structurii și proprietăților unui arbore binar de căutare
- *Realizarea diferitelor operații folosint arborii binari de căutare
-
+ *Înțelegerea conceptului de funcționare si implementarea de stive și cozi.
+ *Implementarea unor funcții individuale de lucru cu acestea.
\\
- ===== Noţiuni introductive=====
- ===Definiţie generală===
+ =====2 Ce este o stivă?=====
+ ====2.1 Definiție====
+ O stivă reprezintă o listă cu structuri de date de tipul: Last-In-First-Out (LIFO).\\
+ Un exemplu comun ar fi un teanc de cărți: tot punem cărți pe o masă, dar în momentul când vrem să le ridicăm
+ începem cu ultima, pusă deasupra teancului.
- Un arbore poate fi definit ca: structură de date ce conţine noduri şi legături, fără circularitate. Un arbore poate fi văzut ca o extindere de la **lista simplu înlănţuită şi necirculară**, **eliminând** condiţia de a exista **o singură legătură** ce pleacă dintr-un nod, adică maxim un singur nod "următor".
+ {{ :laboratoare:stack.jpg?300 |#poza stiva#}}
- ===Rădăcină(Root)===
- Numim rădăcină primul nod al arborelui(echivalentul capului de listă).
+ ====2.2 Operații cu stive====
- ===Copil - Părinte(Child - Parent)===
- Nodul P este părintele nodului C dacă are legătură către C(similar, C este copilul lui P).
- * Pot apărea şi alţi termeni pentru relaţia dintre noduri: fraţi(siblings), veri(cousins) etc.
-
- <note tip>Rădăcina NU poate fi nod-copil.</note>
-
- ===Gradul(Degree)===
- Gradul unui nod este egal cu numărul de copii ai acestuia.
-
- ===Frunză(Leaf) şi nod intern/extern(internal/external)===
- Numim frunză un nod fără copii(**nod terminal**).
- * Frunzele se mai numesc **noduri externe**.
- * Nodurile care au copii se mai numesc **noduri interne**.
-
- ===Urmaş(Descendant)===
- Nodul U este urmaşul nodului S dacă putem "coborî"(mergând numai de la părinte la copil) de la S la U.
-
- ===Strămoş(Ancestor)===
- Nodul S este strămoşul nodului U dacă U este urmaşul lui S(putem "urca" de la U la S).
- <note tip>Rădăcina este strămoşul tuturor celorlalte noduri din arbore.</note>
-
- ===Înălţime(Height)===
- Definim înălţimea unui nod egală cu numărul de legături pe care "coborâm" de la acel nod la cea mai îndepărtată frunză.
- <note tip>înălţimea arborelui = înălţimea rădăcinii</note>
-
- ===Adâncime(Depth)===
- Definim adâncimea unui nod egală cu cu numărul de legături pe care "coborâm" de la rădăcină la nodul respectiv.
- <note tip>adâncimea rădăcinii = 0</note>
-
- ===Nivel(Level)===
- Definim nivelul unui nod egal cu 1 + adâncimea.
-
- ===Pădure(Forest)===
- Numim pădure o mulţime de N(de obicei N >= 2) arbori disjuncţi(care nu au noduri comune).
-
- ===Vector de taţi(Parent array/vector)===
-
- Vectorul de taţi reprezintă o soluţie ieftină(d.p.d.v. al memoriei) de reprezentare a unui arbore atunci când nodurile pot avea un număr diferit de legături. În acest caz, ne putem folosi de faptul că **fiecare nod-copil are un singur părinte**, indiferent de câţi copii are părintele respectiv. **Rădăcina** arborelui este singura **excepţie**.
+ Definim structura astfel:
+ <file cpp>
+ struct stack{
+ int s[size];
+ int top = -1;
+ } st;
+ </file>
+ * **Verificăm dacă stiva e plină sau goală**
<file cpp>
- //fie n = nr. de noduri
- //nodurile sunt numerotate de la 0 la n-1
- //fie doua noduri numerotate cu indicii A si B
- Parent[A] = B; // Parintele nodului A este nodul B
- //fie Root nodul radacina
- Parent[Root] = -1; //nu exista nod numerotat cu -1
+ int st_full(){ //int st_empty{
+ if(st.top>=size - 1) //if(st.top==-1)
+ return 1;
+ else
+ return 0;
+ }
+ </file>
+ * **Adăugarea**
+ <file cpp>
+ void push(int item){
+ st.top++;
+ st.s[st.top]=item;
+ }
+ </file>
+ * **Ștergerea**
+ <file cpp>
+ int pop(){
+ int item;
+ if(st_empty()) //presupunem ca nu exista elemente
+ return -1; //cu valoarea -1
+ item = st.s[st.top];
+ st.top--;
+ return (item);
+ }
</file>
- =====2 Arbori binari=====
- ====2.1 Definiție====
- Un arbore binar este alcătuit din noduri, unde fiecare nod conține un pointer către "stânga" și un pointer către "dreapta" și un element de tip dată.\\
- Pointer-ul "root (rădăcină)" reprezintă adresa celui mai de sus nod din arbore.Pointerii din "stânga" și "drepta" punctează în mod recursiv, pe fiecare aprte, la //subarbori// mai mici.\\
- Arborii sunt folosiți in general pentru a modela o ierarhie de elemente.Astfel,fiecare element **(nod)** poate deține un număr de unul sau mai mulți descentenți,iar în acest caz nodul este numit **părinte** al nodului descendent.\\
- Un nod fără descendenți este un **nod terminal**, sau **nod frunză**.\\
- {{ :laboratoare:arborebinar.png?400 |
- # poza arbore#}}
+ **//Observații//**\\
+ 1.Când introducem elemente într-o stivă,trebuie să incrementăm top-ul și apoi să adăugam elementul.\\
+ 2.Când ștergem un element,trebuie întâi să ștergem elementul și apoi să decrementăm top-ul.\\
+ 3.O stivă poate fi implementată cu ajutorul unui **vector** sau cu **liste înlănțuite**.\\
- ====Alte noţiuni introductive====
- ===Arbore binar plin===
- Un arbore binar este plin dacă nu există niciun nod intern la care mai putem lega un nod-copil nou(Toate nodurile, în afară de frunze, au număr maxim de copii).
+ =====3 Ce este o coadă?=====
- ===Arbore binar complet===
- Un arbore binar este complet dacă fiecare nivel(**cu posibila excepţie a ultimului**) este complet ocupat.
+ ====3.1 Definiție ====
+ O coadă este o structură de date ce modelează un buffer de tip First-In-First-Out (FIFO).Astfel, primul element introdus în coadă va fi și primul care va fi scos din coadă.
- ===Arbore binar perfect===
- Un arbore binar este perfect dacă este complet ocupat pe fiecare nivel(fără excepţii).
+ {{ :laboratoare:fifoex.png?300 |#poza coada#}}
- <note important>Puteţi întâlni **variante diferite** pentru ultimele trei definiţii şi, de aceea, pot apărea confuzii legate de semnificaţia termenilor **plin, complet şi perfect**. În cazul în care aveţi de lucrat cu arbori binari plini/compleţi/perfecţi, asiguraţi-vă că toată lumea se referă la aceleaşi noţiuni.</note>
-
-
- ====2.2 Reprezentare====
- Structura nodului unui arbore este urmatarea:
+ ====3.2 Operații cu cozi====
+ Definim structura astfel:
<file cpp>
- struct node {
- int data;
- struct node* left;
- struct node* right;
- };
+ struct queue{
+ int queue[size];
+ int rear = -1;
+ int front = 0;
+ }Q;
</file>
- ====2.3 Parcurgere====
- * **În adâncime**
- * **Preordine (RSD)**
- *Se parcurge rădăcina
- *Se parcurge subarborele stâng
- *Se parcurge subarborele drept
+ * **IsEmpty** - întoarce 0 dacă coada este goală;1 dacă are cel puțin un element.
<file cpp>
- void search_tree_preordine (tree *root) {
- if( root!=NULL){
- cout << root->data <<"\n";
- search_tree_preordine(root->left);
- search_tree_preordine(root->right);
- }
+ int Qempty(){
+ if(Q.front > Q.rear)
+ return 1;
+ return 0;
}
</file>
- * **Inordine (SRD)**
- *Se parcurge subarborele stâng
- *Se parcurge rădăcina
- *Se parcurge subarborele drept
+ * **Enqueue / Adăugarea** - adaugă un element (entitate) în coadă.Adăugarea se poate face doar la sfârșitul cozii.
<file cpp>
- void search_tree_inordine(tree *root){
- if( root!=NULL){
- search_tree_inordine(root->left);
- cout << root->data <<"\n";
- search_tree_inordine(root->right);
- }
+ void Qinsert(int item){
+ Q.rear++;
+ Q.queue[Q.rear] = item;
}
- </file>
- * **Postordine**
- *Se parcurge subarborele stâng
- *Se parcurge subarborele drept
- *Se parcurge rădăcina
+ </file>
+ * **Dequeue/ștergere** - șterge un element din coadă și îl returnează.Ștergerea se poate face doar la începutul cozii.
<file cpp>
- void search_tree_postordine(tree *root){
- if( root!=NULL){
- search_tree_postordine(root->left);
- search_tree_postordine(root->right);
- cout << root->data <<"\n";
+ int Qdelete(){
+ int item;
+ if( Qempty() ) //in acest caz, alegem o valoare de return
+ return -1; // ce NU poate fi confundata cu un element
+ //presupunem ca NU exista niciun element cu valoarea -1
+ else {
+ item = Q.queue[Q.front];
+ Q.front ++;
+ return item;
}
}
</file>
- * **În lățime**\\
- Această parcurgere reprezintă vizitarea "nivel cu nivel" a arborelui.\\
- De exemplu, vom obține j,f,k,a,h,z,d pentru arborele:
- tree
- ---
- j <--level 0
- / \
- f k <--level 1
- / \ \
- a h z <--level 2
- \
- d <--level 3
-
- \\
- Vom folosi acest tip de parcurgere pentru a evidenția:
- *ierarhia posturilor unei companii,
- *un arbore genealogic,
- *arborele unui joc (unde rădăcina reprezintă starea curentă,nivelul 1 posibilele mele mutări,nivelul 2 posibilele mutări ale adversarului,nivelul 3 posibilele mele mutari și tot așa).\\
- //Cum se realizează această implementare?//\\
- Vom folosi o //coadă// în care vom introduce rădăcina, apoi informația din stânga, apoi informația din dreapta, apoi coborând pe subarborele stâng procedăm la fel, iar după ne vom întoarce pe subarborele drept să aplicăm aceeași operație și tot așa până vom ajunge la frunze.\\
- Coada ne dă posibilitatea să scoatem prima informație,prima băgată =>ierarhia.\\
+ ====3.3 Clasificare====
- **Observatie!**\\
- Nodurile frunză nu au descendenți:nodul stâng și nodul drept pointează la NULL și nu trebuie adăugate în coadă.
+ * **Dequeue** - (sau coadă cu dublu acces) este o structură de tip coadă în care însă accesul (introducere/extragere de elemente) se poate realiza prin ambele capete.\\ \\
+ De cele mai multe ori sunt implementate folosind liste dublu înlănțuite.\\ \\
+ Dintr-un anume punct de vedere, se poate considera că atât stiva cât si coada clasică sunt specializări ale tipului abstract dequeue întrucât ambele se pot implementa folosind dequeue (și restrângând operațiile ce se realizează asupra sa).\\
+ {{ :laboratoare:deque.png?800 |# poza #
+ }}* **Priority queue** - Coada prioritară reprezintă un tip de coadă în care fiecare element are asociată o anume prioritate.\\
+ În aceste condiții,operațiile de bază asupra cozii devin:\\
+ * **Enqueue** - adaugă la coadă un element cu prioritatea specificată\\
+ * **Dequeue** - extrage elementul cu cea mai mare prioritate\\
+ * **Front** - examinează elementul cu cea mai mare prioritate fără a-l extrage din coadă.\\
- =====3 Arbori binari de căutare=====
- ====3.1 Definiție====
- Un arbore binar de căutare este un arbore binar care are în plus următoarele proprietăți:
- *Cheile stocate în noduri (informația utilă) aparțin unei mulțimi peste care există o relație de ordine.
- *Cheia dintr-un nod oarecare este //mai mare// decât cheile tuturor nodurilor din subarborele stâng si este //mai mică// decât cheile tuturor nodurilor ce compun subarborele drept.\\
+ =====4 Exerciții propuse =====
- Astfel,**valoarea maximă** dintr-un arbore binar de căutare se află în nodul din extremitatea dreaptă și se determină prin coborârea pe subarborele drept,iar **valoarea minimă** se află în nodul din extremitatea stângă.\\
- **Observatie!**\\
- Parcurgerea //inordine// produce o secvență ordonată crescător a cheilor din nodurile arborelui.\\
+ ==== 4.1 Exerciții clasice ====
+ 1. **FIFO buffer**
+ O coadă este o modalitate folositoare de a stoca date care provin in mod asincronic de la un microcontroler periferic, dar care nu pot fi citite imediat. Un bun exemplu ar fi stocarea de biți proveniți de la un UART (Universal asynchronous receiver/transmitter).\\
+ Un buffer FIFO stochează date pe principiul "primul venit - primul servit".Structura de stocare este un spațiu alăturat de memorie.\\
+ Datele sunt scrise in capul cozii și citite de la coadă.Dacă parcurgerea are loc de la coadă spre cap,buffer-ul este gol.Dar dacă parcurgerea este de la cap spre coadă, implementarea trebuie să defineascî dacă cea mai veche dată trebuie scoasă sau daca scrierea nu s-a terminat.
- ====3.2 Operații====
- * **Căutarea** unei chei într-un arbore binar de căutare este asemănătoare căutării binare:cheia căutată este comparată cu cheia din nodul curent (inițial nodul rădăcină).În funcție de rezultatul comparației apar trei cazuri:
- *acestea coincid => elementul a fost găsit
- *elementul căutat este mai mic decât cheia din nodul curent => căutarea continuă în subarborele stâng
- *elementul căutat este mai mare decât cheia din nodul curent => căutarea continuă in subarborele drept\\
- \\
- * **Înserarea** unui nod se face,în funcție de rezultatul comparației cheilor,în subarborele stâng sau drept.Dacă arborele este vid,se creează un nod care devine nodul rădăcină al arborelui.În caz contrar,cheia se inserează ca fiu stâng sau fiu drept al unui nod din arbore.\\
- \\
- * **Ștergerea** unui nod este o operație puțin mai complicată,întrucât presupune o rearanjare a nodurilor.Pentru eliminarea unui nod dintr-un arbore binar de căutare sunt posibile următoarele cazuri:
- *nodul de șters nu există => operația se consideră încheiată
- *nodul de șters nu are succesori => este o frunză
- *nodul de șters are un singur succesor => nodul se va șterge și se refac legăturile în arbore
- *nodul de șters are doi succesori => se parcurge arborele drept,căutându-se cea mai mică valoare,mai mare decât a nodului care trebuie șters și se refac legăturile cu acesta.\\
+ **Implementare generală**\\
+ 1) Definite structură:head,tail,size,buffer.\\
+ 2) Se realizează funcția de inițializare a cozii cu bufferul dat și marimea.\\
+ 3) Se realizează funcția de citire a celor nbytes din coadă;nr. citit de biți se returnează\\
+ 3.1 Pentru nbytes:se verifică dacă sunt date valabile (dacă coada e diferită de cap)\\
+ 3.2 Daca da, se ia un byte din buffer și se incrementează coada.\\
+ 3.3 Se verifica apoi dacă s-a terminat parcurgerea pentru a se reinițializa coada cu 0.\\
+ 3.4 În cazul în care nu sunt date valabile se returnează nr. de bytes.\\
+ 4) Se realizează funcția de scriere a celor nbytes din coadă.\\
+ 4.1 Pentru nbytes:inițial se verifică dacă este spațiu în buffer (coadă).\\
+ //[Bonus]// Generarea in mod random a datelor de intrare și prelucrarea lor cu ajutorul funcțiilor de mai sus;astfel valorile folosite vor fi introduse de la tastatură
- =====4 Aplicații=====
- ====4.1 Abstract Syntax Tree (Construcție Parse Tree)====
- {{ :laboratoare:compiler_structure.jpg |#poza compiler structure#}}
- \\
- In general,compilatoarele, indiferent de limbajul pe care îl tratează,parcurg un fisier sursă (sau mai multe),efectuează o serie de prelucrari asupra acestuia,pentru ca în final să obțină un set de intrucțiuni simple ce vor fi executate de procesor.\\
- Primul pas în compilarea unui program este parsarea codului sursă pentru a produce un Abstract Syntax Tree.Programele sunt scrise sub formă de text,deci vom avea o secvență de caractere,ceea ce e dificil de manipulat de un calculator.\\
- Aici intervine rolul unui:
- *lexer[5] care recunoaște șiruri ce aparțin unei gramatici strict prestabilite
- *parser care grupează șirurile structurat după o anumită regulă și adesea produc un AST\\
+ 2.Implementați pentru o structură de tip stivă funcţiile de inserare, extragere a unui nod, precum şi cele de afişare şi de semnalare a situaţiilor extreme (stivă goală au stivă plină).
- Să considerăm o expresie matematică:2 + 4*5 + 1*2*3\\
- Pentru a crea un arbore de parsare avem nevoie să folosim următoarele structuri:
- *stivă rezultat - folosită pentru a reține operanzii si rezultatele intermediare ale operațiilor parcurse până la un moment dat
- *stivă de operatori - folosit pentru a reține operatorii\\
- +
- / \
- 2 +
- / \
- * *
- / \ / \
- 4 5 1 *
- / \
- 2 3
+ ====4.2 Exercitii alternative - schelet de laborator====
+ Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab2-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.
+ Pentru acest laborator sunt două exerciții, primul cu stive și al doilea cu cozi. Fiecare are mai multe task-uri. Urmăriți cu atenție comentariile din fișierele sursă.
- \\
- \\
- <note tip>**Algoritmul presupune:**\\
- - Se parcurge expresia,termen cu termen (un termen poate fi operator sau operand)\\
- - Dacă termenul curent este operand\\
- - Aceasta se adaugă in stivă rezultat și se trece la termenul urmator\\
- - Daca termenul curent este operator ($)\\
- - Daca stiva operatorilor este vidă,se adaugă operatorul in stiva de operatori și se trece la termenul urmator\\
- - Dacă stiva nu este vidă:\\
- - Și operatorul curent are prioritate mai mare decât capul stivei (ex: crt este *,top(stivă) este +) \\
- *se adaugă operatorul în stivă și se trece la termenul următor\\
- - Și operatorul curent are prioritate mai mică decât capul stivei (ex: crt este +,top(stivă) este *)\\
- *Se scot din stivă rezultatele ultimelor două rezultate\\
- *Se scoate un operator din stiva operatorilor \\
- *Se creează un nou rezultat intermediar,aplicând operatorul extras pe cele două rezultate de mai sus\\
- *Acest rezultat intermediar se adaugă în stiva de rezultate\\
- *Se verifică condițiile de la $(se compară din nou același operator curent cu operatorul din vârful stivei).
- </note>
+ ===4.2.1 Linux===
+ Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
+ * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab2-skel.zip%%''
+ * ''%%unzip lab2-skel.zip%%''
- {{ :laboratoare:ast_stiva.jpg? |#poza mare arbori#}} \\
+ <code bash>
+ student@sda-ab-vm:~/Documents$ wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab2-skel.zip
+ --2017-03-02 20:45:55-- http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab2-skel.zip
+ Resolving elf.cs.pub.ro (elf.cs.pub.ro)... 141.85.227.116
+ Connecting to elf.cs.pub.ro (elf.cs.pub.ro)|141.85.227.116|:80... connected.
+ HTTP request sent, awaiting response... 200 OK
+ Length: 2368 (2,3K) [application/zip]
+ Saving to: ‘lab1-skel.zip’
- =====5.1. Exerciții - schelet de laborator====
- Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab4_arbori-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.
+ lab1-skel.zip 100%[===================>] 2,31K --.-KB/s in 0s
- === Linux===
- Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
+ 2017-03-02 20:45:56 (4,78 MB/s) - ‘lab1-skel.zip’ saved [2368/2368]
+
+ student@sda-ab-vm:~/Documents$ ls
+ lab1-skel.zip
+ student@sda-ab-vm:~/Documents$ unzip lab2-skel.zip
+ Archive: lab2-skel.zip
+ creating: lab2_stive-si-cozi/
+ creating: lab2_stive-si-cozi/1-stack/
+ inflating: lab2_stive-si-cozi/1-stack/Makefile
+ inflating: lab2_stive-si-cozi/1-stack/stack.c
+ creating: lab2_stive-si-cozi/2-queue/
+ inflating: lab2_stive-si-cozi/2-queue/Makefile
+ inflating: lab2_stive-si-cozi/2-queue/queue.
+ student@sda-ab-vm:~/Documents$ cd lab2_stive-si-cozi
+ student@sda-ab-vm:~/Documents/lab2_stive-si-cozi$ ls -l
+ total 0
+ drwxrwxrwx 1 student student 248 mar 5 15:57 1-stack
+ drwxrwxrwx 1 student student 248 mar 5 15:58 2-queue
+
+ student@sda-ab-vm:~/Documents/lab2_stive-si-cozi$ cd 1-stack
+ student@sda-ab-vm:~/Documents/lab2_stive-si-cozi/1-stack$ make
+ student@sda-ab-vm:~/Documents/lab2_stive-si-cozi/1-stack$ make run
+ </code>
+
+ Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi comanda ''%%make run%%''.
+
+ * Pentru exercițiul ''1-stack'', executabilul rezultat în urma comenzii ''%%make%%'' se numește ''%%stack%%''.
+ * Pentru exercițiul ''2-queue'', executabilul rezultat în urma comenzii ''%%make%%'' se numește ''%%queue%%''
+
+ ===4.2.2 Linux + Github===
+ [[https://github.com/mateiuli/sda-ab_laboratoare|Aici]] puteți găsi repository-ul de pe GitHub unde se află scheletul de cod pentru fiecare laborator.
- * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab4_arbori-skel.zip%%''
- * ''%%unzip lab4_arbori-skel.zip%%''
+ Dacă sunteți familiari cu git puteți clona repo-ul local folosind comanda ''%%git clone https://github.com/mateiuli/sda-ab_laboratoare%%''.
+ ====4.3 Opţional - de interviu====
- Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi comanda ''%%make run%%'' sau ''%%./tree%%''.
- =====5.2. Exerciții====
- - Se dă un vector cu n întregi. Scrieţi o funcţie care să creeze un arbore binar de căutare cu valorile din vector.
- - Se dă un arbore binar ce stochează întregi. Scrieţi o funcţie care verifică dacă arborele este binar de căutare.
- - Se dă un arbore binar de căutare ce stochează întregi. Scrieţi o funcţie care verifică dacă o valoare dată se află în arbore(căutare).
- - Acelaşi arbore – inserare(şi să rămână arbore de căutare)
- - Acelaşi arbore – ştergere(şi să rămână arbore de căutare)
+ 1. Implementaţi o stivă folosind două cozi.
- Puteţi testa primele 5 exerciţii în acelaşi program.
+ 2. Implementaţi o coadă folosind două stive.(utilizarea apelurilor recursive ale unor funcţii se contorizează ca folosirea unei stive)
- ===Problemă întreagă===
- * Să se realizeze stocul unei farmacii,știind că informațiile pentru medicamentele unei farmacii sunt:nume medicament,preț,cantitate,data primirii,data expirării.
+ 3. Implementaţi o stivă cu valori întregi şi o funcţie care obţine valoarea maximă din stivă. Pentru interviu se cere ca funcţia să aibă complexitate de timp constantă => O(1).
- Evidența medicamentelor se ține cu un program care are drept structură de date un arbore de căutare după nume medicament.
- Să se scrie programul care execută următoarele operații:
- *Creează arborele de căutare
- *Caută un nod după câmpul nume medicament și actualizează câmpurile de informare
- *Tipăreste medicamentele în ordine lexicografică
- *Elimină un nod identificat prin nume medicament
- *Creează un arbore de căutare cu medicamentele care au data de expirare mai "mică" decât o dată specificată de la terminal
- *Determinați greutatea(fie greutatea = numărul de frunze) arborelui și verificați dacă este binar complet sau nu
+ 4. Se dă un vector cu n întregi și un număr k. Aflați valoarea maxima pentru fiecare grupare de k numere de pe poziții consecutive.
- ===Probleme de interviu===
- * Se dă V(un vector de n întregi) şi P(un vector de taţi de lungime n). Verificaţi dacă se poate construi un arbore binar de căutare cu valorile din V şi legăturile copil-părinte din P.
- * Fie un arbore binar perfect cu înălţimea H. Creaţi (H + 1) vectori/liste, câte unul/una pentru fiecare nivel din arbore. Afişaţi fiecare nivel(parcurgerea în lăţime) cu ajutorul vectorilor/listelor.
- * Găsiţi cel mai apropiat strămoş comun pentru două noduri dintr-un arbore binar.
- * Se dau doi arbori binari cu întregi, A1 şi A2, iar A1 conţine mult mai multe noduri decât A2. Verificaţi dacă A2 arată la fel ca un subarbore din A1.(“Arată la fel”, adică valorile întregi sunt aceleaşi)
+ 5. Se dă un vector cu datele pentru n clienţi la un server. Pentru fiecare client, datele cunoscute sunt ora la care se conectează şi ora la care se deconectează. Aflaţi numărul maxim de clienţi conectaţi în acelaşi timp la server. Pentru interviu se cere complexitate de timp O(n).
</pre>text/html2018-02-25T22:42:44+00:00Anonymous (anonymous@undisclosed.example.com)Laborator 05: Arbori
http://elf.cs.pub.ro/sda-ab/wiki/laboratoare/laborator-05?rev=1519591364&do=diff
<pre>
@@ -1,230 +1,275 @@
- ====== Laborator 05: Introducere în teoria grafurilor ======
+ ====== Laborator 05: Arbori ======
\\
=====1 Obiectivele laboratorului=====
- *Definirea structurii și elementelor unui graf neorientat
- *Definirea structurii și elementelor unui graf orientat
+ *Înțelegerea noțiunii de arbore și a structurii unui arbore binar
+ *Citirea unei expresii matematice și construirea arborelui binar asociat
+ *Înțelegerea structurii și proprietăților unui arbore binar de căutare
+ *Realizarea diferitelor operații folosint arborii binari de căutare
+ \\
+ ===== Noţiuni introductive=====
+ ===Definiţie generală===
- =====2 Grafuri neorientate=====
- ====2.1 Definiție====
- Un **graf neorientat** este o pereche ordonată de multimi(X,U),unde:
- *X este o mulțime finită și nevidă de elemente numite **noduri** sau **vârfuri**
- *U este o mulțime de perechi neordonate din X,numite **muchii**
+ Un arbore poate fi definit ca: structură de date ce conţine noduri şi legături, fără circularitate. Un arbore poate fi văzut ca o extindere de la **lista simplu înlănţuită şi necirculară**, **eliminând** condiţia de a exista **o singură legătură** ce pleacă dintr-un nod, adică maxim un singur nod "următor".
- ====2.2 Structură====
+ ===Rădăcină(Root)===
+ Numim rădăcină primul nod al arborelui(echivalentul capului de listă).
- Un graf are următoarele elemente:
- * **Mulțimea nodurilor X** - Mulțimea tuturor nodurilor grafului
- * **Multimea muchiilor U** - Mulțimea tuturor muchiilor grafului
- * **Gradul nodului** - numărul de muchii formate cu ajutorul nodului respectiv
- * **Nod izolat** - Un nod ce nu formează nici-o muchie
- * **Noduri terminale** - Un nod ce formează o singură muchie
- * **Noduri adiacente** - Noduri intre care există o muchie
- * **Nod si muchie incidente** - Nodul face parte dintr-o muchie
+ ===Copil - Părinte(Child - Parent)===
+ Nodul P este părintele nodului C dacă are legătură către C(similar, C este copilul lui P).
+ * Pot apărea şi alţi termeni pentru relaţia dintre noduri: fraţi(siblings), veri(cousins) etc.
- <note important>Ce relaţie există între suma gradelor tuturor vârfurilor dintr-un graf neorientat şi numărul de muchii?</note>
- <note important>Într-un graf **complet**, oricare două noduri sunt adiacente. Câte muchii are un astfel de graf?</note>
- \\
- \\
+ <note tip>Rădăcina NU poate fi nod-copil.</note>
- ====2.3 Reprezentare ====
- * **Matricea de adiacență** - este o matrice **a** cu **n** linii și **n** coloane,în care elementele **a[i,j]** se definesc astfel:
- *a[i,j] = 1 ,dacă ∃ muchia [i,j] cu i≠j
- *a[i,j] = 0 ,în caz contrar
- * **Lista de adiacență** - este un tablou de liste egal cu numarul de varfuri;dacă există o muchie intre nodul curent si un alt nod,atunci acesta se trece în listă
- * **Vectorul de muchii** - mulțime ce conține toate muchiile grafului
+ ===Gradul(Degree)===
+ Gradul unui nod este egal cu numărul de copii ai acestuia.
- {{ :laboratoare:graf1.jpg?500 |}}
+ ===Frunză(Leaf) şi nod intern/extern(internal/external)===
+ Numim frunză un nod fără copii(**nod terminal**).
+ * Frunzele se mai numesc **noduri externe**.
+ * Nodurile care au copii se mai numesc **noduri interne**.
- Având lista de adiacentă:
- * **A**:B→C→D
- * **B**:A→D→E
- * **C**:A→D
- * **D**:A→B→C→D→E
- * **E**:B→D
+ ===Urmaş(Descendant)===
+ Nodul U este urmaşul nodului S dacă putem "coborî"(mergând numai de la părinte la copil) de la S la U.
- <note importante>
- Un **graf parțial** este un graf obținut din graful inițial prin eliminarea uneia sau mai multor muchii
- </note>
+ ===Strămoş(Ancestor)===
+ Nodul S este strămoşul nodului U dacă U este urmaşul lui S(putem "urca" de la U la S).
+ <note tip>Rădăcina este strămoşul tuturor celorlalte noduri din arbore.</note>
+ ===Înălţime(Height)===
+ Definim înălţimea unui nod egală cu numărul de legături pe care "coborâm" de la acel nod la cea mai îndepărtată frunză.
+ <note tip>înălţimea arborelui = înălţimea rădăcinii</note>
- <note importante>
- Un **subgraf** este un graf obținut din graful inițial prin eliminarea unui număr de noduri impreună cu muchiile formate cu acele noduri
- </note>
+ ===Adâncime(Depth)===
+ Definim adâncimea unui nod egală cu cu numărul de legături pe care "coborâm" de la rădăcină la nodul respectiv.
+ <note tip>adâncimea rădăcinii = 0</note>
- <note importante>
- Se numește **lanț** într-un graf,o succesiune de vârfuri L={v1,v2,...,vk},cu proprietatea că oricare două vârfuri consecutive sunt adiacente,adică există o muchie între acestea.
+ ===Nivel(Level)===
+ Definim nivelul unui nod egal cu 1 + adâncimea.
+ ===Pădure(Forest)===
+ Numim pădure o mulţime de N(de obicei N >= 2) arbori disjuncţi(care nu au noduri comune).
- Se numeşte **lanţ elementar** un lanţ în care nu se repetă vârfuri.
+ ===Vector de taţi(Parent array/vector)===
- Se numeşte **lanţ simplu** un lanţ în care nu se repetă muchii.
+ Vectorul de taţi reprezintă o soluţie ieftină(d.p.d.v. al memoriei) de reprezentare a unui arbore atunci când nodurile pot avea un număr diferit de legături. În acest caz, ne putem folosi de faptul că **fiecare nod-copil are un singur părinte**, indiferent de câţi copii are părintele respectiv. **Rădăcina** arborelui este singura **excepţie**.
- Se numeşte **ciclu** un lanţ simplu pentru care primul şi ultimul vârf coincid.
+ <file cpp>
+ //fie n = nr. de noduri
+ //nodurile sunt numerotate de la 0 la n-1
+ //fie doua noduri numerotate cu indicii A si B
+ Parent[A] = B; // Parintele nodului A este nodul B
+ //fie Root nodul radacina
+ Parent[Root] = -1; //nu exista nod numerotat cu -1
+ </file>
- Se numeşte **ciclu elementar** un ciclu în care nu se repetă vârfuri(excepţie primul şi ultimul).
- </note>
+ =====2 Arbori binari=====
+ ====2.1 Definiție====
+ Un arbore binar este alcătuit din noduri, unde fiecare nod conține un pointer către "stânga" și un pointer către "dreapta" și un element de tip dată.\\
+ Pointer-ul "root (rădăcină)" reprezintă adresa celui mai de sus nod din arbore.Pointerii din "stânga" și "drepta" punctează în mod recursiv, pe fiecare aprte, la //subarbori// mai mici.\\
+ Arborii sunt folosiți in general pentru a modela o ierarhie de elemente.Astfel,fiecare element **(nod)** poate deține un număr de unul sau mai mulți descentenți,iar în acest caz nodul este numit **părinte** al nodului descendent.\\
+ Un nod fără descendenți este un **nod terminal**, sau **nod frunză**.\\
+ {{ :laboratoare:arborebinar.png?400 |
+ # poza arbore#}}
- =====3 Grafuri orientate=====
- ====3.1 Definiție====
- Un **graf orientat** este o pereche ordonată de mulțimi G={X,U},unde:
- *X este o mulțime finită și nevidă numită mulțimea nodurilor(vârfurilor)
- *U este o mulțime formată din **perechi ordonate** de elemente ale lui X,numită mulțimea arcelor
+ ====Alte noţiuni introductive====
+ ===Arbore binar plin===
+ Un arbore binar este plin dacă nu există niciun nod intern la care mai putem lega un nod-copil nou(Toate nodurile, în afară de frunze, au număr maxim de copii).
- ====3.2 Structură====
- Într-un graf orientat, distingem:
- * **gradul interior/intern** al unui nod: numărul de arce care intră în nod
- * **gradul exterior/extern** al unui nod: numărul de arce care ies din nod
+ ===Arbore binar complet===
+ Un arbore binar este complet dacă fiecare nivel(**cu posibila excepţie a ultimului**) este complet ocupat.
- <note important>Ce relaţie există între suma gradelor exterioare, suma gradelor interioare şi numărul de arce?</note>
+ ===Arbore binar perfect===
+ Un arbore binar este perfect dacă este complet ocupat pe fiecare nivel(fără excepţii).
- ====3.3 Reprezentare====
- **Matricea de adiacență** - este o matrice **a** cu **n** linii și **n** coloane,în care elementele **a[i,j]** se definesc astfel:
- *a[i,j] = 1 ,dacă ∃ arcul (i,j) în mulțimea U
- *a[i,j] = 0 ,în caz contrar
+ <note important>Puteţi întâlni **variante diferite** pentru ultimele trei definiţii şi, de aceea, pot apărea confuzii legate de semnificaţia termenilor **plin, complet şi perfect**. În cazul în care aveţi de lucrat cu arbori binari plini/compleţi/perfecţi, asiguraţi-vă că toată lumea se referă la aceleaşi noţiuni.</note>
- {{ :laboratoare:graf2.png?400 |}}
+ ====2.2 Reprezentare====
+ Structura nodului unui arbore este urmatarea:
+ <file cpp>
+ struct node {
+ int data;
+ struct node* left;
+ struct node* right;
+ };
+ </file>
+
+ ====2.3 Parcurgere====
+ * **În adâncime**
+ * **Preordine (RSD)**
+ *Se parcurge rădăcina
+ *Se parcurge subarborele stâng
+ *Se parcurge subarborele drept
+ <file cpp>
+ void search_tree_preordine (tree *root) {
+ if( root!=NULL){
+ cout << root->data <<"\n";
+ search_tree_preordine(root->left);
+ search_tree_preordine(root->right);
+ }
+ }
+ </file>
+ * **Inordine (SRD)**
+ *Se parcurge subarborele stâng
+ *Se parcurge rădăcina
+ *Se parcurge subarborele drept
+ <file cpp>
+ void search_tree_inordine(tree *root){
+ if( root!=NULL){
+ search_tree_inordine(root->left);
+ cout << root->data <<"\n";
+ search_tree_inordine(root->right);
+ }
+ }
+ </file>
+ * **Postordine**
+ *Se parcurge subarborele stâng
+ *Se parcurge subarborele drept
+ *Se parcurge rădăcina
+ <file cpp>
+ void search_tree_postordine(tree *root){
+ if( root!=NULL){
+ search_tree_postordine(root->left);
+ search_tree_postordine(root->right);
+ cout << root->data <<"\n";
+ }
+ }
+ </file>
+ * **În lățime**\\
+ Această parcurgere reprezintă vizitarea "nivel cu nivel" a arborelui.\\
+ De exemplu, vom obține j,f,k,a,h,z,d pentru arborele:
+ tree
+ ---
+ j <--level 0
+ / \
+ f k <--level 1
+ / \ \
+ a h z <--level 2
+ \
+ d <--level 3
+
\\
+ Vom folosi acest tip de parcurgere pentru a evidenția:
+ *ierarhia posturilor unei companii,
+ *un arbore genealogic,
+ *arborele unui joc (unde rădăcina reprezintă starea curentă,nivelul 1 posibilele mele mutări,nivelul 2 posibilele mutări ale adversarului,nivelul 3 posibilele mele mutari și tot așa).\\
- Matricea **vârfuri-arce** este o matrice **B** cu n = |X| linii și m = |U| coloane,în care fiecare element **b[i,j]** este:
- * **1** ,dacă nodul i este o extremitate inițială a arcului
- * **-1** ,dacă nodul i este o extremitate finală a arcului
- * **0** ,dacă nodul i nu este o extremitate a arcului
+ //Cum se realizează această implementare?//\\
+ Vom folosi o //coadă// în care vom introduce rădăcina, apoi informația din stânga, apoi informația din dreapta, apoi coborând pe subarborele stâng procedăm la fel, iar după ne vom întoarce pe subarborele drept să aplicăm aceeași operație și tot așa până vom ajunge la frunze.\\
+ Coada ne dă posibilitatea să scoatem prima informație,prima băgată =>ierarhia.\\
- {{ :laboratoare:graf3.png?300 |}}
+ **Observatie!**\\
+ Nodurile frunză nu au descendenți:nodul stâng și nodul drept pointează la NULL și nu trebuie adăugate în coadă.
- =====4 Parcurgerea grafurilor=====
- ====4.1 Parcurgerea în lățime====
+ =====3 Arbori binari de căutare=====
+ ====3.1 Definiție====
+ Un arbore binar de căutare este un arbore binar care are în plus următoarele proprietăți:
+ *Cheile stocate în noduri (informația utilă) aparțin unei mulțimi peste care există o relație de ordine.
+ *Cheia dintr-un nod oarecare este //mai mare// decât cheile tuturor nodurilor din subarborele stâng si este //mai mică// decât cheile tuturor nodurilor ce compun subarborele drept.\\
- Parcurgerea în lățime **(Breadth-First-Search -BFS)** este o metodă ce presupune vizitarea nodurilor în următoarea ordine:
- * nodul sursă (considerat a fi pe nivelul 0)
- * vecinii nodului sursă (reprezentând nivelul 1)
- * vecinii încă nevizitați ai nodurilor de pe nivelul 1 (reprezentând nivelul 2)
- * ș.a.m.d
-
-
- ===4.1.1 Implementare===
-
- Pe masură ce algoritmul avansează,se colorează nodurile în felul următor:
- * **alb** - nodul este nedescoperit încă
- * **gri** - nodul a fost descoperit și este în curs de procesare
- * **negru** - procesarea nodului s-a încheiat
- Se păstrează informațiile despre distanța până la nodul sursă.
- Se obține arborele BFS
+ Astfel,**valoarea maximă** dintr-un arbore binar de căutare se află în nodul din extremitatea dreaptă și se determină prin coborârea pe subarborele drept,iar **valoarea minimă** se află în nodul din extremitatea stângă.\\
+ **Observatie!**\\
+ Parcurgerea //inordine// produce o secvență ordonată crescător a cheilor din nodurile arborelui.\\
+ ====3.2 Operații====
+ * **Căutarea** unei chei într-un arbore binar de căutare este asemănătoare căutării binare:cheia căutată este comparată cu cheia din nodul curent (inițial nodul rădăcină).În funcție de rezultatul comparației apar trei cazuri:
+ *acestea coincid => elementul a fost găsit
+ *elementul căutat este mai mic decât cheia din nodul curent => căutarea continuă în subarborele stâng
+ *elementul căutat este mai mare decât cheia din nodul curent => căutarea continuă in subarborele drept\\
+ \\
+ * **Înserarea** unui nod se face,în funcție de rezultatul comparației cheilor,în subarborele stâng sau drept.Dacă arborele este vid,se creează un nod care devine nodul rădăcină al arborelui.În caz contrar,cheia se inserează ca fiu stâng sau fiu drept al unui nod din arbore.\\
\\
- Pentru implementarea BFS se utilizează o coadă (Q) în care inițial se află doar nodul sursă.Se vizitează pe rând vecinii acestui nod și se pun și ei în coadă.În momentul în care nu mai există vecini nevizitați,nodul sursă este scos din coadă.
+ * **Ștergerea** unui nod este o operație puțin mai complicată,întrucât presupune o rearanjare a nodurilor.Pentru eliminarea unui nod dintr-un arbore binar de căutare sunt posibile următoarele cazuri:
+ *nodul de șters nu există => operația se consideră încheiată
+ *nodul de șters nu are succesori => este o frunză
+ *nodul de șters are un singur succesor => nodul se va șterge și se refac legăturile în arbore
+ *nodul de șters are doi succesori => se parcurge arborele drept,căutându-se cea mai mică valoare,mai mare decât a nodului care trebuie șters și se refac legăturile cu acesta.\\
- <file cpp>
- Pentru fiecare nod u din graf
- {
- culoare[u]=alb
- d[u] = infinit //in d se retine distanta pana la nodul sursa
- p[u] = null //
- }
-
- culoare[sursă]=gri
- d[sursă]=0
- enqueue(Q,sursă) //punem nodul sursă în coada Q
-
- Cât timp coada Q nu este vidă
- {
- v=dequeue(Q) //extragem nodul v din coadă
- pentru fiecare u dintre vecinii lui v
- dacă culoare[u] == alb
- {
- culoare[u] = gri
- p[u] = v
- d[u] = d[v] + 1
- enqueue(Q,u) //adăugăm nodul u în coadă
- }
- culoare[v] = negru //am terminat explorarea vecinilor lui v
- }
-
-
- </file>
+ =====4 Aplicații=====
+ ====4.1 Abstract Syntax Tree (Construcție Parse Tree)====
+ {{ :laboratoare:compiler_structure.jpg |#poza compiler structure#}}
\\
- **Exemplu**
- {{ :laboratoare:bfs.jpg |}}
+ In general,compilatoarele, indiferent de limbajul pe care îl tratează,parcurg un fisier sursă (sau mai multe),efectuează o serie de prelucrari asupra acestuia,pentru ca în final să obțină un set de intrucțiuni simple ce vor fi executate de procesor.\\
+ Primul pas în compilarea unui program este parsarea codului sursă pentru a produce un Abstract Syntax Tree.Programele sunt scrise sub formă de text,deci vom avea o secvență de caractere,ceea ce e dificil de manipulat de un calculator.\\
+ Aici intervine rolul unui:
+ *lexer[5] care recunoaște șiruri ce aparțin unei gramatici strict prestabilite
+ *parser care grupează șirurile structurat după o anumită regulă și adesea produc un AST\\
- ====4.2 Parcurgerea în adâncime====
- Parcurgea în adâncime **(Depth-First-Search -DFS)** presupune explorarea nodurilor în următoarea ordine:
- *Nodul sursă
- *Primul vecin nevizitat al nodului sursă (îl numim //V1//)
- *Primul vecin nevizitat al lui //V1// (îl numim //V2//)
- *ș.a.m.d
- *În momentul în care am epuizat vecinii unui nod //Vn//, continuăm cu următorul vecin nevizitat al nodului anterior,//Vn-1//
+ Să considerăm o expresie matematică:2 + 4*5 + 1*2*3\\
+ Pentru a crea un arbore de parsare avem nevoie să folosim următoarele structuri:
+ *stivă rezultat - folosită pentru a reține operanzii si rezultatele intermediare ale operațiilor parcurse până la un moment dat
+ *stivă de operatori - folosit pentru a reține operatorii\\
+ +
+ / \
+ 2 +
+ / \
+ * *
+ / \ / \
+ 4 5 1 *
+ / \
+ 2 3
- Această metoda de parcurgere pune prioritate pe explorarea **în adâncime** (pe distanțe tot mai mari față de nodul sursă).
- ====4.2.1 Implementare====
+ \\
+ \\
+ <note tip>**Algoritmul presupune:**\\
+ - Se parcurge expresia,termen cu termen (un termen poate fi operator sau operand)\\
+ - Dacă termenul curent este operand\\
+ - Aceasta se adaugă in stivă rezultat și se trece la termenul urmator\\
+ - Daca termenul curent este operator ($)\\
+ - Daca stiva operatorilor este vidă,se adaugă operatorul in stiva de operatori și se trece la termenul urmator\\
+ - Dacă stiva nu este vidă:\\
+ - Și operatorul curent are prioritate mai mare decât capul stivei (ex: crt este *,top(stivă) este +) \\
+ *se adaugă operatorul în stivă și se trece la termenul următor\\
+ - Și operatorul curent are prioritate mai mică decât capul stivei (ex: crt este +,top(stivă) este *)\\
+ *Se scot din stivă rezultatele ultimelor două rezultate\\
+ *Se scoate un operator din stiva operatorilor \\
+ *Se creează un nou rezultat intermediar,aplicând operatorul extras pe cele două rezultate de mai sus\\
+ *Acest rezultat intermediar se adaugă în stiva de rezultate\\
+ *Se verifică condițiile de la $(se compară din nou același operator curent cu operatorul din vârful stivei).
+ </note>
- Spre deosebire de BFS, DFS utilizează o **stivă** în loc de o coadă. Putem defini o stivă sau ne putem folosi de **stiva compilatorului**, prin apeluri **recursive**.
- <file cpp>
- funcţie pasDFS(curent)
- {
- pentru fiecare u dintre vecinii nodului curent
- dacă culoare[u] == alb
- {
- culoare[u] = gri
- p[u] = curent
- d[u] = d[curent] + 1
- pasDFS(u); //adăugăm nodul u în "stivă" şi începem explorarea
- }
- culoare[curent] = negru //am terminat explorarea vecinilor nodului curent
- //ieşirea din funcţie este echivalentă cu eliminarea unui element din stivă
- }
- Pentru fiecare nod u din graf
- {
- culoare[u]=alb
- d[u] = infinit //in d se retine distanta pana la nodul sursa
- p[u] = null
- }
- culoare[sursă] = gri;
- d[sursă] = 0;
+ {{ :laboratoare:ast_stiva.jpg? |#poza mare arbori#}} \\
- //se apelează iniţial pasDFS(sursă)
- </file>
- {{ :laboratoare:df1.jpg |}}
-
- ===== 5. Exerciţii =====
- Implementaţi, pentru fiecare cerinţă, câte o funcţie care:
- - creează matricea de adiacenţă pentru un graf neorientat cu N noduri, folosindu-se de o listă(sau o matrice cu 2 coloane) de muchii(la alegere - muchiile citite în funcţie sau primite printr-un parametru).
- - calculează gradul fiecărui nod. Afişaţi numărul de noduri izolate şi numărul de noduri terminale.
- - primeşte un şir de noduri şi verifică dacă acesta poate reprezenta un lanţ.
- - primeşte un şir de noduri şi afişează matricea de adiacenţă a subgrafului format cu nodurile respective
- - afişează matricea de adiacenţă a unui graf orientat construit astfel:
- * graful orientat are atâtea arce câte muchii are graful neorientat
- * există arc în graful orientat între două noduri daca şi numai dacă există muchie între aceleaşi noduri în graful neorientat.
- * Extra - câte astfel de grafuri orientate pot fi formate?
-
- Cerinţele 2, 3, 4 şi 5 se vor folosi de matricea de adiacenţă a grafului de la cerinţa 1.
-
- ====5.1. Exerciții - schelet de laborator====
- Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab5_grafuri-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.
+ =====5.1. Exerciții - schelet de laborator====
+ Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab4_arbori-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.
=== Linux===
Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
- * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab5_grafuri-skel.zip%%''
- * ''%%unzip lab5_grafuri-skel.zip%%''
+ * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab4_arbori-skel.zip%%''
+ * ''%%unzip lab4_arbori-skel.zip%%''
+
+ Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi comanda ''%%make run%%'' sau ''%%./tree%%''.
+ =====5.2. Exerciții====
+ - Se dă un vector cu n întregi. Scrieţi o funcţie care să creeze un arbore binar de căutare cu valorile din vector.
+ - Se dă un arbore binar ce stochează întregi. Scrieţi o funcţie care verifică dacă arborele este binar de căutare.
+ - Se dă un arbore binar de căutare ce stochează întregi. Scrieţi o funcţie care verifică dacă o valoare dată se află în arbore(căutare).
+ - Acelaşi arbore – inserare(şi să rămână arbore de căutare)
+ - Acelaşi arbore – ştergere(şi să rămână arbore de căutare)
- Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi comanda ''%%make run%%'' sau ''%%./graph%%''.
+ Puteţi testa primele 5 exerciţii în acelaşi program.
- ====De interviu====
- * Plecând dintr-un nod K, verificaţi dacă puteţi găsi un ciclu în graf.
- * Verificaţi dacă există un lanţ care uneşte nodurile sursă(S) şi destinaţie(D). Dacă există, cum puteţi găsi lanţul cu număr minim de muchii?
- * Verificaţi dacă există un lanţ **hamiltonian** în graf.
- * Verificaţi dacă există un lanţ **eulerian** în graf.
- * Verificaţi dacă o muchie dată (A, B) este un **pod** pentru drumul de la S la D.
+ ===Problemă întreagă===
+ * Să se realizeze stocul unei farmacii,știind că informațiile pentru medicamentele unei farmacii sunt:nume medicament,preț,cantitate,data primirii,data expirării.
- Un lanţ hamiltonian este un lanţ elementar(nu se repetă nodurile) care trece prin fiecare nod.
+ Evidența medicamentelor se ține cu un program care are drept structură de date un arbore de căutare după nume medicament.
+ Să se scrie programul care execută următoarele operații:
+ *Creează arborele de căutare
+ *Caută un nod după câmpul nume medicament și actualizează câmpurile de informare
+ *Tipăreste medicamentele în ordine lexicografică
+ *Elimină un nod identificat prin nume medicament
+ *Creează un arbore de căutare cu medicamentele care au data de expirare mai "mică" decât o dată specificată de la terminal
+ *Determinați greutatea(fie greutatea = numărul de frunze) arborelui și verificați dacă este binar complet sau nu
- Un lanţ eulerian este un lanţ simplu(nu se repetă muchiile) care trece prin fiecare muchie.
+ ===Probleme de interviu===
+ * Se dă V(un vector de n întregi) şi P(un vector de taţi de lungime n). Verificaţi dacă se poate construi un arbore binar de căutare cu valorile din V şi legăturile copil-părinte din P.
+ * Fie un arbore binar perfect cu înălţimea H. Creaţi (H + 1) vectori/liste, câte unul/una pentru fiecare nivel din arbore. Afişaţi fiecare nivel(parcurgerea în lăţime) cu ajutorul vectorilor/listelor.
+ * Găsiţi cel mai apropiat strămoş comun pentru două noduri dintr-un arbore binar.
+ * Se dau doi arbori binari cu întregi, A1 şi A2, iar A1 conţine mult mai multe noduri decât A2. Verificaţi dacă A2 arată la fel ca un subarbore din A1.(“Arată la fel”, adică valorile întregi sunt aceleaşi)
- Spunem că muchia (A, B) este pod pentru drumul de la S la D dacă orice lanţ care duce de la S la D trece prin muchia (A, B).
</pre>text/html2018-02-25T22:43:25+00:00Anonymous (anonymous@undisclosed.example.com)Laborator 06: Introducere în teoria grafurilor
http://elf.cs.pub.ro/sda-ab/wiki/laboratoare/laborator-06?rev=1519591405&do=diff
<pre>
@@ -1,139 +1,230 @@
- ====== Laborator 06: Arbori minimi de acoperire ======
+ ====== Laborator 06: Introducere în teoria grafurilor ======
- ===== 1. Obiective laborator=====
- * Înțelegerea conceptului de arbore minim de acoperire
- * Înțelegerea implementării algoritmilor care determină acest arbore
- * Înțelegere aplicațiilor practice în:
- * rețele de calculatoare: obținerea unui cost redus la interconectarea mai multor stații (ex: protocolul STP folosit în LAN-uri)
- * prelucrarea de imagine: segmentarea cadrelor (ex: folosită în analiza medicală)
- * în clustere: determinarea unei topologii de comunicare, în cazul în care topologia nu era una regulată(arbore, inel)
+ \\
+ =====1 Obiectivele laboratorului=====
+ *Definirea structurii și elementelor unui graf neorientat
+ *Definirea structurii și elementelor unui graf orientat
- {{ :laboratoare:segmentation.jpg?600 | Segmentarea de imagini}}
- ===== 2. Introducere =====
- ==== 2.1 Conexitate în grafuri ====
+ =====2 Grafuri neorientate=====
+ ====2.1 Definiție====
+ Un **graf neorientat** este o pereche ordonată de multimi(X,U),unde:
+ *X este o mulțime finită și nevidă de elemente numite **noduri** sau **vârfuri**
+ *U este o mulțime de perechi neordonate din X,numite **muchii**
- ===Componentă conexă===
- O componentă conexă a unui graf **neorientat** este un subgraf cu următoarele proprietăţi:
- - oricare două noduri din acest subgraf sunt **conectate**(există un lanţ între ele)
- - orice nod din acest subgraf **NU este conectat** cu niciun nod din afara subgrafului(nodurile din componentă fac muchii numai cu alte noduri din componentă)
+ ====2.2 Structură====
- <note important>Orice graf neorientat are cel puţin o componentă conexă.</note>
+ Un graf are următoarele elemente:
+ * **Mulțimea nodurilor X** - Mulțimea tuturor nodurilor grafului
+ * **Multimea muchiilor U** - Mulțimea tuturor muchiilor grafului
+ * **Gradul nodului** - numărul de muchii formate cu ajutorul nodului respectiv
+ * **Nod izolat** - Un nod ce nu formează nici-o muchie
+ * **Noduri terminale** - Un nod ce formează o singură muchie
+ * **Noduri adiacente** - Noduri intre care există o muchie
+ * **Nod si muchie incidente** - Nodul face parte dintr-o muchie
- ===Graf neorientat conex===
- Un graf neorientat este numit **conex** dacă are o singură **componentă conexă**.
+ <note important>Ce relaţie există între suma gradelor tuturor vârfurilor dintr-un graf neorientat şi numărul de muchii?</note>
+ <note important>Într-un graf **complet**, oricare două noduri sunt adiacente. Câte muchii are un astfel de graf?</note>
+ \\
+ \\
- <note tip>Putem explora toate nodurile dintr-un graf neorientat conex dintr-o singură parcurgere a grafului(DFS sau BFS).</note>
+ ====2.3 Reprezentare ====
+ * **Matricea de adiacență** - este o matrice **a** cu **n** linii și **n** coloane,în care elementele **a[i,j]** se definesc astfel:
+ *a[i,j] = 1 ,dacă ∃ muchia [i,j] cu i≠j
+ *a[i,j] = 0 ,în caz contrar
+ * **Lista de adiacență** - este un tablou de liste egal cu numarul de varfuri;dacă există o muchie intre nodul curent si un alt nod,atunci acesta se trece în listă
+ * **Vectorul de muchii** - mulțime ce conține toate muchiile grafului
- ===Graf orientat slab conex===
- Fie graful neorientat asociat unui graf orientat obţinut prin înlocuirea tuturor **arcelor** cu **muchii**. Atunci un graf orientat este **slab conex** dacă graful neorientat asociat acestuia este conex.
+ {{ :laboratoare:graf1.jpg?500 |}}
- ===Graf orientat tare conex===
- Un graf orientat este **tare conex** dacă există drum între oricare două noduri, atât într-un sens, cât şi în celelalt.
+ Având lista de adiacentă:
+ * **A**:B→C→D
+ * **B**:A→D→E
+ * **C**:A→D
+ * **D**:A→B→C→D→E
+ * **E**:B→D
- Se pot defini similar componentele slab conexă şi tare conexă.
+ <note importante>
+ Un **graf parțial** este un graf obținut din graful inițial prin eliminarea uneia sau mai multor muchii
+ </note>
- ==== 2.2 Arborele văzut ca graf ====
- Folosind noţiunile de mai sus, putem spune că un arbore este un graf(pentru simplitate, fie neorientat) **conex** şi cu număr minim de muchii, prin urmare, **aciclic**.
- ==== 2.3 Arbore vs. pădure de acoperire ====
- Pentru un graf neorientat, construirea unui arbore de acoperire(nu neapărat de cost minim) presupune construirea unui arbore care să fie **graf parţial**(să **acopere** toate nodurile).
- Acest lucru este posibil numai dacă graful este **conex**. În caz contrar, se poate construi câte un arbore de acoperire pentru fiecare **componentă conexă** a grafului, spunând că se construieşte o **pădure** de acoperire pentru graf.
+ <note importante>
+ Un **subgraf** este un graf obținut din graful inițial prin eliminarea unui număr de noduri impreună cu muchiile formate cu acele noduri
+ </note>
- ==== 2.4 Arbore de cost minim ====
- Dacă fiecare muchie dintr-un arbore are un **cost**(o pondere), atunci **costul arborelui** este dat de **suma costurilor** muchiilor ce formează arborele.
+ <note importante>
+ Se numește **lanț** într-un graf,o succesiune de vârfuri L={v1,v2,...,vk},cu proprietatea că oricare două vârfuri consecutive sunt adiacente,adică există o muchie între acestea.
- Dacă, pe acelaşi principiu, fiecare muchie dintr-un graf are un cost, atunci alegerea unui **arbore minim de acoperire** presupune alegerea unui arbore care să acopere toate nodurile şi care să folosească muchiile ce dau suma costurilor minimă.
- ===== 3. Algoritmul lui Kruskal =====
- Algoritmul lui Kruskal este un algoritm în teoria grafurilor care găsește arborele parțial de cost minim pentru un graf conex ponderat.
+ Se numeşte **lanţ elementar** un lanţ în care nu se repetă vârfuri.
- Cu alte cuvinte, găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și care este minimizat din punct de vedere al costului.
+ Se numeşte **lanţ simplu** un lanţ în care nu se repetă muchii.
- Dacă graful nu este conex, atunci algoritmul găsește o pădure parțială de cost minim (un arbore parțial de cost minim pentru fiecare componentă conexă). Algoritmul lui Kruskal este un exemplu de **algoritm greedy**.
+ Se numeşte **ciclu** un lanţ simplu pentru care primul şi ultimul vârf coincid.
- <note tip>
- Algoritmul funcționează în felul următor:
+ Se numeşte **ciclu elementar** un ciclu în care nu se repetă vârfuri(excepţie primul şi ultimul).
+ </note>
- * creează o pădure F (o mulțime de arbori), unde fiecare vârf din graf este un arbore separat
- * creează o mulțime S care conține toate muchiile din graf
- * atât timp cât S este nevidă
- * elimină o muchie de cost minim din S
- * dacă acea muchie conectează doi arbori distincți, atunci adaugă muchia în pădure, combinând cei doi arbori într-unul singur
- * altfel, ignoră muchia
+ =====3 Grafuri orientate=====
+ ====3.1 Definiție====
+ Un **graf orientat** este o pereche ordonată de mulțimi G={X,U},unde:
+ *X este o mulțime finită și nevidă numită mulțimea nodurilor(vârfurilor)
+ *U este o mulțime formată din **perechi ordonate** de elemente ale lui X,numită mulțimea arcelor
- </note>
+ ====3.2 Structură====
+ Într-un graf orientat, distingem:
+ * **gradul interior/intern** al unui nod: numărul de arce care intră în nod
+ * **gradul exterior/extern** al unui nod: numărul de arce care ies din nod
- {{ :laboratoare:kruskal.gif?900 |}}
+ <note important>Ce relaţie există între suma gradelor exterioare, suma gradelor interioare şi numărul de arce?</note>
+ ====3.3 Reprezentare====
+ **Matricea de adiacență** - este o matrice **a** cu **n** linii și **n** coloane,în care elementele **a[i,j]** se definesc astfel:
+ *a[i,j] = 1 ,dacă ∃ arcul (i,j) în mulțimea U
+ *a[i,j] = 0 ,în caz contrar
- {{ :laboratoare:kruskal2.gif?900 |}}
- ===== 4. Algoritmul lui Prim =====
+ {{ :laboratoare:graf2.png?400 |}}
- Algoritmul lui Prim este un algoritm din teoria grafurilor care găsește arborele parțial de cost minim al unui graf conex ponderat. Înseamnă că găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și al cărui cost este minimizat.
+ \\
- <note tip>
- Algoritmul incrementează mărimea unui arbore, pornind de la un nod, până când sunt incluse toate nodurile.
+ Matricea **vârfuri-arce** este o matrice **B** cu n = |X| linii și m = |U| coloane,în care fiecare element **b[i,j]** este:
+ * **1** ,dacă nodul i este o extremitate inițială a arcului
+ * **-1** ,dacă nodul i este o extremitate finală a arcului
+ * **0** ,dacă nodul i nu este o extremitate a arcului
- * Intrare: Un graf conex ponderat cu nodurile V și muchiile E.
- * Initializare: Vnou = {x}, unde x este un nod arbitrar (punct de plecare) din V, Enou= {} repetă până când Vnou=V:
- * Alege muchia (u,v) din E de cost minim astfel încât u este în Vnou și v nu e (dacă există mai multe astfel de muchii, se alege arbitrar)
- * Se adaugă v la Vnou, (u,v) la Enou
- * Ieșire: Vnou și Enou descriu arborele parțial de cost minim
+ {{ :laboratoare:graf3.png?300 |}}
- </note>
+ =====4 Parcurgerea grafurilor=====
+ ====4.1 Parcurgerea în lățime====
- {{ :laboratoare:prim.gif?900 |}}
+ Parcurgerea în lățime **(Breadth-First-Search -BFS)** este o metodă ce presupune vizitarea nodurilor în următoarea ordine:
+ * nodul sursă (considerat a fi pe nivelul 0)
+ * vecinii nodului sursă (reprezentând nivelul 1)
+ * vecinii încă nevizitați ai nodurilor de pe nivelul 1 (reprezentând nivelul 2)
+ * ș.a.m.d
+ ===4.1.1 Implementare===
- {{ :laboratoare:prim2.gif?900 |}}
- ===== 5. Exerciții de laborator =====
+ Pe masură ce algoritmul avansează,se colorează nodurile în felul următor:
+ * **alb** - nodul este nedescoperit încă
+ * **gri** - nodul a fost descoperit și este în curs de procesare
+ * **negru** - procesarea nodului s-a încheiat
+ Se păstrează informațiile despre distanța până la nodul sursă.
+ Se obține arborele BFS
- 1.Vi s-a asignat rolul de nou coordonator al departamentul de rețelistică al companiei Coca Cola (Pepsi petru cei cărora nu le place Cola). Sediul companiei are arondate N-1 sucursale, iar voi trebuie să asigurațu conectivitate între toate locațiile folosind o lungime minimă de fibră optică, lucru care duce implicit la reducerea costurilor totale.
+ \\
+ Pentru implementarea BFS se utilizează o coadă (Q) în care inițial se află doar nodul sursă.Se vizitează pe rând vecinii acestui nod și se pun și ei în coadă.În momentul în care nu mai există vecini nevizitați,nodul sursă este scos din coadă.
<file cpp>
- # explicatii format
- # n=numar varfuri m=numar muchii
- # m randuri, cate unul pentru fiecare muchie: start end cost
- 8 13
- 1 2 4
- 1 3 9
- 1 4 1
- 1 6 7
- 2 3 12
- 2 4 4
- 3 8 13
- 4 5 7
- 4 6 8
- 5 6 3
- 5 7 6
- 5 8 5
- 7 8 2
+ Pentru fiecare nod u din graf
+ {
+ culoare[u]=alb
+ d[u] = infinit //in d se retine distanta pana la nodul sursa
+ p[u] = null //
+ }
+
+ culoare[sursă]=gri
+ d[sursă]=0
+ enqueue(Q,sursă) //punem nodul sursă în coada Q
+
+ Cât timp coada Q nu este vidă
+ {
+ v=dequeue(Q) //extragem nodul v din coadă
+ pentru fiecare u dintre vecinii lui v
+ dacă culoare[u] == alb
+ {
+ culoare[u] = gri
+ p[u] = v
+ d[u] = d[v] + 1
+ enqueue(Q,u) //adăugăm nodul u în coadă
+ }
+ culoare[v] = negru //am terminat explorarea vecinilor lui v
+ }
+
+
</file>
+ \\
+ **Exemplu**
+ {{ :laboratoare:bfs.jpg |}}
+
+ ====4.2 Parcurgerea în adâncime====
+ Parcurgea în adâncime **(Depth-First-Search -DFS)** presupune explorarea nodurilor în următoarea ordine:
+ *Nodul sursă
+ *Primul vecin nevizitat al nodului sursă (îl numim //V1//)
+ *Primul vecin nevizitat al lui //V1// (îl numim //V2//)
+ *ș.a.m.d
+ *În momentul în care am epuizat vecinii unui nod //Vn//, continuăm cu următorul vecin nevizitat al nodului anterior,//Vn-1//
+
+ Această metoda de parcurgere pune prioritate pe explorarea **în adâncime** (pe distanțe tot mai mari față de nodul sursă).
+
+ ====4.2.1 Implementare====
+
+ Spre deosebire de BFS, DFS utilizează o **stivă** în loc de o coadă. Putem defini o stivă sau ne putem folosi de **stiva compilatorului**, prin apeluri **recursive**.
+
+ <file cpp>
+ funcţie pasDFS(curent)
+ {
+ pentru fiecare u dintre vecinii nodului curent
+ dacă culoare[u] == alb
+ {
+ culoare[u] = gri
+ p[u] = curent
+ d[u] = d[curent] + 1
+ pasDFS(u); //adăugăm nodul u în "stivă" şi începem explorarea
+ }
+ culoare[curent] = negru //am terminat explorarea vecinilor nodului curent
+ //ieşirea din funcţie este echivalentă cu eliminarea unui element din stivă
+ }
+ Pentru fiecare nod u din graf
+ {
+ culoare[u]=alb
+ d[u] = infinit //in d se retine distanta pana la nodul sursa
+ p[u] = null
+ }
+ culoare[sursă] = gri;
+ d[sursă] = 0;
+
+ //se apelează iniţial pasDFS(sursă)
+
+ </file>
+ {{ :laboratoare:df1.jpg |}}
+
+ ===== 5. Exerciţii =====
+ Implementaţi, pentru fiecare cerinţă, câte o funcţie care:
+ - creează matricea de adiacenţă pentru un graf neorientat cu N noduri, folosindu-se de o listă(sau o matrice cu 2 coloane) de muchii(la alegere - muchiile citite în funcţie sau primite printr-un parametru).
+ - calculează gradul fiecărui nod. Afişaţi numărul de noduri izolate şi numărul de noduri terminale.
+ - primeşte un şir de noduri şi verifică dacă acesta poate reprezenta un lanţ.
+ - primeşte un şir de noduri şi afişează matricea de adiacenţă a subgrafului format cu nodurile respective
+ - afişează matricea de adiacenţă a unui graf orientat construit astfel:
+ * graful orientat are atâtea arce câte muchii are graful neorientat
+ * există arc în graful orientat între două noduri daca şi numai dacă există muchie între aceleaşi noduri în graful neorientat.
+ * Extra - câte astfel de grafuri orientate pot fi formate?
+
+ Cerinţele 2, 3, 4 şi 5 se vor folosi de matricea de adiacenţă a grafului de la cerinţa 1.
====5.1. Exerciții - schelet de laborator====
- Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab6_arbori_min-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.
+ Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab5_grafuri-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.
=== Linux===
Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
- * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab6_arbori_min-skel.zip%%''
- * ''%%unzip lab6_arbori_min-skel.zip%%''
+ * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab5_grafuri-skel.zip%%''
+ * ''%%unzip lab5_grafuri-skel.zip%%''
Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi comanda ''%%make run%%'' sau ''%%./graph%%''.
+ ====De interviu====
+ * Plecând dintr-un nod K, verificaţi dacă puteţi găsi un ciclu în graf.
+ * Verificaţi dacă există un lanţ care uneşte nodurile sursă(S) şi destinaţie(D). Dacă există, cum puteţi găsi lanţul cu număr minim de muchii?
+ * Verificaţi dacă există un lanţ **hamiltonian** în graf.
+ * Verificaţi dacă există un lanţ **eulerian** în graf.
+ * Verificaţi dacă o muchie dată (A, B) este un **pod** pentru drumul de la S la D.
- ==== Extra ====
- - Se dă un graf care coincide cu un arbore minim de acoperire. Verificaţi dacă, introducând o nouă muchie în graf, costul arborelui minim de acoperire se schimbă şi, dacă da, găsiţi muchia ce va fi scoasă.
- - Se dă un graf care coincide cu un arbore minim de acoperire şi un vector(V) cu K noduri din graf. Care este costul minim al muchiilor pe care trebuie să le eliminaţi din graf pentru ca fiecare nod din vectorul V să se afle în altă componentă conexă. (Să nu existe drum între oricare două noduri din vectorul V).
- - Se dă un graf care coincide cu un arbore minim de acoperire şi un nod auxiliar care formează doar două muchii. Verificaţi dacă folosirea nodului auxiliar pentru a conecta nodurile duce la un arbore de acoperire cu un cost mai mic.
+ Un lanţ hamiltonian este un lanţ elementar(nu se repetă nodurile) care trece prin fiecare nod.
+ Un lanţ eulerian este un lanţ simplu(nu se repetă muchiile) care trece prin fiecare muchie.
- ===== 6. Referințe =====
- - [[https://en.wikipedia.org/wiki/Minimum_spanning_tree|Minimum spanning tree]]
- - [[https://en.wikipedia.org/wiki/Kruskal%27s_algorithm|Algoritmul lui Kruskal]]
- - [[https://en.wikipedia.org/wiki/Prim%27s_algorithm|Algoritmul lui Prim]]
- - [[http://www.bogdanturcanu.ro/spanning-tree-protocol-stp/|Protocolul STP]]
- - [[https://en.wikipedia.org/wiki/Image_segmentation|Segmentarea de imagini]]
+ Spunem că muchia (A, B) este pod pentru drumul de la S la D dacă orice lanţ care duce de la S la D trece prin muchia (A, B).
</pre>text/html2018-02-25T22:45:00+00:00Anonymous (anonymous@undisclosed.example.com)Laborator 07: Arbori minimi de acoperire
http://elf.cs.pub.ro/sda-ab/wiki/laboratoare/laborator-07?rev=1519591500&do=diff
<pre>
@@ -1,229 +1,139 @@
- ====== Laborator 07: Drumuri de cost minim ======
+ ====== Laborator 07: Arbori minimi de acoperire ======
- ===== 1.Obiective laborator ======
- * Înțelegerea ideii de cost și de drum minim într-un graf
- * Prezentarea algoritmilor care calculează drumul de cost minim
- * Înțelegerea aplicațiilor practice prezente în:
- * găsirea drumului minim între 2 locații (ex: GPS)
- * rutarea în cazul rețelelor de calculatoare (ex: protocolul RIP)
+ ===== 1. Obiective laborator=====
+ * Înțelegerea conceptului de arbore minim de acoperire
+ * Înțelegerea implementării algoritmilor care determină acest arbore
+ * Înțelegere aplicațiilor practice în:
+ * rețele de calculatoare: obținerea unui cost redus la interconectarea mai multor stații (ex: protocolul STP folosit în LAN-uri)
+ * prelucrarea de imagine: segmentarea cadrelor (ex: folosită în analiza medicală)
+ * în clustere: determinarea unei topologii de comunicare, în cazul în care topologia nu era una regulată(arbore, inel)
- {{ :laboratoare:rip.gif?600 | RIP protocol}}
- ===== 2.Considerente teoretice ======
+ {{ :laboratoare:segmentation.jpg?600 | Segmentarea de imagini}}
+ ===== 2. Introducere =====
- ==== 2.1 Costul unei muchii ====
- La fel ca la arbori de acoperire, presupunem că fiecare muchie are un **cost de parcurgere**.
+ ==== 2.1 Conexitate în grafuri ====
- ==== 2.2 Costul unui drum; drumul de cost minim ====
- Într-un graf, orice drum este definit de o succesiune de muchii (cu proprietatea că, pentru oricare două muchii consecutive din succesiune, nodul destinaţie/de sosire al primei muchii este acelaşi cu nodul sursa/de plecare al celei de-a doua muchii).
+ ===Componentă conexă===
+ O componentă conexă a unui graf **neorientat** este un subgraf cu următoarele proprietăţi:
+ - oricare două noduri din acest subgraf sunt **conectate**(există un lanţ între ele)
+ - orice nod din acest subgraf **NU este conectat** cu niciun nod din afara subgrafului(nodurile din componentă fac muchii numai cu alte noduri din componentă)
- Costul unui drum va fi definit ca **suma costurilor** muchiilor ce compun acel drum.
+ <note important>Orice graf neorientat are cel puţin o componentă conexă.</note>
- Fie un nod sursă(S) şi un nod destinaţie(D). Pot exista mai multe drumuri de la S la D(drumuri care au S = primul nod, D = ultimul nod), iar drumul de cost minim de la S la D va fi cel mai ieftin(cu costul cel mai mic) dintre acestea.
+ ===Graf neorientat conex===
+ Un graf neorientat este numit **conex** dacă are o singură **componentă conexă**.
- <note important>Pot exista mai multe drumuri de cost minim de la S la D.</note>
+ <note tip>Putem explora toate nodurile dintr-un graf neorientat conex dintr-o singură parcurgere a grafului(DFS sau BFS).</note>
- ====2.3 Legătura muchii-arce: ====
- <note tip>
- Orice graf **neorientat** este echivalent cu un graf **orientat** dacă înlocuim fiecare **muchie** cu **două arce**(de acelaşi cost, câte un arc pentru fiecare sens).
+ ===Graf orientat slab conex===
+ Fie graful neorientat asociat unui graf orientat obţinut prin înlocuirea tuturor **arcelor** cu **muchii**. Atunci un graf orientat este **slab conex** dacă graful neorientat asociat acestuia este conex.
- Algoritmii următori pot fi folosiţi(în limita observaţiilor finale) pe grafuri orientate la fel ca pe grafuri neorientate.
- </note>
+ ===Graf orientat tare conex===
+ Un graf orientat este **tare conex** dacă există drum între oricare două noduri, atât într-un sens, cât şi în celelalt.
+ Se pot defini similar componentele slab conexă şi tare conexă.
- ===== 3.Drumul de cost minim cu sursă unică ======
- Următorii algoritmi caută drumurile de cost minim de la **un singur nod(sursă)** la **toate celelalte noduri**. Rezultatul acestor algoritmi este un **arbore cu drumuri de cost minim**, unde:
- * nodul sursă(S) este rădăcina arborelui;
- * toate nodurile din graf sunt în arbore;
- * pentru orice nod destinaţie(D), costul drumului din arbore de la rădăcina S la D este drum de cost minim(de la S la D) în graf.
+ ==== 2.2 Arborele văzut ca graf ====
+ Folosind noţiunile de mai sus, putem spune că un arbore este un graf(pentru simplitate, fie neorientat) **conex** şi cu număr minim de muchii, prin urmare, **aciclic**.
+ ==== 2.3 Arbore vs. pădure de acoperire ====
+ Pentru un graf neorientat, construirea unui arbore de acoperire(nu neapărat de cost minim) presupune construirea unui arbore care să fie **graf parţial**(să **acopere** toate nodurile).
+ Acest lucru este posibil numai dacă graful este **conex**. În caz contrar, se poate construi câte un arbore de acoperire pentru fiecare **componentă conexă** a grafului, spunând că se construieşte o **pădure** de acoperire pentru graf.
- ==== 3.1 Algoritmul lui Dijkstra ====
+ ==== 2.4 Arbore de cost minim ====
+ Dacă fiecare muchie dintr-un arbore are un **cost**(o pondere), atunci **costul arborelui** este dat de **suma costurilor** muchiilor ce formează arborele.
- Algoritmul lui Dijkstra se bazează pe un principiu similar cu cel al algoritmului lui Prim:
- * iniţial, toate nodurile sunt neexplorate şi vom construi arborele, începând de la nodul S;
- * atribuim un posibil cost(o estimare a distanţei) pentru fiecare nod. (iniţial, S are costul 0, toate celelalte noduri au costul **infinit**);
- * la fiecare pas, alegem cel mai bun candidat dintre nodurile neexplorate, urmând să îl explorăm(să îi evaluăm vecinii), iar acel candidat va rămâne în arbore;
- * la fiecare explorare(evaluare a vecinilor), dacă găsim o nouă estimare de cost mai bună decât cea precedentă, folosim, mai departe, noua estimare. Dacă dorim să ţinem evidenţa muchiilor folosite, actualizăm şi nodul părinte al vecinului respectiv.
+ Dacă, pe acelaşi principiu, fiecare muchie dintr-un graf are un cost, atunci alegerea unui **arbore minim de acoperire** presupune alegerea unui arbore care să acopere toate nodurile şi care să folosească muchiile ce dau suma costurilor minimă.
+ ===== 3. Algoritmul lui Kruskal =====
- Diferenţa apare, în algoritmul lui Dijkstra, la funcţia folosită pentru estimarea costurilor, atunci când evaluăm vecinii unui nod:
- * Dacă C este nodul curent(pe care îl explorăm), atunci:
- * pentru fiecare nod vecin(V) al lui C, noul cost posibil va fi costul drumului S-V(de la S la V) care trece prin C, mai exact - suma dintre costul drumului S-C şi costul muchiei (C,V).
+ Algoritmul lui Kruskal este un algoritm în teoria grafurilor care găsește arborele parțial de cost minim pentru un graf conex ponderat.
- <note tip>Construind astfel algoritmul, este **garantat** că, în momentul în care explorăm un nod(C), estimarea pentru costul drumului S-C este chiar **costul minim**.</note>
+ Cu alte cuvinte, găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și care este minimizat din punct de vedere al costului.
- <note important>
- Pentru grafuri orientate, ne referim la vecinii la care putem ajunge printr-un arc ce pleacă din C: (C,V).
- </note>
- Paşii algoritmului lui Dijkstra:
- <code>
- 1. Declarăm două mulţimi:
- mulţimea nodurilor neexplorate(MN), iniţial MN conţine toate nodurile;
- mulţimea nodurilor explorate(ME) ce compun arborele, iniţial ME = vidă;
- 2. Atribuim fiecărui nod o estimare iniţială a costului:
- 0 pentru nodul sursă(S);
- infinit pentru toate celelalte;
- 3. Cât timp există noduri în MN
- 1. Alegem, din MN(nodurile neexplorate), nodul cu cel mai mic cost estimat
- îl numim C(nodul curent)
- 2. pentru fiecare din vecinii lui C care se află în MN
- 3. calculăm noua estimare de cost = cost(drumul S-C) + cost(muchia (C,V));
- 4. comparăm noua estimare cu vechiul cost(drumul S-V):
- dacă noul cost e mai bun
- 1. actualizăm cost(drumul S-V) = noul cost;
- 2. actualizăm parinte(V) = C; (pentru păstrarea muchiei folosite)
- altfel păstrăm vechiul cost
- 5. Marcăm nodul C ca explorat: îl eliminăm din MN şi îl adăugăm în ME.
- (Nu va mai fi verificat)
- </code>
+ Dacă graful nu este conex, atunci algoritmul găsește o pădure parțială de cost minim (un arbore parțial de cost minim pentru fiecare componentă conexă). Algoritmul lui Kruskal este un exemplu de **algoritm greedy**.
- ==== 3.2 Algoritmul Bellman-Ford ====
- Principii similare pentru algoritmul Bellman-Ford:
- * vom construi arborele, începând de la nodul S;
- * atribuim un posibil cost(o estimare a distanţei) pentru fiecare nod. (iniţial, S are costul 0, toate celelalte noduri au costul **infinit**);
- * la fiecare evaluare, dacă găsim o nouă estimare de cost mai bună decât cea precedentă, folosim, mai departe, noua estimare. Dacă dorim să ţinem evidenţa muchiilor folosite, actualizăm şi nodul părinte.
- * funcţia de estimare a costului este definită la fel ca la algoritmul lui Dijkstra(costul drumului de la S la nodul respectiv)
-
- <note tip>Rezultatul algoritmului va fi un arbore cu N noduri(unde N = |V|, numărul de noduri din graf). Prin urmare, **lungimea** oricărui drum de la S la alt nod va fi **maxim N-1**. (Presupunem că nu se repetă muchii)
- </note>
+ <note tip>
+ Algoritmul funcționează în felul următor:
- Diferenţa apare, în algoritmul Bellman-Ford, la alegerea nodurilor pentru care facem evaluarea:
- * Algoritmul nu are preferinţe pentru anumite noduri şi nu extrage, la fiecare pas, cel mai bun candidat.
- * În schimb, acest algoritm evaluează **toate muchiile** la un pas. Folosindu-se de principiul de mai sus, (N-1) astfel de paşi vor fi suficienţi.
+ * creează o pădure F (o mulțime de arbori), unde fiecare vârf din graf este un arbore separat
+ * creează o mulțime S care conține toate muchiile din graf
+ * atât timp cât S este nevidă
+ * elimină o muchie de cost minim din S
+ * dacă acea muchie conectează doi arbori distincți, atunci adaugă muchia în pădure, combinând cei doi arbori într-unul singur
+ * altfel, ignoră muchia
- <note important>
- În cazul grafurilor neorientate, evaluăm fiecare muchie în ambele sensuri.
</note>
- Paşii algoritmului Bellman-Ford:
- <code>
- 1. Atribuim fiecărui nod o estimare iniţială a costului:
- 0 pentru nodul sursă(S);
- infinit pentru toate celelalte;
- 2. Executăm de N-1 ori:
- 1. Pentru fiecare pereche (u, v) a.i. există muchie de la u la v
- 1. calculăm noua estimare de cost = cost(drumul S-u) + cost(muchia (u,v));
- 2. comparăm noua estimare cu vechiul cost(drumul S-v):
- dacă noul cost e mai bun
- 1. actualizăm cost(drumul S-v) = noul cost;
- 2. actualizăm parinte(v) = u; (pentru păstrarea muchiei folosite)
- altfel păstrăm vechiul cost
- </code>
+ {{ :laboratoare:kruskal.gif?900 |}}
- ===== 4.Drumul de cost minim între oricare 2 noduri ======
- Următorul algoritm caută cel mai scurt drum de la **orice nod sursă(S)** la **fiecare nod destinaţie(D)**.
+ {{ :laboratoare:kruskal2.gif?900 |}}
+ ===== 4. Algoritmul lui Prim =====
- ==== 4.1 Algoritmul Floyd-Warshall ====
- Rezultatul algoritmului este o matrice N x N(unde N = |V|, numărul de noduri), iar valorea din matrice de la poziţia [i][j] va fi costul minim pentru drumul i-j. Fie această matrice numită **dist**.
+ Algoritmul lui Prim este un algoritm din teoria grafurilor care găsește arborele parțial de cost minim al unui graf conex ponderat. Înseamnă că găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și al cărui cost este minimizat.
- Pentru simplitate, algoritmul numerotează nodurile de la 1 la N şi foloseşte următoarea construcţie:
- * defineşte o funcţie costMinim(i,j,k) = cel mai ieftin drum care:
- * -pleacă din i
- * -ajunge în j
- * -în afară de primul şi de ultimul nod, conţine numai noduri din {1,2,3,...,k}(primele k noduri).
+ <note tip>
+ Algoritmul incrementează mărimea unui arbore, pornind de la un nod, până când sunt incluse toate nodurile.
- Algoritmul calculează costMinim(i,j,k) pentru toate perechile (i,j,k), folosind formula: **costMin(i,j,k+1) = min(costMin(i,j,k), costMin(i,k+1,k) + costMin(k+1,j,k))**;
-
- <note tip>
- Observaţii:
- * costMin(i,j,0) = costMuchie(i,j) (dacă există muchie de la i la j) sau infinit(altfel);
- * costMin(i,j,N) = drumul de cost minim de la i la j.
+ * Intrare: Un graf conex ponderat cu nodurile V și muchiile E.
+ * Initializare: Vnou = {x}, unde x este un nod arbitrar (punct de plecare) din V, Enou= {} repetă până când Vnou=V:
+ * Alege muchia (u,v) din E de cost minim astfel încât u este în Vnou și v nu e (dacă există mai multe astfel de muchii, se alege arbitrar)
+ * Se adaugă v la Vnou, (u,v) la Enou
+ * Ieșire: Vnou și Enou descriu arborele parțial de cost minim
</note>
- Paşii algoritmului Floyd-Warshall:
+ {{ :laboratoare:prim.gif?900 |}}
- <code>
- 1. Declarăm matricile:
- dist, matrice N x N şi o iniţializăm dist[i][j] = infinit, pentru orice i şi j
- next, matrice N x N în care vom salva prima muchie din drumul i-j de cost minim
- //next este necesar doar în cazul în care ne interesează muchiile folosite
- //pasul k = 0
- 2. Pentru fiecare nod v
- 1. dist[v][v] = 0;
- 3. Pentru fiecare pereche (u,v) a.i. există muchie de la u la v
- 1. dist[u][v] = costMuchie(u,v);
- 2. next[u][v] = v; //pentru urmărirea muchiilor ce compun drumul
- //am terminat pasul k = 0
- 4. Pentru fiecare pas k (de la 1 la N)
- 1. Pentru fiecare nod i (de la 1 la N)
- 1. Pentru fiecare nod j (de la 1 la N)
- 1. calculăm costul nou = dist[i][k] + dist[k][j];
- 2. comparăm costul nou cu costul vechi = dist[i][j]
- dacă e mai bun costul nou:
- 1. dist[i][j] = costul nou;
- 2. next[i][j] = next[i][k]; //pentru urmărirea muchiilor
- altfel păstrăm costul vechi
- </code>
- Pentru obţinerea nodurilor ce formează drumul de cost minim de la u la v, putem folosi următoarea secvenţă:
- <code>
- funcţie afişareDrum(u, v)
- 1. dacă u == v
- 1. print(v); STOP
- 2. print(u);
- 3. afişareDrum(next[u][v], v);
- </code>
- ===== 5. Observaţii finale ======
- <note tip>
- Cei 3 algoritmi funcţionează bine atunci când **toate muchiile** au **cost pozitiv**.
- </note>
- <note warning>
- Drumul de cost minim **NU** este bine definit atunci când există **cicluri cu cost negativ**.
- * putem ajunge de la un nod la acelaşi nod, folosind acelaşi ciclu de oricâte ori => costMinim = -infinit);
- * în aceste cazuri, nu putem pune problema găsirii drumurilor de cost minim.
-
- </note>
- <note warning>
- O **muchie cu cost negativ** este echivalentă cu **2 arce cu cost negativ** şi implică existenţa unui ciclu cu cost negativ.
- </note>
- <note tip>
- Algoritmii **Bellman-Ford** şi **Floyd-Warshall** pot detecta dacă un graf conţine **cicluri cu cost negativ**:
- * Bellman-Ford: executăm încă o evaluare a tuturor muchiilor la final. Dacă găsim cel puţin o estimare nouă mai buna, graful conţine măcar un ciclu cu cost negativ.
- * Floyd-Warshall: putem verifica, la fiecare pas, dacă avem o valoare negativă pe diagonala matricei dist. Dacă găsim cel puţin o valoare negativă, graful conţine măcar un ciclu cu cost negativ.
-
- </note>
- <note important>
- Pentru algoritmul lui **Dijkstra**, "garanţia" se pierde când există chiar şi **un singur arc cu cost negativ**.
- * Algoritmul se bazează pe ideea că, odată explorat un nod, drumul de cost minim până la acel nod a fost găsit, ceea ce **NU** este mereu corect în prezenţa unui arc cu cost negativ.
- * De aceea, algoritmul poate produce răspunsuri **greşite** în acest caz.
-
- </note>
- <note tip>În schimb, algoritmii **Bellman-Ford** şi **Floyd-Warshall** funcţionează pe grafurile cu **arce cu cost negativ**, atâta timp cât drumurile de cost minim sunt bine definite(**fără cicluri cu cost negativ**).
- </note>
+ {{ :laboratoare:prim2.gif?900 |}}
+ ===== 5. Exerciții de laborator =====
- ===== 6. Exerciții laborator ======
+ 1.Vi s-a asignat rolul de nou coordonator al departamentul de rețelistică al companiei Coca Cola (Pepsi petru cei cărora nu le place Cola). Sediul companiei are arondate N-1 sucursale, iar voi trebuie să asigurațu conectivitate între toate locațiile folosind o lungime minimă de fibră optică, lucru care duce implicit la reducerea costurilor totale.
- - Daţi un exemplu de graf orientat cu un singur arc cu cost negativ pentru care algoritmul lui Dijkstra dă rezultate greşite.
- - Cum putem folosi algoritmul lui Dijkstra sau algoritmul Bellman-Ford pentru a obţine aceleaşi rezultate ca algoritmul Floyd-Warshall(drumul de cost minim pentru toate perechile de noduri)? Ne limităm la grafurile pe care merg toţi cei trei algoritmi.
- - Implementaţi unul din algoritmi pentru a calcula drumurile de cost minim de la un nod sursă la toate celelalte noduri într-un graf cu toate muchiile/arcele cu cost pozitiv.
- - Verificaţi dacă un graf conţine cicluri negative.
+ <file cpp>
+ # explicatii format
+ # n=numar varfuri m=numar muchii
+ # m randuri, cate unul pentru fiecare muchie: start end cost
+ 8 13
+ 1 2 4
+ 1 3 9
+ 1 4 1
+ 1 6 7
+ 2 3 12
+ 2 4 4
+ 3 8 13
+ 4 5 7
+ 4 6 8
+ 5 6 3
+ 5 7 6
+ 5 8 5
+ 7 8 2
+ </file>
- ====6.1. Exerciții - schelet de laborator====
- Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab7_drumuri_minime-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.
+ ====5.1. Exerciții - schelet de laborator====
+ Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab6_arbori_min-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.
=== Linux===
Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
- * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab7_drumuri_minime-skel.zip%%''
- * ''%%unzip lab7_drumuri_minime-skel.zip%%''
+ * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab6_arbori_min-skel.zip%%''
+ * ''%%unzip lab6_arbori_min-skel.zip%%''
Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi comanda ''%%make run%%'' sau ''%%./graph%%''.
- ===Extra===
-
- - Se dă un graf pentru care se cunoaşte drumul de cost minim de la un nod sursă(S) la un nod destinaţie(D). Dacă adăugăm 100 la costul fiecărei muchii, se modifică drumul de cost minim? (dacă da, daţi un exemplu; dacă nu, explicaţi de ce).
- - Aceeaşi întrebare dacă înmulţim fiecare cost cu 100.
- - Cum găsiţi(mai rapid decât cu cei 3 algoritmi prezentaţi) drumul de cost minim de la S la D într-un graf în care toate muchiile au acelaşi cost(1)? Cum adaptaţi soluţia în cazul în care toate muchiile au costul 1 sau 2?
- - Daţi un exemplu în care folosirea algoritmului lui Dijkstra(pentru a obţine drumul de cost minim pentru toate perechile de noduri) ar fi mai rapidă decât algoritmul Floyd-Warshall.
+ ==== Extra ====
+ - Se dă un graf care coincide cu un arbore minim de acoperire. Verificaţi dacă, introducând o nouă muchie în graf, costul arborelui minim de acoperire se schimbă şi, dacă da, găsiţi muchia ce va fi scoasă.
+ - Se dă un graf care coincide cu un arbore minim de acoperire şi un vector(V) cu K noduri din graf. Care este costul minim al muchiilor pe care trebuie să le eliminaţi din graf pentru ca fiecare nod din vectorul V să se afle în altă componentă conexă. (Să nu existe drum între oricare două noduri din vectorul V).
+ - Se dă un graf care coincide cu un arbore minim de acoperire şi un nod auxiliar care formează doar două muchii. Verificaţi dacă folosirea nodului auxiliar pentru a conecta nodurile duce la un arbore de acoperire cu un cost mai mic.
- ===== 7.Referințe ======
- - [[https://en.wikipedia.org/wiki/Dijkstra's_algorithm|Algoritmul lui Dijkstra]]
- - [[https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm|Algoritmul lui Bellman Ford]]
- - [[http://www.algorithmist.com/index.php/Floyd-Warshall's_Algorithm|Algoritmul lui Floyd-Warshall]]
- - [[https://profs.info.uaic.ro/~busaco/teach/courses/net/docs/protocoale_rutare.pdf|Protocoale de rutare]]
- - [[http://example.com|Link extern]]
+ ===== 6. Referințe =====
+ - [[https://en.wikipedia.org/wiki/Minimum_spanning_tree|Minimum spanning tree]]
+ - [[https://en.wikipedia.org/wiki/Kruskal%27s_algorithm|Algoritmul lui Kruskal]]
+ - [[https://en.wikipedia.org/wiki/Prim%27s_algorithm|Algoritmul lui Prim]]
+ - [[http://www.bogdanturcanu.ro/spanning-tree-protocol-stp/|Protocolul STP]]
+ - [[https://en.wikipedia.org/wiki/Image_segmentation|Segmentarea de imagini]]
</pre>text/html2018-04-23T22:48:18+00:00Anonymous (anonymous@undisclosed.example.com)Laborator 08: Drumuri de cost minim
http://elf.cs.pub.ro/sda-ab/wiki/laboratoare/laborator-08?rev=1524512898&do=diff
<pre>
@@ -225,5 +225,5 @@
- [[https://en.wikipedia.org/wiki/Dijkstra's_algorithm|Algoritmul lui Dijkstra]]
- [[https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm|Algoritmul lui Bellman Ford]]
- [[http://www.algorithmist.com/index.php/Floyd-Warshall's_Algorithm|Algoritmul lui Floyd-Warshall]]
- [[https://profs.info.uaic.ro/~busaco/teach/courses/net/docs/protocoale_rutare.pdf|Protocoale de rutare]]
- - [[http://example.com|Link extern]]
+
</pre>text/html2017-04-27T21:18:20+00:00Anonymous (anonymous@undisclosed.example.com)Laborator 09: Algoritmi de sortare 2
http://elf.cs.pub.ro/sda-ab/wiki/laboratoare/laborator-09?rev=1493317100&do=diff
<pre>
@@ -322,11 +322,22 @@
}
}
</file>
- =====5. Extra=====
+ ===== 5. Exerciţii de laborator (Linux) =====
+ Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab9_sortari_avansate.zip|aici]]. Descărcați arhiva și dezarhivați-o.
- ====5.1 qsort====
+ === Linux===
+ Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
+
+ * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab9_sortari_avansate.zip%%''
+ * ''%%unzip lab9_sortari_avansate.zip%%''
+
+ Pentru compilare folositi comanda ''%%make%%''.
+
+ =====6. Extra=====
+
+ ====6.1 qsort====
Funcţia qsort este inclusă în **stdlib.h** şi se apelează astfel: qsort(numeVector,nrElemente,sizeof(element),functieComparare);
<file cpp>
@@ -339,9 +350,9 @@
//...main...
qsort(v, n, sizeof(int), functieComparare);
</file>
- ====5.2 sort====
+ ====6.2 sort====
Funcţia sort este inclusă în **algorithm** din pachetul STL şi se apelează astfel: sort(pointerStart,pointerStop,functieComparare); Valoarea de la pointerStart este prima valoare inclusă în sortare, valoarea de la pointerStop este prima valoare exclusă din sortare.
<file cpp>
</pre>text/html2017-05-08T15:24:05+00:00Anonymous (anonymous@undisclosed.example.com)Laborator 10: Divide et impera și Greedy
http://elf.cs.pub.ro/sda-ab/wiki/laboratoare/laborator-10?rev=1494246245&do=diff
<pre>
@@ -218,9 +218,9 @@
6. Aproximaţi, printr-o abordare de tip Divide et Impera, cu o eroare (relativă) de maxim 1e-3, funcţia lg(n) (extragerea logaritmului în baza 10). Aveţi voie să vă folosiţi de funcţia pow(bază, exp) din "math.h".
7*. Problema 5 (extras logaritm) fără a vă folosi de funcţia pow, ci doar de funcţia construită la 4 (extragerea radicalului).
- 8**. Se dă un vector cu N numere întregi, apoi se fac un număr de C cereri de tipul "Calculează suma numerelor de la poziţia i până la poziţia j". Reduceţi sub O(N * C) timpul necesar pentru a răspunde la toate cererile dacă N este prea mare pentru a reţine în memorie toate perechile de sume(de la orice i la orice j) şi, în acelaşi timp, C > N.
+ 8**. Se dă un vector cu N numere întregi, apoi se fac un număr de C cereri de tipul "Calculează suma numerelor de la poziţia i până la poziţia j". Reduceţi sub O(N * C) timpul necesar pentru a răspunde la toate cererile dacă N este prea mare pentru a reţine în memorie toate perechile de sume(de la orice i la orice j) şi, în acelaşi timp, C > N. (Variantă alternativă - minim în loc de sumă)
===== 5. Exerciţii de laborator (Linux) =====
Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab10_di_si_greedy-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.
</pre>text/html2017-05-12T02:37:31+00:00Anonymous (anonymous@undisclosed.example.com)Laborator 11: Programare dinamică
http://elf.cs.pub.ro/sda-ab/wiki/laboratoare/laborator-11?rev=1494545851&do=diff
<pre>
@@ -71,9 +71,9 @@
Putem deduce o legătură între coeficienţii polinoamelor de tipul P(n) dacă scriem P(n + 1) = (X + 1) P(n) = X P(n) + P(n).
<note tip>
Folosind proprietăţile de mai sus, observăm:
- * coef(P(n + 1), k) = coef( X P(n), k) + coef(P(n), k) = **coef(P(n), k-1) + coef(P(n), k)**, pentru orice număr natural (k-1).
+ * coef(**P(n + 1), k**) = coef( X P(n), k) + coef(P(n), k) = **coef(P(n), k-1) + coef(P(n), k)**, pentru orice număr natural (k-1).
Dar coef(P(n), k) = C(n, k), deci am obţinut o recurenţă ce foloseşte doar o adunare.
</note>
</pre>text/html2017-05-18T22:41:51+00:00Anonymous (anonymous@undisclosed.example.com)Laborator 12: Backtracking
http://elf.cs.pub.ro/sda-ab/wiki/laboratoare/laborator-12?rev=1495136511&do=diff
<pre>
@@ -77,4 +77,16 @@
- Problema reginelor pe tabla de şah;
- Găsirea unui lanţ Hamiltonian într-un graf;
-* Găsirea unui ciclu Hamiltonian într-un graf;
-** Problema comisului-voiajor;
+
+ ==== 5. Exerciţii de laborator (Linux) ====
+ Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab12_backtracking-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.
+
+ === Linux===
+ Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
+
+ * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab12_backtracking-skel.zip%%''
+ * ''%%unzip lab12_backtracking-skel.zip%%''
+
+ Pentru compilare folositi comanda ''%%make%%''.
+
</pre>text/html2017-05-15T08:29:49+00:00Anonymous (anonymous@undisclosed.example.com)Laborator 13: Best-first search și A*
http://elf.cs.pub.ro/sda-ab/wiki/laboratoare/laborator-13?rev=1494826189&do=diff
<pre>
@@ -10,9 +10,9 @@
===Cum definim potenţialul?===
*Trebuie să atribuim un "**potenţial de rezultat**" fiecărui candidat, adică să găsim o metodă cu care să decidem dacă un candidat prezintă mai mult interes decât altul, dacă avem aşteptări mai mari de a găsi rezultatul dorit alegând acest candidat.
- *În multe cazuri, funcţia de "**cost potenţial**" ne ajută să descriem **potenţialul de rezultat**. Cu cât este mai mare costul la care ne aşteptăm de la un candidat, cu atât este mai mic potenţialul lui de a ne duce la rezultatul căutat. Cu alte cuvinte, putem spune că **cel mai bun** candidat este **cel mai puţin costisitor** candidat.
+ *În multe cazuri, este mai ușor să măsurăm cât de "rău" este un candidat. Funcţia de "**cost potenţial**" ne ajută să descriem **potenţialul de rezultat**. Cu cât este mai mare costul la care ne aşteptăm de la un candidat, cu atât este mai mic potenţialul lui de a ne duce la rezultatul căutat. Cu alte cuvinte, putem spune că **cel mai bun** candidat este **cel mai puţin costisitor** candidat.
*După ce definim o funcţie de acest fel, putem introduce candidaţii într-o coadă prioritară(**priority queue**) în funcţie de costul aşteptat în aşa fel încât **primul** candidat din coadă să fie **cel mai bun** candidat.
====1.2 Greedy vs. Dijkstra====
</pre>