Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Tree decompositions  (Citit de 2826 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« : Februarie 20, 2009, 03:06:29 »

Comentarii la articolul Tree decompositions
Memorat

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #1 : Ianuarie 19, 2010, 20:35:37 »

Poate povesti cineva puțin mai mult la ce se referă când zice "Se elimina cel mai lung lant radacina-frunza din arbore si se apeleaza recursiv pentru restul componentelor conexe" și cum se face update? Smile
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #2 : Ianuarie 19, 2010, 23:36:41 »

Poate povesti cineva puțin mai mult la ce se referă când zice "Se elimina cel mai lung lant radacina-frunza din arbore si se apeleaza recursiv pentru restul componentelor conexe" și cum se face update? Smile

Iniţial, consideri cel mai lung lanţ (cu cele mai multe noduri) de la rădăcină la oricare din frunze. Reţii acest lanţ şi îl scoţi din arbore. Astfel, dacă lanţul ăsta „taie” arborele pe jumătate o să ai doi arbori separaţi pe care repeţi procedeul. Apelând recursiv rezolvi aceeaşi problemă. Şi vei reţine astfel o mulţime de lanţuri ce reprezintă descompunerea arborelui. Ulterior, pe ele faci operaţiile.

Query-urile se fac pe un arbore de intervale. Deci, un update din problemă se reduce la un update pe un arbore de intervale. Mai întreabă dacă nu ai înţeles.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #3 : Ianuarie 20, 2010, 13:27:06 »

Nu am prea înțeles cum fac acea descompunere, pentru că dacă scot un lanț din arbore e foarte posibil să apară o grămadă de arbori mai mici, și ce se reține mai exact în Path[].parrent?
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #4 : Ianuarie 20, 2010, 13:44:34 »

Intocmai. Apar o gramada de arbori mai mici si apelezi aceeasi functie recursiv pentru fiecare dintre ei. Parent e lantul de care trebuie sa unesti lantul tau ca sa il pui pe drumul spre radacina.
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #5 : Ianuarie 20, 2010, 14:09:26 »

Dar numărul de lanțuri nu poate să fie mai mare de sqrt(N)? De exemplu, dacă am N-1 noduri sunt legate de rădăcină, nu vor fi N-1 lanțuri?
Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #6 : Ianuarie 20, 2010, 14:24:18 »

Daca scoti un lant din cele N-1, scoti radacina => raman N - 2 frunze.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #7 : Ianuarie 20, 2010, 14:26:11 »

Dar numărul de lanțuri nu poate să fie mai mare de sqrt(N)? De exemplu, dacă am N-1 noduri sunt legate de rădăcină, nu vor fi N-1 lanțuri?

Ba da, numarul total de lanturi poate sa fie O(N). Ceea ce ne intereseaza este ca numarul de lanturi prin care treci de la orice nod la radacina sa fie de ordinul O(sqrt(N)).
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #8 : Ianuarie 20, 2010, 16:42:00 »

Dar numărul de lanțuri nu poate să fie mai mare de sqrt(N)? De exemplu, dacă am N-1 noduri sunt legate de rădăcină, nu vor fi N-1 lanțuri?

Scrie în articol, deasupra figurii 2... „Este evident ca memoria ocupata este O(N), fiecare nod fiind inclus intr-un singur lant. Numarul maxim de lanturi prin care putem trece pornind din radacina pana intr-una din frunze, este O(sqrt(N)).”
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines