Záhadné písmená

Hint: Ploché myslenie Vám nepomôže.

Najkratšie prepojenie

Máme n+1 miest, pričom n z nich leží na vrcholoch pravidelného n-uholníka vpísaného do jednotkovej kružnice a jedno mesto leží v počiatku súradnicovej sústavy. Chceme vybudovať čo najkratšiu cestnú sieť tak, aby sa po nej dalo prejsť z každého mesta do každého iného mesta. Pre n=3 samozrejme nič nenašpekulujeme a jednoducho spojíme každé okrajové mesto priamou cestou s centrálnym mestom, ako je znázornené na obrázku. Ako by sme však vybudovali najkratšiu cestnú sieť pre n=4 (t.j. celkovo päť miest) a pre n=6 (t.j. celkovo sedem miest)?

Náhodné bludiská

Podarí sa Vám vymyslieť spôsob, akým je možné algoritmicky generovať náhodné bludiská? Môžete sa nechať inšpirovať nasledovnými obrázkami. Ak Vás "náhodné bludiská" zaujmú, prezradím Vám, akú metódu som použil ja.

Torricelliho cesty

Tri mestá A,B,C je potrebné spojiť cestami tak, aby sa po nich dalo prejsť z každého mesta do každého iného mesta. Ako to realizovať, aby bol súčet dĺžok týchto ciest čo najmenší?

Obrázok vľavo pochopiteľne neznázorňuje optimálne riešenie. Ak Vás tento slávny problém zaujme, napíšeme si o ňom viac.

Poznámka 18.2.: Táto úloha nie je úplne triviálna. Nebojte sa pri riešení použiť silnejší matematický aparát, napríklad diferenciálny počet funkcií dvoch premenných. Na druhej strane, bolo by veľmi pekné, keby niekto z Vás našiel elementárne riešenie (presnejšie rigorózny dôkaz optimality daného riešenia) s použitím stredoškolskej matematiky.

Sci-fi anketa

"Two possibilities exist: Either we are alone in the Universe or we are not. Both are equally terrifying." Arthur C. Clarke.

(Poznámka: Anketa je už uzavretá; výsledky si môžete pozrieť na konci príspevku.)

Napadlo ma, že by sme si opäť mohli dať hĺbavejšiu anketu - tentokrát o Vašich názoroch na budúcnosť ľudstva.

Moje výroky sú nasledovné:

1. Ľudstvu sa podarí prekonať ekologické hrozby.


2. Človek vytvorí umelú inteligenciu, ktorá bude disponovať vedomím.


3. Ľudia vytvoria kolónie mimo našej slnečnej sústavy.


4. Ľudskí jedinci v budúcnosti dosiahnu stav praktickej nesmrteľnosti.


5. Ľudia sa v budúcnosti stretnú so životom mimozemského pôvodu.

Vo formulári v pravom stĺpci blogu zaškrtnite všetky tie tvrdenia, ktoré považujte za skôr platné ako neplatné. Pozor! Každé políčko, ktoré nezaškrtnete, sa počíta akoby ste hlasovali za to, že dané tvrdenie skôr neplatí.

Samozrejme, pravda nie je to, čo by sme mohli uzákoniť hlasovaním, najmä keď sa jedná o otázky, na ktoré v súčasnosti nevie vyčerpávajúco odpovedať vôbec nikto. Niekto by tiež mohol celkom oprávnene namietať, že sa predsa nemôže vyjadriť k niečomu, kde sa nemá o čo oprieť, podobne, ako na otázku "What is your gut feeling?" odpovedal Carl Sagan slávnym výrokom "I try not to think with my gut".

Ale táto anketa má za cieľ len Vás zabaviť a prípadne primäť k zamysleniu. So do not be afraid to think with your gut. :-)

Deformovaná kocka

Chceme sa hrať človeče nehnevaj sa, ale máme k dispozícii iba deformovanú (poprípade zle vyváženú) kocku, pri ktorej nevieme, s akými pravdepodobnosťami padajú jednotlivé hodnoty 1,...,6. Človeče nehnevaj sa s takouto kockou by síce mohlo byť zaujímavé ozvláštnenie nudnej hry, ale povedzme, že nám ide o presné dodržanie klasického typu náhodnosti. Naša otázka teda znie:

Existuje nejaký spôsob, ako len pomocou hádzania deformovanou kockou "nasimulovať" hádzanie normálnou kockou, t.j. výber každej hodnoty 1,...,6 s pravdepodobnosťou presne 1/6?

Poznámka: Táto úloha má veľmi blízko skutočným problémom, ktoré sa riešia pri aplikácii hardwarových generátorov náhodných čísiel. (Napadla ma počas prípravy na zajtrajšiu prednášku zo simulačných metód.) V prípade niektorých generátorov totiž nepoznáme úplne presne špecifiká náhodnosti, ktorú produkujú, avšak pre aplikácie potrebujeme mať zdroj náhodnosti so známym pravdepodobnostným rozdelením.

Vyhodnotenie ankety 'O čom by ste chceli príspevok'

Som príjemne prekvapený, že na prvom mieste skončil Banachov-Tarskeho paradox, čo je síce enormne zaujímavá, no nie až taká populárna téma. Jedna z mnohých formulácií tohoto paradoxu je takáto: existuje rozklad (rozbitie) gule s polomerom 1 na konečne veľa podmnožín, z ktorých sa len rotáciou a posunutím dajú poskladať dve (plné) gule, obe opäť s polomerom 1. Ako je to možné? Dopočul som sa, že už ku mne cestuje kniha "The Pea and the Sun", takže sa máme na čo tešiť.

Tiež si postupne pripravím príspevok o umelých neurónových sieťach, hoci na túto problematiku sú u nás na matfyze iní machri. Keďže toto je extrémne široká oblasť, vyberiem si z nej asi len nejakú malú špeciálnu podoblasť, ktorá má bližšie k mojej špecializácii. Možno podiskutujeme o starých a relatívne jednoduchých, ale metodologicky stále základných "dopredných" sieťach.

Do tretice, rád napíšem príspevok o výhodách a nevýhodách simulovaného žíhania, čo je populárna metóda na optimalizáciu mnohorozmerných funkcií. A možno bude aj video z akadémie trojstenu :-)

Poznámka 23.2.: Ukazuje sa, že letný semester budem mať obzvlášť nabitý, takže tieto článočky vidím tak na jún. Stay tuned. :)

Zápalková klasika

Posledná úloha bola dosť náročná, takže tentokrát zápalková oddychovka. Presuňte dve (a len dve) zápalky tak, aby z piatich jednotkových štvorcov na obrázku vznikli štyri jednotkové štvorce. Pritom vo výslednom obrazci musí byť každá zápalka súčasťou nejakého jednotkového štvorca.

Výsledok môžete zapísať pomocou koordinát podobne ako v šachu: Napríklad D3-E2, eIII-fII vytvorí síce štyri štvorce, avšak jeden z nich nie je jednotkový, takže toto nie je správne riešenie.

V najlepšom treba skončiť

Isté kasíno zaviedlo nasledovnú hru: Krupier postupne hádže mincou, až pokým hráč nepovie "stop!", čím hru ukončí. Hráč však musí hru ukončiť najneskôr po desiatom hode. Akonáhle hráč zahlási "stop!", dostane ako výhru toľko dolárov, v koľkých posledných po sebe nasledujúcich hodoch padol znak. Napríklad: ZHHZZZZ[stop!] = výhra 4 doláre, ZHZHZZ[stop!] = výhra 2 doláre, ZZHZZHZHZ[stop!] = výhra 1 dolár, alebo ZZHZZHZHHH[stop!] = výhra 0 dolárov. Aká je v tejto hre optimálna stratégia hráča, t.j. stratégia, ktorá hráčovi maximalizuje očakávanú výšku výhry?

Poznámka 5.2.: Po rozhovore s kolegom som dospel k názoru, že by som mal uviesť toto upozornenie: Nehľadajte úžasnú a jednoduchú fintu, ako tento príklad plne vyriešiť za päť minút; zdá sa, že najrýchlejšia metóda riešenia si vyžaduje napísať malý programík pre počítač. Takže riešením tohoto príkladu môže byť algoritmus, ako sa pomocou počítača dopracovať k (nejakej) optimálnej stratégii hráča. A čím bude ten algoritmus rýchlejší/jednoduchší, tým lepšie riešenie ste našli.

Poznámky: Obrázky doláru pochádzajú zo stránok random.org, kde si napríklad môžete nechať vygenerovať náhodné hody mincou, alebo kockou, pričom v pozadí stojí generátor "pravej" náhodnosti založený na atmosferickom šume a nie obvykle používané generátory pseudonáhodných čísiel. A samozrejme - spomínané kasíno je len moja fikcia :-)

Ako sťažiť odpisovanie

Dajú sa každému zo siedmich študentov priradiť na riešenie práve tri zo siedmich rôznych príkladov tak, aby každý príklad dostali práve traja študenti a aby žiadna dvojica študentov nemala viac než jeden spoločný príklad?