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

 abc


Zápočet

Předměty jsou ukončeny klasifikovaným zápočtem. Za první úspěšně ukončený semestr studia předmětu získá posluchač 4 kredity, za druhý úspěšně ukončený semestr studia předmětu získá posluchač rovněž 4 kredity, nezávisle na tom, ve které úrovni to bude. Pokud se posluchač poté rozhodne navštěvovat další úroveň/úrovně, další kreditový zisk už nebude možný, protože účast ve třetím a vyšším běhu semináře považujeme za specializovanou přípravu na soutěž ACM, nad rámec studia.

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. Zápočet v úrovni 5. se uděluje pouze na základě výsledku v ACM soutěži .


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.

 
Groups:
courses/a4b36acm/start.txt · Last modified: 2015/10/06 12:17 by berezovs