**Bold Text** ====== 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]])\\ === Velké díky dr. Marko Genyk Berezovskému, který tyto semináře uvedl v život. Současný tým učitelů se snaží stavět na jeho základech. Děkujeme studentům, že nám s tímto úkolem pomáhají. === === Kontakt a informace === **Garant:** : \\ [[mailto:mannova@fel.cvut.cz| Ing. Božena Mannová, Ph.D. ]]\\ **Vyučují:**: \\ [[mailto:rysavpe1@fel.cvut.cz| Bc. Petr Ryšavý, MSc., Ph.D. ]]\\ [[mailto:martin.kacer@fit.cvut.cz| Ing. Martin Kačer, Ph.D. ]]\\ [[mailto:ulricji1@fel.cvut.cz| Ing. Jiří Ulrich ]]\\ [[mailto:mannova@fel.cvut.cz| Ing. Pavel Strnad, Ph.D. ]]\\ ---- === Přednášky === Přednášku Slovník, Dynamické programovaní najdete zde [[https://moodle.fel.cvut.cz/mod/resource/view.php?id=356377] | Přednáška Martina Kačera ]]\\ Přednáška Jiří Ulrich[[https://moodle.fel.cvut.cz/pluginfile.php/526670/mod_resource/content/3/01-alg03_2011.pdf | První část ]] [[https://moodle.fel.cvut.cz/pluginfile.php/526671/mod_resource/content/1/02-alg04_2011.pdf | Druhá část]] [[https://moodle.fel.cvut.cz/pluginfile.php/526672/mod_resource/content/1/03-alg06_2011.pdf | Třetí část ]] \\ Grafové Algoritmy I (P. Ryšavý): {{courses:a4b36acm1:20250410_bfs_dfs_topsort_sccs.pdf|slidy}} \\ Grafové Algoritmy II - nejkratší cesty (P. Ryšavý) {{20250424_dijkstra_bellman-ford-floyd-warshall.pdf|slidy}} \\ Výpočetní geometrie (P. Ryšavý): {{courses:a4b36acm1:20250514_comput_geometry.pdf|slidy}} **Minisoutěže** Úlohy na minisoutěž "První jarní den" najdete zde [[https://codeforces.com/problemset/problem/368/B | Uloha 1.]] [[https://codeforces.com/problemset/problem/1660/C | Úloha 2. ]] [[https://codeforces.com/problemset/problem/1703/B | Úloha 3. ]] \\ Úlohy na minisoutěž 3. dubna najdete zde [[https://codeforces.com/problemset/problem/1741/D | Uloha 1.]] [[https://codeforces.com/problemset/problem/1971/A | Úloha 2. ]] [[https://codeforces.com/problemset/problem/1975/A | Úloha 3. ]] [[https://codeforces.com/problemset/problem/1742/B | Úloha 4. ]] \\ \\ Úlohy na minisoutěž 17. dubna najdete zde: \\ [[ https://codeforces.com/problemset/problem/35/C | Uloha 1. (lehká)]] \\ [[ https://codeforces.com/problemset/problem/173/B | Úloha 2. (lehká)]] \\ [[ https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2499 | Úloha 3. (lehká)]] \\ [[ https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2021 | Úloha 4. (střední)]] \\ [[ https://codeforces.com/problemset/gymProblem/101102/K | Úloha 5. (střední)]] \\ [[ https://codeforces.com/problemset/problem/29/E | Úloha 6. (těžká)]] \\ Úlohy na minisoutěž 6. května najdete zde: \\ [[ https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=499 | Úloha 1. (lehká) ]] \\ [[ https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2487 | Úloha 2. (lehká) ]] \\ [[ https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1927 | Úloha 3. (lehká) ]] \\ [[ https://codeforces.com/gym/102569/problem/D | Úloha 4. (střední) ]] \\ [[ https://codeforces.com/contest/2014/problem/E | Úloha 5. (střední) ]] \\ [[ https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2352 | Úloha 6. (střední) ]] \\ [[ https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1498 | Úloha 7. (těžká) ]] \\ Pro případné nápovědy si můžete napsat na [[mailto:rysavpe1@fel.cvut.cz| rysavpe1@fel.cvut.cz ]] ;) \\ Úlohy na minisoutěž 22. května najdete zde: \\ [[ https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=314 | Úloha 1. (lehká) ]] \\ [[ https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=861 | Úloha 2. (lehká) ]] \\ [[ https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=154 | Úloha 3. (lehká) ]] \\ [[ https://codeforces.com/group/DeilFl9Bhi/contest/329191/problem/C | Úloha 4. (střední) ]] \\ [[ https://codeforces.com/contest/120/problem/J | Úloha 5. (střední, VSTUP ZE SOUBORU!) ]] \\ [[ https://codeforces.com/problemset/problem/70/D | Úloha 6. (střední) ]] \\ [[ https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3552 | Úloha 7. (těžká) ]] \\ ---- === Přednášky Marka Berezovského === Najdete zde [[https://www.youtube.com/results?search_query=cvut+fel+berezovsky| Nahrané přednášky na FEL]] ---- === Zaměř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řípravě 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]] nebo [[http://codeforce.com/| codeforce ]]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. 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. \\ Pro ZS 2024/2025 jsou stanovené následující limity: 8 a více vyřešených úloh odpovídá známce (A), 7 B, 6 C, 5 D, 4 E 3 a méně F. ---- ==== 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]] \\ [[http://www.acmsolver.org/books/Programming_Challenges_Miguel_Skiena.pdf|Programming Challenges]] \\ **[Codeforces]** Vyhodnocovací systém Codeforces: [[http://codeforces.com|]] \\ \\ **[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]]. \\