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
Ultima versiune Both sides next revision
laboratoare:laborator-08 [2017/04/20 17:53]
iulian.matesica [4. Exerciţii]
laboratoare:laborator-08 [2018/02/25 20:45]
mihai.iacov
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). +
- +
-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). +
- +
-<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 verificare, fără a încărca funcţia de sortare.</​note>​ +
- +
-Puteţi utiliza următorul model pentru exerciţiile propuse: {{ :​laboratoare:​scheletsortare.zip |}} +
- +
-===== 4. 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/​lab8_sortari-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/​lab8_sortari-skel.zip%%''​ +  ​- 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). 
-  ​* ''​%%unzip lab8_sortari-skel.zip%%''​+  - 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.
  
-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]]
 +    - [[http://​example.com|Link extern]]
laboratoare/laborator-08.txt · Ultima modificare: 2018/04/23 19:48 de către mihai.iacov