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.

π

Ako ste možno zaregistrovali, včera prebehla médiami informácia o tom, že sa istému 13 ročnému žiakovi z Banskej Bystrice podarilo zapamätať si číslo π na 300 desatinných miest, čím vytvoril nový slovenský rekord. Gratulujeme.

Každopádne, najlepšie svetové výkony v tejto "disciplíne" sa pohybujú v úplne iných rádoch. V súvislosti s fenomenálnou pamäťou Vám odporúčam pozrieť si veľmi zaujímavé videá o Danielovi Tammetovi a o Kimovi Peekovi; je ohromujúce, čoho je ich mozog, a možno principiálne aj mozog každého z nás, schopný.

Tento príspevok som však začal písať s cieľom formulovať pre Vás nasledovnú úlohu: Predstavme si, že si budeme musieť zapamätať postupnosť povedzme 15 cifier. Nebudeme si môcť pritom vôbec nič poznačiť, avšak môžeme použiť akúkoľvek mnemotechnickú pomôcku, ktorú si vopred pripravíme (a budeme ju môcť používať ako pri zapamätávaní si, tak aj pri rekonštruovaní danej postupnosti čísiel). Máte nejaké nápady, akú pomôcku by ste si pripravili Vy?

Banachov-Tarskeho paradox: časť 2: úloha

Nech A je kružnica s polomerom 1 a nech B je tiež kružnica s polomerom 1, ktorej však chýba jeden bod (pozri obrázok). Sú množiny A a B zhodne rozložiteľné? T.j., trochu nepresne formulované: Je možné rozbiť A na konečný počet podmnožín, z ktorých len posunutím a rotáciou môžeme poskladať B?

Poznámka: Pojem "zhodne rozložiteľné množiny" sme presne definovali v predchádzajúcom príspevku. Teším sa na Vaše riešenia.

Banachov-Tarskeho paradox: časť 1: formulácia

Toto je prvý v sérii príspevkov, ktorými sa pokúsim ozrejmiť Banachov-Tarskeho paradox, ako som kedysi sľúbil. Čiastočne sa pritom budem držať knihy Leonarda Wapnera "The Pea and the Sun". Na začiatok úplne postačí, keď sa nám podarí pochopiť presné znenie tohoto paradoxu. Potrebujeme k tomu niekoľko matematických definícií na úrovni obtiažnosti nepresahujúcej prvý ročník na matfyze.

Nech Eⁿ je Euklidovský priestor, napríklad priamka (pre n=1), rovina (pre n=2), alebo klasický trojrozmerný priestor (pre n=3). Nech v je vektor v Eⁿ a nech U je matica rotácie typu nxn. Zobrazenie f, ktoré priradí každému bodu x v Eⁿ bod x+v, nazveme translácia (posun) a zobrazenie g, ktoré priradí každému bodu x v Eⁿ bod Ux nazveme rotácia (pootočenie). Ľahko si uvedomíme, že rotáciou v E¹ je len jediné zobrazenie a to identické. Každú rotáciu v E² si môžeme predstaviť ako pootočenie okolo bodu (0,0) a každú rotáciu v E³ si môžeme predstaviť ako pootočenie okolo nejakej priamky prechádzajúcej bodom (0,0,0).

Nech f je posun o vektor v, nech g je rotácia definovaná maticou rotácie U a nech M je nejaká množina v Eⁿ. Transláciou f množiny M nazveme množinu všetkých bodov tvaru x+v, kde x je bod z M a rotáciou množiny M nazveme množinu všetkých bodov tvaru Ux, kde x je bod z M. Ako príklad som na nasledovnom obrázku načrtol modrým transláciu f(M) zelenej množiny M o vektor (2,1) a ružovým rotáciu g(M) množiny M o uhol α=π/4 (t.j. o 45 stupňov).


Rozkladom množiny M nazývame každý systém M₁,...,M_k navzájom disjunktných podmnožín množiny M, ktorých zjednotenie je M. Dve množiny A a B v priestore Eⁿ nazveme zhodne rozložiteľné, ak existuje rozklad A₁,...,A_k množiny A a rozklad B₁,...,B_k množiny B tak, že pre každé i=1,...,k je množina B_i zrotovaná a posunutá množina A_i, t.j. existujú translácie f₁,...,f_k priestoru Eⁿ a rotácie g1,...,gn priestoru Eⁿ, že pre všetky i=1,...,n platí B_i=f(g(A_i)). To, že sú množiny A a B zhodne rozložiteľné, označíme A~B.

Čiže, veľmi voľne povedané, A~B znamená, že A je možné rozbiť na kúsky, z ktorých len posunutím a zrotovaním môžeme poskladať B. Ako príklad som načrtol obrázok dokazujúci A~B pre pravouhlý rovnoramenný trojuholník A (bez jednej odvesny) a štvorec B (bez jednej strany) s rovnakým obsahom ako má A.

Pripomeňme ešte, že pod pojmom guľa v E³ s polomerom r a stredom v bode P rozumieme množinu tých bodov E³, ktorých vzdialenosť od P je menšia, alebo rovná r.

Znenie Banachovho-Tarskeho paradoxu (vo formulácii nazývanej ''pea and the Sun''): Akékoľvek dve gule v E³, nie nutne s rovnakým polomerom, sú zhodne rozložiteľné.


Banachov-Tarskeho paradox je teda (dokázateľne platné) matematické tvrdenie že, voľne povedané, akúkoľvek malú trojrozmernú guľu vieme rozbiť na konečný počet podmnožín, z ktorých len pootočením a posunutím vieme poskladať (plnú) guľu s akokoľvek veľkým polomerom. Vaše prípadné nejasnosti a námietky napíšte do komentárov a ja sa Vám ich pokúsim vysvetliť resp. odmietnuť :)

Tri mince

Na stole sú tri mince: štvrťdolár, poldolár a dolár. Hráč A vlastní jednu z týchto troch mincí a hráč B zvyšné dve. Hráči budú hádzať súčasne všetkými tromi týmito mincami, až pokým aspoň na jednej z nich nepadne hlava. Výsledné skóre pre každého hráča bude rovné súčtu hodnôt tých jeho mincí, na ktorých padne hlava. Hráč, ktorý získa vyššie skóre, vyhráva všetky tri mince. Ktorú mincu by mal vlastniť hráč A, aby bola hra spravodlivá, t.j. aby stredná hodnota zisku každého z hráčov bola 0?

Poznámka: Táto priamočiara, no pekná úloha s prekvapivým riešením pochádza údajne z knihy D.L. Silvermana "Your Move".

Chris Frith: Making up the mind

Kniha významného anglického neurovedca Chrisa Fritha "Making up the Mind" vo mne utvrdzuje už dlhšiu dobu silnejúci pocit, že sme súčasníkmi nového prevratu v chápaní sveta, tichého, ale zásadného; ďalšieho vytriezvenia z iluzórnej samozrejmosti.

Podobne, ako to bolo s teóriou relativity, ktorá nás obrala o jednoduchú predstavu priestoru a času, alebo s kvantovou mechanikou, ktorá nám zrútila prirodzené chápanie kauzality, moderné neurovedy spochybňujú dôveryhodnosť toho, čo vieme sami o sebe; spochybňujú našu pamäť, zmyslové vnímanie, dokonca naše pohnútky a samotnú slobodnú vôľu.

Spomeňme napríklad experimenty Benjamina Libeta, ktoré potvrdzujú, že aktivita mozgu smerujúca k nejakej činnosti je merateľná už podstatne skôr ako nastáva to, čo sa nám javí ako vedomé rozhodnutie túto činnosť vykonať. Ako si výsledok týchto, alebo viacerých iných podobných experimentov vysvetliť? Zdá sa isté, že si musíme podstatným spôsobom upraviť našu predstavu o slobodnej vôli.

Moderné zobrazovacie techniky nás dokonca pripravili o súkromie našich myšlienok; pomocou prístrojov vedci doslova vidia naše predstavy, plány a emócie; zatiaľ len hrubo, ale Pandorina skrinka je už otvorená. Opakovateľné experimenty naznačujú, že naše "ja" je len aspektom epistemického modelu sveta, redukovateľného na základné fyzikálne princípy komunikácie medzi neurónmi. Čím ďalej, tým je ťažšie brániť dualistický pohľad na myseľ, ktorý je spolu so slobodnou vôľou ideovým pilierom najrozšírenejších svetových náboženstiev.

Otázka už neznie, či revolúcia v neurovedách bude mať na náš život nejaký dopad, ale skôr ako sa s novým pohľadom na nás samotných vyrovnáme.

Krátke poznámky a odkazy:

• Pozrite si stránku s fascinujúcimi optickými klamami; aby som uveril, musel som si vyrobiť špeciálne tienítko. Trochu pozorouhodnej frustrácie môžete zažiť pri hľadaní zmien na obrázkoch na tejto stránke demonštrujúcej fenomén "change blindness". Zaujímavé sú aj tieto videá na stránke profesora Richarda Gregoryho.
• O Benjaminovi Libetovi a jeho experimentoch si môžete prečítať zaujímavý článok od Susan Blackmoreovej, verejnosti známej predovšetkým knihou "The Meme Machine".
• K svojej knihe pripravil Chris Frith túto krátku prezentáciu. Ako aj ostatné knihy z mojej malej knižnice, aj túto Vám rád požičiam. Ak Vás problematika neurologického pohľadu na myseľ zaujíma, môžem Vám požičať aj úchvatnú tematicky podobnú knihu Olivera Sacksa "Anthropologist on Mars", alebo menej slávnu, no tiež veľmi zaujímavú knihu Douglasa Tweeda "Microcosms of the Brain".