Matematická olympiáda – kategorie P

ústředního kola 46. ročníku

Pavel Töpfer, MFF UK Praha

Letošní celostátní kolo MO kategorie P (programování) se konalo v Jevíčku ve dnech 23.-26.4.1997. Soutěže se zúčastnilo všech 30 pozvaných nejúspěšnějších řešitelů oblastních kol MO-P. Největší zastoupení ze všech oblastí měla již tradičně Praha (devět studentů z šesti různých gymnázií), z jednotlivých škol se mohlo největší účastí pochlubit gymnázium na tř. Kpt. Jaroše v Brně (čtyři účastníci).

Po organizační stránce celostátní kolo připravili a zabezpečovali pracovníci gymnázia a domova mládeže v Jevíčku, kteří mají s pořádáním podobných akcí velké zkušenosti. Odborného zajištění soutěže (příprava úloh, vzorových řešení, opravování, vyhodnocovací software atd.) se ujali pracovníci pražského centra MO kategorie P z Matematicko-fyzikální fakulty Univerzity Karlovy v Praze. Velký kus práce při opravování úloh odvedli zejména studenti informatiky z MFF UK, kteří sami patřili v minulých letech k nejlepším řešitelům této soutěže a reprezentovali nás také na mezinárodních programátorských soutěžích středoškoláků.

V prvním soutěžním dnu řešili soutěžící písemně tři teoretické úlohy. Ve dvou z nich bylo úkolem nalézt vhodný algoritmus řešení zadaného problému. Při jejich hodnocení se kladl důraz nejen na správnost nalezeného algoritmu, ale také na jeho efektivitu, popis a na zdůvodnění správnosti zvoleného postupu. Třetí úloha vycházela z modelu kombinačních obvodů, se kterým se soutěžící seznámili již v domácím a oblastním kole. Nyní dostali za úkol sestavit ze základních hradel typu NAND, NOR a NOT tři konkrétní kombinační obvody. Při hodnocení se vedle správnosti navržených obvodů přihlíželo také k tomu, jak přehledně jsou obvody sestaveny a kolik hradel je k jejich výstavbě zapotřebí.

Druhý soutěžní den probíhal na gymnáziu v učebnách výpočetní techniky. Každý soutěžící dostal za úkol vyřešit pomocí přiděleného osobního počítače dvě praktické úlohy. V jednom případě šlo o grafový problém určení maximálního párování, druhou praktickou úlohou byla desková hra. Zajímavostí této druhé úlohy bylo, že výsledný program měl hrát hru s protihráčem, který byl předem realizován pomocí programové knihovny. Jednu takovou knihovnu dostali soutěžící k dispozici pro potřeby ladění, s jinou (lépe hrající) knihovnou pak byly vytvořené programy testovány. Správnost odevzdaných programů byla vyhodnocována zcela automaticky pomocí vyhodnocovacího programu a připravené sady testovacích dat. Provádění jednotlivých testů přitom bylo spojeno se stanovenými časovými limity. Tím se odlišilo hodnocení různých programů i z hlediska efektivity.

Každá z úloh byla hodnocena maximálně 10 body. Poměrně nízká celková hodnocení svědčí o tom, že všechny letošní soutěžní úlohy byly poměrně obtížné. Jen čtyři nejúspěšnější řešitelé získali alespoň polovinu z možných padesáti bodů. Celkem 16 řešitelů bylo vyhlášeno úspěšnými řešiteli a z nich prvních šest vítězi celostátního kola 46. ročníku matematické olympiády - kategorie P.

Stejně jako v minulých letech, také letos dostanou nejlepší řešitelé příležitost reprezentovat Českou Republiku na mezinárodních programátorských olympiádách studentů středních škol. Celosvětová olympiáda v informatice se bude letos konat až na podzim v Kapském Městě v Jihoafrické republice, obdobná středoevropská soutěž se uskuteční o prázdninách v Polsku ve městě Nowy Sacz. O pořádání mezinárodní olympiády v informatice je ve světě stále velký zájem, následující ročníky mají již na několik let dopředu zamluveno Portugalsko, Turecko a Čína. Do soutěže se také zapojuje stále více zemí, letos pořadatelé očekávají rekordní účast asi 60 reprezentačních družstev z celého světa.