Autor Zpráva
thases
Profil
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
thases - takéto akademické problémy odtrhnuté od reality, má to vôbec zmysel riešiť?
thases
Profil
tiso
Znášam vnútornú dilemu, ženie ma to povedať, že nemá, ale áno, MÁ :).
tiso
Profil
thases - toto je celé zadanie? Nemáš viac informácií?
Kajman_
Profil *
Asi máte využít tranzitivitu.
TomášK
Profil
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
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
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
TomášK - pravdu máš, sorry...
thases
Profil
TomášK
Diki moc, toto vyzerá dobre :). Zachránil si ma...

Vaše odpověď


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm:

0