Úloha 1.u4: Medián dvou množin (4 b)

Zadáno v čísle 24.1.

Řešeno v čísle 24.3.

Zadání

Z hromádky kartiček očíslovaných od 1 do $2^ k$ jsem si vybral $m$ kousků, můj kamarád si poté vylosoval svých $n$ kousků. Chtěli bychom zjistit medián čísel1 na všech našich kartičkách, ale nevíme, jaká čísla si vylosoval ten druhý. Jak máme postupovat, abychom si mezi sebou museli pro zjištění mediánu předat co nejméně bitů informace? Průběh výměny informací si dohodneme předem, tj. můžeme se například dohodnout, že nejdřív já pošlu své nejmenší číslo, pak kamarád pošle svoje nejmenší číslo atd.


1) Medián z čísel $a_1$, $a_2$, …, $a_ n$ je takové $a_ i$, že skončí přesně uprostřed, pokud čísla seřadíme podle velikosti. Je-li $n$ sudé, pak jsou „prostřední“ prvky dva a medián je jejich průměr. Tedy medián z čísel 1, 4, 2, 5, 1 je 2, medián z čísel 1, 4, 2, 5 je $(4+2)/2 = 3$.

Řešení

Na úvod si dovolím napsat něco málo o samotné úloze. Tato úloha pochází z odvětví teoretické informatiky zvaného komunikační složitost. Ta se zabývá právě tím, jak ve více lidech (obvykle ve dvou) spočítat nějakou zajímavou věc, když každý má jen část vstupních dat a když přitom chceme komunikovat co nejméně. Komunikační složitost hraje v současné informatice poměrně důležitou roli – jde totiž o jeden z mála nástrojů, pomocí kterých umíme o některých problémech dokázat, že pro ně neexistují „lepší“ algoritmy.

A teď už k samotnému řešení. Jak bývá v informatice zvykem, budeme se snažit o řešení, které je nejlepší jen asymptoticky1 a nebudeme vše dopočítávat přesně.

Začneme s nejjednodušším možným řešením. Já si od kamaráda nechám poslat všech jeho $n$ čísel – díky tomu mohu spočítat medián a ten pošlu zpět kamarádovi. Kolik bitů informace tak přeneseme? Inu, přeneseme celkem $n+1$ čísel. Čísla jsou z intervalu 1 až $2^ k$ – na reprezentaci čísla nám tak stačí $k$ bitů (čísla budeme přenášet zmenšená o jedničku)2. Přeneseme tedy $(n+1)k \in \mathcal{O}(nk)$ bitů.

To ale samozřejmě není nejefektivnější postup. K navrhnutí efektivnějšího protokolu využijeme jeden klíčový trik. Problém si trochu zobecníme – nebudeme hledat medián, ale $d$-tý největší prvek. Medián není nic jiného než $(\left(n+m+1)/2\right)$-tý největší prvek (pro $n+m$ liché), nebo aritmetický průměr $(\left(n+m)/2\right)$-tého a $(\left(n+m+2)/2\right)$-tého největšího prvku, pokud tedy umíme najít obecně $d$-tý největší prvek, umíme najít i medián.

Náš trik bude podobný jako ve známém algoritmu pro nalezení mediánu v lineárním čase (pomocí mediánů pětic). Cílem bude se v každé fázi zbavit části prvků (konkrétně alespoň poloviny prvků jednoho z hráčů). To uděláme následovně: Já pošlu kamarádovi medián svých prvků a on mi na oplátku pošle informaci o tom, zda je můj medián větší než ten jeho. Co z toho dokážeme zjistit? Inu, označme si můj medián jako $M$, kamarádův medián jako $N$, dále množinu mých prvků větších než $M$ jako $G_ M$ a množinu mých prvků menších než $M$ jako $L_ M$, analogicky množina kamarádových prvků větších než $N$ bude $G_ N$ a menších než $N$ bude $L_ N$. Ještě si jako $S$ označíme posloupnost všech čísel (mých a kamarádových) seřazenou sestupně.

Nyní předpokládejme, že $M$ je větší než $N$ (opačný případ funguje analogicky). Potom určitě můžeme říct, že prvky z $G_ M$ se nachází někde v první polovině $S$. Zjevně všechny prvky z $G_ M$ jsou v $S$ před $M$ a před vším z $L_ M$ – to je alespoň $m/2$ čísel, která jsou v $S$ za $G_ M$. Ale zároveň je $M$ větší než $N$, a tudíž je $M$ větší než všechny prvky z $L_ N$. Z toho ale plyne, že všechny prvky z $G_ M$ jsou v $S$ před $N$ a $L_ N$, což je dalších alespoň $n/2$ čísel. Tudíž za prvky z $G_ M$ je v $S$ alespoň $(m+n)/2$ dalších prvků (neboť moje a kamarádova posloupnost neobsahuje stejné číslo). Pro lepší představu je celá situace znázorněna na Obrázku 1.

Obrázek 1: Schéma nerovností v mojí a kamarádově posloupnosti po poslání mediánu – nahoře je moje posloupnost, dole kamarádova.

Co z toho můžeme usoudit o hledaném $d$-tém největším prvku? Pokud je $d \ge (m+n)/2$, tedy hledaný prvek je ve druhé polovině $S$, víme, že to není žádný z prvků $G_ M$. Můžeme tedy celé $G_ M$ zahodit a dále hledat jen $(d-|G_ M|)$-tý největší prvek. Podobný argument můžeme použít pro $d < (m+n)/2$, jen s tím rozdílem, že tentokrát můžeme zahodit prvky z $L_ N$ a dále hledat $d$-tý největší prvek.

A kdy skončíme? Inu, když má jeden z hráčů už dostatečně málo prvků, řekněme dva, tak prostě pošle tomu druhému své prvky a jeho protějšek už triviálně spočítá medián3.

A kolik informace přeneseme? V každé fázi komunikace4 přeneseme jedno $k$-bitové číslo (medián) a jeden bit navíc, který signalizuje, zda je můj medián větší než ten kamarádův. Jedinou výjimkou je poslední fáze, kdy přenesme až tři čísla – dvě za posloupnost jednoho z hráčů a jedno za výsledný medián. Tedy celkem $\mathcal{O}(k)$ bitů na fázi. A kolik bude fází? Pro jednoduchost předpokládejme, že $m \ge n$. V každé fázi jeden z hráčů zmenší počet svých prvků na polovinu – nemůže tedy proběhnout více než $(\log m + \log n)\in \mathcal{O}(\log m)$ fází. Celkem tedy přeneseme $\mathcal{O}(k\log m)$ bitů.

Algoritmus přenášející tolik bitů informace stačil na plný počet bodů – byť lze vytvořit i lepší. Spousta z vás použila algoritmus, který přenese jen $\mathcal{O}(k\log n)$ bitů ($n\le m$). Ten funguje v podstatě jako výše popsaný algoritmus, jen s tím rozdílem, že v každé fázi zahazují prvky oba hráči – je ale třeba dát pozor, aby se vždy zahodil stejný počet prvků před a za mediánem.

Na závěr ještě zmíníme, že ani $\mathcal{O}(k\log n)$ není optimální řešení. Existuje algoritmus, kterému stačí přenést jen $\mathcal{O}(k)$ bitů.

$\mathcal{O}(N)$dra


1) To, že přeneseme $\mathcal{O}(n^2)$ bitů, znamená, že můžeme přenést třeba $10n^2 + 5n$ bitů (protože nejvýraznější člen je právě $n^2$), ale už ne třeba $0,0001n^3$ bitů (protože pro dostatečně velké $n$ stejně $0,0001n^3$ přeroste $n^2$). Podrobněji je vše vysvětleno třeba zde: http://ksp.mff.cuni.cz/kucharky/slozitost/.

2) Čísla budeme reprezentovat jejich zápisem ve dvojkové soustavě doplněným o případné nuly na začátku tak, aby měl zápis přesně $k$ cifer – bitů.

3) Rozpoznání konce nemusíme v komunikaci nijak řešit – oba hráči na začátku ví, kolik má jejich protějšek čísel, a z poslaných informací mohou vždy určit, kolik čísel v daném kroku jejich protějšek zahodil. Tedy oba poznají, kdy se má přejít do „finální fáze“.

4) Fází máme na mysli celou část komunikace začínající tím, že já pošlu kamarádovi svůj medián, a končící tím, že jeden z nás zahodí část svých prvků.