Unelte utilizator

Unelte site


laboratoare:laborator-08

Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

Both sides previous revision Versiuni anterioare
Urmatoarea versiune
Versiuni anterioare
laboratoare:laborator-08 [2017/04/20 17:53]
iulian.matesica [4. Exerciţii]
laboratoare:laborator-08 [2018/04/23 19:48]
mihai.iacov [7.Referințe]
Linia 1: Linia 1:
-====== Laborator 08: Algoritmi ​de sortare 1 ======+====== Laborator 08: Drumuri ​de cost minim ======
  
-=====1. ​Obiectivele laboratorului=====+===== 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)
  
-Propunem studierea următorilor algoritmi de sortare+{{ :laboratoare:​rip.gif?​600 | RIP protocol}} 
- * Bubble Sort +===== 2.Considerente teoretice ======
- * Selection Sort +
- * Insertion Sort +
- * Merge Sort +
- * Quick Sort+
  
-=====2. Introducere===== 
  
-====2.1 ​Caracterizarea unui algoritm====+==== 2.1 Costul unei muchii ​==== 
 +La fel ca la arbori de acoperire, presupunem că fiecare muchie are un **cost de parcurgere**.
  
-Numim **sortare** ​orice aşezare(sau - mai clar - **reaşezare**) a unor elemente date în aşa fel încâtdupă aşezaresă existe o  **ordine completă** în funcţie de un atribut(numit **cheie**al elementelor.+==== 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 succesiunenodul destinaţie/de sosire al primei muchii este acelaşi cu nodul sursa/de plecare al celei de-a doua muchii).
  
-Pentru a exista o **ordine completă**,​ trebuie să alegem o **relaţie** pe care vrem sa o impunem. Dacă relaţia este valabilă între **oricare două elemente** pentru care **primul** element **este** aşezat **la stânga** celui de-al doilea, atunci avem o **ordine completă**.+Costul unui drum va fi definit ca **suma costurilor** muchiilor ce compun acel drum.
  
-Exemplu: dacă alegem drept cheie un atribut **număr întreg** ​şi relaţia **mai mic sau egal**(<=), obţinem **ordinea crescătoare**.+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.
  
-Vom descrie un algoritm ​de sortare prin: +<note important>​Pot exista mai multe drumuri ​de cost minim de la la D.</note>
- *timp mediu - timpul ​de execuţie ​la care ne aşteptăm, **în medie**, pentru sortare +
- ​*timp ​la limită- timpul de execuţie pentru **cel mai rău** caz posibil +
- ​*memorie - memoria **maximă** de care are nevoie algoritmul pentru sortare(**excludem memoria deja alocată** înainte de algoritm -vectorul efectiv ce va fi sortat) +
- ​*stabilitate - un algoritm stabil păstrează ordinea în care apar două elemente cu aceeaşi cheie(atributul după care sortăm)+
  
-Folosim notaţia O(n) pentru a indica+====2.3 Legătura muchii-arce==== 
- ​*un ​număr de operaţii de ordinul lui n. În acest caz, spunem că avem "**complexitate de timp de ordinul lui n**+<note tip> 
- *o dimensiune de ordinul lui n pentru memoria alocată. În acest caz, spunem că avem "**complexitate ​de spaţiu de ordinul lui n**"+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).
  
 +Algoritmii următori pot fi folosiţi(în limita observaţiilor finale) pe grafuri orientate la fel ca pe grafuri neorientate.
 +</​note>​
  
-====2.2 Metodele de sortare folosite==== 
  
-Fiecare algoritm se bazează pe o metodă de sortare: +===== 3.Drumul de cost minim cu sursă unică ====== 
- *Bubble sort - interschimbare +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: 
- *Selection sort - selecţie +  nodul sursă(S) este rădăcina arborelui; 
- *Insertion sort - inserare +  toate nodurile din graf sunt în arbore; 
- *Merge sort - interclasare +  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.
- *Quick sort - partiţionare+
  
  
-=====3. ​Algoritmii=====+==== 3.1 Algoritmul lui Dijkstra ​====
  
-====3.1 Bubble sort====+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.
  
-  * timp mediuO(N^2) +Diferenţa apare, în algoritmul lui Dijkstra, la funcţia folosită pentru estimarea costurilor, atunci când evaluăm vecinii unui nod
-  * timp la limită: O(N^2+  * Dacă C este nodul curent(pe care îl explorăm), atunci: 
-  * memorie: O(1) +  * pentru fiecare nod vecin(Val 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).
-  * Stabil: DA+
  
-===Descriere :=== +<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>​
-Sortarea prin metoda bulelor se consideră drept una din cele mai puţin efective metode de +
-sortaredar cu un algoritm mai simplu.+
  
- ​*Ideea de bază a sortării prin metoda bulelor este în a parcurge tabloulde la stânga spre dreapta+<note important>​ 
-fiind comparate elementele alăturate **a[i] si a[i+1]**Dacă vor fi găsite elemente neordonate, +Pentru grafuri orientate, ne referim la vecinii la care putem ajunge printr-un arc ce pleacă din C: (C,V). 
-valorile lor vor fi interschimbate+</​note>​ 
- *Parcurgerea tabloului de la stânga spre dreapta se va repeta atât timp cât vor fi întâlnite +Paşii algoritmului lui Dijkstra: 
-elemente neordonate.+<​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. Alegemdin 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)); 
 + 4compară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>​
  
-{{ :​laboratoare:​bubble-sort-example-300px.gif?nolink |}}+==== 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)
  
-===Implementare :=== +<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
-<file cpp> +</note>
-//sortare descrescatoare +
-void bubble(int a[],int n) +
-+
-    int i,schimbat,​aux;​ +
-    do { +
-        schimbat = 0; +
-        // parcurgem vectorul +
-        for(i = 0; i < n-1; i++) { +
-     // daca valoarea i din vectorul a este mai mica decat cea de pe pozitia i+1 +
-            if (a[i] < a[i+1]{  +
-                // interschimbare +
-         aux = a[i]; +
- a[i] = a[i+1]; +
- a[i+1] = aux; +
- schimbat = 1; +
-     } +
-        } +
-    } while(schimbat);​ +
-} +
-</file>+
  
-====3.2 Selection sort====+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.
  
-  * timp mediu: O(N^2) +<note important>​ 
-  * timp la limită: O(N^2) +În cazul grafurilor neorientate,​ evaluăm fiecare muchie în ambele sensuri. 
-  * memorie: O(1) +</​note>​
-  * Stabil: DA+
  
-===Descriere ​:=== +Paşii algoritmului Bellman-Ford
-Acest algoritm selectează, la fiecare pas i, cel mai mic element din vectorul nesortat(de la poziţia +<​code>​ 
-i până la n).Valoarea minimă găsită la pasul este pusă în vector ​la poziţia i,​facându-se +1. Atribuim fiecărui nod o estimare iniţială a costului: 
-intereschimbarea cu poziţia actuală a minimului.Nu este un algoritm indicat pentru vectorii + 0 pentru nodul sursă(S)
-mari, în majoritatea cazurilor oferind rezultate ​mai slabe decât **insertion sort** şi **bubble sort**. + infinit pentru toate celelalte;​ 
-{{ :​laboratoare:​selection-sort.gif?nolink |}}+2Execută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)); 
 + 2comparăm noua estimare cu vechiul cost(drumul S-v): 
 + dacă noul cost e mai bun 
 + 1. actualizăm cost(drumul S-v) = noul cost; 
 + 2actualizăm parinte(v) = u; (pentru păstrarea muchiei folosite) 
 + altfel păstrăm vechiul cost 
 +</​code>​
  
-===Implementare :=== +===== 4.Drumul de cost minim între oricare 2 noduri ​====== 
-<file cpp> +Următorul algoritm caută cel mai scurt drum de la **orice nod sursă(S)** ​la **fiecare nod destinaţie(D)**.
-void selectionSort(int a[],int n) +
-+
- int i,​j,​aux,​min,​minPoz;​ +
- for(i ​0; i < n - 1;i++) +
-+
- minPoz ​i; +
- min a[i]; +
- for(j ​i + 1;j < n;j++) //selectam minimul +
- //din vectorul ramas( ​de la i+1 la n) +
-+
- if(min > a[j]//sortare crescatoare +
-+
- minPoz = j; //pozitia elementului minim +
- min = a[j]; +
-+
-+
- aux = a[i] ; +
- a[i] = a[minPoz]; //​interschimbare +
- a[minPoz] = aux; +
-+
-+
-</​file>​+
  
-====3.3 Insertion sort==== 
  
-  * timp mediu: O(N^2) +==== 4.1 Algoritmul Floyd-Warshall ==== 
-  * timp la limită: O(N^2) +Rezultatul algoritmului este o matrice N x N(unde = |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**.
-  ​memorie: O(1) +
-  ​Stabil: DA+
  
-===Descriere :=== +Pentru simplitate, algoritmul numerotează nodurile ​de la 1 la N şfoloseşte următoarea construcţie: 
-Spre deosebire ​de alţalgoritmi de sortare, sortarea prin inserţie este folosită destul de des +  defineşte o funcţie costMinim(i,j,k) = cel mai ieftin drum care: 
-pentru sortarea tablourilor cu **număr mic de elemente**. De exemplupoate fi folosit pentru a +  ​* ​   -pleacă din 
-îmbunătăţrutina de sortare rapidă. +     ​-ajunge în j 
- *Sortarea prin inserţie seamană oarecum cu sortarea prin selecţie. Tabloul este împărţit +  ​* ​   -în afară de primul ​şi de ultimul nod, conţine ​numai noduri din {1,2,3,...,k}(primele k noduri).
-imaginar ​în două părţi - o parte sortată şi o parte nesortată. La începutpartea sortată ​conţine +
-primul element al tabloului şi partea nesortată conţine restul tabloului.  +
- *La fiecare pasalgoritmul ia primul element din partea nesortată şi il inserează în locul potrivit al părţii sortate. +
- ​*Când partea nesortată nu mai are nici un elementalgoritmul se opreste.+
  
-{{ :laboratoare:​insertion-sort-example-300px.gif?​nolink |}}+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))**;​
  
-===Implementare :=== +<note tip
-<file cpp+Observaţii:​ 
-void insertionSort(int a[], int n) +  * costMin(i,j,0) = costMuchie(i,j) (dacă există muchie de la la j) sau infinit(altfel)
-+  * costMin(i,j,N) drumul de cost minim de la i la j.
-    int i, j, aux; +
-    for (i = 1; i < n; i++) +
-    { +
-        j = i+
-        while (j > 0 && a[j - 1] > a[j]) +
-        { //cautam pozitia pe care sa mutam a[i+
-            aux = a[j]//​interschimbare +
-            a[ja[- 1]; +
-            a[--j] = aux; +
-        } +
-    } +
-+
-</​file>​+
  
-====3.4 Merge sort====+</​note>​
  
-  * timp mediuO(N log N) +Paşii algoritmului Floyd-Warshall:
-  * timp la limită: O(N log N) +
-  * memorie: O(N) +
-  * Stabil: DA+
  
-===Descriere :=== +<​code>​ 
-În cazul sortării prin interclasare,​ vectorii care se interclasează sunt două secvenţordonate +1. Declarăm matricile:​ 
-din acelaşvector+ dist, matrice N x N şi o iniţializăm dist[i][j] ​infinit, pentru orice i şi j 
-Sortarea prin interclasare utilizează metoda **Divide et Impera**:+ 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 
 +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; 
 + 2next[i][j] = next[i][k]; //pentru urmărirea muchiilor 
 + altfel păstrăm costul vechi 
 +</​code>​
  
- *se împarte vectorul în secvenţe din ce în ce mai mici, astfel încât fiecare secvenţă să fie +Pentru obţinerea nodurilor ​ce formează drumul de cost minim de la u la v, putem folosi următoarea ​secvenţă: 
-ordonată la un moment dat şi interclasată cu o altă secvenţă ​din vector corespunzătoare. +<​code>​ 
- *practicinterclasarea va începe când se ajunge la o secvenţă formată din două elementeAceasta, odată ordonată, se va interclasa cu o alta corespunzătoare(cu elemente). Cele două secvenţe vor alcătui un subşir ordonat din vector mai mare(cu 4 elemente) carela rândul lui, se va interclasa cu un subşir corespunzător(cu 4 elementeş.a.m.d.+funcţie afişareDrum(uv) 
 +1. dacă u == v 
 + 1print(v); STOP 
 +2. print(u)
 +3afişareDrum(next[u][v]v)
 +</​code>​
  
-{{ :​laboratoare:​merge-sort-example-300px.gif?nolink |}}+===== 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.
  
-===Implementare :=== +</note
-<file cpp+<note warning> 
-void mergeSort(int a[],int st, int m, int dr) +O **muchie cu cost negativ** este echivalentă cu **2 arce cu cost negativ** şimplică existenţunui ciclu cu cost negativ. 
-+</note> 
-    int b[100]; +<note tip> 
-    int i, j, k; +Algoritmii **Bellman-Ford** ş**Floyd-Warshall** pot detecta dacă un graf conţine **cicluri cu cost negativ**: 
-    i = 0; j = st; +  * Bellman-Ford:​ executăîncă o evaluare ​tuturor muchiilor la final. Dacă găsim cel puţin o estimare nouă mai bunagraful conţine ​măcar un ciclu cu cost negativ. 
-    // copiem prima jumatate a vectorului a in b +  * Floyd-Warshall:​ putem verificala fiecare pasdacă 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.
-    while (j <= m) +
-        b[i++] = a[j++]; +
-    i = 0; k = st; +
-    // copiem inapoi cel mai mare element la fiecare pas +
-    while (k j && j <= dr) +
-        if (b[i] <= a[j]) +
-            a[k++] = b[i++]; +
-        else +
-            a[k++] = a[j++]; +
-    ​// copiem elementele ramase daca mai exista +
-    while (k j) +
-        ​a[k++] = b[i++]; +
-+
-void merge(int a[],int st, int dr) +
-+
-    if (st < dr) +
-    { +
-        int = (st+dr)/​2;​ +
-        merge(a,st, m); +
-        ​merge(a,m+1dr); +
-        mergeSort(a,​st, m, dr); +
-    } +
-+
-</​file>​+
  
-====3.5 Quick sort====+</​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.
  
-  ​* timp mediu: O(N log N) +</​note>​ 
-  ​timp la limită: O(N^2) +<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**). 
-  ​memorie: O(log N+</​note>​
-  * Stabil: NU+
  
-===Descriere :==+===== 6Exerciții laborator ======
-Quick Sort este unul dintre cei mai rapizi şi mai utilizaţi algoritmi de sortare până în acest moment,​bazându-se pe tehnica "​**Divide et impera**"​.Deşi cazul cel mai nefavorabil este O(N^2), în practică, QuickSort oferă rezultate mai bune decât restul algoritmilor de sortare din clasa "O(N log N)".+
  
-Algoritmul se bazează pe următorii paşi: +  - Daţi un exemplu de graf orientat cu un singur arc cu cost negativ pentru care algoritmul lui Dijkstra dă rezultate greşite. 
- *alegerea unui element pe post de **pivot** +  - Cum putem folosi algoritmul lui Dijkstra sau algoritmul Bellman-Ford pentru a obţine aceleaş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. 
- ​*parcurgerea vectorului din două părţi(de ​la stânga la pivot, ​de la dreapta la pivot, ambele în acelaşi timp) +  - Implementaţi unul din algoritmi pentru ​calcula drumurile ​de cost minim de la un nod sursă la toate celelalte noduri într-un graf cu toate muchiile/​arcele cu cost pozitiv. 
- ​*interschimbarea elementelor care se află pe "​**partea greşită**"​ a pivotului(mutăm la dreapta pivotului elementele mai mari, la stânga pivotului elementel mai mici) +  - Verificaţi dacă un graf conţine cicluri negative.
- *divizarea algoritmului:​ după ce mutăm elementele pe "​**partea corectă**" ​pivotului, avem **2 subşiruri ​de sortat**, iar pivotul se află pe poziţia bună.+
  
-<​note>​Nu există restricţii pentru alegerea pivotuluiAlgoritmul prezentat alege mereu elementul din mijloc</note>+====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. ​
  
-{{ :​laboratoare:​sorting_quicksort_anim.gif?nolink |}}+=== Linux=== 
 +Puteti folosi utilitarul ''​%%wget%%''​ pentru descarcare si utilitarul ''​%%unzip%%''​ pentru dezarhivare.
  
-===Implementare ​:=== +  * ''​%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab7_drumuri_minime-skel.zip%%''​ 
-<file cpp> +  * ''​%%unzip lab7_drumuri_minime-skel.zip%%''​
-void qSort(int a[],int st,int dr) +
-+
-    int temp,​min,​max,​mijl;​ +
-    mijl = a[st+(dr-st)/2]; //luam mijlocul intervalului +
-    min = st; max = dr; +
-    do +
-    { +
-        while(a[min] < mijl) min++; +
-        while(a[max] > mijl) max--; +
-        if(min <= max) //interschimbare +
-        { +
-            temp = a[min]; +
-            a[min++] = a[max]; +
-            a[max--] = temp; +
-        } +
-    }while(min <= max); //la fiecare pas sortam "mai bine" intervalul st-dr +
-    //​cand numai avem ce face schimbam intervalul +
-    if(st < max) qSort(a,​st,​max);​ //​crescator +
-    if(dr > min) qSort(a,​min,​dr);​ //​crescator +
-+
-</​file>​+
  
-===== 4Exerciţii =====+Pentru compilare folositi comanda ''​%%make%%''​. Pentru rulare puteti folosi comanda ''​%%make run%%''​ sau ''​%%./​graph%%''​.
  
-E0. Alegeţi un algoritm A(dintre Bubble, Insertion şi Selection) şi un algoritm B(dintre Merge şi Quick). Introduceţi nişte variabile globale cu care să contorizaţi numărul de **comparaţii** pentru algoritmii A şi B. Comparaţi rezultatele pentru un vector de întregi de lungime n = 20. 
  
-E1. Implementaţi un algoritm(dintre Bubble, Insertion şi Selection) pentru sortarea unui vector cu n cuvinte de maxim 4 litere fiecare.+===Extra===
  
-E2. Implementaţi ​un algoritm(dintre Merge şi Quick) pentru sortarea unui vector ​de structuri, unde fiecare structură reprezintă un moment de timp(int ora,min,sec)+  - Se dă un graf pentru care se cunoaşte drumul ​de cost minim de la un nod sursă(Sla un nod destinaţie(D). Dacă adăugăm 100 la costul fiecărei muchii, se modifică drumul de cost minim? (dacă dadaţi un exemplu; dacă nuexplicaţde ce)
- +  - Aceeaşîntrebare dacă înmulţim fiecare cost cu 100
-E3. Se dă un vector de n întregi, iar toate valorile din vector sunt între 0 şi 1000. Sortaţi vectorul în timp O(n). +  - 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şcost(1)? Cum adaptaţsoluţia în cazul în care toate muchiile au costul 1 sau 2? 
- +  - Daţ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.
-<note tip>Este uşor să verificăm dacă două elemente sunt în ordine atunci când elementele au o structură simplă. Dacă avem o structură mai complicată, atunci este recomandat să definim o funcţie de comparare pe care s-o apelăm pentru verificarefără a încărca funcţia de sortare.</​note>​ +
- +
-Puteţutiliza următorul model pentru exerciţiile propuse: {{ :​laboratoare:​scheletsortare.zip |}} +
- +
-===== 4. Exerciţii de laborator ​(Linux) ===== +
-Pentru acest laborator putețdescărca scheletul ​de cod de [[http://​elf.cs.pub.ro/​sda-ab/​wiki/​_media/​laboratoare/​lab8_sortari-skel.zip|aici]]. Descărcațarhiva ș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/​lab8_sortari-skel.zip%%''​ 
-  * ''​%%unzip lab8_sortari-skel.zip%%''​ 
  
-Pentru compilare folositi comanda ''​%%make%%''​Pentru rulare puteti folosi comanda ''%%make run%%''​ sau ''​%%./sort%%'​'.+===== 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]]
  
laboratoare/laborator-08.txt · Ultima modificare: 2018/04/23 19:48 de către mihai.iacov