Lukáš Lánský: Webové algoritmizační soutěže

Klíčem k účinné výuce algoritmizačního myšlení v omezených podmínkách současného středního školství je motivace žáků k další práci doma. Prostředí internetu nabízí aktivity, které je možné v hodinách ICT představit, využít pro naplnění záměrů RVP a po vypršení úzkého časového rámce, který je tomuto druhu výuky vymezen, nechat žáky, ať v práci pokračují samostatně, mimo prostředí školy. Projekty, které článek představí, k takovému pokračování vybízejí.



Výuka algoritmizace se na všeobecně zaměřených středních školách netěší velké podpoře. Má se za to, že jde o obor, který sice má velké uplatnění v praxi, leč jen pro malou skupinu žáků. Tento názor je v ostrém kontrastu s rostoucím významem všech odrůd programování a skriptování ve vědecké činnosti v oborech, jako je ekonomie, chemie či biologie. Hromadné a netriviální strojové zpracování velkého objemu dat je jedním ze zásadních problémů, který stojí před fyziky v CERNu.

Nutností ve výuce algoritmizace se tedy v podmínkách nedostatečné časové dotace pro toto téma stává motivace nadaných žáků k samostatné práci mimo školské prostředí. Českým, dnes už téměř tradičním řešením jsou Korespondenční semináře pořádané „matfyzem“ (pro programování je to konkrétně KSP) a čerstvě Masarykovou univerzitou (KSI).

Semináře umí budoucí informatiky výtečně namotivovat k práci, protože jim nabízejí alternativní kolektiv lidí s podobnými zájmy a kulturou. Nejsou však řešením pro každého, neboť jsou poměrně hodně časově náročné a vyhraněné svým specifickým směrem: jsou dosti teoretické, nenutí sepisovat a odlaďovat funkční programy, oproti tomu bazírují na optimální časové a prostorové složitosti výsledných algoritmů.

Project Euler

Project Euler je první z představovaných webových projektů. Žákům jsou v něm zadávány problémy jako:

• Jaký je největší prvočíselný dělitel čísla 600 851 475 143?
• Jaká je miliontá permutace čísel 1 ... 9 v lexikografickém uspořádání?
• Jaký je součet všech čísel od jedné do milionu, které jsou palindromem jak v soustavě desítkové, tak dvojkové?

Jak vidno, nejde o matematicky zajímavé otázky, protože jsou velmi konkrétní povahy. Velké konstanty, které se v nich nacházejí, nutí řešitele psát efektivní kód, ačkoliv samozřejmě nemusí být naprosto optimální: program může běžet na stroji řešitele libovolně dlouhou dobu, protože se konstanty v zadání nemění.
Řešitel po jednoduché registraci vidí všechna zadání, kterých je v současnosti (květen 2011) takřka 350. Citovaná patří mezi úvodní stovku, kde jsou formulačně i řešitelsky jednoduchá zadání  Nová zadání, z konce seznamu, svou obtížností míří spíše na vysokoškolské studenty, neboť je k jejich řešení zapotřebí znalost, či spíše zkušenost se základy teorie čísel, kombinatoriky, kombinatorické teorie her, …

Kdykoliv řešitel získá správnou odpověď, zadá ji do formuláře, načež mu stránka odpoví, nalezl-li ji správně. V kladném případě ho vpustí do diskuzního fóra, kde si může (anglicky) popovídat s ostatními řešiteli o tom, jakým způsobem řešení dosáhl, a je mu přičten bod. Existuje přehledná tabulka řešitelů z jednotlivých států. Pod ČR se jich hlásí tři stovky, z toho prvních 25 má alespoň sto bodů. Jsou mezi nimi i někteří středoškolští žáci, kteří jsou též úspěšní v mezinárodních programátorských soutěžích, jako je IOI.

Typická hodina, při které žáci řeší úlohy z Projectu Euler, vypadá následovně: vyučující představí prostředí a požádá žáky, aby se zaregistrovali. Pak vybere tři úlohy a prodiskutuje způsob, jakým je je možno řešit. Na to třída programuje a vyučující chodí od počítače k počítači a řeší otázky. V polovině stanoveného času prozradí řešení polopatičtěji a shrne časté zádrhele. Na konci poděkuje nejlepším řešitelům a všem rozešle e-mail s adresou projektu a doporučenými úlohami k dalšímu procvičování.

SPOJ

Zatímco Project Euler vkládá do svých zadání jeden konkrétní vstup (v první zmíněné úloze jde o číslo 600 851 475 143) a očekává odpověď jediným číslem (největším dělitelem 6 857), polský SPOJ (Sphere Online Judge) předkládá vedle otázky předepsaný formát vstupu a výstupu algoritmu a jako odpověď, kterou vyhodnocuje, bere od řešitele celý program v široké škále jazyků (C, C++, Pascal, C#, Java, Python, Haskell, …). Ten na serveru spustí danou množinu tajných zadání a řešiteli oznámí, na kolik vstupů jeho kód odpověděl správně (popř. jestli při výpočtu nebo kompilaci nehavaroval či jestli nevypršel časový limit).
Tato metoda se už dlouho používá při programátorských soutěžích (např. na české MO-P), posledních několik let vznikají projekty, které jsou schopné vyhodnocovat řešení mnoha set až tisíců vzdálených řešitelů přes webové rozhraní.

SPOJ nabízí registrovaným uživatelům dva tisíce různě obtížných úloh v angličtině. Takto vypadají zadání některých z nich:

• PALIN: Na každém z N řádků na vstupu dostanete přirozené číslo o nejvíce milionu číslic. Pro každý z nich, v tom samém pořadí, na výstup vypište nejmenší vyšší přirozené číslo, jehož desítkový zápis tvoří palindrom.
• ACODE: Na vstupu dostanete přirozené číslo, které má nejvýše 5 000 číslic. Kolika způsoby můžeme jeho zápis chápat jako konkatenaci zápisů čísel 1 ... 26?
• ONP: Přepište algebraický výraz v reverzní polské notaci do tradičního, infixového zápisu.

Úlohy v této soutěži odpovídají tradičním zadáním víc a projekt je tedy dobře použitelný i jako „pouhý“ inspirační zdroj pro zadání do písemek a domácích úkolů. Řešení na druhou stranu zabere poněkud delší dobu.

Přestože SPOJ obsahuje poměrně kvalitní online editor zdrojových kódů, je stále nutné, aby učitel žákům připravil vývojové prostředí, na kterém budou moci své programy ladit. Doporučit lze Code::Blocks pro C, Eric pro Python a MS Visual Express pro C#, které jsou dostupné zadarmo.

Džungle, PROSO

Stojí za to se alespoň několika slovy zmínit o českých alternativách k výše zmíněným stránkám.
Programátorská džungle je webová adventura od Korespondenčního semináře z programování, která předkládá návštěvníkovi programátorské úlohy se vstupními daty a podobně jako Project Euler očekává pouze výstup. Její součástí je i mapa pro výuku základů jazyka Python.

PROSO je soutěž ve vyhodnocovacím prostředí CodEx, kterou připravují učitelé matematicko-fyzikální fakulty. CodEx je systém podobný SPOJi, který si MFF vyvíjí především pro potřeby výuky svých předmětů.

Závěrem

Každý z výše uvedených webů se snaží své řešitele motivovat různými vyznamenáními a výhodami. Euler rozdává odznáčky, KSP zve dobré řešitele Džungle na svá soustředění, a pokud se čtenář po světě těchto projektů rozhlédne, objeví stránky jako TopCoder, které sice nejsou příliš dobré pro vyučování algoritmizace, tečou však do nich velké peníze od nadnárodních společností, které po světě loví kvalitní programátory.

Nejdůležitější motivací jsou však nakonec výsledkové listiny. Při práci řešitel postupuje výš a výš, nechává za sebou konkrétní, podepsané žáky/studenty a učitele různých jiných škol z celého světa, což v něm zanechává uspokojení z uplatněných dovedností.

Převzato z RVP.CZ.