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?

Júnové odkazy

Záverečný zhon semestra (odovzdávanie bakalárskych a diplomových prác, posudky, obhajoby, skúšanie najrôznejšieho druhu) sa skončil a dovolenku v Taliansku mám už tiež za sebou, takže sa môžem opäť vrátiť k častejšiemu písaniu príspevkov na QED. Ani tento mesiac nevynechám prehľad nových zaujímavých odkazov.

V prvom rade by som chcel v komunite nadšených blogerov - matematikov privítať Petra Richtárika, ktorý si po absolvovaní našej fakulty spravil doktorát na Cornellovej univerzite a teraz pôsobí v Belgicku; veľmi Vám odporúčam pozrieť si jeho nový blog. Keď sme už pri tom, pekné blogy majú aj niektorí iní súčasní, alebo bývalí matfyzáci; pozrite si odkazy v pravom stĺpci môjho blogu. Samozrejme, najväčší zhluk matfyzáckych blogov je na blog.matfyz.sk. Neviete náhodou o ďalších? A nechcete si založiť blog aj Vy?

Určite si tiež nezabudnite popozerať videá na stránke TED talks, na ktorú ma upozornil práve Peťov blog. Vypočuť si môžete napríklad názory vynálezcu a futurológa Raya Kurzweila, proponenta teórie technologickej singularity, ďalej mladého amerického profesora ekonómie Sevena Levitta, autora slávnej a kontroverznej knihy Freakonomics, alebo anglickej spisovateľky Susan Blackmoreovej, autorky nemenej slávnej a nemenej kontroverznej knihy The meme machine a tak ďalej. Videí na TED talks je veľmi veľa a ak nájdete nejaké, ktoré Vás obzvlášť zaujali, napíšte nám o nich, prosím, do komentárov k tomuto príspevku.

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. Po prvé, pod ťarchou experimentálnych dôkazov musím zmierniť moju istotu, s ktorou som kedysi napísal príspevok "Vymyslené hádzanie". A po druhé, na budúci rok by bolo zaujímavé vyskúšať to isté s chlapcami ;-)

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.