Seminář ACM pokročilá algoritmizace a programovací techniky I - V (A4B36ACM1-5)

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)

Kontakt a informace

Záměření semináře

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ů.


Struktura semináře

Č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.


Pravidelná minisoutěž

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

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.


Úrovně semináře

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ů.

 abc


Zápočet

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.


Odkazy a literatura

[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.

courses/a4b36acm1/start.txt · Last modified: 2020/09/23 22:21 by berezovs