Unelte utilizator

Unelte site


laboratoare:laborator-10

Diferențe

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

Link către această vizualizare comparativă

Ambele părți revizuirea anterioară Versiuni anterioare
Urmatoarea versiune
Versiuni anterioare
laboratoare:laborator-10 [2017/02/20 01:46]
florina_elena.barbu [4 Exerciții propuse]
laboratoare:laborator-10 [2017/05/08 15:24] (curent)
mihai.iacov [4 Exerciții propuse]
Linia 15: Linia 15:
 ====2.1 Prezentare generală==== ====2.1 Prezentare generală====
 Algoritmii de tip greedy vor să construiască într-un mod cât mai rapid soluția unei probleme.Ei se caracterizează prin luarea unor decizii rapide care duc la găsirea unei soluții potențiale a problemei.\\  Algoritmii de tip greedy vor să construiască într-un mod cât mai rapid soluția unei probleme.Ei se caracterizează prin luarea unor decizii rapide care duc la găsirea unei soluții potențiale a problemei.\\ 
-Este in înțeles de ce un astfel de algoritm se numeste "lacom" (greedy), deoarece la fiecare pas, funcția alege cel mai bun candidat la momentul respectiv, fără să-i pese de viitor și fără să revină asupra alegerii. Daca un candidat este inclus în soluție, el rămâne în soluție, iar dacă un candidat este exclus din soluție, el nu va mai fi niciodată reconsiderat. \\ +Este in înțeles de ce un astfel de algoritm se numeste "lacom" (greedy), deoarece la fiecare pas, funcția alege **cel mai bun candidat la momentul respectiv****fără** să-i pese de **viitor** și **fără să revină** asupra alegerii. Daca un candidat este inclus în soluție, el rămâne în soluție, iar dacă un candidat este exclus din soluție, el nu va mai fi niciodată reconsiderat. \\ 
  
 ====2.2 Implementare ==== ====2.2 Implementare ====
Linia 45: Linia 45:
 *Explicație: punctul 2 se afla în primele 3 intervale, iar punctul 14 în ultimele 2 *Explicație: punctul 2 se afla în primele 3 intervale, iar punctul 14 în ultimele 2
  
-Soluție:Se observă că dacă x este un punct din M care nu este capăt dreapta al nici unui interval, o translație a lui x la dreapta care îl duce în capătul dreapta cel mai apropiat nu va schimba intervalele care conțin punctul. Prin urmare,există o mulțime de cardinal minim pentru care toate punctele x sunt capete dreapta.+Soluție:Se observă că dacă x este un punct din M care nu este capăt dreapta al nici unui interval, o translație a lui x la dreapta care îl duce în capătul dreapta cel mai apropiat nu va schimba intervalele care conțin punctul. Prin urmare,există o mulțime (M) de cardinal minim pentru care toate punctele x sunt capete dreapta.
 \\  \\ 
 ===2.3.3 Problema rucsacului=== ===2.3.3 Problema rucsacului===
Linia 57: Linia 57:
    *Nu intră în totalitate în rucsac și atunci se determină ce procent din obiectul respectiv va intra în rucsac; în acest caz se va cumula la câștigul total procentul de profit asociat părții din obiectul încărcat în rucsac, iar greutatea rămasă va fi zero.\\    *Nu intră în totalitate în rucsac și atunci se determină ce procent din obiectul respectiv va intra în rucsac; în acest caz se va cumula la câștigul total procentul de profit asociat părții din obiectul încărcat în rucsac, iar greutatea rămasă va fi zero.\\
  
-===2.3.4 Problema comisului voiajor=== +===2.3.4 Problema comisului voiajor (TSP)=== 
-TODO !!!!!!+Un comis-voiajor stă într-un oraş (X1) şi vrea să viziteze toate cele N oraşe dintr-o regiune (X1, X2, ..., XN), plecând dimineaţa de acasă (X1) şi întorcandu-se (tot în X1) la finalul zilei. 
 + 
 +În mod ideal, el îşi doreşte să viziteze fiecare oraş exact o singură dată (excepţie făcând numai oraşul X1 unde se întoarce seara), iar drumul găsit să fie cât mai scurt. 
 + 
 +Problema poate fi modelată cu grafuri (oraş = nod, drum între 2 oraşe = muchie) şi cerinţa devine găsirea unui **Ciclu/Circuit Hamiltonian minim** (un ciclu care conţine o singură dată fiecare nod, cu excepţia nodului de plecare care coincide doar cu nodul final, şi care este de cost minim). 
 + 
 +<note warning> 
 +Soluţia de **cost minim** pentru TSP **nu poate fi garantată** cu un algoritm de tip Greedy, dar un astfel de algoritm poate fi folosit pentru a găsi în timp util un drum. 
 +</note> 
 +Varianta **Greedy** (pură): -parcurgem în adâncime (DFS) graful din nodul de plecare (X1), continuând mereu pe cea mai ieftină muchie. La prima fundătură (primul nod din care nu mai avem vecini nevizitaţi), algoritmul se opreşte: 
 +  * dacă algoritmul s-a blocat după ce a vizitat N noduri şi ultimul nod găsit (nodul curent) este vecin cu nodul de plecare (X1), atunci: mesaj de reuşită + soluţia găsită. 
 +  * altfel: mesaj de nereuşită (+ eventual soluţia parţială). 
 + 
 +Varianta **Greedy + revenire**: -la fel ca varianta Greedy (pură), dar permitem revenirea în cazul unui blocaj, respectând parcurgerea DFS (eliminăm nodul curent din soluţie, ne întoarcem la nodul găsit imediat înainte de nodul curent şi, din acel nod, alegem următoarea variantă). 
 + 
 +<note warning> 
 +Această variantă **nu** mai respectă principiul de bază al tehnicii Greedy, va avea nevoie de mai mult timp, dar va oferi un răspuns mai bun. 
 +</note>
  
 =====3 Paradigma Divide et impera ===== =====3 Paradigma Divide et impera =====
Linia 154: Linia 171:
 Apoi este apelată de doua ori funcția de desenare, cu parametrii modificați: punctele de început ale următoarei linii vor avea coordonatele punctului de sfârșit al ultimelei linii desenate, lungimea va fi micșorată printr-un raport stabilit (ex: 4/7), numărul nivelului va fi cu o unitate mai mic, iar unghiul va fi modificat cu 45° (o dată în plus,a doua oară în minus) \\  Apoi este apelată de doua ori funcția de desenare, cu parametrii modificați: punctele de început ale următoarei linii vor avea coordonatele punctului de sfârșit al ultimelei linii desenate, lungimea va fi micșorată printr-un raport stabilit (ex: 4/7), numărul nivelului va fi cu o unitate mai mic, iar unghiul va fi modificat cu 45° (o dată în plus,a doua oară în minus) \\ 
 Condiția de efectuare a instrucțiunilor din funcție este ca numărul de niveluri ale fractalului să fie mai mare decât 0. \\  Condiția de efectuare a instrucțiunilor din funcție este ca numărul de niveluri ale fractalului să fie mai mare decât 0. \\ 
 +\\
 În cazul fractalilor de tip **Koch**, liniile nu se adaugă, ci se înlocuiesc. Pentru calcularea lungimii, poziției și unghiului fiecărui segment al liniei, funcția este apelată de n ori,segmentul fiind desenat atunci când nivelul devine 0. \\  În cazul fractalilor de tip **Koch**, liniile nu se adaugă, ci se înlocuiesc. Pentru calcularea lungimii, poziției și unghiului fiecărui segment al liniei, funcția este apelată de n ori,segmentul fiind desenat atunci când nivelul devine 0. \\ 
 La fractalul de tip Koch triunghiular, coordonatele care ne interesează se află la prima treime, a doua treime și jumatatea segmentului. La fiecare dintre acestea, unghiul de desenare se modifică cu 60°,-120°, respectiv 60°. \\  La fractalul de tip Koch triunghiular, coordonatele care ne interesează se află la prima treime, a doua treime și jumatatea segmentului. La fiecare dintre acestea, unghiul de desenare se modifică cu 60°,-120°, respectiv 60°. \\ 
Linia 189: Linia 207:
 =====4 Exerciții propuse===== =====4 Exerciții propuse=====
 1. Simulați un proces de back-up a unor date fără a partiționa mediul de stocare. 1. Simulați un proces de back-up a unor date fără a partiționa mediul de stocare.
 +
 +2. Folosiţi un algoritm de tip Greedy pentru a găsi numărul minim de bancnote necesare pentru a da o anumită sumă de bani ca rest. Presupunem numai valori întregi pentru suma de bani şi următoarele bancnote: {1, 5, 10, 50, 100} (RON).
 +
 +3*. Găsiţi un exemplu pentru care un algoritm de tip Greedy nu ar funcţiona pentru o problemă similară, dar care foloseşte următoarele bancnote: {1, 3, 5, 15, 30, 50, 150}. Încercaţi să explicaţi de ce, în acest caz, tehnica Greedy nu mai e optimă.
 +
 +4*. Găsiţi un exemplu pentru care varianta Greedy (pură) de rezolvare a problemei TSP (comis-voiajor) găseşte o soluţie, dar aceasta nu este optimă.
 +
 +5. Aproximaţi, printr-o abordare de tip Divide et Impera, cu o eroare (relativă) de maxim 1e-6, funcţia sqrt(n) (extragerea rădăcinii pătrate a unui număr). Nu aveţi voie să folosiţi nicio funcţie din "math.h". Încercaţi să extindeţi exerciţiul pentru extragerea radicalului de ordin 3.
 +
 +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. (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. 
 +
 +=== Linux===
 +Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
 +
 +  * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab10_di_si_greedy-skel.zip%%''
 +  * ''%%unzip lab10_di_si_greedy-skel.zip%%''
 +
 +Pentru compilare folositi comanda ''%%make%%''.
 +
laboratoare/laborator-10.1487547982.txt.gz · Ultima modificare: 2017/02/20 01:46 (editare externă)