Search
The whole object is to bite off more than you can chew. (…) It’s the correct way to look at things and the correct place to start, I think. ( Eric Idle ) a ( interview s citátem)
Garant: : Ing. Božena Mannová, Ph.D. Vyučují:: Tomáš Tunys , Marko Genyk-Berezovskyj
Studenti, kteří chtějí systematicky zlepšovat svoje algoritmizační a programátorské schopnosti, potřebují vhodně navázat na předměty programování/algoritmizace v prvním ročníku. K dobrému programování je nutné kromě kodérské pohotovosti také disponovat co nejširším arzenálem algoritmů a zkušeností s jejich přizpůsobováním pro různé situace. ACM seminář se snaží poskytnout posluchačům praxi a základ pro další studium pokročilejších algoritmů a datových struktur. Kromě toho se seminář inspiruje každoroční programovací soutěží ACM Programming Contest a klade si za cíl připravit zájemce co nejlépe na tuto soutěž. Seminář je otevřen pro posluchače všech studijních programů.
Čas semináře se dělí mezi teoretickou přípravu a praktické řešení úloh. Teoretické příparavě je věnována 1/3 celkového času semináře a 2/3 času (tj. cca 28 hodin za semestr) jsou věnovány programování ve formě minisoutěží. Teoretická příprava navazuje na algoritmická témata bakalářské etapy, praktické programování tuto přípravu využívá a akcentuje efektivní implementaci.
Během jednoho semináře jsou zadány 2-3 úlohy podle úrovně posluchačů, které je nutno na místě co nejrychleji a zároveň co nejlépe vyřešit. Vyučující přitom průbežně prochází se studenty jejich jednotlivá řešení, konzultuje jejich kvalitu, použité algoritmy a datové struktury a navrhuje vhodné úpravy. Semestr obsahuje cca 20 úloh k samostatnému programování v minisoutěži.
Úlohy, které posluchači řeší, jsou ve většině případů dobře ohodnoceny jejich relativní náročností podle mezinárodní úspěšnosti řešitelů v předchozích letech. Výsledky posluchačů jsou hodnoceny mezinárodně využívaným automatem UVA Online Judge, což představuje dobrý tréninkový model účasti ve skutečné soutěži. Strojové hodnocení zároveň poskytuje vzájemné porovnání pokroku posluchačů a využívá se pro klasifikaci. Doufáme, že forma minisoutěže sama o sobě přispěje k motivaci účastníků podat co nejlepší výkon.
Teoretické partie jsou pokryty literaturou [CLRS] , [Demel] , [Sedgewick 1-4] , [Töpfer] aj. Standardní partie základních algoritmů a datových struktur jsou v nich přehledně a do značné hloubky probírány. Zájemci se během semestru mohou s těmito knihami seznámit, většina z nich je zároveň dobrou referenční příručkou jak během studia tak i po jeho ukončení a má své místo v knihovničce profesionála.
Předmět existuje v v pěti úrovních se vzrůstající náročností a má v každé úrovni časovou dotaci 0+3. Úrovně 1.-4. jsou vypisovány v obou semestrech, úroveň 5. jen v zimním semestru jako příprava na soutěž ACM, cvičení pro všechny úrovně jsou společná v jednu dobu.
Posluchač může začít navštěvovat předmět v kterékoli úrovni, pokud jsou jeho znalosti dostatečné. Po úspěšném absolvování úrovně si může zapsat vyšší úroveň. Přitom, pokud to jeho znalosti umožňují nebo vynucují, může řešit úlohy z ostatních úrovní, podle svých individuálních možností a zájmů.
Předměty jsou ukončeny klasifikovaným zápočtem. Nutnou podmínkou pro udělení zápočtu je správně vyřešení dostatečného množství zadaných úloh. Podle úrovně semináře a ročníku je předepsán v každém semestru příslušný počet úloh a způsob vyhodnocení jednotlivých řešení. Volbu algoritmů a datových struktur a jejich adekvátní použití v úloze posoudí vyučující. Výsledná klasifikace závisí na počtu správně vyřešených úloh a na programátorské kvalitě řešení. Umístění v první polovině skupiny všech řešitelů regionálního kola ACM programming Contest je vždy postačující podmínkou zápočtu s hodnocením A.
[ACM Contest] Soutěžní stránky ACM na FEL: ACM International Collegiate Programming Contest [KSP] Korespondenční semináře z programování, MFF UK Praha, MFF UK Bratislava, MU Brno. [OLD] Loňské stránky předmětu zde. [Skiena] Steven S. Skiena, Miguel A. Revilla: Programming Challenges [UVA Judge] Vyhodnocovací systém na University of Valladolid: UVA Online Judge
[CLRS] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009, ISBN-13: 978-0262533058, link. [Demel] J. Demel: Grafy a jejich aplikace, Praha, Academia 2002, ISBN 80-200-0990-6, link. [Sedgewick 1-4] Robert Sedgewick: Algoritmy v C, části 1-4, SoftPress, Praha, 2003, ISBN 80-86497-56-9, link [Sedgewick 5] Robert Sedgewick: Algorithms in C Part 5: Graph Algorithms (3rd Edition), Addison-Wesley Professional, 2002, ISBN-13: 978-0201316636, link . [Töpfer] Pavel Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995, 2. vydání 2007, ISBN: 978-80-7196-350-9, link.