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 Urmatoarea versiune Ambele părți următoarea reviziune | ||
laboratoare:laborator-10 [2017/02/19 22:33] florina_elena.barbu [Laborator 10: D&I și Greedy] |
laboratoare:laborator-10 [2017/04/29 19:58] mihai.iacov [4 Exerciții propuse] |
||
---|---|---|---|
Linia 5: | Linia 5: | ||
*Însușirea abilităților de implementare a algoritmilor bazați pe greedy | *Însușirea abilităților de implementare a algoritmilor bazați pe greedy | ||
*Înțelegerea implementării algoritmilor Greedy privind probleme de optimizare | *Înțelegerea implementării algoritmilor Greedy privind probleme de optimizare | ||
- | *Înțelegera utilității practice ale D&I: | + | *Înțelegera utilității practice ale paradigmei Divide et Impera: |
| | ||
| | ||
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 " | + | Este in înțeles de ce un astfel de algoritm se numeste " |
====2.2 Implementare ==== | ====2.2 Implementare ==== | ||
Descrierea formală a algoritmului este următoarea: | Descrierea formală a algoritmului este următoarea: | ||
- | <code> | + | <file cpp> |
function Greedy (C) | function Greedy (C) | ||
//C = mulțimea candidaților | //C = mulțimea candidaților | ||
Linia 30: | Linia 30: | ||
S = S∪(x); | S = S∪(x); | ||
| | ||
- | </code> | + | </file> |
====2.3 Probleme tip rezolvate cu acest algoritm==== | ====2.3 Probleme tip rezolvate cu acest algoritm==== | ||
Linia 45: | Linia 45: | ||
*Explicație: | *Explicație: | ||
- | 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, | + | 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, |
\\ | \\ | ||
===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 |
- | 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/ | ||
+ | |||
+ | <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. | ||
+ | </ | ||
+ | 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), | ||
+ | * 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. | ||
+ | </ | ||
=====3 Paradigma Divide et impera ===== | =====3 Paradigma Divide et impera ===== | ||
Linia 69: | Linia 86: | ||
====3.2 Implementare==== | ====3.2 Implementare==== | ||
- | <code> | + | <file cpp> |
void divide_et_impera(int P[],int n,int S[]{ | void divide_et_impera(int P[],int n,int S[]{ | ||
if(n <= n0 ) | if(n <= n0 ) | ||
Linia 81: | Linia 98: | ||
} | } | ||
} | } | ||
- | </code> | + | </file> |
- | # poza pana la urmă#\ | + | |
====3.3 Complexitate==== | ====3.3 Complexitate==== | ||
Linia 94: | Linia 111: | ||
Singura operație case se poate efectua este de selecta un disc ce se află în vârful unei tije si plasarea lui în vârful altei tije,astfel încât să nu fie așezat deasupra unui disc de dimensiune mai mică decât a sa.\\ | Singura operație case se poate efectua este de selecta un disc ce se află în vârful unei tije si plasarea lui în vârful altei tije,astfel încât să nu fie așezat deasupra unui disc de dimensiune mai mică decât a sa.\\ | ||
Să se găsească un algoritm prin ca\re se mută toate discurile pe tija B.\\ | Să se găsească un algoritm prin ca\re se mută toate discurile pe tija B.\\ | ||
- | #poza cu tijele# | + | {{: |
+ | {{ : | ||
+ | <note tip> | ||
Pentru rezolvarea problemei folosim următoarea strategie: | Pentru rezolvarea problemei folosim următoarea strategie: | ||
*Mutăm primele n-1 discuri de pe tija A pe tija C folosindu-ne de tija B. | *Mutăm primele n-1 discuri de pe tija A pe tija C folosindu-ne de tija B. | ||
*Mutăm discul n pe tija B. | *Mutăm discul n pe tija B. | ||
*Mutăm apoi cele n-1 discuri de pe tija C pe tija B folosindu-ne de tija A. | *Mutăm apoi cele n-1 discuri de pe tija C pe tija B folosindu-ne de tija A. | ||
- | \\ | + | |
+ | </ | ||
+ | |||
+ | |||
Linia 108: | Linia 131: | ||
Se dă un vector sortat crescător ce conține valori reale distincte și o valoare x. \\ | Se dă un vector sortat crescător ce conține valori reale distincte și o valoare x. \\ | ||
Să se găsească pe ce poziție apare x (introdus de la tastatură) în vectorul dat. \\ | Să se găsească pe ce poziție apare x (introdus de la tastatură) în vectorul dat. \\ | ||
- | Pentru rezolvarea problemei folosim următoarea strategie: | + | <note tip>Pentru rezolvarea problemei folosim următoarea strategie: |
- | *Împărțim vectorul în doi sub-vectori de dimensiunea n/2. \\ | + | *Împărțim vectorul în doi sub-vectori de dimensiunea n/2. |
- | *Aplicăm algoritmul de căutare binară pe sub-vectorul care conține valoarea căutată | + | *Aplicăm algoritmul de căutare binară pe sub-vectorul care conține valoarea căutată |
- | *Soluția sub-problemei devine soluția problemei inițiale, motiv pentru care nu mai este nevoie de etapa de combinare. | + | *Soluția sub-problemei devine soluția problemei inițiale, motiv pentru care nu mai este nevoie de etapa de combinare. |
- | \\ | + | |
+ | </ | ||
- | #poza binary search# | ||
Linia 138: | Linia 161: | ||
*Acest procedeu se aplică în mod repetat până când lungimea intervalului scade cu 2*ε(β - α < 2*ε)\\ | *Acest procedeu se aplică în mod repetat până când lungimea intervalului scade cu 2*ε(β - α < 2*ε)\\ | ||
- | #poza funcție# | + | {{ : |
===3.4.4 Fractali=== | ===3.4.4 Fractali=== | ||
Fractalii de tip Divide-et-Impera sunt construiți, | Fractalii de tip Divide-et-Impera sunt construiți, | ||
Fractalii generați prin metode Divide-et-Impera au la bază un model simplu, pe baza căruia se adaugă (în cazul arborilor și al triunghiului lui Sierpinski) sau se înlocuiesc (în cazul fractalilor Koch) segmente, după o regulă bine definită, așa cum se poate observa: | Fractalii generați prin metode Divide-et-Impera au la bază un model simplu, pe baza căruia se adaugă (în cazul arborilor și al triunghiului lui Sierpinski) sau se înlocuiesc (în cazul fractalilor Koch) segmente, după o regulă bine definită, așa cum se poate observa: | ||
- | # poza fractali arbore# | + | {{ : |
Se calculează coordonatele punctului de sfârșit al liniei ce trebuie reprezentată, | Se calculează coordonatele punctului de sfârșit al liniei ce trebuie reprezentată, | ||
Apoi este apelată de doua ori funcția de desenare, cu parametrii modificați: | Apoi este apelată de doua ori funcția de desenare, cu parametrii modificați: | ||
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, | Î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, | ||
La fractalul de tip Koch triunghiular, | La fractalul de tip Koch triunghiular, | ||
- | #poza fractali Koch triunghiular# | + | {{ : |
Ca și în cazul arborelui, | Ca și în cazul arborelui, | ||
Se pornește de la un triunghi în care au fost desenate liniile mijlocii și se desenează liniile mijlocii ale triunghiurilor mai mici marginale formate. \\ | Se pornește de la un triunghi în care au fost desenate liniile mijlocii și se desenează liniile mijlocii ale triunghiurilor mai mici marginale formate. \\ | ||
- | # poza fractali sierpinski# | + | {{ : |
**Aplicații practice!** \\ | **Aplicații practice!** \\ | ||
Linia 162: | Linia 186: | ||
Compresia cu fractali se bazează pe faptul că în anumite imagini, părți ale imaginii seamănă cu părți ale aceeași imagini.\\ | Compresia cu fractali se bazează pe faptul că în anumite imagini, părți ale imaginii seamănă cu părți ale aceeași imagini.\\ | ||
Tehnica copiază imaginea originală în 2 seturi: ranguri și domenii, apoi computer-ul face legătura fiecărui rang cu un domeniu și produce o trasformare de la domeniu la rang: | Tehnica copiază imaginea originală în 2 seturi: ranguri și domenii, apoi computer-ul face legătura fiecărui rang cu un domeniu și produce o trasformare de la domeniu la rang: | ||
- | # poza compresia de data# | + | {{ : |
===3.4.5 Parser top-down=== | ===3.4.5 Parser top-down=== | ||
Linia 173: | Linia 197: | ||
* **Gestiunea structurilor de date** | * **Gestiunea structurilor de date** | ||
* **Tratarea erorilor**\\ | * **Tratarea erorilor**\\ | ||
- | # poza etapele procesului de compilare# | + | \\ {{ : |
- | \\ | ||
Vom trata problema analizei sintactice care are două obiective principale: | Vom trata problema analizei sintactice care are două obiective principale: | ||
*Stabilește dacă un cuvânt dat aparține sau nu limbajului | *Stabilește dacă un cuvânt dat aparține sau nu limbajului | ||
Linia 183: | Linia 206: | ||
=====4 Exerciții propuse===== | =====4 Exerciții propuse===== | ||
- | 1.// [1p]// | + | 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, 2, 5, 10, 20, 50, 100} ($). Încercaţi să explicaţi de ce nu mai e optimă tehnica Greedy. |