ACM International Collegiate Programming Contest - http://icpc.baylor.edu/icpc/
- je celosvětová soutěž v programování pořádaná mezinárodní organizací Association for Computing Machinery,
nejstarší počítačovou organizací na světě vůbec existující již od roku
1947. Soutěž je určena studentům vysokých škol po celém světě a probíhá ve dvou
hlavních kolech - nejprve se soutěžící přihlásí do regionálního kola podle
geografické polohy svého státu (například v Evropě je pět regionů).
V našem regionu soutěží Česká
republika, Polsko, Slovensko, Rakousko, Maďarsko a Slovinsko. Nejlepší týmy
z těchto kol postupují do světového finále, které se na různých
místech koná již od roku 1977. Letošní finále bude ve dnech 22.-26.3. v Beverly Hills v Kalifornii. Kromě těchto dvou hlavních kol pořádá ČVUT v Praze ještě před
regionálním kolem české a slovenské přípravné kolo této soutěže s názvem CTU Open
Contest - http://contest.felk.cvut.cz/02prg/
, do kterého se mohou hlásit týmy
z libovolné české či slovenské vysoké školy.
Soutěže se účastní tříčlenné týmy (vedené koučem), které
řeší 5 až 10 úloh. Vlastní soutěž trvá 5 hodin a úlohy jsou zadávány v
angličtině. Hlavním kritériem hodnocení je počet odevzdaných funkčních úloh,
teprve na druhém místě je čas řešení. Řešení se vyhodnocuje plně automaticky,
program je otestován na konkrétních datech. Pokud je jeho výstup správný a
vypočten v časovém limitu, je program přijat. Záleží tedy na funkčnosti
a efektivitě algoritmu. Hodnocení je zcela objektivní. Odevzdaná úloha,
která nevyhověla zadání anebo překročila povolený čas výpočtu, je vrácena a tým
má možnost ji přepracovat a znovu odevzdat. Tým má k dispozici jeden
počítač, programuje se v ANSI C nebo Pascalu a je povolena jakákoliv
literatura. Nesmějí se používat kalkulačky, mobilní telefony, pagery, jiná
komunikační zařízení a vlastní hardware. Podrobnější informace o soutěži
a příklady zadání úloh z minulých let a prostředí pro kontakt zájemců
můžete najít na webové stránce http://www.kiv.zcu.cz/~netrvalo/acm/acm.html.
V posledních šesti letech se této soutěže účastní
i týmy FAV ZČU v Plzni. Získaly dvakrát sedmé místo v přípravném kole
v Praze a třikrát postoupily do regionálního kola. V listopadu 2002 se
toto kolo konalo již podruhé ve Varšavě - http://cepc.mimuw.edu.pl/
. Soutěž byla tentokrát mimořádně těžká, o čemž svědčí fakt, že
z celkového počtu 61 týmů plných 31 týmů nevypracovalo ani jednu úlohu.
Naši univerzitu reprezentovaly dva týmy, z nichž zkušenější tým ve složení
Martin Benda, Tomáš Budai, Ladislav Lang s koučem Ing. Radkem Svitákem
obsadil 25. místo, ale před námi skončily z České republiky pouze dva týmy
z MFF Univerzity Karlovy, jejichž výuka je k typickým problémům řešeným v
soutěži jen snad blíže, a navíc na MFF existuje seminář zaměřený přímo na přípravu
k soutěži. Zbylé týmy z ostatních českých vysokých škol nevypracovaly ani
jednu úlohu. Z tohoto pohledu můžeme považovat vystoupení našich studentů
za úspěch.
V prosinci 2002 se uskutečnila beseda s
účastníky soutěže ve Varšavě
s cílem získat další zájemce. Účast v této soutěži je velmi zajímavá
a pokud máte v sobě alespoň trochu soutěživosti, určitě by se vám líbila. Svědčí
o tom i to, že všichni naši soutěžící se účastní i dalších ročníků.
Jestliže máte hlavy otevřené, máte šanci postoupit do regionálního kola
a podívat se tak "do světa". Navíc může dobrý výsledek zvýšit
vaši prestiž a pomoci při získávání zaměstnání nebo stipendia na zahraniční
univerzitě.
Zdůrazněme, že soutěž není jenom o kódování programu.
Jako příklad uveďme následující problém. Pro Stirlingova čísla druhého druhu
definovaná pro kladná celá čísla m
a n rekurentním vztahem
S(0,0) =
1, S(0,n) = 0, S(m,0) = 0,
S(n,m)
=mS(n-1,m) + S(n-1,m-1)
máte
určit hodnotu S(n,m) mod 2. Přímočarý rekurzivní
program bude, řekněme pro větší hodnoty m
a n, odmítnut kvůli časové
náročnosti.
Student
Karel Černohorský odvodil vlastnost,
která vede na následující programové řešení v Pascalu
n := n – m;
m:=(m-1)div2;
if
Boolean (m and n) then WriteLn(0) else WriteLn(1);
a
jehož doba výpočtu je na velikosti m
a n nezávislá.
I
když nemáme na univerzitě speciální předmět nebo seminář orientovaný na ACM soutěž, která by snad
neměla být cílem vzdělávání, výsledek našich studentů prokázal, že v našem
prostředí hlubokým studiem lze docílit velmi dobrých znalostí ve srovnání
s podobnými univerzitami v mezinárodním okolí. Navíc v předmětu Algorithms Design
and Problem Solving, už z jeho
povahy, se využívá úloh z ACM jako prostředku a může být dobrou průpravou
pro soutěž.
V případě, že máte předběžný zájem o účast
v soutěži, obraťte se na dále uvedenou e‑mailovou adresu:
netrvalo@kiv.zcu.cz .
Tým WBU Kings
Tým Pilsen++
(zleva: Martin Benda, Ladislav
Lang, Tomáš Budai) (zleva: Milan Dűnghűbel, Tomáš Smlsal, Karel Černohorský)