Keresési problémák

SZAKDOLGOZAT

Wiener Gábor  Katona O.H. Gyula
V. matematikus–hallgató  témavezető

Eötvös Loránd Tudományegyetem Természettudományi Kar

Tartalomjegyzék

1. A kombinatorikus keresés . . . . . . . . . . . . . . . 2 1.1. Bevezetés . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2. Keresési fák . . . . . . . . . . . . . . . . . . . . . . . 6 1.3. Keresési kódok . . . . . . . . . . . . . . . . . . . . . 7 1.4. Játékelméleti megközelítés . . . . . . . . . . . . . . . 8

2. Alapvető problémák . . . . . . . . . . . . . . . . . . . 10

2.1. A legrosszabb eset–probléma

tetszőleges teszt–függvények mellett . . . . . . . . . . 10 2.2. Az átlagos eset–probléma

tetszőleges teszt–függvények mellett . . . . . . . . . . 12 2.3. Nem adaptív algoritmusok . . . . . . . . . . . . . . . 20 2.4. Bináris keresési eljárások . . . . . . . . . . . . . . . . 21

3. Többségi elem keresése . . . . . . . . . . . . . . . . . 29 3.1. Bevezetés . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2. A probléma átfogalmazása . . . . . . . . . . . . . . . 30 3.3. A legrosszabb eset–probléma . . . . . . . . . . . . . . 33 3.4. Az átlagos eset–probléma . . . . . . . . . . . . . . . . 38 3.5. Nyitott problémák . . . . . . . . . . . . . . . . . . . 44

1. A kombinatorikus keresés

1.1. Bevezetés

A kombinatorikus keresés fogalma a ’60–as évek elején alakult ki. Ekkor történt ugyanis, hogy Rényi Alfréd Hillman típusú kocsija elromlott. A hibáért valamelyik elektromos berendezés volt felelős, de a szerelők nem tudták megmondani, hogy melyik, így ezt Rényinek magának kellett kiderítenie. Ez végül sikerült, és az eljárás közben Rényi kifejlesztette a keresés általános matematikai elméletét.

Az autót tekinthetjük alkatrészei véges halmazának, ami pontosan akkor működik, ha az alkatrészek hibátlanok. Ha tehát az autó nem működik, legalább egy alkatrész hibás. (Remélhetőleg pontosan egy alkatrész — így ezt feltesszük …) Ahhoz, hogy kiderítsük, melyik, a részek bizonyos halmazait tesztelhetjük, azaz megvizsgálhatjuk, hogy együtt működnek-e. Ha nem, akkor köztük van a hibás rész, ha igen, akkor a maradékban. Szerencsés esetben előbb–utóbb megtaláljuk a hibát.

A keresési problémáknak természetesen más forrásaik is vannak. Legyen X katonák egy halmaza a II. világháborúban. Mindegyiküktől rendelkezésre áll egy vérminta, ezt használhatjuk, hogy kiderítsük, kik a szifilisszel fertőzöttek közülük. Erre szolgál a Wasserman–teszt, ami azonban meglehetősen költséges. Ezért érdemes a vérminták közül néhányat összeönteni, és együtt vizsgálni; így azt deríthetjük ki, hogy a katonák egy (általunk választott) részhalmazában van-e fertőzött. Ez az úgynevezett csoport–tesztelési modell.

A harmadik fő forrás a jól ismert sorbarendezési feladat, amely eredetileg Steinhaustól származik [19]. Bár első ránézésre nem nyilvánvaló, de ez speciális esete a csoport–tesztelésnek. Legyen X az n elem összes permutációinak halmaza. (|X| = n!). ezek közül keresünk egyet. Két elem összehasonlítása meghatározza, hogy a keresett permutáció melyik n! ; 2–höz tartozik.

Számos más példa is létezik, (hazudós barkochba, hamispénz–keresés egykarú mérleggel, kétkarú mérleggel, stb.) de ezek taglalása helyett most már fordítsuk figyelmünket a matematikai modellre!

1.1. Definíció. Legyen S egy nem üres halmaz, x ∈ S, és legyen F az S–en értelmezett függvények egy családja. S–et keresési tartománynak (search domain), F–et teszt–családnak (test family) hívjuk. Választunk egy f_{1} ∈ F függvényt és megkapjuk f_{1}(x) értékét. Ezután választunk egy f_{2} ∈ F–et^{1} és megkapjuk f_{2}(x)- et, és így tovább. Az A = (f_{1}, f_{2}, …, f_{k}) ,(f_{i} ∈ F, i = 1, 2, …, k) függvény– sorozat (sikeres) kereső–algoritmus, ha az f_{1}(x), f_{2}(x), …, f_{k}(x) értékek egyértelműen meghatározzák x–et. Feltesszük, hogy legalább egy ilyen algoritmus mindig létezik. (S, F)–et keresési eljárásnak (search process) nevezzük.

A keresési eljárások igen sokfélék lehetnek, és sokféle tulajdonság szerint osztályozhatók. Tekintsük át a fontosabbakat:

1Hogy ez függhet-e f_{1}(x)–től, arról később szólunk.

1. S számossága. Ha S megszámlálható, diszkrét eljárásról, egyébként folytonos eljárásról beszélünk.

2. S–en megadható egy ζ valószínűségi eloszlás, ami meghatározza, hogy milyen valószínűséggel lesznek azonosak az egyes elemek a keresettel. Ha ζ nincs megadva, bizonyos esetekben feltételezhetjük az egyenletes eloszlást.

3. F szerkezete. Általában csak igen speciális függvények szerepelhetnek F– ben.

4. A megengedett algoritmusok szerkezete. Egy A algoritmust adaptívnak nevezünk, ha f_{k+1} választása függhet az f_{1}(x), f_{2}(x), …, f_{k}(x) értékektől. Ha az f_{i}–ket előre kell megadnunk, az algoritmus nem adaptív. (Használatos még a dinamikus–statikus, és a szekvenciális–előre megadott elnevezés is.)

5. Az eljárás célja. Mire optimalizáljunk? Minimalizálhatjuk az algoritmus hosszát az összes lehetséges esetre; ezt a legrosszabb eset problémájának (worst case problem) hívjuk. Minimalizálhatjuk az algoritmus hosszának várható értékét egy adott eloszlás mellett, ennek a neve: átlagos–eset probléma (average case problem). Rendelhetünk F elemeihez költségeket, és minimalizálhatjuk az algoritmus összköltségét,vagy a költségek és a lépésszám egy függvényét.(Ezek az úgynevezett trade–off problémák.)

Bizonyos eljárásokkal nem kívánunk foglalkozni, ezért a következő feltevésekkel élünk:

1. S véges.

2. F véges. Minthogy minden f ∈ F csak véges sok értéket vehet fel, feltehetjük, hogy f(S) ⊆ {0, 1, …, q − 1} ,∀f ∈ F, ahol q ≥ 2.

Megjegyzés. A leggyakoribb a q = 2 eset (neve: bináris keresési eljárás), ekkor bármely f ∈ F tesztfüggvényhez rendelhetünk egy R halmazt a következőképp:

R = {x ∈ S : f(x) = 1} .

Ilyenkor R és f kölcsönösen meghatározzák egymást, így F helyett egy ℜ ⊆ 2^{S} halmazrendszert használhatunk, az algoritmusok pedig S részhalmazainak sorozatai lesznek.

1.2. Definíció. (S, F)–et (n,q)–eljárásnak nevezzük, ha |S| = n ≥ 1, és f(S) ⊆ {0, 1, …, q − 1} , (q ≥ 2) , ∀f ∈ F–re.

Legyen adott egy sikeres algoritmus A = (f_{1}, f_{2}, …, f_{l(x)}), (ez azt jelenti, hogy az f_{1}(x), f_{2}(x), …, f_{l(x)}(x) értékek egyértelműen meghatározzák x–et), tegyük fel továbbá, hogy

| {y ∈ S : f_{i}(y) = f_{i}(x) : i = 1, 2, …, l(x) − 1} | > 1

(azaz f_{1}(x), f_{2}(x), …, f_{l−1(x)}(x) még nem határozzák meg egyértelműen x–et).

1.3. Definíció. l(x)–et az x–re vonatkozó keresés hosszának nevezzük az A algoritmus mellett. L(A) = max_{x∈S} l(x) az A algoritmus hossza.

Legyen ζ egy adott valószínűségi eloszlás S–en: ζ = (p(x) : x ∈ S),

(p(x) ≥ 0 ∀x ∈ S, ∑_{x∈S} p(x) = 1).

1.4. Definíció. Az A algoritmus átlagos hosszának hívjuk a ζ eloszlás mellett

az L(A, ζ) = ∑_{x∈S} p(x)l(x) számot. ζ = ( \underbrace{1 ; n, 1 ; n, …, 1 ; n}_{n db} ) (n = |S|) esetén az

L(A) jelölést használjuk.

1.5. Definíció. Legyen (S, F) egy (n, q)–eljárás, ζ egy eloszlás S–en. Az (S, F) legrosszabb eseti költségén az L(S, F) = min_{A} L(A) számot értjük, átlagos költsé-

gén pedig (a ζ eloszlás mellett) az L(S, F, ζ) = min_{A} L(A, ζ) számot. Egy A algoritmus L–optimális, ha L(A) = L(S, F) , L–optimális, ha L(A, ζ) = L(S, F, ζ).

(Minthogy a tett feltevések mellett csak véges sok algoritmus létezik, a definíciók korrektek). A fentiek alapján célunk adott (S, F) és adott ζ mellett L(S, F) és L(S, F, ζ) kiszámítása.Vezessük be a következő jelölést:

S(e_{1}, e_{2}, …, e_{k}) = {y ∈ S : f_{1}(y) = e_{1}, …, f_{k}(y) = e_{k}} ,

ahol e_{1}, e_{2}, …, e_{k} ∈ {0, 1, …, q − 1}. S(e_{1}, e_{2}, …, e_{k}) tehát azon S–beli elemek halmaza, melyek k lépés után még a keresett elemként szóbajöhetnek. Legyen még S_{i}(x) = S(f_{1}(x), …, f_{i}(x)). Világos, hogy ekkor

S = S_{0}(x) ⊇ S_{1}(x) ⊇ S_{2}(x) ⊇ … S_{l(x)}(x) = {x} .

1.6. Állítás. S és az S(e_{1}, e_{2}, …, e_{k}) halmazok egyértelműen meghatározzák az algoritmust. (e_{1}, e_{2}, …, e_{k} ∈ {0, 1, …, q − 1} k = 1, 2, …)

Bizonyítás. Az f_{i} függvényeket kell meghatároznunk. (i = 1, 2, …). S(j) azon elemek halmaza lesz,melyeken f_{1} j–t veszi fel. Így az S(j) halma-

zok (j = 0, 1, …, q − 1) meghatározzák f_{1}–et. ⋃_{i=1}^{q} S(i, j) azon elemek halmaza,

melyeken f_{2} j–t veszi fel. Ezzel f_{2}–t is ismerjük. Hasonlóképp

\underbrace{⋃_{i_{1}=1}^{q} . . . . . . ⋃_{i_{t−1}=1}^{q}}_{t−1 db} S(i_{1}, i_{2}, …, i_{t−1}, j)

lesz azon elemek halmaza, melyeken f_{t} j–t veszi fel, így minden f_{t}–t ki tudunk számítani, ha az S(e_{1}, e_{2}, …, e_{k}) halmazokat ismerjük. □

Példa. Vegyük szemügyre az ezen pontban definiált fogalmakat egy példán, a legegyszerűbb keresési eljáráson, amit elemenkénti keresésnek hívunk. Legyen S = {x_{1}, x_{2}, …, x_{n}}, F_{0} = {f_{1}, f_{2}, …, f_{n}}, ahol f_{i} : S ⟶ {0, 1}

f_{i}(x) = \{ \begin{matrix}1, & ha x = x_{i} \\ 0, & ha x ≠ x_{i} . \end{matrix}

Egy A algoritmus ekkor (f_{π(1)}, f_{π(2)}, …, f_{π(k)}) alakú, ahol k ≤ n, π pedig az {1, 2, …, n} halmaz tetszőleges permutációja. Megmutatjuk, hogy ha k < n − − 1, akkor létezik x ∈ S, hogy az f_{π(1)}(x), f_{π(2)}(x), …, f_{π(k)}(x) értékek még nem határozzák meg x–et egyértelműen, azaz l(x) ≥ n − 1, és így L(A) = max_{x∈S} l(x) ≥

≥ n − 1, ebből pedig L(S, F_{0}) = min_{A} L(A) ≥ n − 1 következik. Az x = x_{π(k+1)} választás jó lesz, mert ekkor f_{1}(x) = f_{2}(x) = … = f_{k}(x) = = 0, ami x = x_{π(k+1)} és x = x_{π(k+2)} mellett is lehetséges (x_{π(k+2)} ∈ S, mivel k < n − 1 ⇒ k + 2 ≤ n). Másrészt tetszőleges x ∈ S és A mellett l(x) ≤ n − − 1. Valóban, ha az A–ban szereplő függvények közt f_{j} is ott van, kész vagyunk (f_{j}(x) = 1 csak x_{j}–re teljesül). Ha pedig f_{j} nem szerepel A–ban, akkor ∀i ≠ j (i ∈ {1, 2, …, n}) esetén f_{i} szerepel, és f_{i}(x) = 0–t kapunk rájuk, ami egyedül x = x_{j} esetén teljesülhet. Így L(A) = max_{x∈S} l(x) ≤ n − 1 tetszőleges A–ra, amiből

L(S, F_{0}) ≤ n − 1 adódik.Tehát L(S, F_{0}) = n − 1. Látható, hogy mindkét irányú egyenlőtlenség bizonyítása érvényes a dinamikus és a statikus esetben is. Legyen most adott egy ζ = (p(x_{1}), p(x_{2}), …, p(x_{n})) eloszlás S–en, és vizsgáljuk L(S, F_{0}, ζ)–t! Számozzuk S elemeit úgy, hogy p(x_{1}) ≥ p(x_{2}) ≥ … ≥ p(x_{n}) teljesüljön. Az A = (f_{π(1)}, f_{π(2)}, …, f_{π(k)}) algoritmus a j. lépésben pontosan az x_{π(j)} elemet találja meg (j < n − 1), az (n − 1)–edik lépésben pedig x_{π(n−1)}–et és x_{π(n)}–et. Így A átlagos lépésszáma :

L(A) = ∑_{x∈S} l(x)p(x) = ∑_{i=1}^{n−1} ip(x_{π(i)})

Ez nyilván π = [1, 2, …, n] és π = [1, 2, …, n − 2, n, n − 1] mellett minimális, így

L(S, F_{0}, ζ) = min_{A} L(A) = ∑_{i=1}^{n−1} ip_{i} − p_{n} ,

ahol p_{i} = p(x_{i}). Egyenletes eloszlás esetén L(S, F_{0}) = n+1 ; 2 − 1 ; n adódik. Az optimális algoritmust előre megadtuk, így a bizonyítás megintcsak érvényes a statikus és a dinamikus esetben is.

1.2. Keresési fák

1.7. Definíció. Az r-gyökerű T fenyőt (n, q)–fának nevezzük^{2} , ha pontosan n levele van, és a pontok ki–foka legfeljebb q. T reguláris (n, q)–fa, ha minden belső pont (nem levél) ki–foka pontosan q. q = 2 esetén bináris fáról beszélünk.

Legyen A = (f_{1}, f_{2}, …) tetszőleges algoritmus az (S, F) (n, q)–eljáráshoz. Most hozzárendelünk egy T irányított gráfot az A algoritmushoz. Feleltessünk meg az S halmaznak egy kitüntetett r csúcsot; az S(e_{1}, e_{2}, …) nem üres halmazoknak a többi csúcsot. Húzzunk éleket r-ből minden S(i)-be (i = 0, 1, …, q−1), továbbá S(e_{1}, e_{2}, …, e_{k})–ból S(e_{1}, e_{2}, …, e_{k}, i)–be, ha egyikük sem üres, ∀i, e_{1}, …, e_{k} ∈ {0, 1, …, q − 1}–re (k = 1, 2, …).

1.8. Állítás. T egy r-gyökerű (n, q)–fa.

Bizonyítás. Nyilvánvaló, hogy T -ben nincs irányított kör, és r-ből minden más csúcs pontosan egy (irányított) úton érhető el. Eszerint T egy r-gyökerű fenyő. Ugyancsak nyilvánvaló, hogy minden csúcs ki-foka legfeljebbb q. (Nem biztos, hogy pont q, mert a potenciális leszármazottak közt üres halmazok is lehetnek). Mivel minden legalább kételemű halmaznak van (nem üres) leszármazottja, levelek csak az egyelemű halmazok lehetnek, ezek viszont levelek is lesznek, ha szerepelnek T -ben, amit pedig az a korábbi feltevésünk biztosít, hogy minden elemhez létezik őt megtaláló algoritmus. Így T -nek n levele van. Mindezek együttesen azt jelentik, hogy T egy (n, q)-fa. □

Az így kapott T (n, q)-fát az A algoritmushoz tartozó döntési fának nevezzük. l(t)-vel jelölve az r-ből t-be vezető (egyértelmű) irányított út hosszát: l({x}) = l(x) nyilván, így ha T mélységét (a benne lévő leghosszabb irányított út hosszát) L(T)-vel jelöljük, akkor ebből az L(A) = L(T) egyenlőség adódik. Megjegyzés. Könnyen látható, hogy minden (szereplő) halmaz előáll leszármazottainak uniójaként, így tehát a belőle elérhető levelek uniójaként is.

1.9. Definíció. Egy (n, q)–eljáráshoz tartozó A algoritmus reguláris, ha

|S(e_{1}, e_{2}, …, e_{k})| ≥ 2 ⟹ S(e_{1}, e_{2}, …, e_{k}, i) ≠ ∅, ∀i = 0, 1, …, q − 1

Tehát a reguláris algoritmusokhoz tartozó döntési fák belső csúcsainak ki–foka q, így ezek reguláris (n, q)–fák lesznek.

1.10. Állítás. Minden T (n, q)–fához létezik A algoritmus valamilyen (n, q)– eljáráshoz, aminek a döntési fája T.

Bizonyítás. Írjuk T leveleire az S elemeiből alkotott egyelemű halmazokat. A belső csúcsokból kiinduló éleket számozzuk meg a 0, 1, …, q − 1 számokkal úgy, hogy az egy csúcsból kiinduló élek különböző számot kapjanak. (Ezt nyilván megtehetjük, hiszen minden csúcs legfeljebb q ki–fokú.) Legyen f_{k} a következő függvény: (k = 1, 2, …, L(T)) f_{k} : S ⟶ {0, 1, …, q − 1}

2Az elnevezés kicsit logikátlannak tűnhet, de ne feledjük, hogy minden fenyő egyben fa is!

f_{k}(x) = \{ \begin{matrix}j, & ha k ≤ l(x) és az r → x út k. éle a j számot viseli \\ 0, & ha k > l(x) . \end{matrix}

Az így kapott A = (f_{1}, f_{2}, …, f_{L(T)}) algoritmus döntési fája épp T lesz. □

Megjegyzés. Ez az algoritmus szemmel láthatóan statikus. Annyiban azonban függ x választásától, hogy l(x) lépés után ér véget. Ezen függés nélkül a statikus algoritmusok átlagos lépésszámának definíciója értelmetlen lenne. Megjegyzés. Jól látható, hogy egy (n, q)–fához több sikeres algoritmus is tartozik, hiszen a leveleket és az éleket sokféleképp számozhatjuk.

Ha tehát F = {0, 1, …, q − 1}^{S}, akkor az (n, q)–eljárások vizsgálatakor— mivel minden (n, q)–fa valamilyen A algoritmushoz tartozik — elegendő az (n, q)– fák vizsgálatára szorítkoznunk.

1.3. Keresési kódok

1.11. Definíció. Legyen H tetszőleges halmaz, H^{∗} = ⋃_{i=0}^{∞} H^{i} . H^{∗} elemeit a H

ábécé fölötti szavaknak hívjuk. (H^{0} álljon az üres szóból). H^{∗} részhalmazai a H fölötti kódok. A C kód (n, q)–kód, ha |H| = q és |C| = n.

1.12. Definíció. Legyen C H fölötti kód, w ∈ C és ezen belül w ∈ H^{l}, ekkor l(w) := l a w kódszó (röviden: szó) hossza, L(C) := max_{w∈C} l(w) a C kód hossza.

1.13. Definíció. Legyen (S, F) tetszőleges (n, q)–eljárás, A = (f_{1}, f_{2}, …) egy algoritmus (S, F)–hez. Legyen H = {0, 1, …, q − 1}. Rendeljük x ∈ S–hez a következő vektort: w(x) = (f_{1}(x), f_{2}(x), …, f_{l(x)}(x)). w(x) ∈ H^{l(x)} egy l(x) hosszúságú H fölötti szó, amit az x–hez tartozó kódszónak hívunk. C = {w(x) : x ∈ S} ⊆ H^{∗} az A–hoz tartozó (keresési) kód.

Az x ↦ w(x) megfeleltetés bijekció S és C között, amire ráadásul l(x) = l(w(x)) is teljesül. Minden algoritmushoz tartozik tehát egy kód. Ennek a fordítottja csak bizonyos feltételekkel teljesül. A keresési kódok rendelkeznek ugyanis egy fontos speciális tulajdonsággal.

1.14. Definíció. Az a = (a_{1}, a_{2}, …, a_{k}) szó kezdőszelete a b = (b_{1}, b_{2}, …, b_{n}) szónak, ha k ≤ n és a_{i} = b_{i} minden i = 1, 2, …, k mellett.

1.15. Állítás. Legyen C az A–hoz tartozó keresési kód. Ha a, b ∈ C, a ≠ b, akkor a nem kezdőszelete b–nek, és b nem kezdőszelete a–nak.

Bizonyítás. Legyen a = w(x), b = w(y). Tehát a = (f_{1}(x), f_{2}(x), …, f_{l(x)}(x)), b = (f_{1}(y), f_{2}(y), …, f_{l(y)}(y)). Ha a kezdőszelete b–nek, akkor

f_{1}(x) = f_{1}(y), f_{2}(x) = f_{2}(y), …, f_{l(x)}(x) = f_{l(x)}(y),

azaz S_{l(x)}(x) ⊇ {x, y}, ami nem lehetséges, hiszen az

f_{1}(x), f_{2}(x), …, f_{l(x)}(x)

értékek egyértelműen meghatározzák x–et. Ugyanígy látható be, hogy b sem kezdőszelete a–nak. □

Az ezen tulajdonsággal rendelkező kódokat prefix kódnak nevezzük.

1.16. Állítás. Tetszőleges C prefix (n, q)–kódhoz létezik A algoritmus valamely (S, F) (n, q)–eljáráshoz úgy, hogy C az A–hoz tartozó kód.

Bizonyítás. |S| = |C| = n. w legyen tetszőleges bijekció S és C között. Az f_{k} : S ⟶ {0, 1, …, q − 1} függvényt definiáljuk a következőképp:

f_{k}(x) = \begin{cases}j, & ha k ≤ l(w(x)) és j a k. eleme w(x)–nek \\ 0, & ha k > l(w(x)) . \end{cases}

Világos, hogy az A = (f_{1}, f_{2}, …) algoritmushoz a C kód tartozik. □

Megjegyzés. Ugyanúgy, mint a keresési fáknál, ez az algoritmus is előre megadott, és itt is több algoritmus tartozik egy kódhoz. Ha F = {0, 1, …, q − 1}^{S}, akkor bármelyik prefix (n, q)–kód egy A algoritmushoz tartozik, így ilyenkor elegendő az előbbieket vizsgálnunk. A prefix kódok és a keresési eljárások közti kapcsolatot elsőként M. Sobel [17],[18], C. Picard [13], és L.L.Campbell [5] fedezték fel, és elsősorban Sobel vizsgálta több cikkében is behatóbban. Ez a kapcsolat azért különösen fontos, mert segítségével optimális kódokra vonatkozó információelméleti eredményeket — mint például Shannon tétele (ld. 2.1) — alkalmazhatunk keresési feladatokra.

1.4. Játékelméleti megközelítés

A (H, F) (n, q)–eljárás legrosszabb eseti problémáját felfoghatjuk két játékos, A és B közötti játékként, ahol A kiválasztja az f_{1}, f_{2}, … ∈ F függvényeket, és "Mennyi f_{i}(x) értéke?" típusú kérdéseket tesz fel, amikre B megpróbál úgy válaszolni (azaz úgy változtatni az A által keresendő x elemet), hogy A–nak minél többet kelljen kérdezni, míg meg tudja határozni x–et. A természetesen minimalizálni szeretné a szükséges kérdések számát. Egy, az x–et meghatározó A = (f_{1}, f_{2}, …) sorozatot (f_{1}, f_{2}, … ∈ F) A egy algoritmusának, egy S = = (e_{1}, e_{2}, …) sorozatot (e_{1}, e_{2}, … ∈ {0, 1, …, q − 1}) — ha kompatibilis F–fel (azaz ∃ f_{i} ∈ F : f_{i}(x) = e_{i}) — B egy stratégiájának hívjuk.

A játék hossza az x meghatározásáig feltett kérdések száma. Tegyük fel, hogy A az A algoritmust, B az S stratégiát használja. A játék hosszát ekkor L(A, S)– sel jelöljük. Természetesen midőn A az A algoritmust választja, számítania kell arra, hogy ehhez B olyan stratégiát választ, amire L(A, S) maximális. Hasonlóképp, B–nek arra kell számítani, hogy S stratégiájához A talál olyan A algoritmust, amely mellett L(A, S) minimális. Ennek fényében vezessük be a következő definíciókat:

1.17. Definíció. L(A) := max_{S} L(A, S) az A algoritmus hossza; L(S) := min_{A} L(A, S) az S stratégia hossza.

1.18. Állítás. min_{A} max_{S} L(A, S) = max_{S} min_{A} L(A, S), vagy másképp

min_{A} L(A) = max_{S} L(S) .

A közös szélsőérték megegyezik L(H, F)–fel.

Bizonyítás. Tetszőleges rögzített A, S mellett :

L(A) = max_{S} L(A, S) ≥ min_{A} L(A, S) = L(S) , így

min_{A} L(A ≥ max_{S} L(S) .

Az egyenlőség bizonyításához indukciót használunk n = |H|–ra. Legyen (H, F) (n, q)–eljárás. A–t optimálisnak mondjuk, ha L(A) = min_{A} L(A), hasonlóképp S optimális, ha L(S) = max_{S} L(S). Legyen A első teszt–függvénye f, és legyen H_{i} := {x ∈ H : f(x) = i}, továbbá π(f) := {H_{0}, H_{1}, …, H_{q−1}} a H–nak f által meghatározott partíciója. Nyilván feltehető, hogy f legalább két értéket vesz fel, így a H_{i}–k valódi részhalmazai H–nak. Legyen A_{H_{i}} optimális algoritmus (H_{i}, F_{i})–hez, ahol F_{i} az F megszorítása H_{i}–re. Látható, hogy

L(A) = 1 + min_{f} max_{H_{i}∈π(f)} L(A_{H_{i}}) .

Hasonlóan, legyen S_{H_{i}} optimális stratégia (H_{i}, F_{i})–hez. Ekkor

L(S) = 1 + max_{f} min_{H_{i}∈π(f)} L(S_{H_{i}}) .

Az indukciós feltevés szerint — mivel az A_{H_{i}}–k és az S_{H_{i}}–k is optimálisak — L(A_{H_{i}}) = L(S_{H_{i}}) minden i és f mellett, ahonnan a fentiek szerint L(A) = L(S).

A–nak bármely algoritmusa nyilván felső becslést ad L(H, F)–re : L(H, F) ≤ ≤ L(A). Másrészt B bármely S stratégiájára természetesen L(H, F) ≥ L(S). Így, mivel ∃ A, S : L(A) = L(S):

min_{A} L(A) = max_{S} L(S) = L(H, F) .

□

Megjegyzés. Az 1.18. állítás speciális esete a játékelmélet híres dualitás– tételének.

A fentihez hasonló módon járhatunk el az átlagos eset–problémánál is, a kapott keresési játékra teljesül a megfelelő minimax–tétel. A nem adaptív algoritmusok esetén annyi a változás, hogy itt A "nyílt lapokkal" játszik. (B tulajdonképpen eddig is ezt tette).

2. Alapvető problémák

2.1. A legrosszabb eset–probléma tetszőleges teszt–függvények mellett

Ezen pontban feltesszük, hogy F = {0, 1, …, q − 1}^{S}. Ilyenkor — mint láttuk — elegendő keresési fákkal vagy kódokkal dolgoznunk. Jelöljük T (n, q)–val az (n, q)–fák halmazát, I(T)–vel pedig a T (n, q)–fa belső pontjainak halmazát.

2.1. Állítás. Tetszőleges T ∈ T (n, q) esetén:

1. |I(T)| ≥ ⌈ n−1 ; q−1⌉

2. T reguláris ⇔ |I(T)| = n−1 ; q−1 speciálisan: T reguláris ⇒ q − 1 | n − 1

Bizonyítás. Legyen T ∈ T (n, q). Bármely csúcsba, ami nem a gyökér, pontosan egy él vezet. Másrészt legfeljebb q él vezet ki, ha a csúcs belső, és egy sem, ha levél (számuk: n). Így

n + |I(T)| − 1 ≤ q |I(T)| ,

amiből 1. és 2. is következik. □

2.2. Állítás. Minden (n, q) párhoz (n ≥ 1, q ≥ 2) létezik (n, q)–fa, melyre |I(T)| = ⌈ n−1 ; q−1⌉, és reguláris (n, q)–fa, ha q − 1 | n − 1.

Bizonyítás. (1) Indukciót használunk k = ⌈ n−1 ; q−1⌉–re. k = 0 és k = 1 esetén az állítás triviális. Legyen k ≥ 2, és

n − 1 = k(q − 1) + r , 0 ≤ r < q − 1 .

Ekkor n − q = (k − 1)(q − 1) − r, azaz

⌈(n − q + 1) − 1 ; q − 1⌉ = k − 1 ,

tehát az indukciós feltevés szerint létezik (n − q + 1, q − 1)–fa, k − 1 belső ponttal. Ennek tetszőleges leveléből q új élt indítva q új pontba, egy k belső ponttal rendelkező (n, q)–fát kapunk. Ha q − 1 | n − 1, akkor az előző állítás szerint a kapott fa reguláris. □

Bizonyítás. (2) Konstruálunk egy T (n, q)–fát, amire |I(T)| = ⌈ n−1 ; q−1⌉. Jelöljük E(T)–vel T leveleinek halmazát, δ(v)–vel a v csúcs ki–fokát. Definiáljuk a T fa k. szintjét a következőképp:

S_{k}(T) := {v ∈ V (T) : l(v) = k} .

Rendelkezzen T a következő két tulajdonsággal:

1. v ∈ S_{k} , k ≤ L(T) − 2 ⇒ δ(v) = q

2. S_{L(T)−1}–ben a lehető legtöbb csúcs legyen levél, az 1. tulajdonság adta lehetőségeken belül.

Azt állítjuk, hogy az így kapott T fa, amit teljes (n, q)–fának nevezünk, alkalmas lesz. Az 1. feltétel miatt |S_{k}(T)| = q^{k}, k = 1, 2, …, L(T) − 1 mellett. Legyen S_{L(T)−1}–ben a levelek száma a, a belső pontok száma pedig b. (a + b = q^{L(T)−1}). Az S_{L(T)}–beli levelek száma ekkor n − a, az S_{L(T)}–be vezető élek száma pedig legfeljebb qb, így qb ≥ n − a, ahonnan

(q − 1)b ≥ n − a − b = n − q^{L(T)−1} ,

vagyis

b ≥ ⌈n − q^{L(T)−1} ; q − 1 ⌉ .

a akkor maximális, ha b minimális, tehát b = ⌈ n−q^{L(T)−1} ; q−1 ⌉, ekkor a = ⌊ q^{L(T)}−n ; q−1⌋.

A belső pontok I(T) számára I(T) = ∑_{k=0}^{L(T)−2} q^{k} + b adódik, vagyis

I(T) = q^{L(T)−1} − 1 ; q − 1 + ⌈n − q^{L(T)−1} ; q − 1 ⌉ = ⌈n − 1 ; q − 1⌉ ,

ahogy állítottuk. □

Mivel a ≥ 0, és b > 0, ezért n ≤ q^{L(T)}, és n > q^{L(T)−1}, azaz L(T) = ⌈log_{q} n⌉, ami egyben azt is jelenti, hogy a T teljes (n, q)–fa egyértelmű. Jelöljük a továbbiakban L(n, q)–val min{L(T) : T ∈ T (n, q)}–t.

2.3. Tétel. L(n, q) = ⌈log_{q} n⌉ (n ≥ 1, q ≥ 2)

Bizonyítás. Legyen T ∈ T (n, q). Mivel minden csúcs ki–foka legfeljebb q, |S_{k}(T)| ≤ q^{k}, (k = 1, 2, …, L(T)). Minden v_{0} levélhez, amire l(v_{0}) < l(T), hozzuk létre a v_{1}, v_{2}, …, v_{L(T)−l(v_{0})} új csúcsokat, és húzzunk élt v_{i}–ből v_{i+1}–be. (i = 0, 1, …, L(T) − l(v_{0}) − 1). A kapott T′ fenyő is (n, q)–fa lesz, melyre E(T′) ⊆ S_{L(T′)}(T′). |S_{k}(T)| ≤ q^{k} miatt n = |E(T)| = |E(T′)| ≤ q^{L(T)}, így L(T) ≥ ⌈log_{q} n⌉, mivel L(T) egész. Másrészt az egyértelműen létező T ∈ T (n, q) teljes fára L(T) = ⌈log_{q} n⌉. □

2.4. Következmény. (Információelméleti alsó korlát) Tetszőleges (S, F) (n, q)–eljárásra L(S, F) ≥ ⌈log_{q} n⌉ .

Bizonyítás. F ⊆ {0, 1, …, q − 1}^{S} miatt bármely A ∈ F^{∗}–ra A ∈ [{0, 1, …, q − 1}^{S}]^{∗}, így

L(S, F) = min_{A∈F^{∗}} L(A) ≥ min_{A∈({0,1,... ,q−1}^{S})^{∗}} L(A) = ⌈log_{q} n⌉ .

□

Megjegyzés. Az információelméleti alsó korlátot (n, q)–fák használata nélkül is bebizonyíthatjuk, a játékelméleti megközelítés segítségével. Kövesse a B játékos az alábbi egyszerű stratégiát: ha k lépés után a még szóbajövő elemek halmaza S_{k} ⊆ S, f pedig az A által választott következő ((n + 1) − edik) teszt–függvény , továbbá

S_{k,i} = {x ∈ S_{k} : f(x) = i} ,

akkor az S_{k,i}–k közül válassza B a legnagyobb elemszámút. (Ha több ilyen van, az egyiket). Ily módon |S_{k+1}| ≥ |S_{k}| ; q, ahonnan 1 = |S_{L}| ≥ |S| ; q^{L}, ha a játék L lépésben ér véget. Ebből L ≥ ⌈log_{q} n⌉.

2.2. Az átlagos eset–probléma tetszőleges teszt–függvények mellett

Továbbra is feltesszük, hogy F = {0, 1, …, q − 1}^{S}. Jelöljük ekkor L(n, q, ζ)–val

L(S, F, ζ)–t (n = |S|).

2.5. Lemma. (Kraft–egyenlőtlenség)

1. Legyen T ∈ T (n, q), x_{1}, x_{2}, …, x_{n} T levelei, l_{1} = l(x_{1}), …, l_{n} = l(x_{n}).

Ekkor ∑_{i=1}^{n} q^{−l_{i}} ≤ 1, és az egyenlőség pontosan akkor teljesül, ha T reguláris.

2. Legyenek l_{1}, l_{2}, …, l_{n} tetszőleges pozitív egészek, melyekre ∑_{i=1}^{n} q^{−l_{i}} ≤ 1

teljesül. Ekkor létezik T (n, q)–fa, melynek x_{1}, x_{2}, …, x_{n} leveleire l_{1} = l(x_{1}), …, l_{n} = l(x_{n}).

Bizonyítás. Tetszőleges T (n, q)–fából előállíthatunk egy T′ reguláris (n′, q)–fát (n′ ≥ n), úgy, hogy azon v belső csúcsokhoz, melyekre δ(v) < q beveszünk T –be q − δ(v) új élet, melyek q − δ(v) új levélbe vezetnek. A ∑ q^{−l_{i}} összeg ezen eljárás

során csak nőhet,így elég azt belátni, hogy ∑_{i=1}^{n} q^{−l_{i}} = 1 teljesül a reguláris (n.q)–

fákra. Indukciót használunk k = n−1 ; q−1–re. (k egész a 2.1 Állítás 2. pontja szerint ). k = 0 esetén az állítás triviális. Legyen most k ≥ 1. Válasszunk egy v belső csúcsot T –ből, melynek leszármazottai mind levelek. (Ilyen v nyilván létezik). Töröljük ki a v–ből kivezető q darab élt, és végpontjaikat. A kapott T′ fenyő egy reguláris (n − q + 1, q)–fa lesz, így teljesül rá az indukciós feltevés. Legyenek az elhagyott levelek x_{1}, x_{2}, …, x_{q}. Ekkor

∑_{i=1}^{n} q^{−l_{i}} = ∑_{i=q+1}^{n} q^{−l_{i}} + qq^{−(l(v)+1)} = ∑_{i=q+1}^{n} q^{−l_{i}} + q^{−(l(v)} = 1 ,

ahol az utolsó egyenlőség éppen azt fejezi ki, hogy a T′ reguláris (n, q)–fára teljesül az indukciós feltevés. Ezzel az állítás 1. pontját beláttuk.

Legyenek most l_{1}, l_{2}, …, l_{n} tetszőleges pozitív egészek, melyekre ∑_{i=1}^{n} q^{−l_{i}} ≤ 1

teljesül. Legyen továbbá

w_{k} := |{i : l_{i} = k}| (k = 0, 1, …, L = max_{i} l_{i})

Ekkor ∑_{k=0}^{L} w_{k}q^{−k} = ∑_{i=1}^{n} q^{−l_{i}} ≤ 1 ⟹ ∑_{k=0}^{L} w_{k}q^{L−k} ≤ q^{L} .

Szintről–szintre konstruáljuk meg T –t. Ha w_{0} = 1, akkor L = 0 kell legyen, ekkor T az egypontú gráf. Tegyük most fel, hogy T –t már megadtuk a k. szintig úgy, hogy az i. szinten w_{i} darab levél van. (i = 1, 2, …, k). Ha S_{k+1}–et is meg tudjuk úgy adni, hogy w_{k+1} levél legyen benne, akkor kész vagyunk. Ha T a k. szintig a teljes fa lenne, akkor |S_{k}| = q^{k} teljesülne. Mivel az i. szinten w_{i} levél van

|S_{k}| = q^{k} − ∑_{i=1}^{k} w_{i}q^{k−i} (i = 1, 2, …, k − 1) ,

és ebből w_{k} a levél, a többi belső pont, így S_{k}–ban a belső pontok száma q^{k} − ∑_{i=0}^{k} w_{i}q^{k−i}. Ahhoz, hogy S_{k+1}–en w_{k+1} levelet tudjunk megadni, tehát pontosan az kell, hogy q(q^{k} − ∑_{i=0}^{k} w_{i}q^{k−i}) ≥ w_{k+1} teljesüljön. Tudjuk, hogy

∑_{i=0}^{L} w_{i}q^{L−i} ≤ q^{L}, eszerint

w_{k+1}q^{L−k−1} ≤ q^{L} − ∑_{i=0}^{k} w_{i}q^{L−i} , ahonnan

w_{k+1} ≤ q^{k+1} − ∑_{i=0}^{k} w_{i}q^{k+1−i} = q(q^{k} − ∑_{i=0}^{k} w_{i}q^{k−i})

Ezt akartuk belátni. □ 2.6. Lemma. Legyenek s_{1}, s_{2}, …, s_{n} és y_{1}, y_{2}, …, y_{n} pozitív valós számok, melyekre ∑_{i=1}^{n} s_{i} ≤ ∑_{i=1}^{n} y_{i}. Ekkor ∑_{i=1}^{n} y_{i} log_{a} y_{i} ; s_{i} ≥ 0 , minden a > 1 esetén, és egyenlőség pontosan akkor teljesül, ha s_{i} = y_{i} (i = 1, 2, …, n). Bizonyítás. Nyilván elég az e alapú logaritmusra belátni az állítást. Mivel x > 0 esetén ln x ≤ x − 1 (egyenlőség x = 1–re),

∑_{i=1}^{n} y_{i} log_{a} s_{i} ; y_{i} ≤ ∑_{i=1}^{n} y_{i} (s_{i} ; y_{i} − 1) = ∑_{i=1}^{n} s_{i} − ∑_{i=1}^{n} y_{i} ≤ 0 ,

így ∑_{1}^{n} y_{i} ln y_{i} ; s_{i} ≥ 0, az egyenlőséghez pedig ln s_{i} ; y_{i} = s_{i} ; y_{i} − 1 ⟹ y_{i} = s_{i} kell, minden i = 1, 2, …, n–re. □ 2.7. Definíció. A ζ = (p_{1}, p_{2}, …, p_{n}) valószínűségi eloszlás entrópiájának nevezzük a H(ζ) = − ∑_{\begin{matrix}i=1 \\ p_{i}≠0 \end{matrix}}^{n} p_{i} log p_{i} számot.

2.8. Tétel. ( Shannon ) Legyen n ≥ 1, q ≥ 2, ζ = (p_{1}, p_{2}, …, p_{n}) egy valószínűségi eloszlás. Ekkor

H(ζ) ; log q ≤ L(n, q, ζ) < H(ζ) ; log q + 1 .

Bizonyítás. A baloldali egyenlőtlenség bizonyításához azt kell megmutatnunk, hogy ∀T ∈ T (n, q)–ra, az x_{1}, x_{2}, …, x_{n} levelekkel,

l(x_{1}) = l_{1}, l(x_{2}) = l_{2}, …, l(x_{n}) = l_{n} mellett ∑_{i=1}^{n} p_{i}l_{i} ≥ H(ζ) ; log q = − ∑_{i=1,p_{i}≠0}^{n} p_{i} log_{q} p_{i}.

A Kraft–egyenlőtlenség szerint (2.5 lemma) ∑_{i=1}^{n} q^{−l_{i}} ≤ 1 = ∑_{i=1}^{n} p_{i}. Így alkalmaz-

hatjuk a 2.6. lemmát a q^{−l_{1}}, q^{−l_{2}}, …, q^{−l_{n}} és a p_{1}, p_{2}, …, p_{n} számokra; így tehát

0 ≤ ∑_{i=1,p_{i}≠0}^{n} p_{i} log_{q}(p_{i}q^{l_{i}}) = ∑_{i=1,p_{i}≠0}^{n} p_{i}(1 + l_{i}) log_{q} p_{i} ,

ahonnan átrendezés után éppen a bizonyítandó állítást kapjuk. A felső becslés bizonyításához definiáljuk az l_{i} természetes számokat a következőképp:

− log_{q} p_{i} ≤ l_{i} < − log_{q} p_{i} + 1

(l_{i} ≥ 0 valóban, mert p_{i} ≤ 1). A definícióból 1 ; p_{i} ≤ q^{l_{i}} ⇒ q^{−l_{i}} ≤ p_{i}, így

∑_{i=1}^{n} q^{−l_{i}} ≤ ∑_{i=1}^{n} p_{i} = 1. Ekkor megintcsak a Kraft–egyenlőtlenség szerint létezik T

(n, q)–fa, x_{1}, x_{2}, …, x_{n} levelekkel, melyekre l(x_{i}) = l_{i} (i = 1, 2, …, n). Erre a T fára l_{i} < − log_{q} p_{i} + 1 miatt

L(T, ζ) = ∑_{i=1}^{n} p_{i}l_{i} < ∑_{i=1}^{n} p_{i}(− log_{q} p_{i} + 1) = − ∑_{i=1}^{n} p_{i} log_{q} p_{i} + 1 = H(ζ) ; log q + 1 ,

így L(n, q, ζ) < H(ζ) ; log q + 1. □

2.9. Következmény. Legyen (S, F) tetszőleges (n, q)– eljárás, ζ = (p_{1}, p_{2}, …, p_{n}) tetszőleges eloszlás. Ekkor L(S, F, ζ) ≥ H(ζ) ; log q. □

Vizsgáljuk a továbbiakban a q = 2 esetet^{3}. Ekkor Shannon tétele a

H(ζ) ≤ L(n, ζ) ≤ H(ζ) + 1

alakot ölti. Ez meglehetősen jó becslés, de mennyi lehet a pontos érték? Az alábbiakban ennek meghatározására adunk egy algoritmust a prefix kódok segítségével.

2.10. Definíció. A C (n, q)–kód ζ–optimális, ha ζ = (p(x_{1}), …, p(x_{n}))

mellett ∑_{i=1}^{n} l(x_{i})p(x_{i}) minimális.

3Az f_{i} függvények most tehát {0, 1}–be képeznek.

Jelöljük p(x_{i})–t p_{i}–vel, l(x_{i})–t l_{i}–vel.

2.11. Tétel. ( D.A. Huffman ) A következő algoritmus (az ún. Huffman–eljárás) ζ–optimális kódot eredményez. Tegyük fel, hogy már megadtunk egy optimális kódot ζ′ = (p_{1}, p_{2}, …, p_{n−2}, p_{n−1}+ + p_{n})–hez, ahol p_{n−1} és p_{n} a két legkisebb a p_{1}, p_{2}, …, p_{n} számok közül. Írjunk minden kódszó végére 0–t p_{n−1} valószínűséggel, 1–et p_{n} valószínűséggel. A kapott kód (p_{1}, p_{2}, …, p_{n})–optimális.

Bizonyítás. Feltehetjük, hogy p_{1} ≥ p_{2} ≥ … ≥ p_{n}.

2.12. Lemma. Bármely ζ–optimális prefix kódra l_{1} ≤ l_{2} ≤ … ≤ l_{n}.

Bizonyítás. Tegyük fel, hogy a C kódban valamely x_{i}, x_{j} párra p_{i} > p_{j} és l_{i} > l_{j}. Cseréljük ki az x_{i} és az x_{j} szavakat! A kód átlagos hossza ekkor (p_{i}l_{j} + + p_{j}l_{i} − p_{i}l_{i} − p_{j}l_{j})– vel nő. Mivel p_{i}l_{j} + p_{j}l_{i} − p_{i}l_{i} − p_{j}l_{j} = (p_{i} − p_{j})(l_{j} − l_{i}) < 0, C nem lehet optimális. □

2.13. Lemma. Ha C ζ–optimális kód, és l_{i} = l_{n}, akkor az a szó, amelyik x_{i}–től pontosan az utolsó elemben különbözik, C–ben van:

x_{i}^{c} = (f_{1}(x_{i}), f_{2}(x_{i}), …, f_{l_{i}−1}(x_{i}), 1 − f_{l_{i}}(x_{i})) ∈ C

Bizonyítás. Tegyük fel indirekt, hogy (f_{1}(x_{i}), f_{2}(x_{i}), …, f_{l_{i}−1}(x_{i}), 1−f_{l_{i}}(x_{i})) ∉ C. Cseréljük ki az x_{i} = (f_{1}(x_{i}), f_{2}(x_{i}), …, f_{l_{i}−1}(x_{i}), f_{l_{i}}(x_{i})) szót az x′_{i} := (f_{1}(x_{i}), f_{2}(x_{i}), …, f_{l_{i}−1}(x_{i})) szóra. x′_{i} a C–beli szavak közül csak x_{i}–nek és x_{i}^{c}–nek lehet kezdőszelete, l_{i} = l_{n} miatt. Mivel feltevésünk szerint x_{i}^{c} nincs C–ben, C ∪ {x′_{i}} \ {x_{i}}–ben x′_{i} nem kezdőszelete egyetlen más szónak sem. Másrészt ha egy x szó kezdőszelete x′_{i}–nek, akkor x_{i}–nek is kezdőszelete, így C ∪ {x′_{i}} \ {x_{i}} prefix kód, és átlagos hossza C átlagos hosszánál kisebb, ami ellentmondás. □

Jelöljük L_{C}(p_{1}, p_{2}, …, p_{n})–nel ∑_{i=1}^{n} p_{i}l_{i}–t egy adott C kódra.

L_{min}(p_{1}, p_{2}, …, p_{n}) := min_{C prefix} L_{C}(p_{1}, p_{2}, …, p_{n}) .

Vizsgáljunk egy ζ–optimális kódot, erre L_{C}(p_{1}, p_{2}, …, p_{n}) = L_{min}(p_{1}, p_{2}, …, p_{n}). A 2.12. lemma szerint max_{i≤n} l_{i} = l_{n}. A 2.13. lemma szerint

x_{n}^{c} = (f_{1}(x_{n}), f_{2}(x_{n}), …, f_{l_{n}−1}(x_{n}), 1 − f_{l_{n}}(x_{n}))

C–ben van, mondjuk legyen x_{n}^{c} = x_{i} (i ≠ n). l_{i} = l_{n}, így a 2.12. lemma

szerint l_{i} = l_{n−1} = l_{n}. Az x_{i} és x_{n−1} kódokat felcserélve ∑_{i=1}^{n} p_{i}l_{i} nem változik, így feltehetjük, hogy i = n−1. Hagyjuk most el C–ből x_{n−1}–et és x_{n}–et, és helyettük vegyük be p_{n−1} + p_{n} valószínűséggel az x′_{n−1} = (f_{1}(x_{n}), f_{2}(x_{n}), …, f_{l_{n}−1}(x_{n})) szót, ami eddig nem szerepelt, hiszen kezdőszelete x_{n}–nek. Tehát C′ = = C \ {x_{n−1}, x_{n}} ∪ {x′_{n−1}}. Könnyen látható, hogy a kapott kód is prefix, és átlagos hossza p_{n−1} + p_{n}–nel kisebb, mint C–é:

L_{C′}(p_{1}, p_{2}, …, p_{n−2}, p_{n−1} + p_{n}) = L_{min}(p_{1}, p_{2}, …, p_{n}) − p_{n−1} − p_{n} ,

amiből

L_{min}(p_{1}, p_{2}, …, p_{n}) ≥ L_{min}(p_{1}, p_{2}, …, p_{n−2}, p_{n−1} + p_{n}) + p_{n−1} + p_{n}

következik. Másrészt ha adott egy (n − 1) elemű prefix kód, melynek az átlagos hossza L_{min}(p_{1}, p_{2}, …, p_{n−2}, p_{n−1} + p_{n}), abból kaphatunk egy n elemű kódot a következőképp: minden szó végére írjunk 0–t p_{n−1} valószínűséggel, 1–et p_{n} valószínűséggel. A kapott kód nyilván prefix, és átlagos hossza L_{min}(p_{1}, p_{2}, …, p_{n−2}, p_{n−1} + p_{n}) + p_{n−1} + p_{n}. Eszerint L_{min}(p_{1}, p_{2}, …, p_{n}) ≤ ≤ L_{min}(p_{1}, p_{2}, …, p_{n−2}, p_{n−1} + p_{n}) + p_{n−1} + p_{n}, azaz

L_{min}(p_{1}, p_{2}, …, p_{n}) = L_{min}(p_{1}, p_{2}, …, p_{n−2}, p_{n−1} + p_{n}) + p_{n−1} + p_{n} .

Ezzel tételünket beláttuk. □

A tételt A.M. Huffman 1952–ben bizonyította [8], de tőle függetlenül S. Zimmerman is felfedezte 1959–ben. [21]. Megjegyzés. A q > 2 esetben is alkalmazható Huffman módszere, de ennek részleteit itt nem tárgyaljuk.

Nézzünk egy konkrét példát a Huffman–eljárásra! Példa. Adjunk optimális prefix kódot a (0,3 ; 0,25 ; 0,25 ; 0,1 ; 0,05 ; 0,05) eloszlásra.

ζ_{1}  ζ_{2}  ζ_{3}  ζ_{4}  ζ_{5}  ζ_{6}
0,3  0,3  0,3  0,45  0,55  1
0,25  0,25  0,25  0,3  0,45
0,25  0,25  0,25  0,25
0,1  0,1  0,2
0,05  0,1

0,05

ζ_{6}–ra az üres kód, ζ_{5}–re (0,1) optimális; a Huffman–tételt felhasználva ζ_{4}–re (1,00,01), ζ_{3}–ra (00,01,10,11), ζ_{2}–re (00,01,10,110,111), végül ζ_{1}–re (00,01,10,110,1110,1111) optimális prefix kód lesz. A Huffman–algoritmus segítségével tehát konkrét eloszlásokra meg tudjuk határozni az átlagos kódhossz optimumát, de mi a helyzet például a

ζ = ( \underbrace{1 ; n, 1 ; n, …, 1 ; n}_{n} ) esettel? Ha egyszerűen megpróbáljuk alkalmazni a Huffman–

eljárást, akkor — mint abba könnyen belegondolhatunk — számos nehézségbe ütközünk. (Két esetet kell megnézni aszerint, hogy n páros, vagy páratlan, ezeken belül ismét két esetet aszerint, hogy [ n ; 2] páros vagy páratlan, és így tovább …) Az eddigi eredmények tehát nem tisztázzák L_{min}( 1 ; n, 1 ; n, …, 1 ; n) pontos értékét. (Ami nem más, mint az alábbi keresési problémában szereplő várható érték optimuma. Adott n elem (alkatrész), közülük pontosan egy hibás, egyenlő valószínűséggel az n elem közül. Az elemek tetszőleges részhalmazát tesztelve megtudhatjuk, hogy köztük van-e a hibás. Mennyi a hibás elem megtalálásához szükséges lépések várható értéke? ) Erre ad választ a következő tétel.

2.14. Tétel. (Sandelius [15])

L_{min} ( 1 ; n, 1 ; n, …, 1 ; n) = ⌈log n⌉ − (2^{⌈log n⌉} ; n − 1)

Bizonyítás. (Katona O.H. Gyula [10])

2.15. Lemma. Ha a C prefix kódra L_{C}( 1 ; n, 1 ; n, …, 1 ; n) = L_{min} ( 1 ; n, 1 ; n, …, 1 ; n), ak-

kor a C–beli szavak csak kétféle hosszúságúak lehetnek, s ezek a hosszak szomszédos egész számok.

Bizonyítás. Feltehetjük, hogy l_{1} ≤ l_{2} ≤ … ≤ l_{n}. Tegyük most fel indirekt, hogy l_{1} ≤ l_{n−2}. Tekintsük az x_{n} = (f_{1}(x_{n}), f_{2}(x_{n}), …, f_{l_{n}}(x_{n})) szót. A 2.13. lemma szerint az x_{n}^{c} = (f_{1}(x_{n}), f_{2}(x_{n}), …, f_{l_{n}−1}(x_{n}), 1 − f_{l_{n}}(x_{n})) szó is C–ben van. Hajtsuk végre a következő cseréket:

(f_{1}(x_{n}), f_{2}(x_{n}), …, f_{l_{n}}(x_{n})) ⟶ (f_{1}(x_{n}), f_{2}(x_{n}), …, f_{l_{n}−1}(x_{n}))

(f_{1}(x_{n}), …, f_{l_{n}−1}(x_{n}), 1 − f_{l_{n}}(x_{n})) ⟶ (f_{1}(x_{1}), f_{2}(x_{1}), …, f_{l_{1}}(x_{1}), 0)

(f_{1}(x_{1}), f_{2}(x_{1}), …, f_{l_{1}}(x_{1})) ⟶ (f_{1}(x_{1}), f_{2}(x_{1}), …, f_{l_{1}}(x_{1}), 1) .

Könnyen láthetó, hogy a kapott C′ kód is prefix, és

L_{C′} ( 1 ; n, 1 ; n, …, 1 ; n) = L_{C} ( 1 ; n, 1 ; n, …, 1 ; n) + 2(l_{1} + 1) + l_{n} − 1 ; n − 2l_{n} + l_{1} ; n =

= L_{C} ( 1 ; n, 1 ; n, …, 1 ; n) + l_{1} − l_{n} + 1 ; n < L_{C} ( 1 ; n, 1 ; n, …, 1 ; n) ,

hiszen a feltevés szerint l_{1} ≤ l_{n−2}. Ez pedig ellentmondás, mert C optimális kód. □

2.16. Lemma. Ha a C prefix kódra L_{C} ( 1 ; n, 1 ; n, …, 1 ; n) = L_{min} ( 1 ; n, 1 ; n, …, 1 ; n),

akkor tetszőleges c_{1}, c_{2}, …, c_{l_{n}−1} ∈ {0, 1} mellett, a c = (c_{1}, c_{2}, …, c_{l_{n}−1}), c^{0} = (c_{1}, c_{2}, …, c_{l_{n}−1}, 0), c^{1} = (c_{1}, c_{2}, …, c_{l_{n}−1}, 1) jelöléseket használva

(c ∈ C) ∨ ((c^{0} ∈ C) ∧ (c^{1} ∈ C)) .

Bizonyítás. Először belátjuk, hogy ha c ∉ C, akkor c^{0} ∈ C, vagy c^{1} ∈ C. Ha ez nem teljesülne, tetszőleges l_{n} hosszúságú C–beli szót c–re cserélhetnénk úgy, hogy C prefix maradjon, hiszen c csak c^{0}–nak és c^{1}–nek kezdőszelete. Mivel l(c) = l_{n} − 1 < l_{n}, C ekkor nem lenne optimális. Ellentmondás. Így

(c ∈ C) ∨ ((c^{0} ∈ C) ∨ (c^{1} ∈ C))

teljesül. Másrészt a 2.13. lemma szerint c^{0} ∈ C ⇔ c^{1} ∈ C , amiből a lemma következik. □

Jelöljük s–sel az l_{n} − 1 hosszúságú szavak számát C–ben. A 2.15. lemma szerint az l_{n} hosszúságú szavak száma ekkor n − s. A 2.16. lemmát felhasználva pedig a következő egyenlőség adódik:

s + n − s ; 2 = 2^{l_{n}−1}, azaz n + s = 2^{l_{n}} .

Mivel 0 ≤ s < n, ebből n ≤ 2^{l_{n}} < 2n következik, tehát log n ≤ l_{n} < log n + 1. l_{n} egész, így l_{n} = ⌈log n⌉. Továbbá n + s = 2^{l_{n}}–ből s = 2^{⌈log n⌉} − n adódik. Tehát

L_{min} ( 1 ; n, 1 ; n, …, 1 ; n) = s(⌈log n⌉ − 1) + (n − s)(⌈log n⌉ ; n =

= ⌈log n⌉ − (2^{⌈log n⌉} ; n − 1)

□

Ugyanezzel a módszerrel láthatjuk be a tétel következő általánosításait:

2.17. Tétel. (Katona O.H. Gy. és M.A. Lee, [12])

Adott p_{1} ≥ p_{2} ≥ … ≥ p_{n} ∑_{i=1}^{n} p_{i} = 1, p_{n−1} + p_{n} ≥ p_{1} valószínűségek mellett

L_{min}(p_{1}, p_{2}, …, p_{n}) = ⌈log n⌉ − ∑_{i=1}^{s} p_{i} , ahol s = 2^{⌈log n⌉} − n.

2.18. Tétel. (Katona O.H. Gy. és M.A. Lee, [12]) Ha a p_{1} ≥ p_{2} ≥ … ≥ p_{n} valószínűségekre (∑ p_{i} = 1 mellett) p_{n} + kp_{n−1} > > p_{1} teljesül, akkor l_{n} − l_{1} ≤ k, azaz C–ben legfeljebb k páronként különböző hosszúságú szó lehet.

Ezen fejezet végén, visszatérve az (n, q)–eljárásokhoz, bizonyítás nélkül megemlítjük az egyenletes eloszlás egy extremális tulajdonságát:

2.19. Tétel. Legyen ζ_{e} = ( \underbrace{1 ; n, 1 ; n, …, 1 ; n}_{n} ), ζ = (p_{1}, p_{2}, …, p_{n}) tetszőleges el-

oszlás. Ekkor

L(n, q, ζ) ≤ L(n, q, ζ_{e}) .

2.3. Nem adaptív algoritmusok

Mint azt egy korábbi példán is láthattuk, az előre megadott algoritmusok lépésszáma sokszor nem rosszabb, mint a szekvenciális algoritmusoké. Előre megadott algoritmus esetén egyszer s mindenkorra le kell fixálnunk az f_{1}, f_{2}, …, f_{L} függvényeket (L az algoritmus hossza), és természetesen sorrendjüket is.

Legyen (S, F) tetszőleges (n, q)–eljárás, f_{1}, f_{2}, …, f_{L} ∈ F adott függvények, A = (f_{1}, f_{2}, …, f_{L}). Az A algoritmust a következő mátrix–szal szemléltethetjük: rendeljük az M_{A} L × n–es mátrix oszlopaihoz az x_{1}, x_{2}, …, x_{n} ∈ S elemeket, soraihoz az f_{1}, f_{2}, …, f_{L} ∈ F függvényeket, M_{A}(i, j) pedig legyen f_{i}(x_{j}). Vegyük észre, hogy ha A sikeres algoritmus, akkor M_{A} oszlopai páronként különbözők. Ennek az állításnak a fordítottja is igaz: ha M egy n oszlopból álló mátrix, melynek a sorai F–re nézve szabályosak (azaz minden (a_{1}, a_{2}, …, a_{n}) sorhoz létezik olyan f ∈ F, hogy f(x_{1}) = a_{1}, f(x_{2}) = a_{2}, …, f(x_{n}) = a_{n}) és M oszlopai páronként különbözők, akkor M = M_{A} valamilyen A algoritmussal az (S, F) (n, q)–eljáráshoz. Valóban, ha az f_{1}, f_{2}, …, f_{L} függvényeket M sorainak megfelelően adjuk meg, (vagyis f_{i}(x_{j})–t M i. sorának j. elemeként határozzuk meg) akkor bármilyen értékeket kapjunk is az f_{i} függvényekhez, ezek végül egyértelműen meghatározzák M egy oszlopát, és így a keresett elemet.

2.20. Definíció. A 0, 1, …, q − 1 elemekkel kitöltött, n oszloppal rendelkező M mátrixot az (S, F) (n, q)–eljáráshoz tartozó keresési mátrixnak nevezzük, ha M oszlopai páronként különbözők, sorai pedig (f(x_{1}), f(x_{2}), …, f(x_{n})) alakúak valamely f ∈ F mellett. (S = {x_{1}, x_{2}, …, x_{n}}).

Ha csak nem adaptív algoritmusokat használhatunk, akkor tehát a legrosszabb eset–probléma — a fentiek szerint — megfogalmazható a következőképp is: találjunk az (S, F) eljáráshoz minél kevesebb sorból álló keresési mátrixot. Ha F = {0, 1, …, q − 1}^{S}, akkor M pontosan akkor keresési mátrix, ha oszlopai különbözőek. Legyen M–nek L sora. Mivel M a 0, 1, …, q − 1 elemekkel van kitöltve, a különböző oszlopok száma legfeljebb q^{L} lehet, így q^{L} ≥ n ⇒ L ≥ ≥ ⌈log_{q} n⌉. Másrészt tetszőleges n ≤ q^{⌈log_{q} n⌉} különböző, ⌈log_{q} n⌉ hosszúságú oszlopból állítva össze M–et, egy keresési mátrixot kapunk. Jelöljük L_{pre}(S, F)– fel az (S, F) eljárás legrosszabb eseti költségét, ha csak előre megadott algoritmusokat engedünk meg; L_{pre}(n, q)–val L_{pre} ({x_{1}, x_{2}, …, x_{n}}, {0, 1, …, q − 1}^{S})–et. A fentiekben tehát a következő tételt bizonyítottuk be:

2.21. Tétel. L_{pre}(n, q) = ⌈log_{q} n⌉. □

2.22. Következmény. L_{pre}(S, F) ≥ ⌈log_{q} n⌉, tetszőleges (S, F) (n, q)– eljárásra. □

Megjegyzés. Ez utóbbi természetesen azonnali folyománya a 2.4. következménynek is.

Látható tehát, hogy ha tetszőleges teszt–függvényeket megengedünk, akkor az előre megadott algoritmusok ugyanolyan jók, mint a szekvenciálisak. Vizsgáljuk most az átlagos esetet. Legyen A egy tetszőleges, L hosszúságú, előre megadott algoritmus az (S, F) (n, q)–eljáráshoz, S = {x_{1}, x_{2}, ldots, x_{n}}; ζ = = (p_{1}, p_{2}, …, p_{n}) (p_{i} = p(x_{i}), i = 1, 2, …, n) egy eloszlás S–en. Tekintsük az M_{A} keresési mátrixot. Ha az x ∈ S elemet már az első k teszt egyértelműen meghatározza, úgy az x–hez tartozó oszlopban az utolsó L − k elemet húzzuk ki. A kapott M′_{A} ún. parciális mátrix a következő tulajdonságokkal rendelkezik:

1. Minden sorban kitölthetők úgy az üres helyek, hogy a sor

(f(x_{1}), f(x_{2}), …, f(x_{n}))

alakot öltsön, valamely f ∈ F mellett

2. M′_{A} egyetlen oszlopa sem kezdőszelete egy másiknak.

Nyilvánvaló, hogy ha egy, a 0, 1, …, q − 1 elemekkel kitöltött n oszloppal rendelkező M parciális mátrix rendelkezik a fenti két tulajdonsággal, akkor valamely ((S, F)–hez tartozó) A algoritmusra M = M′_{A}. Mivel ez nem fog zavart okozni, az ilyen parciális mátrixokat is keresési mátrixnak fogjuk hívni. A fentiek alapján a nem adaptív algoritmusok esetében az átlagos eset–problémát is megfogalmazhatjuk a keresési mátrixok segítségével: olyan M keresési mátrixot kell

megadnunk, melynek l_{1}, l_{2}, …, l_{n} oszlophosszaira L(M, ζ) := ∑_{i=1}^{n} p_{i}l_{i} minimális.

Jelöljük L_{pre}(S, F, ζ)–val az (S, F) eljárás átlagos költségét a ζ eloszlás mellett.

L_{pre}(n, q, ζ) := L_{pre}({x_{1}, x_{2}, …, x_{n}}, {0, 1, …, q − 1}^{{x_{1},x_{2},... ,x_{n}}}, ζ) .

Mint azt az 1.3. fejezetben láttuk, F = {0, 1, …, q − 1}^{S} mellett minden C (n, q)–kódhoz tartozik egy előre megadott A algoritmus. Könnyen látható, hogy M′_{A} oszlopai épp C szavai lesznek. Ezzel a következőt láttuk be:

2.23. Tétel. Tetszőleges ζ eloszlásra: L_{pre}(n, q, ζ) = L(n, q, ζ) . □

Ha F nem az összes teszt–függvényből áll, akkor a helyzet természetesen merőben más.

2.4. Bináris keresési eljárások

A keresési eljárások legfontosabb és legtöbbet vizsgált esete a q = 2 eset, amit bináris keresésnek nevezünk. Mint azt már az 1.1. fejezetben is említettük, az f : S ⟶ {0, 1} teszt–függvények helyett dolgozhatunk az R = {x ∈ S : f(x) = = 1} halmazok ℜ rendszerével. A bináris keresési eljárások esetében ezentúl (S, F) helyett (S, ℜ)–et írunk.Az A = (f_{1}, f_{2}, …, f_{L}) algoritmus helyett pedig U = (R_{1}, R_{2}, …, R_{L})–et. x ∈ S–et természetesen egyértelműen meghatározza, hogy mely R_{i}–kben van benne. Az (n, 2)–kódokat bináris kódnak nevezzük. Bináris kódokkal a 2.1. fejezetben már találkozhattunk.

2.24. Definíció. Egy N = {N_{1}, N_{2}, …, N_{k}} ⊆ 2^{S} halmazrendszert elválasztó rendszernek (separating set system) hívunk, ha ∀x, y ∈ S–hez (x ≠ y) ∃N_{i} ∈ N, hogy x ∈ N_{i}, y ∉ N_{i}, vagy x ∉ N_{i}, y ∈ N_{i}.

Világos, hogy ha U = (R_{1}, R_{2}, …, R_{L}) sikeres algoritmus, akkor {R_{1}, R_{2}, …, R_{L}} elválasztó rendszer, és bármely N elválasztó rendszer elemeit tetszőleges sorrendben véve, sikeres algoritmust kapunk. A legrosszabb eset– probléma ilyenkor tehát ekvivalens minimális elemszámú elválasztó rendszer megadásával. Felírva az U–hoz tartozó keresési mátrixot:

m_{ij} = \{ \begin{matrix}1, & ha x_{j} ∈ R_{i} \\ 0, & ha x_{j} ∉ R_{i} , \end{matrix}

cseppet sem meglepődve tapasztaljuk, hogy épp az U–nak megfelelő halmazrendszer incidencia–mátrixát kaptuk. A vizsgálható halmazok ℜ rendszerére megkötéseket téve különböző érdekes problémákhoz juthatunk. Vizsgáljunk meg ezek közül néhányat!

Legyen a megengedett halmazok rendszere ℜ_{≤k} := {R ⊆ S : |R| ≤ k}. Ha k ≥ n ; 2, akkor ez nem jelent megkötést, hiszen mindegy, hogy az R halmazt vizsgáljuk, vagy a komplementerét. Tegyük fel tehát, hogy k < n ; 2.

2.25. Tétel. L(S, ℜ_{≤k}) = t + ⌈log(n − tk)⌉, ahol n = |S|, és t = ⌈ n ; k⌉ − 2.

Bizonyítás. Jelöljük az egyszerűség kedvéért f_{k}(n)–nel L(S, ℜ_{≤k})–t. Adott k–ra f_{k}(n) monoton növő függvénye n–nek, hiszen ha T ⊆ S, és U egy L hosszúságú sikeres algoritmus S–hez, akkor U elemeit T –vel metszve sikeres algoritmust kapunk T –hez, melynek hossza L. Legyen A_{1} az első teszt–halmaz egy (S, ℜ_{≤k})–hoz tartozó optimális algoritmusban. Jelöljük |A_{1}|–et l–lel, l ≤ k. Ha megtudtuk, hogy a keresett elem A_{1}–ben, vagy S\A_{1}–ben van, ezen halmazokon folytathatjuk a keresést, így a következő rekurziót kapjuk:

f_{k}(n) = 1 + max(f_{k}(l), f_{k}(n − l)) = 1 + f_{k}(n − l) ≥ 1 + f_{k}(n − k) ,

hiszen l ≤ k és f_{k} monoton növő. Az eljárást iterálva:

f_{k}(n) ≥ 1 + f_{k}(n − k) ≥ 2 + f_{k}(n − 2k) ≥ … ≥ t + f_{k}(n − tk)

adódik, ahol t a legkisebb egész, melyre n − tk ≤ 2k ⇒ t = ⌈ n ; k⌉ − 2. Ekkor f_{k}(n − tk) = ⌈log(n − tk)⌉, hiszen n − tk ≤ 2k, így a vizsgálható halmazok méretére tett kikötés itt nem jelent megszorítást. Ezzel beláttuk, hogy L(S, ℜ_{≤k}) ≥ t + ⌈log(n − tk)⌉. Az egyenlőség bizonyításához konstruálunk egy algoritmust, ami éppen t + ⌈log(n − tk)⌉ lépést használ a legrosszabb esetben. Legyen az első t vizsgált halmaz:

A_{1} = {x_{1}, x_{2}, …, x_{k}}
A_{2} = {x_{k+1}, x_{k+2}, …, x_{2k}}
⋮  ⋮
A_{t} = {x_{(t−1)k+1}, x_{(t−1)k+2}, …, x_{tk}} .

Ha a keresett x elemre x ∈ ⋃_{i=1}^{t} A_{i}, akkor még legfeljebb ⌈log k⌉ lépésben

megtaláljuk. (Az A_{i}–k k eleműek, így a méretkorlátozás itt sem érdekes). Ha

x ∈ S \ ⋃_{i=1}^{t} A_{i}, akkor egy n − tk elemű halmazból kell kikeresnünk x–et, így

ekkor még ⌈log(n − tk)⌉ lépés kell. (n − tk ≤ 2k !) Mivel t definíciója szerint

n − (t − 1)k > 2k ⟹ n − tk > k ,

eszerint max (⌈log(n − tk)⌉, ⌈log(k)⌉) = ⌈log(n − tk)⌉, tehát algoritmusunk a legrosszabb esetben t + ⌈log(n − tk)⌉ lépést igényel. □

Foglalkozzunk most ugyanezen probléma nem adaptív verziójával! Olyan M mátrixot kell megadnunk, melyre

1. m_{ij} ∈ {0, 1} ∀i, j

2. az oszlopok páronként különbözők

3. az egy sorban lévő 1–esek száma legfeljebb k

4. a sorok száma a lehető legkisebb.

k ≥ n ; 2 esetén természetesen L_{pre}(S, ℜ_{≤k}) = ⌈log(n)⌉. Mi a helyzet, ha k < n ; 2 ? Ezen probléma tanulmányozásához néhány definíciót és lemmát kell segítségül hívnunk a valószínűségszámítás területéről.

2.26. Definíció. Legyen Ω egy véges halmaz, P : Ω ⟶ R_{+} függvény, melyre ∑_{ω∈Ω} P (ω) = 1 . Egy X : Ω ⟶ T (T ⊆ R_{+} véges) függvényt valószínűségi

változónak nevezünk, és x ∈ T –re definiáljuk p(x)–et a következőképp:

p(x) := p(X = x) := ∑_{X(ω)=x} P (ω) .

(Az üres összeget 0–nak értelmezzük). Ily módon p definiál egy eloszlást T –n, ezt az X valószínűségi változó eloszlásának, vagy indukált eloszlásnak hívjuk.

2.27. Definíció. Az X valószínűségi változó entrópiájának az indukált eloszlás entrópiáját nevezzük: H(X) := − ∑_{\begin{matrix}x∈T \\ p(x)≠0 \end{matrix}} p(x) log p(x).

2.28. Definíció. Legyen X : Ω ⟶ T Y : Ω ⟶ U két valószínűségi változó, a p_{X}, p_{Y} indukált eloszlásokkal. X és Y együttes eloszlását a

p(x, y) := p(X = x ∧ Y = y) := ∑_{ω∈Ω} (P (ω) : X(ω) = x ∧ Y (ω) = y)

képlettel definiáljuk. Az (X, Y) pár entrópiája:

H(X, Y) = − ∑_{(x,y)∈T ×U)} p(x, y) log p(x, y) .

X és Y független, ha p(x, y) = p_{X}(x)p_{Y} (y) ∀x ∈ T, y ∈ U.

A definiált fogalmakat triviális módon általánosíthatjuk több valószínűségi változóra is, pl X_{1}, X_{2}, …, X_{L} függetlenek, ha

p(X_{1}, X_{2}, …, X_{L}) = ∏_{i=1}^{L} p(X_{i} = x_{i}), ∀x_{1}, x_{2}, …, x_{L} .

2.29. Lemma. Az X_{1}, X_{2}, …, X_{L} valószínűségi változókra

H(X_{1}, X_{2}, …, X_{L}) ≤ ∑_{i=1}^{n} H(X_{i}).

Egyenlőség pontosan akkor teljesül, ha X_{1}, X_{2}, …, X_{L} függetlenek.

Bizonyítás. Mivel H(X_{1}, X_{2}, …, X_{L}) = H((X_{1}, X_{2}, …, X_{L−1}), X_{L}), az állítást elég két valószínűségi változóra belátni. Legyenek ezek X : Ω ⟶ T és Y : Ω ⟶ U.

H(X, Y) = − ∑_{(x,y)∈T ×U} p(x, y) log p(x, y)

H(X) + H(Y) = − ∑_{\begin{matrix}x∈T \\ p_{X}(x)≠0 \end{matrix}} p_{X}(x) log p_{X}(x) − ∑_{\begin{matrix}y∈U \\ p_{Y} (y)≠0 \end{matrix}} p_{Y} (y) log p_{Y} (y) =

= − ∑_{\begin{matrix}x∈T \\ p_{X}(x)≠0 \end{matrix}} ∑_{y∈U} p(x, y) log p_{X}(x) − ∑_{x∈T} ∑_{\begin{matrix}y∈U \\ p_{Y} (y)≠0 \end{matrix}} p(x, y) log p_{Y} (y) ,

mivel p_{X}(x) = ∑_{y∈U} p(x, y) , p_{Y} (y) = ∑_{x∈T} p(x, y) . A szummákat összevonva:

H(X) + H(Y) = − ∑_{\begin{matrix}(x,y)∈T ×U \\ p(x,y)≠0 \end{matrix}} p(x, y) log (p_{X}(x) · p_{Y} (y)) .

Használjuk most fel a 2.6. lemmát a 2.1. fejezetből, tetszőlegesen megszámozva az (x, y) párokat 1–től |T × U|–ig, az y_{i} := p((x, y)_{i}) , s_{i} :=

= p_{X}(proj_{1}(x, y)_{i}) · p_{Y} (proj_{2}(x, y)_{i}) szereposztásban. ∑_{i=1}^{|T ×U|} y_{i} = 1 nyilván, és

∑_{i=1}^{|T ×U|} s_{i} = (∑_{x∈T} p_{X}(x)) · (∑_{y∈U} p_{Y} (y)) = 1, tehát a lemma feltételei teljesülnek,

így

H(X, Y) = − ∑_{(x,y)∈T ×U)} p(x, y) log p(x, y) = − ∑_{i=1}^{|T ×U|} y_{i} log y_{i} ≤

≤ − ∑_{i=1}^{|T ×U|} y_{i} log s_{i} = − ∑_{\begin{matrix}(x,y)∈T ×U \\ p(x,y)≠0 \end{matrix}} p(x, y) log (p_{X}(x) · p_{Y} (y)) = H(X) + H(Y).

Egyenlőség pontosan akkor, ha y_{i} = s_{i} ∀i, azaz p_{X}(x) · p_{Y} (y) = p(x, y), ∀x ∈ T, y ∈ U, vagyis ha X és Y függetlenek. □

Következzék most egy egyszerű segédtétel az analízisből:

2.30. Lemma. Az f(x) = x log x + (1 − x) log(1 − x) függvény a (0, 1 2] intervallumban monoton csökken.

Bizonyítás. log x = ln x ; ln 2 miatt elég ezt a g(x) = x ln x+(1−x) ln(1−x) függvényre belátni. Ezt deriválva:

g′(x) = 1 + ln(x) − 1 ; 1 − x − ( −x ; 1 − x + ln(1 − x)) = ln x ; 1 − x.

Ez pontosan akkor negatív, ha x ; 1−x < 1, ami a (0, 1 2] intervallumban teljesül, így itt g(x) — és vele f(x) — monoton csökken. □

Most már készen állunk, hogy bebizonyítsuk Katona O.H. Gyula 1966–os tételét (bővebben ld. [9]).

2.31. Tétel. (Katona O.H. Gy.) Az n elemű S halmazra és k < n ; 2–re :

L_{pre}(S, ℜ_{≤k}) ≥ log n ; log e n ; k · n ; k .

Bizonyítás. Legyen U = {R_{1}, R_{2}, …, R_{L}} elválasztó rendszer az S = {x_{1}, x_{2}, …, x_{n}} alaphalmazon. Lássuk el S–et az egyenletes eloszlással: P (x_{i}) := 1 ; n. Rendeljük az R_{i} ∈ U halmazhoz az X_{i} : S ⟶ {0, 1} valószínűségi változót, melyre X_{i}(x_{j}) = 1 pontosan akkor, ha x_{j} ∈ R_{i}. Ekkor (X_{i}(x_{1}), X_{i}(x_{2}), …, X_{i}(x_{n})) nem más, mint R_{i} incidencia–vektora. Az X_{i} által indukált eloszlás:

p_{X_{i}}(1) = |A_{i}| ; n , p_{X_{i}}(0) = 1 − |A_{i}| ; n , i = 1, 2, …, L .

Tekintsük az (X_{1}, X_{2}, …, X_{L}) : S ⟶ {0, 1}^{L}

(X_{1}, X_{2}, …, X_{L})(x_{j}) := (X_{1}(x_{j}), X_{2}(x_{j}), …, X_{L}(x_{j}))

függvényt. (X_{1}, X_{2}, …, X_{L})(x_{j}) ≠ (X_{1}, X_{2}, …, X_{L})(x_{i}), ha i ≠ j, hiszen U elválasztó rendszer. Így az (X_{1}, X_{2}, …, X_{L}) együttes eloszlására a következőt kapjuk:

p_{(X_{1},X_{2},... ,X_{L})}(c_{1}, c_{2}, …, c_{L}) = \begin{cases}1 ; n, & ha ∃x ∈ S : X_{i}(x) = c_{i} ∀i ∈ \{1, 2, …, L\} \\ 0, & különben . \end{cases}

Tehát (X_{1}, X_{2}, …, X_{L}) egyenletes eloszlású N elemen. Ekkor

H(X_{1}, X_{2}, …, X_{L}) = − ∑_{i=1}^{n} 1 ; n log 1 ; n = log n

A 2.29. lemma szerint H(X_{1}, X_{2}, …, X_{L}) ≤ ∑_{i=1}^{L} H(X_{i}),

azaz ∑_{i=1}^{L} H(X_{i}) ≥ log n .

X_{i} eloszlását ismerjük, így H(X_{i})–t ki tudjuk számolni:

H(X_{i}) = −|A_{i}| ; n log |A_{i}| ; n − (1 − |A_{i}| ; n) log (1 − |A_{i}| ; n) .

A 2.30. lemma szerint H((x, 1 − x)) monoton növő 0 < x ≤ 1 2 esetén, így —

mivel |A_{i}| ; n ≤ k ; n < 1 2 :

H(X_{i}) ≤ −k ; n log k ; n − (1 − k ; n) log (1 − k ; n) , ∀i ∈ {1, 2, …, L} .

A fentieket összevetve a következő egyenlőtlenséget kapjuk:

log n ≤ L (−k ; n log k ; n − (1 − k ; n) log (1 − k ; n)) =

= L (k ; n log n ; k + n − k ; n log n ; n − k ) = Lk ; n (log n ; k + n − k ; k log (1 + k ; n − k )) .

Ismeretes, hogy ln x ≤ x − 1 ∀x > 0 esetén, ahonnan log x ≤ (x − 1) log e ∀x > 0–ra, vagyis log(x + 1) < x log e ∀x > −1. Ezt felhasználva kapjuk a következőt:

log Lk ; n (log n ; k + log e) = Lk ; n log en ; k .

Végül ebből

L ≥ log n ; log e n ; k · n ; k .

□

Bizonyítás nélkül megemlítjük a legjobb ismert alsó korlátot (ld. [20]):

2.32. Tétel. (I. Wegener, 1979)

L_{pre}(S, ℜ_{≤k}) ≤ ⌈\begin{matrix}log n \\ log & n ; k \end{matrix}⌉ · (⌈n ; k⌉ − 1) .

Az átlagos esetben meg lehet mutatni, hogy a 2.25. tétel bizonyításában konstruált algoritmus L (S, ℜ_{≤k}, ( 1 ; n, 1 ; n, …, 1 ; n))–optimális is, amiből

L (S, ℜ_{≤k}, ( 1 ; n, 1 ; n, …, 1 ; n)) ∼ n ; 2k + log k + C , ha n → ∞ .

Az átlagos esetben, nem adaptív algoritmusok esetén

L_{pre} (S, ℜ_{≤k}, ( 1 ; n, 1 ; n, …, 1 ; n)) ≲ n ; k + 1 + C(k) .

Tetszőleges eloszlásokra gyakorlatilag semmi nem ismert.

Egy másik érdekes problémát kapunk, ha a vizsgálható halmazok rendszere ugyan 2^{S}, de csak olyan U = (R_{1}, R_{2}, …, R_{L}) algoritmust használhatunk, melyre |R_{i} ∩ R_{j}| ≤ k , ∀i ≠ j ∈ {1, 2, …, L}–re. Részletesebben csak a k = 1 esettel foglalkozunk. Látni fogjuk, hogy ilyenkor az előre megadott algoritmusok ugyanolyan hatékonyak, mint a szekvenciálisak.

2.33. Definíció. Egy ℜ halmazrendszert k–családnak (k–family) hívunk, ha bármely A ≠ B ∈ ℜ esetén |A ∩ B| ≤ k.

Legyen S = {x_{1}, x_{2}, …, x_{n}}, ℜ pedig egy 1–család S–en. Jelöljük L(S, ℜ)–et g(n)–nel. Vegyük észre, hogy

g(n) ≤ g(n + 1) ≤ g(n) + 1 .

Az első egyenlőség nyilvánvaló, míg a második abból következik, hogy egy (n + 1) elemű halmazt vizsgálhatunk úgy, hogy először x_{n+1}–et teszteljük, majd ha x ≠ x_{n+1}, akkor az {x_{1}, x_{2}, …, x_{n}} halmazon g(n) lépésben megtaláljuk x– et. Így a g(n) függvényt leírhatjuk azzal, ha megadjuk azon j_{0}, j_{1}, … pontokat, ahol g "ugrik" :

g(n) = L ⇔ j_{L−1} < n ≤ j_{L} .

j_{0} = 1, mert g(1) = 0, és g(2) = 1.

2.34. Lemma. j_{L} = j_{L−1} + L, minden L ≥ 1–re.

Bizonyítás. Teszteljünk először egy tetszőleges, k elemű A_{1} halmazt. Ha az derül ki, hogy a keresett x–re x ∈ A, akkor még legfeljebb k − 1 lépésben végetér az algoritmus. (Ennyi viszont kellhet, mert egy lépésben csak egy elemet hasíthatunk le A_{1}–ről). Ha x ∉ A_{1}, akkor még pontosan g(n − k) lépés kell. Így g–re a következő rekurziót kapjuk:

g(n) = min_{1≤k≤n−1} max (k, 1 + g(n − k)) .

Legyen n := j_{L}, és vegye fel g(n) a fenti rekurzióban szereplő minimumát k = k_{0} mellett. Ekkor

L = g(j_{L}) = max (k_{0}, 1 + g(j_{L} − k_{0})) ,

amiből k_{0} ≤ L, és 1 + g(j_{L} − L) ≤ 1 + g(j_{L} − k_{0}) ≤ L következnek. Tehát g(j_{L} − L) ≤ L − 1, ami azt jelenti, hogy j_{L} − L ≤ j_{L−1}. Legyen most n := j_{L−1} + L. A rekurziós képletből:

g(j_{L−1} + L) ≤ max (L, 1 + g(j_{L−1})) = L .

Így j_{L−1} + L ≤ j_{L}, ahonnan a fentieket is figyelembe véve j_{L} = j_{L−1} + L következik. □

2.35. Tétel. (Sebő A. ,1982 [16]) Ha S egy n elemű alaphalmaz, és ℜ egy 1–család S–en, akkor

L(S, ℜ) = L_{pre}(S, ℜ) = ⌈√8n − 7 − 1 ; 2⌉ .

Bizonyítás. Az előző lemmából és j_{0} = 1 –ből következik, hogy j_{L} = L(L+1) ; 2 + 1, így

L(S, ℜ) = g(n) = L ⟺ L(L − 1) ; 2 + 1 < n ≤ L(L + 1) ; 2 .

Az egyenlőtlenséget megoldva:

√8n − 7 − 1 ; 2 ≤ g(n) < √8n − 7 + 1 ; 2 , így

L(S, ℜ) = ⌈√8n − 7 − 1 ; 2⌉ .

Az L_{pre}(S, ℜ) = L(S, ℜ) állítást S elemszámára vonatkozó indukcióval látjuk be. |S| = 1 esetén az egyenlőség triviálisan teljesül. Tegyük most fel, hogy minden, legfeljebb n − 1 elemű alaphalmaz esetén az állítás igaz. Legyen A_{1} tetszőleges, g(n) elemű halmaz, és vizsgáljuk az (A_{1}, ℜ) és az (S \ A_{1}, ℜ) eljárásokat. A_{1}– en belül nem adaptív algoritmussal is könnyűszerrel megkereshetjük x–et g(n) − − 1 további lépésben, elemenként, hiszen |A_{1}| = g(n). Ha x ∈ S \ A_{1}, akkor alkalmazzuk az indukciós feltevést. Tudjuk, hogy

n ≤ g(n)(g(n) + 1) ; 2 + 1, ahonnan n − g(n) ≤ g(n)(g(n) − 1) ; 2 + 1 ,

azaz g(n − g(n)) ≤ g(n) − 1, ami azt jelenti, hogy S \ A_{1}–en belül is meg tudjuk keresni x–et g(n) − 1 lépésben. Legyen az A_{1}–en belüli előre megadott keresés (g(n) − 1) db halmaza A_{2}^{1}, A_{3}^{1}, …, A_{g(n)}^{1} , az S \ A_{1}–en belüli előre megadott keresés (g(n) − 1) db halmaza A_{2}^{2}, A_{3}^{2}, …, A_{g(n)}^{2} .

{A_{1}, A_{2}^{1} ∪ A_{2}^{2}, A_{3}^{1} ∪ A_{3}^{2}, …, A_{g(n)}^{1} ∪ A_{g(n)}^{2}}

g(n) elemű elválasztó rendszer S–en, és bármely két elemének metszete legfeljebb 1 elemű. □

k > 1–re adaptív algoritmusok esetén k ≤ c ^{3} √n mellett ad [16] jó becslést. A statikus esetben k ≤ n ; 4–re [16] pontosan meghatározza L_{pre}(S, ℜ) értékét (ℜ természetesen k–család), a formula azonban meglehetősen bonyolult, így bemutatását mellőzük.

3. Többségi elem keresése

3.1. Bevezetés

Legyen X egy n elemű halmaz, t egy kétértékű tulajdonság X–en. (X = {x_{1}, x_{2}, …, x_{n}} , t : X ⟶ {0, 1} ). Feladatunk egy olyan x_{i} ∈ X megtalálása, amely a többségi (tehát több elemhez rendelt) tulajdonsággal rendelkezik, illetve ha n páros, és nincs többségi tulajdonság, akkor ezt kell megállapítanunk. Ehhez a következő eszköz áll rendelkezésünkre: két tetszőleges elemről eldönthetjük, hogy a hozzájuk tartozó tulajdonságok azonosak-e. Kérdés, hogy hány ilyen összehasonlítás szükséges a többség egy képviselőjének meghatározásához. (Ez nyilván nem azonos a többség meghatározásával; tekintsünk például 11 golyót, amiből 10–ről már tudjuk, hogy 5 piros, és 5 kék van köztük, de hogy melyek a pirosak, illetvvee a kékek, azt nem. A 11. golyó ekkor a többséghez tartozik, sőt azt is tudjuk, hogy ez a többség 6 elemű, de hogy melyik ez a 6 elem, azt nem tudjuk megmutatni. [Ezt a piros–kék golyós modellt egyébként a továbbiakban is használni fogjuk.]) A probléma legrosszabb eseti lépésszámára jó felső becslést — tehát jó algoritmust — igen sokan adtak, de jó alsó becslést (amely — mint látni fogjuk — megegyezik a felsővel) csak 1991–ben publikált M. Saks és M.E. Werman. [14]. Tételükre valamivel egyszerűbb bizonyítást adott 1993–ban L. Alonso, E.M.

Reingold és R. Schott. [2]. Ők a lépésszám várható értékének kérdésével is foglalkoztak (az egyenletes eloszlás mellett) [3]. A probléma egy általánosabb változatát elemzi M.J. Fisher és S.L.Salzberg cikke [6], amelyben nem csak kettő, hanem tetszőleges számú tulajdonságot engednek megadni az elemeken. (A többség fogalmát ilyenkor többféleképp is definiálhatjuk; ők többség alatt az abszolút többséget értették). Bebizonyítják, hogy ekkor ⌈ 3n ; 2⌉ lépés szükséges és elegendő. Az átlagos eset–problémát ilyenkor már megfogalmazni is jóval bonyolultabb: először meg kell adnunk egy valószínűségi eloszlást a pozitív egész számokon, ami megmondja, hogy milyen p_{i} valószínűséggel kell i tulajdonság jelenlétével számolnunk. Ezután már feltehetjük, hogy minden elemre egy adott tulajdonság előfordulásának valószínűsége 1 ; i, amennyiben i darab tulajdonság van jelen. A várható értéket nyilván pontosan akkor tudjuk kiszámítani, ha tetszőleges i–re meg tudjuk mondani, hogy i darab tulajdonságot megengedve mennyi a várható lépésszám. Mivel erről i = 2–re is csak 1995–ben jelent meg eredmény, (Alonso, Reingold és Schott már említett cikke [3]) a probléma valószínűleg még megoldatlan. Kissé eltérő feladatot kapunk, ha az elemek között nem többségit, hanem csak k azonos tulajdonságút keresünk. (Pontosabban olyan elemet, amelyhez létezik k − 1 vele azonos tulajdonságú). (A tulajdonságok száma, és k tetszőleges pozitív egészek). Erre az esetre vonatkozó becsléseket tartalmaz J.Misra és D. Gries cikke. [7].

Az összehasonlítások C halmaza a következő c elemekből állhat:

c = (x_{i}, x_{j}, g) , ahol x_{i}, x_{j} ∈ X , g ∈ {0, 1} ,

és ha az x_{i}–t az x_{j}–vel összehasonlítjuk, amennyiben a hozzájuk tartozó tulajdonságok azonosak, úgy (x_{i}, x_{j}, 1) kerül C–be, különben pedig (x_{i}, x_{j}, 0).

3.2. A probléma átfogalmazása

Legyen C összehasonlítások egy halmaza, és legyen χ(C) X azon két részre való partícióinak halmaza, melyekre a C–beli összehasonlítások igazak. Azaz

χ(C) = { {A, B} : A ∩ B = ∅, A ∪ B = X, ∄x_{i}, x_{j} ∈ A : ∃c = (x_{i}, x_{j}, 0) ∈ C,

∄x_{i}, x_{j} ∈ B : ∃c = (x_{i}, x_{j}, 0) ∈ C, ∄x_{i} ∈ A, x_{j} ∈ B : ∃c = (x_{i}, x_{j}, 1) ∈ C}.

Az eljárás akkor ér véget, ha a következő feltétel teljesül: (T) : Vagy ∃ x ∈ X, ami minden χ(C)–beli partícióra a nagyobbik részben van, vagy minden χ(C)–beli partíció két azonos méretű halmazból áll. Tekintsük a G = (X, C) gráfot.(x_{i} ∈ X és x_{j} ∈ X a 0–s színnel van összekötve, ha (x_{i}, x_{j}, 0) ∈ C; az 1–es színnel, ha (x_{i}, x_{j}, 1) ∈ C). Legyenek G_{1}, G_{2}, …, G_{k} G összefüggő komponensei, X_{i} pedig G_{i} ponthalmaza. Mivel fölösleges összehasonlítások nincsenek C–ben, a G_{i} gráfok fák. Az X_{i} halmazokon belül bármely két elemről el tudjuk dönteni, hogy azonos színűek-e: ha a köztük lévő egyértelmű G–beli út páros sok 0–s színű élt tartalmaz, akkor egyformák, ha páratlant, akkor különbözők. Így X_{i}–t felbonthatjuk az L_{i}, S_{i} halmazokra úgy, hogy az egy halmazon belüli elemek azonos színűek, a különböző halmazban lévők pedig különböző színűek. (L_{i} ∩ S_{i} = ∅ ; L_{i} ∪ S_{i} = X , a,b ∈ L_{i} : ∃c ∈ C : c = (a, b, 1) a,b ∈ S_{i} : ∃c ∈ C : c = (a, b, 1) , a ∈ S_{i} , b ∈ L_{i} : ∃c ∈ C : c = (a, b, 0) ). Legyen mondjuk |L_{i}| ≥ |S_{i}|, és legyen m_{i} = |L_{i}|−|S_{i}|. Jelöljük az {1, 2, …, k} halmazt [k]–val. Tetszőleges I ⊆ [k] esetén legyen

L_{I} = ⋃_{i∈I} L_{i} , S_{I} = ⋃_{i∈I} S_{i} , m_{I} = ∑_{i∈I} m_{i} .

Azonnal látható, hogy

χ(C) = {{L_{I} ∪ S_{[k]\I} , S_{I} ∪ L_{[k]\I}} I ⊆ [k] }
és  ||L_{I} ∪ S_{[k]\I} | − |S_{I} ∪ L_{[k]\I} || = |m_{I} − m_{[k]\I} | .

Egy x ∈ X elem tehát pontosan akkor fog minden χ(C)–beli partíció esetén a többséghez tartozni, ha x ∈ L_{j} mellett (j ∈ [k]) m_{I} > m_{[k]\I} ∀ I–re, ami j–t tartalmazza.

Ilyen x tehát pontosan akkor létezik, ha létezik j ∈ [k], amire m_{j} > ∑_{\begin{matrix}i=1 \\ i≠j \end{matrix}}^{k} m_{i}.

|L_{I} ∪ S_{[k]\I} | = |S_{I} ∪ L_{[k]\I} | pedig pontosan akkor teljesül, ha m_{I} = m_{[k]\I}. Ahhoz, hogy ez minden I ⊆ [k] esetén igaz legyen, m_{1} = m_{2} = … = m_{k} = 0 szükséges (és elegendő is persze). A fentiek szerint a (T) feltétel tehát ekvivalens az alábbi (T’) feltétellel:

(T’) : ( ∃j ∈ [k] : m_{j} > ∑_{\begin{matrix}i=1 \\ i≠j \end{matrix}}^{k} m_{i} ) ∨ (m_{1} = m_{2} = … = m_{k} = 0 ).

Mivel továbbra sem akarunk fölösleges összehasonlításokat tenni, egy újabb kérdés x ∈ X_{i}–re és y ∈ X_{j}–re vonatkozhat, ahol i ≠ j. Ekkor

\{ A_{0} ∩ (X_{i} ∪ X_{j}) , B_{0} ∩ (X_{i} ∪ X_{j}) \} = \begin{cases}\{ L_{i} ∪ L_{j} , S_{i} ∪ S_{j}\}, & ha t(x) = t(y) \\ \{ L_{i} ∪ S_{j} , L_{j} ∪ S_{i}\}, & ha t(x) ≠ t(y) , \end{cases}

így m_{i} és m_{j} eltűnik, és helyettük vagy m_{i} + m_{j} vagy |m_{i} − m_{j}| jelenik meg. Eszrint a keresési problémát a következő játék formájában adhatjuk meg: a két játékos a választó (V) és a cserélő (C). A játék állása egy adott pillanatban az M = (m_{1}, m_{2}, …, m_{k}) sorozat. V minden körben választ két számot az M sorozatból, C ezeket kiveszi M–ből, és tetszése szerint vagy az összegüket, vagy a különbségük abszolút értékét teszi vissza helyettük. Azt a sorozatot, amit M– ből úgy kapunk, hogy m_{i} és m_{j} helyett az összegük (különbségük abszolút értéke) szerepel M_{ij}^{+}–vel (M_{ij}^{−}–vel) jelöljük. Nyilvánvaló, hogy a játék állásának mérete minden körben eggyel csökken. A játék akkor ér véget, ha már létezik olyan eleme M–nek, mely a többiek összegénél nagyobb, vagy ha az összes elem 0. A választó minimalizálni, a cserélő maximalizálni szeretné a körök l számát a játék végéig. Mivel l + |M| = n, ez azt jelenti, hogy V M_{v} méretét maximalizálni, C minimalizálni akarja az M_{v} végállásra.

3.1. Definíció. V (M) = V (m_{1}, m_{2}, …, m_{k}) := |M_{v}|, ahol M_{v} az M–ből kapott végállás, ha mindkét játékos optimálisan játszik.^{4} Jelöljük V (\underbrace{1, 1, …, 1}_{n})–et

V (n)–nel.

A probléma ezen átfogalmazása (legalábbis páratlan n–ek esetén) Saks–tól és Werman–tól ered [14], így (S–W)–átfogalmazásnak fogjuk hívni. Ha a legrosszabb eseti probléma helyett az átlagos érdekel minket, csupán annyit kell változtatnunk, hogy a cserélő kezét megkötjük: 1 2- 1 2 eséllyel kell (m_{i} + m_{j})– t illetve |m_{i} − m_{j}|–t választania. Egy másik (bár igen hasonló) átfogalmazást kapunk, ha a fentieken annyit változtatunk, hogy 0–kat nem engedünk meg az M = (m_{1}, m_{2}, …, m_{k}) sorozatban, azaz ha |m_{i} − m_{j}| = 0, akkor nem rakjuk be M–be. Ilyenkor M mérete természetesen nem eggyel, hanem kettővel csökken. Az eljárás befejeződésére vonatkozó feltétel is módosul:

(T”) : vagy ∃j ∈ [k] : m_{j} > ∑_{\begin{matrix}i=1 \\ i≠j \end{matrix}}^{k} m_{i}, vagy M üres.

Az, hogy ez az átfogalmazás az eredeti problémával ekvivalens, a következő szemléletes kép helyességét igazolja: az elemeket kupacokba pakoljuk oly módon, hogy az azonos kupacban lévő elemek deklaráltan azonos színűek, a különböző kupacban lévő elemek viszonyáról pedig semmit sem tudunk. Egy lépés ilyenkor nem más, mint két kupac összehasonlítása: ha azonos színűnek bizonyulnak, egy kupaccá olvasztjuk össze őket, ha különbözők, akkor a kisebbik eltűnik, a nagyobbikból pedig annyi elemet veszünk el, amennyi a kisebbikben volt. Ennek szemléletes indoka: legyen m_{i} a kisebbik, m_{j} a nagyobbik kupac mérete, ekkor a két kupacban van 2m_{i} elemünk, melyek közt m_{i} piros és m_{i} kék található, továbbá m_{j} − m_{i} elem, amiről semmmit sem tudunk. A 2m_{i} elemre a többségi elem keresése során nem lesz szükségünk, hiszen ha kitöröljük őket, a visszamaradó elemek között pontosan ugyanazok lesznek többségiek, mint korábban, így legjobb, ha gyorsan elfelejtjük őket, és örülünk, hogy sikerült az elemek számát csökkenteni. Ezt természetesen csak szemléletünk súgja (helyesen, persze), a korrekt bizonyítást az (S-W)–átfogalmazás, pontosabban annak módosítása adja, ezért ezt a szemléletes képet (S-W)’–átfogalmazásnak nevezzük el.

hogy |M| < k–ra létezik, ekkor V (m_{1}, m_{2}, …, m_{k}) = max_{i,j} min (V (M_{ij}^{−}) , V (M_{ij}^{+})).

4Azt, hogy ez az optimális lejátszás létezik, triviális indukcióval láthatjuk be: tegyük fel,

3.3. A legrosszabb eset–probléma

3.2. Definíció. Az n természetes szám kettes számrendszerbeli felírásában szereplő 1–esek számát ν(n)–nel jelöljük.^{5}

3.3. Definíció. Az n természetes szám prímtényezős felbontásában a 2 kitevőjét jelöljük P (n)–nel.

3.4. Definíció. A többségi elem kereséséhez n elemű alaphalmaz esetén a legrosszabb esetben szükséges lépésszám legyen az adaptív keresésre g(n), a nem adaptív keresésre g_{pre}(n). (Természetesen g_{pre}(n) ≥ g(n)).

Foglalkozzunk először a — lényegesen egyszerűbb — statikus esettel.

3.5. Állítás.

g_{pre}(n) = \begin{cases}n − 1, & ha n páros \\ n − 2, & ha n páratlan \end{cases}

Bizonyítás. n − 1 lépés mindig elég, hiszen ha egy elemet az összes többivel összehasonlítunk, akkor mindent tudunk. (Csak azt nem, hogy melyik osztály a piros, és melyik a kék, de ez senkit nem érdekel). Ha n = 2k + 1, akkor 2k − 1 lépés is elég, mert ha 2k elem között tudunk többségit mutatni, akkor az nyilván 2k + 1 elem között is többségi, míg ha ilyen nincs a 2k között, akkor a (2k + 1). elem lesz nyerő. Megjegyzés. Ebből a megfigyelésből nem csak g_{pre}(2k + 1) ≤ g_{pre}(2k) hanem g(2k + 1) ≤ g(2k) is következik, sőt ezt a tényt az adaptív esetben lényegesen jobban ki tudjuk aknázni, mint azt látni fogjuk.

Most belátjuk, hogy ennyi összehasonlítás szükséges is. Legyen V az elemek, E az összehasonlítások halmaza. G = (V, E) egy gráf, melyben az élek két színnel vannak színezve. Legyen először |V | páros. Ha |E| < n − 1, akkor G nem összefüggő. Húzzunk be annyi élt (ha szükséges), hogy G két komponensből álljon (G_{1} = (V_{1}, E_{1}) , G_{2} = (V_{2}, E_{2}) ). Mivel |V | páros, |V_{1}| ≡ |V_{2}| (mod 2). Adjuk meg az élek színezését úgy, hogy az V_{1}–ben és V_{2}–ben is minimális többséget jelentsen. Ha a V_{1}–beli és a V_{2}–beli többség azonos színű, akkor ezek V –ben is többséget alkotnak, de ha különbözők, akkor V –ben nincs többség. Azt, hogy a kettő közül melyik áll fönn, nem lehet eldönteni, így (n−1)–nél kevesebb összehasonlítás nem elegendő. Annak bizonyítása, hogy a páratlan esetben (n−2)–nél kevesebb lépés nem elég, ugyanígy megy, csak kettő helyett három komponenssel kell dolgoznunk. □

Térjünk rá az adaptív esetre.

5ν(n)–et másképp is definiálhatjuk: tekintsük n–nek 2–hatványokra való partícióit. (Az 1 is 2–hatvány). Ezek közt lesz (egy) minimális elemszámú, legyen ez az elemszám ν(n). A két definíció ekvivalenciája könnyen látható.

3.6. Állítás. g(n) ≤ n − ν(n).

Bizonyítás. Megadunk egy algoritmust (pontosabban algoritmusok egy családját), amely a legrosszabb esetben n − ν(n) lépésbn talál többségi elemet. Használjuk az (S–W)’–átfogalmazást. Egy algoritmus abból áll, hogy megmondjuk, mikor melyik kupacokat akarjuk összehasonlítani. Definiáljuk az algoritmusok egy G családját a következőképp: egy algoritmus pontosan akkor van G–ben, ha minden lépésben két azonos méretű kupacot hasonlít össze.

3.7. Állítás. G nem üres.

Bizonyítás. Tetszőleges G ∈ G algoritmus során ha egy lépésnél a két hasonlított kupac azonos színű, akkor összeolvadnak, tehát az új kupac elemszáma az eredeti elemszámok kétszerese lesz; ha különböző színűek, akkor egyszerűen eltűnnek. Így, mivel a kupacok eredetileg egyeleműek, mnden lépés után az összes szereplő elemszám 2–hatvány. (Az 1–et természetesen most is — és a továbbiakban is— 2–hatványnak tekintjük). Ha az elemszámok közt nincs két azonos, akkor köztük a legnagyobb nagyobb lesz, mint a többi együtt, hiszen 2–hatványokról van szó. Amíg tehát a keresésnek nincs vége, mindig lesz két azonos elemszámú kupac, ami azt jelenti, hogy G nem üres. (Sőt …) □

3.8. Állítás. Az G–beli algoritmusok legrosszabb eseti lépésszáma legfeljebb n − ν(n).

Bizonyítás. Az M = (m_{1}, m_{2}, …, m_{k}) sorozatban a még vizsgálandó kupacok méretei vannak. Az M′ sorozatba tegyük be minden olyan lépésnél, amikor két kupac eltűnik, az eltűnt elemek számát. Így az M–beli és az M′–beli elemek összege mindig n marad, és az |M| + |M′| szám minden lépésnél eggyel csökken. Egy G ∈ G algoritmus tetszőleges lépése után (így speciálisan a végállásra is) igaz, hogy |M| + |M′| ≥ ν(n), hiszen M és M′ elemei 2–hatványok, és összegük n, n–et pedig ν(n)–nel kevesebb 2–hatvány összegeként nem lehet előállítani. A lépések számára tehát n − (|M| + |M′|) ≤ n − ν(n) adódik. □

Megjegyzés. Tulajdonképpen kicsit többet bizonyítottunk, mint az állítás, hiszen ha nem addig folytatjuk az eljárást, míg lesz egy, a többiek összelemszámánál nagyobb kupac, hanem addig, ameddig csak lehet (vagyis amíg van két azonos méretű kupac), akkor is legfeljebb n − ν(n) lépést tehetünk.

A felső becsléshez szükségünk lesz az alábbi lemmára:

3.9. Lemma. P (\binom{2k}{k}) = ν(k)

Bizonyítás. Indukcióval k–ra. k = 1 esetén az állítás triviális. k ≥ 2 esetén az indukciós feltevést kihasználva:

P (\binom{2k}{k}) = P (2k(2k − 1) ; k^{2} \binom{2k − 2}{k − 1}) = P (\binom{2k − 2}{k − 1}) + 1 − P (k) =

= ν(k − 1) + 1 − P (k) = ν(k) ,

ahol az utolsó egyenlőség azért teljesül, mert k utolsó P (k) + 1 számjegye a 2– es számrendszerben felírva 1 \underbrace{00 … 0}_{P (k)}, így (k − 1) utolsó P (k) + 1 számjegye a

2–es számrendszerben: 0 \underbrace{11 … 1}_{P (k)}, továbbá (k − 1) és k a többi számjegyükben

azonosak, így ν(k − 1) = ν(k) + P (k) − 1. □

3.10. Állítás. g(n) ≥ n − ν(n), ha n páratlan.

Bizonyítás. (Saks–Werman) Az alábbi lemma magától értetődő.

3.11. Lemma.

V (M) = max_{i,j} min (V (M_{ij}^{−}), V (M_{ij}^{+})) ,

ha M nem végállás. □

Konstruálni fogunk egy Φ függvényt, ami minden M álláshoz egy pozitív egész számot rendel, és rendelkezik az alábbi tulajdonságokkal:

(1) Φ(M) ≥ V (M), ha M végállás.

(2) Φ(M) ≥ min (Φ(M_{ij}^{−}), Φ(M_{ij}^{+})), ∀i, j, ha M nem végállás.

E két tulajdonságból az előző lemma szerint következik az alábbi harmadik:

(3) Φ(M) ≥ V (M), minden M állásra.

Végül megmutatjuk, hogy

(4) Φ(\underbrace{1, 1, …, 1}_{n}) = ν(n), ha n páratlan.

Ha ilyen Φ–t sikerül megadnunk, az nyilván bizonyítja V (n) ≥ ν(n)–et, és így állításunkat is. Legyen M_{I} az M azon részsorozata, mely az I indexű tagokból áll (I ⊆ [k]), és jelöljük ezen tagok összegét m_{I}–vel. I–t nehéznek hívjuk (az M–re nézve), ha m_{I} > m_{[k]\I}. Definiáljuk az f_{M} generátorfüggvényt a következőképp:

f_{M}(x) := ∑_{I nehéz} x^{m_{I}} .

Végül legyen

Φ(M) := 1 + P (f_{M}(−1)) .

Megmutatjuk, hogy Φ rendelkezik az (1), (2) és (4) tulajdonságokkal. Egy M állás pontosan akkor végállás, ha valamelyik eleme — mondjuk m_{1} — nagyobb, mint a többi elem összege. Így ekkor I nehéz ⇔ 1 ∈ I, ezért

f_{M}(x) = x^{m_{1}}(1 + x^{m_{2}})(1 + x^{m_{3}}) … (1 + x^{m_{k}}) .

Ilyetén körülmények között |f_{M}(−1)| vagy 0, vagy 2^{k−1}, tehát

Φ(M) = 1 + P (f_{M}(−1)) ≥ k = V (M) ,

ami (1)–et bizonyítja.

(2) bizonyításához föltehetjük, hogy i = k − 1, j = k, és m_{k−1} ≥ m_{k}. Jelöljük M_{k−1,k}^{+}–t M^{+}–szal, M_{k−1,k}^{−}–t M^{−}–szal.

3.12. Lemma. f_{M}(x) = f_{M^{+}}(x) + x^{m_{k}}f_{M^{−}}(x)

Bizonyítás. Legyen M^{+} = (m_{1}^{+}, m_{2}^{+}, …, m_{k}^{+}), M^{−} = (m_{1}^{−}, m_{2}^{−}, …, m_{k}^{−}), ahol persze m_{i}^{+} = m_{i}^{−} = m_{i}, ha i ≤ k −2, és m_{k−1}^{+} = m_{k−1} +m_{k}, m_{k−1}^{−} = m_{k−1} −m_{k}. Legyen A_{1} a [k] részhalmazainak azon halmaza, melyek metszete {k − 1, k}–val egyelemű. Legyen A_{0} a [k] többi részhalmazainak halmaza. Ha I ∈ A_{0}, akkor könnyen látható, hogy m_{I} = m_{I\{k}}^{+}, így — mivel M–ben és M^{+}–ban az elemek összege azonos

I ∈ A_{0} nehéz M–re nézve ⟺ I \ {k} nehéz M^{+}–ra nézve .

Ha I ∈ A_{1}, akkor m_{I} = m_{I\{k}}^{−} + m_{k}, és mivel M^{−}–ban az elemek összege 2m_{k}–val kevesebb, mint M–ben

I ∈ A_{1} nehéz M–re nézve ⟺ I \ {k} nehéz M^{−}–ra nézve .

Ezek alapján a következőket írhatjuk fel:

f_{M}(x) = ∑_{\begin{matrix}I nehéz \\ M−re \end{matrix}}x^{m_{I}} = ∑_{\begin{matrix}I∈A_{0} \\ nehéz \\ M−re \end{matrix}}x^{m_{I}} + ∑_{\begin{matrix}I∈A_{1} \\ nehéz \\ M−re \end{matrix}}x^{m_{I}} = ∑_{\begin{matrix}I∈A_{0} \\ I\\{k\} nehéz \\ M^{+}−ra \end{matrix}}x^{m_{I}} + ∑_{\begin{matrix}I∈A_{1} \\ I\\{k\} nehéz \\ M^{−}ra \end{matrix}}x^{m_{I}} =

= ∑_{\begin{matrix}I∈A_{0} \\ I\\{k\} nehéz \\ M^{+}−ra \end{matrix}}x^{m_{I\\{k\}}^{+}} + ∑_{\begin{matrix}I∈A_{1} \\ I\\{k\} nehéz \\ M^{−}ra \end{matrix}}x^{m_{I\\{k\}}^{−}+m_{k}} = f_{M^{+}}(x) + x^{m_{k}}f_{M^{−}}(x) .

□

Így tehát

Φ(M) = 1 + P (f_{m}(−1)) = 1 + P (f_{M^{+}}(−1) + (−1)^{m_{k}}f_{M^{−}}(−1)) ≥

≥ 1 + min (P (f_{M^{+}}(−1), P (f_{M^{−}}(−1))) = min (Φ(M^{+}), Φ(M^{−})) .

(Felhasználtuk, hogy P (a + b) ≥ P (a) + P (b)). Ezzel (2)–t is beláttuk.

(4) bizonyításához legyen n = 2k + 1, M = (\underbrace{1, 1, …, 1}_{n}).

Ekkor I nehéz ⇔ |I| ≥ k + 1, ahonnan

f_{M}(−1) = ∑_{j=k+1}^{2k+1}(−1)^{j}\binom{2k + 1}{j} =

= ∑_{j=k+1}^{2k+1}(−1)^{j} (\binom{2k}{j − 1} + \binom{2k}{j}) = (−1)^{k−1}\binom{2k}{k} .

Így, mivel ν(2k + 1) = ν(k) + 1, a (4) tulajdonság következik a 3.9. lemmából. Ezzel a bizonyítást befejeztük. □

3.13. Tétel. (Saks–Werman, 1991, [14])

g(n) = n − ν(n)

Bizonyítás. Páratlan n-ekre a 3.6. és a 3.10. állítások szerint g(n) = n − ν(n). Legyen most n = 2k. g(2k) ≤ 2k − ν(2k) a 3.6. állítás szerint. Másrészt g(2k) ≥ g(2k + 1) a 3.5. állítás után található megjegyzés szerint, így

g(2k + 1) ≤ g(2k) ≤ 2k − ν(2k) = (2k + 1) − ν(2k + 1) = g(2k + 1) ,

ahonnan g(2k) = 2k − ν(2k). Q.E.D. □

A tétel bizonyításában a 3.10. állítás játszik kulcsszerepet, amit Saks és Werman 1991-ben bizonyított generátorfüggvények segítségével.(Mint azt a fentiekben láthattuk.Az általuk alkalmazott módszerről bővebben ld. [4]). Ha 3.10.–et nem páratlan, hanem páros n–ekre mondjuk ki, egyszerűbb bizonyítás is adható.

3.14. Állítás. g(2n) ≥ 2n − ν(2n)

Bizonyítás. Ismét az (S–W)–átfogalmazást használjuk. A cserélőnek egy olyan stratégiáját fogjuk megadni, amely mellett a játék 2n − ν(2n) lépésnél előbb nem érhet véget. A stratégia első szempontja, hogy n piros és n kék golyó legyen. Ekkor a játék csak a (0, 0, …, 0) sorozattal érhet véget. Ha n piros és n kék golyóval indulunk, minden lépés után lesz egy I indexhalmaz, hogy m_{I} = m_{[k]\I} (az (m_{1}, m_{2}, …, m_{k}) állásra ). Jelöljük az ilyen indexhalmazok halmazát J_{M}^{k}–val. (A felső indexre csak kényelmi szempontokból van szükség, azt mutatja, hogy hány elemű az alsó indexben szereplő állás). J_{M}^{k} tehát soha nem üres, és ha M = (\underbrace{0, 0, …, 0}_{k}) végállás, akkor |J_{M}^{k}| = 2^{k} nyilván.

3.15. Lemma. |J_{M}^{k}| = |J_{M^{+}}^{k−1}| + |J_{M^{−}}^{k−1}|

Bizonyítás. Legyen A_{1} azon I ⊆ [k]–k halmaza, melyek k − 1 és k közül pontosan az egyiket tartalmazzák, A_{0} pedig álljon a többi indexhalmazból. Könnyen látható, hogy J_{M}^{k} ∩ A_{1} = J_{M^{−}}^{k−1} és J_{M}^{k} ∩ A_{0} = J_{M^{+}}^{k−1}. Így

|J_{M^{+}}^{k−1}| + |J_{M^{−}}^{k−1}| = |J_{M}^{k} ∩ A_{1}| + |J_{M}^{k} ∩ A_{0}| = |J_{M}^{k}| ,

hiszen A_{0} és A_{1} diszjunkt, és uniójuk 2^{[k]}. □

A cserélő második szempontja legyen a következő: ha P (|J_{M^{+}}^{k−1}|) > P (|J_{M^{−}}^{k−1}|), akkor M^{−}-ra cserél, ha P (|J_{M^{−}}^{k−1}|) ≥ P (|J_{M^{+}}^{k−1}|), akkor M^{+}–ra. Mivel |J_{M}^{k}| = = |J_{M^{+}}^{k−1}| + |J_{M^{−}}^{k−1}| (az előző lemma szerint), P (|J_{M}^{k}|) = P (|J_{M^{+}}^{k−1}| + |J_{M^{−}}^{k−1}|), ahonnan P (|J_{M}^{k}|) ≥ min (P (|J_{M^{+}}^{k−1}|) , P (|J_{M^{−}}^{k−1}|). Azaz a második szempont szerint P (|J_{M}|) nem nőhet a cserék során. Kezdetben M = (1, 1, …, 1), ekkor

P (|J_{M}|) = P (\binom{2n}{n}) = ν(n), így az M′ = (\underbrace{0, 0, …, 0}_{k}) végállásra

k = P (|J′_{M}|) ≤ ν(n) = ν(2n), tehát a lépések 2n − k számára 2n − k ≥ 2n − − ν(2n). □

Nyitott kérdés, hogy pontosan mely algoritmusok legrosszabb eseti lépésszáma optimális. Tudjuk, hogy a G–beli algoritmusok ilyenek. Létezik-e G–n kívül is ilyen algoritmus? Ennek vizsgálatában hasznosak lehetnek az iménti bizonyításban bevezetett |J_{M}^{k}| részpartíciószámok.

3.4. Az átlagos eset–probléma

Most tehát a lépésszám várható értékét igyekszünk minimalizálni, midőn mind a 2^{n} színkiosztás egyenlő valószínűségű. Jelöljük ezt az optimumot h(n)–nel. A továbbiakban a probléma (S–W)’–átfogalmazását használjuk, tehát az M = = (m_{1}, m_{2}, …, m_{k}) állás az m_{i} méretű kupacokból áll, ahol m_{i} ≠ 0 (i = = 1, 2, …, k). Feltehetjük, hogy m_{1} ≥ m_{2} ≥ … ≥ m_{k}. Egy tetszőleges algoritmus futása során a keletkező állásokból egy bináris fát építünk a következőképp: a gyökér legyen a kezdeti állás: (\underbrace{1, 1, …, 1}_{n}). Ha az algoritmus az

M = (m_{1}, m_{2}, …, m_{k}) állásban az i. és a j. kupacot hasonlítja össze, akkor M jobb gyereke legyen M_{ij}^{+}, bal gyereke M_{ij}^{−}. Ha az algoritmus végetér, akkor természetesen nem ágaztatjuk tovább a fát, tehát a levelek a végállások lesznek. A kapott bináris fa és az algoritmus kölcsönösen meghatározzák egymást. Az A algoritmushoz tartozó fát jelöljük T_{A}–val. Emlékeztetünk két jelölésre az 1.2. és a 2.1. fejezetből: E(T)–vel jelöltük a T fa leveleit, I(T)–vel pedig a többi pontját. h_{A}(n)–nel jelölve az A algoritmus átlagos lépésszámát:

h_{A}(n) = ∑_{l∈E(T_{A})} d(l) ; 2^{d(l)} ,

ahol d(v) a v csúcs távolsága a gyökértől (azaz v mélysége (depth)). Jelöljük

∑_{l∈E(T)} d(l) ; 2^{d(l)} -et C(T)–vel. Ekkor tehát h(n) = min_{A sikeres ; algoritmus} C(T_{A}).

3.16. Tétel.

h(n) ≥ 2n ; 3 − √8n ; 9π + Θ(1)

Bizonyítás. Egy tetszőleges algoritmushoz tartozó T bináris fát fogunk vizsgálni. A fa egy csúcsát normálisnak nevezzük, ha az algoritmus hozzá tartozó lépésében két azonos méretű kupacot hasonlítunk össze, egyébként a csúcs különös. Könnyen látható, hogy

C(T) = ∑_{l∈E(T)} d(l) ; 2^{d(l)} = ∑_{v∈I(T)} 1 ; 2^{d(v)} .

Ha a v csúcshoz az M = (m_{1}, m_{2}, …, m_{k}) állás tartozik, akkor legyen l(v) = = k, a csúcs hossza. Az algoritmus végére kapott állás hosszának várható értékét L(T)–vel jelölve:

L(T) = ∑_{v∈E(T)} l(v) ; 2^{d(v)} .

3.17. Lemma. Legyen f tetszőleges függvény a T csúcsain. Ekkor

∑_{v∈I(T)} (f(v) − f(bal(v)) − f(jobb(v)) = f(gyökér) − ∑_{l∈E(T)} f(l) ,

ahol természetesen bal(v) és jobb(v) a v csúcs megfelelő irányú gyerekeit jelentik.

Bizonyítás. Triviális. □

Alkalmazzuk a lemmát az f(v) = l(v) ; 2^{d(v)} függvényre! f(gyökér)= n, ∑_{l∈E(T)} f(l) = L(T), és

f(v) − f(bal(v)) − f(jobb(v)) = \begin{cases}3 ; 2^{d(v)+1} , & ha v normális \\ 1 ; 2^{d(v)} , & ha v különös . \end{cases}

A lemmából tehát a következőt kapjuk:

∑_{v∈I(T) ; normális} 3 ; 2^{d(v)+1} + ∑_{\begin{matrix}v∈I(T) \\ különös \end{matrix}} 1 ; 2^{d(v)} = n − L(T) .

Minthogy minden belső csúcs vagy normális, vagy különös, ezt az egyenlőséget a következőképp írhatjuk át:

3 2 ∑_{v∈I(T)} 1 ; 2^{d(v)} − 1 2 ∑_{\begin{matrix}v∈I(T) \\ különös \end{matrix}} 1 ; 2^{d(v)} = n − L(T) .

∑_{v∈I(T)} 1 ; 2^{d(v)} = C(T) így 3 2C(T) − 1 2 ∑_{\begin{matrix}v∈I(T) \\ különös \end{matrix}} 1 ; 2^{d(v)} = n − L(T), vagyis

C(T) = 2n ; 3 − 2 3L(T) + 1 3 ∑_{\begin{matrix}v∈I(T) \\ különös \end{matrix}} 1 ; 2^{d(v)} ≥ 2n ; 3 − 2 3L(T) ≥ 2n ; 3 − 2 3E(m_{1}) ,

ahol E(m_{1}) az m_{1} várható értéke az algoritmus végére. Az utolsó egyenlőtlenség szorul még bizonyításra: E(m_{1}) ≥ L(T), hiszen az M = (m_{1}, m_{2}, …, m_{k})

végállásra m_{1} ≥ ∑_{i=2}^{k} m_{i}, és egyenlőség pontosan akkor teljesül, ha mindkét oldal

üres, így m_{1} ≥ k, mert m_{i} ≥ 1 ∀i. Mivel ez minden végállásra teljesül, a várható értékekre is igaz kell legyen.

3.18. Lemma. A v csúcshoz tartozó állásban a golyók össszes lehetséges színezéseinek száma 2^{n−d(v)}.

Bizonyítás. Triviális, hiszen a lehetséges színezések száma minden lépésben feleződik. □

A továbbiakban E(m_{1}) értékét szeretnénk kiszámítani. Definiáljuk ehhez a következő függvényt:

M(n) := 1 ; 2^{n} ∑_{C színezés}(|többség C–ben| − |kisebbség C–ben|) .

Minden színezéshez pontosan egy levél van, amelyhez tartozó állás kompatibilis a színezéssel, így:

M(n) = 1 ; 2^{n} ∑_{l∈E(T)} ∑_{C l−hez ; tartozik} (|többség C–ben| − |kisebbség C–ben|) .

Ha az l levélhez az M = (m_{1}, m_{2}, …, m_{k}) végállás tartozik, akkor

|többség C–ben| − |kisebbség C–ben| = m_{1} ± m_{2} ± . . . . . . ± m_{k} ,

ahol az m_{i} előjele +, ha az i. és az 1. kupac azonos színű, és -, ha különbözők. Az l levél mindegyik ilyen színezést tartalmazza (többnyire többszörösen is), így a szummázásnál csak az m_{1} marad meg, éspedig annyiszor, ahány színezés az l–hez tartozik. A következőt kapjuk tehát:

∑_{C l−hez ; tartozik} (|többség C–ben| − |kisebbség C–ben|) = 2^{n−d(l)}m_{1} .

Ebből

M(n) = 1 ; 2^{n} ∑_{l∈E(T)} 2^{n−d(l)}m_{1} = ∑_{l∈E(T)} m_{1} ; 2^{d(l)} = E(m_{1}) .

Most már csak M(n) értékét kell kiszámítanunk, ez viszont rutinfeladat:

M(n) = 1 ; 2^{n} ∑_{l∈E(T)} ∑_{C l−hez ; tartozik} (|többség C–ben| − |kisebbség C–ben|) =

= 1 ; 2^{n−1} ∑_{k≤ n ; 2}(n − 2k)\binom{n}{k} = 1 ; 2^{n−1} ∑_{k≤ n ; 2} [(n − k)\binom{n}{k} − k\binom{n}{k}] =

1 ; 2^{n−1} ∑_{k≤ n ; 2} [n\binom{n − 1}{k} − n\binom{n − 1}{k − 1}] =

= n ; 2^{n−1} ∑_{k≤ n ; 2} [\binom{n − 1}{k} − \binom{n − 1}{k − 1}] = n ; 2^{n−1} \binom{n − 1}{⌊ n−1 ; 2⌋} .

Ez utóbbi a Stirling–formula felhasználásával √ 2n ; π +Θ(1)–nak adódik. Eszerint

C(T) ≥ 2 3n − 2 3E(m_{1}) = 2 3n − 2 3M(n) = 2n ; 3 − √8n ; 9π + Θ(1) .

Így h(n) = min_{A sikeres ; algoritmus} C(T_{A}) ≥ 2n ; 3 − √ 8n ; 9π + Θ(1). □

Alsó becslésünk ezzel már van, most egy jó algoritmus kéne. Az előző tétel bizonyításában használt módszer ebben is segíthet: h(n) = min_{A sikeres ; algoritmus} C(T_{A}), és

C(T) = 2n ; 3 − 2 3L(T) + 1 3 ∑_{\begin{matrix}v∈I(T) \\ különös \end{matrix}} 1 ; 2^{d(v)} .

Tehát 2 3L(T) − 1 3 ∑_{\begin{matrix}v∈I(T) \\ különös \end{matrix}} 1 ; 2^{d(v)} –t kell maximalizálnunk.

3.19. Tétel.

h(n) ≤ 2n ; 3 − √8n ; 9π + O(log n)

Bizonyítás. Megadunk egy A algoritmust, melyre C(T_{A}) = 2n ; 3 − √ 8n ; 9π + O(log n). Tegyük fel, hogy az M állás

(⋆) M = (m_{1}, m_{2}, …, m_{k}) = ((2t + 1)2^{e_{1}}, 2^{e_{2}}, …, 2^{e_{k}})

alakú. (A kezdeti állás nyilván ilyen). Ha M nem végállás, tehát ha (2t+1)2^{e_{1}} ≤

≤ ∑_{i=2}^{k} 2^{e_{i}}, akkor az e_{i}–k közt van két azonos. Legyen i a legkisebb olyan szám,

melyre e_{i} egynél többször fordul elő. (Azaz a legkisebb j, melyre m_{j} ; m_{j+1} páratlan).

Ha most ∑_{j≤i} m_{j} > ∑_{j>i} m_{j}, akkor az 1. és a 2. kupacot hasonlítjuk össze, ha

∑_{j≤i} m_{j} ≤ ∑_{j>i} m_{j}, akkor az i. és az (i + 1). kupacot. Az eredménytől függetlenül

mindkét esetben ismét (⋆) alakú állást kapunk. Ezzel megadtunk egy algoritmust és egy hozzá tartozó bináris fát. Vezessük be a következő jelölést: ha M = (m_{1}, m_{2}, …, m_{k}), akkor

N_{M} := |{i : m_{i} = 1}|

.

3.20. Lemma. A kapott T bináris fa tetszőleges csúcsában lévő M állásra:

N_{M} + 2 ≥ ∑_{m_{j}≠1} m_{j} .

Bizonyítás. Triviális, indukcióval a fa mélységére. □

3.21. Lemma. A végállások a következő alakúak lehetnek:

() ; (2) ; (i, \underbrace{1, 1, …, 1}_{j}) ,

ahol j = i − 1, vagy j = i − 2.

Bizonyítás. Állításunk azzal ekvivalens, hogy ha létezik m_{2} az M végállásban, akkor m_{2} = 1. Tegyük fel indirekt, hogy m_{2} ≥ 2. Az előző lemma szerint:

m_{1} + m_{2} ≤ ∑_{m_{j}≠1} m_{j} ≤ 2 + N_{M} ,

ahonnan

m_{1} ≤ (2 − m_{2}) + N_{M} ≤ N_{M} ,

ami ellentmond annak, hogy M végállás. □

A most belátott lemmából következik az alábbi állítás: 3.22. Állítás. T tetszőleges v levelére: l(v) = m_{1} + O(1). □

Így a levelek hosszának várható értékére:

L(T (n)) = E(m_{1}) + O(1) = M(n) + O(1) = √2n ; π + Θ(1) .

Hátravan még ∑_{\begin{matrix}v∈I(T) \\ különös \end{matrix}} 1 ; 2^{d(v)} kiszámítása. Algoritmusunk során m_{2} csak a 2^{i}

értékeket veheti fel, 0 ≤ i ≤ ⌊log n⌋ mellett, így

∑_{\begin{matrix}v∈I(T) \\ különös \end{matrix}} 1 ; 2^{d(v)} = ∑_{i=0}^{⌊log n⌋} ∑_{\begin{matrix}v∈I(T) \\ különös \\ m_{2}=2^{i} \end{matrix}} 1 ; 2^{d(v)} .

Az alábbi lemma bizonyításának technikai részleteivel nem kívánjuk terhelni az olvasót. 3.23. Lemma. ∑_{\begin{matrix}v∈I(T) \\ különös \\ m_{2}=k \end{matrix}} 1 ; 2^{d(v)} ≤ 2

A lemmát alkalmazva

∑_{\begin{matrix}v∈I(T) \\ különös \end{matrix}} 1 ; 2^{d(v)} ≤ 2⌊log n⌋ = O(log n)

adódik, így tehát

C(T_{A}) ≤ 2n ; 3 − √8n ; 9π + O(log n) ,

ahogy állítottuk. □

3.5. Nyitott problémák

Adjuk meg az összes olyan algoritmust, melynek a legrosszabb eseti bonyolultsága optimális. Ezt a problémát a 3.3. fejezet végén már tárgyaltuk. Alonso, Reingold és Schott 3.4.–ben látott, az átlagos esetben az optimumtól legfeljebb O(log n)–ben eltérő, igen jó algoritmusa a legrosszabb esetben nem optimális. (Ezt könnyen ellenőrizhetjük, pl. n = 12–re). Sőt, Reingoldék az algoritmus legrosszabb eseti lépésszámát egyáltalán nem tudták kiszámítani. (Persze az átlagos esetre sincs pontos lépéssszámunk). Kérdés, hogy létezik-e egyáltalán olyan algoritmus, amely mindkét esetben optimális. Vagy legalább olyan, amelyik a legrosszabb esetben optimális, és az átlagos esetben O(log n)–re megközelíti az optimumot. (Az előbbi probléma elég nehéznek tűnik, hiszen egyelőre még olyan algoritmust sem ismerünk, amelyik az átlagos esetben optimális, sőt az optimumot sem tudjuk). Ilyen algoritmus keresése során akadhatunk az alábbira:

Algoritmus:

Tekintsük az (S–W)’–átfogalmazás M állásait, és a belőlük alkotott T bináris fát. Tegyük fel, — ugyanúgy, mint a 3.19. tételben — hogy az M állás (⋆) alakú.

Tekintsük most is a legkisebb i-t melyre m_{i} ; m_{i+1} páratlan. Ha m_{1} + m_{2} > ∑_{j=3}^{k} m_{j},

akkor hasonlítsuk össze az első két kupacot, különben pedig az i. és az (i + 1). kupacot.

Alonso, Reingold és Schott sejtése szerint ez az algoritmus a legrosszabb esetben optimális, és az átlagos esetben legfeljebb O(log n)–nel tér el az optimumtól. Ezt eddig sem bizonyítani, sem cáfolni nem sikerült. n ≤ 52–re a legrosszabb eseti bonyolultsága optimális. Az átlagos esetben n ≤ 20–ra optimális, de pl. n = 52–re nem.

Köszönetnyilvánítás

Szeretném köszönetemet kifejezni témavezetőmnek, Katona Gyulának, aki munkám során ellátott a szükséges irodalommal és szakmai jótanácsokkal. Köszönettel tartozom még Szalkai Ákosnak, Hídvégi Zoltánnak és Fleiner Balázsnak a Latex programcsomag használatában nyújtott értékes segítségükért.

Irodalom

[1] M.Aigner: Combinatorial Search, John Wiley, Chichester and Teubner, Stuttgart, 1988

[2] l. Alonso, E.M. Reingold and R. Schott: Determining the majority, Information Processing Letters, Elsevier, Amsterdam 47 (1993), pp. 253– 255.

[3] l. Alonso, E.M. Reingold and R. Schott: Average–case complexity of determining the majority, SIAM J. Comput. 1995.

[4] B. Bollobás: Extremal Graph Theory, Academic Press, 1978

[5] L.L. Campbell: Note on the connection between search theory and coding theory, Proc. Colloq. on Information Theory (A. Rényi ed.), János Bolyai Mathematical Society, Budapest, 1968

[6] M.J. Fisher and S.L. Salzberg: Finding a majority among n votes, Journal of Algorithms, 3 (1982) pp. 143–152.

[7] D. Gries and J. Misra:Finding repeated elements, Science of Computer Programming 2 (1982) pp. 143–152.

[8] D.A. Huffman: A method for the construction of minimum redundancy codes, Proc. I.R.E. 40 (1952)

[9] G. Katona: On Separating Systems of a Finite Set, Journal of Combinatorial Theory 1 (1966) pp. 174–194.

[10] G. Katona: Combinatorial Search Problems, Survey of Combinatorial Theory, ed. by J.N. Srivastava et al. , North–Holland, Amsterdam, 1973 pp. 285–308.

[11] G. Katona: Rényi and the combinatorial search problems, Stud. Sci. Math. Hung. 26 (1991) pp. 363–378.

[12] G. Katona and M.A. Lee: Some remarks on the construction of optimal codes, Acta Math. Acad. Sci. Hung. 1973

[13] C. Picard: Theorie de Questionnaires, Gauthier–Villars, Paris

[14] M.E. Saks and M. Werman: On computing the majority by comparisons, Combinatorica 11 (1991) pp. 383–387.

[15] M. Sandelius: On an optimal search procedure, American Mathematical Monthly 68 (1961) pp. 138–154.

[16] A. Sebő: Sequential search using question–sets with bounded intersections, J. Statist. Plann. Inference 7 (1982/83) pp. 139–150.

[17] M. Sobel: Group–testing to classify efficiently all defectives in a binomial sample, Information and Decision Processes (R.E. Machol ed.), McGraw– Hill, New York, 1960 pp. 127–161.

[18] M. Sobel: A characterization of binary codes that correspond to a class of group–testing procedures, Tech. Rept. No.148 , Dept. of Statistics, University of Minnesota, 1970

[19] H. Steinhaus: Mathematical Snapshots, Oxford University Press, New York, 1950

[20] I. Wegener: On separating systems whose elements are sets of at most k elements, Discrete Math. 28 (1979) pp. 219–222.

[21] S. Zimmerman: An optimal search procedure, American Mathematical Monthly 66 (1959) pp. 690–693.