Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare | ||
laboratoare:laborator-10 [2017/04/29 19:26] mihai.iacov [2.3 Probleme tip rezolvate cu acest algoritm] |
laboratoare:laborator-10 [2017/05/08 15:24] (curent) mihai.iacov [4 Exerciții propuse] |
||
---|---|---|---|
Linia 58: | Linia 58: | ||
===2.3.4 Problema comisului voiajor (TSP)=== | ===2.3.4 Problema comisului voiajor (TSP)=== | ||
- | 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. | + | 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. | Î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/ | + | Problema poate fi modelată cu grafuri (oraş = nod, drum între 2 oraşe = muchie) şi cerinţa devine găsirea unui **Ciclu/ |
<note warning> | <note warning> | ||
Linia 207: | 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, | ||
+ | |||
+ | 6. Aproximaţi, | ||
+ | |||
+ | 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 " | ||
+ | |||
+ | |||
+ | ===== 5. Exerciţii de laborator (Linux) ===== | ||
+ | Pentru acest laborator puteți descărca scheletul de cod de [[http:// | ||
+ | |||
+ | === Linux=== | ||
+ | Puteti folosi utilitarul '' | ||
+ | |||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | Pentru compilare folositi comanda '' | ||
+ |