====== 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.** \\ ([[http://en.wikipedia.org/wiki/Eric_Idle| Eric Idle ]]) a ([[http://www.indielondon.co.uk/Film-Review/not-the-messiah-he-s-a-very-naughty-boy-eric-idle-interview| interview s citátem]])\\ === Kontakt a informace === **Garant:** : [[mailto:mannova@fel.cvut.cz| Ing. Božena Mannová, Ph.D. ]]\\ **Vyučují:**: [[mailto:tunystom@gmail.com | Tomáš Tunys ]], [[mailto:berezovs@fel.cvut.cz| Marko Genyk-Berezovskyj ]]\\ ---- === 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ěží [[http://contest.felk.cvut.cz/| 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 [[http://uva.onlinejudge.org/| 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 [[http://www.amazon.co.uk/Introduction-Algorithms-T-Cormen/dp/0262533057/ref=sr_1_1?ie=UTF8&qid=1327340064&sr=8-1| [CLRS] ]], [[http://kix.fsv.cvut.cz/~demel/grafy/| [Demel] ]], [[http://newwiki.ceske-hry.cz/Kniha_Algoritmy_v_C,_%C4%8D%C3%A1sti_1-4 | [Sedgewick 1-4] ]], [[http://www.prometheus-nakl.cz/index.php?zobraz=detail&id_katalog=228| [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ů. \\ {{:courses:a4b36acm:levels.gif| 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 [[http://contest.felk.cvut.cz/| v ACM soutěži]] .\\ ---- ==== Odkazy a literatura ==== **[ACM Contest]** Soutěžní stránky ACM na FEL: [[http://contest.felk.cvut.cz/|ACM International Collegiate Programming Contest]] \\ **[KSP]** Korespondenční semináře z programování, [[http://ksp.mff.cuni.cz/ |MFF UK Praha]], [[http://www.ksp.sk/ksp2.0/news/|MFF UK Bratislava]], [[http://ganymed.math.muni.cz/ks/|MU Brno]]. \\ **[OLD]** Loňské stránky předmětu [[http://acm.algoritmy.eu/|zde]]. \\ **[Skiena]** Steven S. Skiena, Miguel A. Revilla: [[http://www.acmsolver.org/books/Programming_Challenges_Miguel_Skiena.pdf|Programming Challenges]] \\ **[UVA Judge]** Vyhodnocovací systém na University of Valladolid: [[http://uva.onlinejudge.org/| 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, [[http://www.amazon.co.uk/Introduction-Algorithms-T-Cormen/dp/0262533057/ref=sr_1_1?ie=UTF8&qid=1327340064&sr=8-1| link]]. \\ **[Demel]** J. Demel: Grafy a jejich aplikace, Praha, Academia 2002, ISBN 80-200-0990-6, [[http://kix.fsv.cvut.cz/~demel/grafy/| link]]. \\ **[Sedgewick 1-4]** Robert Sedgewick: Algoritmy v C, části 1-4, SoftPress, Praha, 2003, ISBN 80-86497-56-9, [[http://newwiki.ceske-hry.cz/Kniha_Algoritmy_v_C,_%C4%8D%C3%A1sti_1-4 | link ]] \\ **[Sedgewick 5]** Robert Sedgewick: Algorithms in C Part 5: Graph Algorithms (3rd Edition), Addison-Wesley Professional, 2002, ISBN-13: 978-0201316636, [[http://www.amazon.co.uk/Algorithms-C-Graph-Pt-5/dp/0201316633/ref=sr_1_10?s=books&ie=UTF8&qid=1327340310&sr=1-10| link]] .\\ **[Töpfer]** Pavel Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995, 2. vydání 2007, ISBN: 978-80-7196-350-9, [[http://www.prometheus-nakl.cz/index.php?zobraz=detail&id_katalog=228| link]]. \\