Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Ești aici: Structuri de date și algoritmi » Laboratoare » Laborator 10: Divide et impera și Greedy
Traseu:
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 Ambele părți următoarea reviziune
laboratoare:laborator-10 [2017/04/29 20:19]
mihai.iacov [4 Exerciții propuse] 		laboratoare:laborator-10 [2017/04/29 20:34]
mihai.iacov [4 Exerciții propuse]
Linia 210: Linia 210:
 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). 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 nu mai e optimă tehnica Greedy.+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. 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.+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-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".+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. Problema 5 (extras logaritm) fără a vă folosi de funcţia pow, ci doar de funcţia construită la 4 (extragerea radicalului).+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<sup>2</sup> 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.
  
laboratoare/laborator-10.txt · Ultima modificare: 2017/05/08 15:24 de către mihai.iacov

Unelte pagină

Exceptând locurile unde este altfel specificat, conținutul acestui wiki este licențiat sub următoarea licență: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki