 |
Na obálke ročenky je vyznačených 114 bodov a tzv. Hamiltonovská kružnica – teda
najkratšia cesta, ktorá ich postupne navštívi všetky a vráti sa na miesto odkiaľ
začínala. Ide o veľmi dôležitý optimalizačný problém, ktorý súvisí s mnohými
pre prax zaujímavými úlohami. Zároveň je však už dobre preskúmaný z teoretického
hľadiska – lenže bohužiaľ s negatívnym výsledkom: vieme o ňom dokázať, že je
veľmi ťažký. Nepoznáme žiaden polynomiálny algoritmus, ktorý by túto úlohu riešil,
a máme dobré dôvody domnievať sa, že taký algoritmus ani neexistuje.
Aj napriek tomu, že sme použili jeden z najefektívnejších známych všeobecných algoritmov
(postupnú optimalizáciu pomocou celočíselného lineárneho programovania), trval
výpočet riešenia, ktoré vidíte na obálke, približne dva dni.
|
 |
Na obálke ročenky je tzv. oblak slov (word cloud) tvorený najčastejšie sa vyskytujúcimi slovami
z textu minulej ročenky. Veľkosť písma približne zodpovedá logaritmu počtu
výskytov daného slova.
Oblaky slov síce asi nemajú žiadne prísne vedecké využitie, ide však o veľmi
účinnú formu vizualizácie dát – človek dokáže v priebehu niekoľkých
sekúnd pochopiť podstatnú časť ich zloženia.
|
 |
Na obálke ročenky je dlhý reťazec textu. Ak sa ho pokúsite prečítať,
zistíte, že síce zmysel príliš nedáva, ale čítať sa dá a znie skoro ako slovenčina.
Ide o výstup z tzv. Markovovského zdroja.
Pre každý znak textu závisia jeho pravdepodobnosti od predchádzajúcich troch znakov.
(Použité pravdepodobnosti sú získané z textu 26. ročenky OI.)
Markovovské zdroje majú svoje využitie napr. v kompresii textu, kryptoanalýze,
bioinformatike a mnohých ďalších oblastiach.
|
 |
Okolo klasických olympiádnych kociek sú dva rôzne Steinerovské stromy.
Steinerovský strom je optimálnym riešením úlohy: "V rovine sú mestá, postav cestnú sieť, ktorá ich všetky pospája."
Všimnite si, že na rozdiel od najlacnejšej kostry je povolené aj vytvoriť novú križovatku mimo miest.
V ľavej časti obrázka je pravouhlý Steinerovský strom: optimálne riešenie tej istej úlohy, ak máme navyše obmedzenie, že
každá cesta musí viesť rovnobežne s niektorou zo súradnicových osí.
|
 |
Na pozadí je Voronoiov diagram: prázdne krúžky sú krčmy, čiary
delia rovinu na oblasti podľa toho, ku ktorej krčme to máme najbližšie. Ide o veľmi užitočnú štruktúru, využívanú vo výpočtovej geometrii.
|
 |
Čiary a ich priesečníky na pozadí sú vygenerované pomocou programu riešiaceho jednu z úloh celoštátneho kola.
|
 |
Na pozadí je niekoľko obrázkov zo zadaní dotyčného ročníka a jednoduché makro v C++, ktorým sa dá iterovať cez skoro ľubovoľnú dátovú štruktúru z
STL.
|
 |
Na pozadí sú úryvky z programov pre Minského registrový stroj.
|
 |
Fraktál: vhodne upravená Mandelbrotova množina.
|
 |
Obrázok je grafickým znázornením jednoduchého kvadratického sita. Skúsený riešiteľ MO si určite ľahko dokáže, že nevyškrtnuté
krúžky na x-ovej osi zodpovedajú práve všetkým prvočíslam.
|
 |
V hmle miznúci Śierpinského štvorsten: fraktál, ktorý sa skladá zo štyroch kópií seba samého.
|
 |
Toto nie sú dva podobné uzly, toto sú dva mierne pootočené pohľady na ten istý uzol. Ak zvládnete správne rozostriť oči
a každým sa pozerať na jeden z nich, uvidíte tento uzol v 3D. (Rovnaká technika sa používa pri pozeraní na stereogramy.)
|
 |
Graf funkcie dvoch premenných, pravdepodobne vhodne naškálovaná variácia na sin(sqrt(x^2+y^2))/sqrt(x^2+y^2).
|
 |
"Escherovské" trojrozmerné bludisko.
|
 |
Po obvode sú jednotlivé dieliky stavebnice podobnej kocke Soma. V strede je z nich postavený koník.
Jedna z úloh Medzinárodnej olympiády v informatike v roku 2000 sa týkala práve tejto stavebnice.
|
 |
Olympijské "kruhy" tvorené rôznymi fázami skladania štvorstenu z niekoľkých dielikov. Ide o obrázky z úlohy, ktorá sa vyskytla
v jednom zo skorších ročníkov MO.
|
