Olympiáda
v informatike

 

Ročenky

Všetky materiály súvisiace s Olympiádou v informatike bývali do roku 2014 každoročne spracované do prehľadnej ročenky. Tieto vyšli aj v tlačenej podobe a väčšinou sa ešte niekde na matfyze povaľuje pár výtlačkov pre záujemcov. Na tejto stránke si môžete stiahnuť ich elektronickú verziu.

 

Obálky ročeniek

Na obálkach ročeniek sú zväčša celkom zaujímavé veci. Ak by ste o nich chceli vedieť viac, tu sú ich popisy:
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.