Autor | Zpráva | ||
---|---|---|---|
thases Profil |
#1 · Zasláno: 22. 4. 2009, 13:25:54
Ahojte,
mám jeden zaujímavý algoritmický problém. Znie nasledovne: Pracujete s databázou, ktorá obsahuje informácie o študijných odboroch. Každý študent študuje práve jeden študijný odbor. Každý študijný odbor môže študovať viac študentov. Povieme, že 2 študenti sú spolužiaci, práve keď študujú jeden študijný odbor. Úlohou je zistiť, či v súbore N študentov existuje skupina aspoň N/2 spolužiakov, tj. študentov, ktorí študujú rovnaký odbor. Problémom je, že jediný databázový dotaz, ktorý je povolené použiť je dotaz na dvoch študentov, ktorý odpovie, či sú alebo nie sú spolužiaci. Cieľom je navrhnúť algoritmus, ktorý požadovanú odpoveď nájde a pritom prevedený počet dotazov bude O (N log N). Pomôckou je technika rozdeľ a panuj. |
||
tiso Profil |
#2 · Zasláno: 22. 4. 2009, 13:34:27
thases - takéto akademické problémy odtrhnuté od reality, má to vôbec zmysel riešiť?
|
||
thases Profil |
#3 · Zasláno: 22. 4. 2009, 13:47:56
tiso
Znášam vnútornú dilemu, ženie ma to povedať, že nemá, ale áno, MÁ :). |
||
tiso Profil |
#4 · Zasláno: 22. 4. 2009, 14:10:10
thases - toto je celé zadanie? Nemáš viac informácií?
|
||
Kajman_ Profil * |
#5 · Zasláno: 22. 4. 2009, 14:21:55
Asi máte využít tranzitivitu.
|
||
TomášK Profil |
#6 · Zasláno: 22. 4. 2009, 16:36:28
Popíšu algoritmus spol(S), který zavolám na sadu studentů S a on mi řekne, jestli existuje množina spolužáků větší než N/2 a pokud ano, tam mi ji řekne, kteří studenti do ní patří. Rozdělím si je na dvě poloviny A = (a1, a2, ..., aN/2) a B = (b1, b2, ..., bN/2), na každou polovinu se zavolám rekurzivně. Nechť max(A) je největší množina spolužáků v A, max(B) totéž v B.
1, Pokud max(A) < N/4 a max(B) < N/4, pak neexistuje skupina spolužáků > N/2 (největší možná množina max(A)+max(B), pokud by studovali stejný obor a i ta má méně než N/4 + N/4 = N/2. 2, Pokud max(A) > N/4 a max(B) > N/4, pak pokud max(A) i max(B) studují stejný obor, pak mi tyto množiny dají dohromady > N/2 spolužáků. Pokud nestudují stejný obor, pak se pokusím max(A) doplnit o studenty z B, kteří nejsou v max(B). Pokud se mi podaří najít dost studentů, abych tu množinu doplnil na N/2, vyhrál jsem a končím, pokud ne, zkusím doplnit max(B) doplnit o studenty z A, kteří nejsou v max(A). Pokud ani to se nepodaří, pak skupina > N/2 neexistuje. 3, Pokud max(A) > N/4 a max(B) < N/4, pak se pokusím studenty z max(A) doplnit o studenty z B, tak abych dostal množinu aspoň N/2. Pokud se mi to nepodaří, pak taková množina neexistuje. Ke složitosti: Nechť T(n) je počet dotazů pro množinu velikosti n. platí T(n) = 2*T(n/2) + n/2, kde 2*T(n/2) je třeba na zjištění max(A) a max(b) n/2 je maximální počet prvků, který budu zkoušet do množiny doplnit. A dle master theoremu je celková složitost O(n log n). Snad jsem se někde neseknul :) |
||
tiso Profil |
#7 · Zasláno: 22. 4. 2009, 17:09:10
TomášK - sekol si sa, nestačí ti kontrolovať max(A)>N/4 ale všetky množiny spolužiakov z A väčšie ako N/4, a rovnako pre B.
|
||
TomášK Profil |
#8 · Zasláno: 22. 4. 2009, 17:28:59
tiso
Zdá se mi, že to nemůže nastat - pokud najdu v A množinu max(A) > A/2 = N/4, pak už tam žádná další množina spolužáků větší než N/4 nemůže být - protože mi zbývá méně než N/4 studentů, ze kterých bych ji měl složit. |
||
tiso Profil |
#9 · Zasláno: 22. 4. 2009, 17:37:06
TomášK - pravdu máš, sorry...
|
||
thases Profil |
#10 · Zasláno: 24. 4. 2009, 21:28:22
TomášK
Diki moc, toto vyzerá dobre :). Zachránil si ma... |
||
Časová prodleva: 15 let
|
0