Disjunktné párovanie

S knihou sa nenudím ani počas niekoľkohodinového čakania a ak aj nemám knihu, nie je problém sa príjemne zabaviť - len tak v mysli. Minule ma počas dlhej cesty autom (samozrejme keď som nešoféroval!) napadla takáto úloha:

Predpokladajme, že v rovine máme párny počet bodov. Zdá sa intuitívne zrejmé, že tieto body môžeme pospájať úsečkami do dvojíc tak, aby sa žiadne dve z týchto úsečiek nepretínali. Vedeli by ste vymyslieť úplne jasný dôkaz, že to je naozaj tak? A vedeli by ste popísať nejaký efektívny algoritmus, ktorý také párovanie bodov nájde?

Najmenšia vzdialenosť dvoch bodov

V práci môjho bakalára sa vyskytol nasledovný okrajový, ale celkom zaujímavý algoritmický problém:

Vstupom je n vektorov x₁,...,x_n v m-rozmernom Euklidovskom priestore. Cieľom je zistiť Euklidovskú vzdialenosť dvoch najbližších bodov, t.j. vypočítať hodnotu

Otázkou je, či je možné skonštruovať asymptoticky rýchlejší algoritmus, než výpočet vzdialeností medzi všetkými n(n-1)/2 dvojicami rôznych bodov.

Poznámka: Sám neviem na tento problém odpovedať v plnej všeobecnosti (vlastne len pre m=1), takže neviem ani odhadnúť, aký je vo všeobecnosti náročný. Naviac, som si takmer istý, že tomuto jednoducho formulovanému problému sa už ľudia venovali, takže vyriešený už asi je. To nám však nebráni, aby sme sa nad ním zamysleli.

Vymyslené hádzanie II

Základný kurz z počítačovej štatistiky som tento semester učil iba druhýkrát a preto si ho stále ešte len vylaďujem. Napadlo ma, že by som ako súčasť hodnotenia predmetu mohol experimentálne zaviesť novinku: domácu úlohu, v ktorej si študenti vyskúšajú nielen to, ako dáta štatisticky spracovávať, ale aj čo obnáša ich získavanie. Vymyslel som teda niekoľko zadaní, v ktorých si študenti musia vytvoriť vlastné dátové súbory z veľmi jednoduchých, no úplne reálnych experimentov, alebo prieskumov. Naviac, experimenty sú navrhnuté tak, aby ich moji štatistici-začiatočníci vedeli spracovať pomocou obmedzeného repertoáru techník, ku ktorým sa počas semestra dostaneme. V tomto príspevku okomentujem výsledky jedného z týchto experimentov.

Mince. V tejto úlohe bolo potrebné najprv "mentálne" simulovať náhodnosť; presnejšie, vysloviť postupnosť symbolov H (hlava) a Z (znak) s cieľom čo najvernejšie napodobňovať výsledky nezávislých hodov mincou a potom rôznymi štatistickými testami otestovať hypotézu, že daná postupnosť zodpovedá reálnemu hádzaniu. Inými slovami, kladieme si otázku, či vie človek mentálne napodobniť náhodnosť, alebo sa nutne prejavia psychologické faktory, ktoré umožnia odhaliť, že sa nejedná o skutočný generátor náhodnosti.

Mentálne simulovanie hádzania mincou robili dve študentky; každá z nich nadiktovala sériu 240 výsledkov. Prekvapivo, jedna zo študentiek vygenerovala tak dokonalú náhodnú postupnosť, že použité testy na nej neodhalili absolútne žiadne anomálie. (A aj pre druhú študentku len jeden test "potvrdil", že sa nejedná o pravú náhodnosť. Slovo potvrdil som dal do úvodzoviek, pretože štatistická analýza nám nikdy neumožňuje robiť uzávery s absolútnou istotou.)

Dievčatá si (aj) za túto úlohu odo mňa odniesli A-čko a ja som si z tejto úlohy odniesol niekoľko poznatkov. Predovšetkým, pod ťarchou experimentálnych dôkazov musím zmierniť moju istotu, s ktorou som kedysi napísal príspevok "Vymyslené hádzanie".

Poznámky: Obrázok vľavo hore je z môjho predmetu "simulačné metódy", ale na "počítačovej štatistike" to vyzerá veľmi podobne. Inak ak budete mať záujem, môžem okomentovať aj výsledky ďalších úloh.