**Místo a čas konání** KN:E-311, čtvrtek od 16:15, střídavě 2 a 4 hodiny týdně, viz rozpis níže. ===== Rozvrh ===== ^ Seminář ^ Datum \\ (hodiny) ^ Náplň ^ Úlohy/odkazy/prezentace \\ viz také pod tabulkou ^ | **1.** | **23.2.** (4) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání |Základní: [[https://a2oj.com/register?ID=30243| A2OJ - úlohy a výsledky]] \\ Pokročilí: [[https://a2oj.com/contest?ID=30244|Regionals 2005 - Africa/Middle East - Arab and North Africa ]] | | **2.** | **2.3** (2) |Základní: Průchody grafem \\ Pokročilí: Trie, suffix tree | | | **3.** | **9.3.** (4) |** Minisoutěž I** | Základní: [[https://a2oj.com/register?ID=30520| A2OJ - úlohy a výsledky]] \\ Pokročilí: [[https://a2oj.com/register?ID=30521|Regionals 2005 - North America - Rocky Mountain]] + Pattern Matching | | **4.** | **16.3.** (2) |Základní: Grafy a nejkratší cesty \\ Pokročilí: Binary trie, radix trie | | | **5.** | **23.3.** (4) |** Minisoutěž II** | Základní: [[https://a2oj.com/standings?ID=30786|A2OJ - úlohy a výsledky]] \\ Pokročilí: [[https://a2oj.com/standings?ID=30790|Regionals 2008 - Asia - Beijing]]| | **6.** | **30.3.** (2) |Základní: Dynamické programování \\ Pokročilí: Finite automata, Aho-Corasick | | | **7.** | **6.4.** (4) | ** Minisoutěž III** | Základní: [[https://a2oj.com/standings?ID=31062|A2OJ - úlohy a výsledky]] \\ Pokročilí: [[https://a2oj.com/standings?ID=31063 |Regionals 2003 - North America - East Central NA]] | | **8.** | **13.4.** (2) |Základní: Aritmetika a kombinatorika, teorie čísel \\ Pokročilí: Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin | | | **9.** | **20.4** (4) |**Minisoutěž IV** | Základní: [[https://a2oj.com/standings?ID=31310|A2OJ - úlohy a výsledky]] \\ Pokročilí: [[https://a2oj.com/standings?ID=31313|Regionals 2001 - Europe - Northwestern]] \\ | | **10.** | **27.4.** (2) |Základní: Výpočetní geometrie, mřížky \\ Pokročilí: Segment tree, treap | | | **11.** | **4.5.** (4) | **Minisoutěž V** | Základní: [[https://a2oj.com/standings?ID=31522|A2OJ - úlohy a výsledky]] \\ Pokročilí: [[https://a2oj.com/standings?ID=31523|A2OJ - úlohy a výsledky]] \\ [[ https://docs.google.com/spreadsheets/d/17y9viz3O71tO5nyFDE3BxqEj3ITDWntbX4p6Kvo1L2g/edit#gid=0|Náhradní tabulka ]]| | | //12.// | //11.5.// (2) | //odpadá, pondělní rozvrh // | | | **13.** | **18.5.** (4) | **Minisoutěž VI** | Základní: [[https://a2oj.com/standings?ID=31695|A2OJ - úlohy a výsledky]] \\ Pokročilí: [[https://a2oj.com/standings?ID=31696|A2OJ - úlohy a výsledky]] | | **14.** | **25.5.** (2) |Základní: Anatgonistické hry, Nim \\ Pokročilí: Jiné dle zájmu, dodělávky, ad lib. | | | **CELKEM** | LS 2017 | **Průběžný stav** | [[https://docs.google.com/spreadsheets/d/1uOx5yEnPf7JbTQm0yHLTSiGkkxkKzpb1DdNBtoDpfOM/edit?usp=sharing|Tabulka]] | ===== Pokročilá skupina ===== [[https://docs.google.com/spreadsheets/d/1J7CA8OymzUk70lm6mT_mfbscejv6e9N0AN5_kNcaIVk/edit#gid=0| Seznam účastníků a rozdělení témat]] {{:courses:a4b36acm:2017_ls:zdary.pdf|zdary.pdf}} ===== Prezentace ===== **Přibližně návodná ukázka struktury prezentace**: {{:courses:a4b36acm:2016_zs:ukazkaprez.pdf| Voda v rourách}} ===== Seminář 1 ===== [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm/trenink?&#jak_na_reseni| Návodník na řešení ]] {{:courses:a4b36acm:2016_zs:grafy-ulohy.pptx| malá kategorizace grafových úloh }} ==== Ahmed Aly Online Judge ==== V průběhu praktických cvičení (sudé výukové týdny) svá řešení budete odevzdávat do **A2 Online Judge**. Prosíme, vytvořte si každý svůj vlastní účet sledováním následujícího linku: [[http://a2oj.com/signup|Sign Up]]. Vzhledem k tomu, že A2 Online Judge je pouze tzv. //agregátor výsledků//, musíte si vytvořit účty v příslušných judgích, které skutečně ověřují správnost vašich řešení, a to: [[http://www.spoj.com/register/|Sphere Online Judge]], [[https://uva.onlinejudge.org/index.php?option=com_comprofiler&task=registers|UVa Online Judge]] a [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_comprofiler&task=registers|ACM-ICPC Live Archive]]. \\ Aby A2OJ věděl o odevzdaných úlohách, musíte vyplnit ve svém profilu ID, které jste si vytvořili či vám bylo přiděleno u výše uvedených judgů. Zde je shrnut postup, jak se k nim dostat: === Sphere Online Judge (SPOJ) === - Neuvěřitelné, ale login je vaše ID. === UVA Online Judge === - V hlavním menu po přihlášení ťukněte na [My Account] - Ve vašem profilu na řádku _Online Judge ID:_ je Vaše UVA ID. === ACM-ICPC Online Judge === * Postup je stejný jako u UVA Online Judge. ==== Test odevzdávacího systému ==== Po vytvoření účtů se můžete registrovat do soutěže na A2 Online Judge, klikněte na příslušný odkaz do A2OJ nahoře v tabulce. ===== Seminář 2: Grafové algoritmy ===== Dnešní cvičení bude úvod do grafových algoritmů. Nejprve nás ale čeká diskuze nad úlohami z posledního cvičení. Poté probereme základní pojmy z teorie grafů a popovídáme si o základních úlohách, které lze řešit jedním z nejverzatilnějších algoritmů (z říše grafových algoritmů), a to o prohledávání do hloubky. Ale i mnohem více... Stěžejní algoritmy a datové struktury: * [[http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/|Prohledávání do hloubky]] * [[http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/|Prohledávání do šířky]] * [[http://www.geeksforgeeks.org/union-find/|Union-Find]] Motivační úlohy s řešeními (hlavně na příští seminář): * **Spreadsheet** - kód: {{:courses:a4b36acm:2015_zs:spreadsheet.java|spreadsheet.java}}, vstupy: {{:courses:a4b36acm:2015_zs:spreadsheet.txt|spreadsheet.txt}} * **Hádanka s kozou, vlkem a zelím** - kód: {{:courses:a4b36acm:2015_zs:riddle.java|riddle.java}} * **Hádanka s tunelem** - kód: {{:courses:a4b36acm:2015_zs:riddle2.java|riddle2.java}} * **Maze Runner** - kód: {{:courses:a4b36acm:2015_zs:mazerunner.java|mazerunner.java}}, {{:courses:a4b36acm:2015_zs:mazerunner2.java|mazerunner2.java}} (alternativní), vstupy: {{:courses:a4b36acm:2015_zs:mazerunner1.txt|mazerunner1.txt}}, {{:courses:a4b36acm:2015_zs:mazerunner2.txt|mazerunner2.txt}}, {{:courses:a4b36acm:2015_zs:mazerunner3.txt|mazerunner3.txt}}, {{:courses:a4b36acm:2015_zs:mazerunner4.txt|mazerunner4.txt}}, {{:courses:a4b36acm:2015_zs:mazerunner5.txt|mazerunner5.txt}} * **Heretic** - kód: {{:courses:a4b36acm:2015_zs:heretic.java|heretic.java}}, vstupy: {{:courses:a4b36acm:2015_zs:heretic1.txt|heretic1.txt}},{{:courses:a4b36acm:2015_zs:heretic2.txt|heretic2.txt}}, {{:courses:a4b36acm:2015_zs:heretic3.txt|heretic3.txt}}, {{:courses:a4b36acm:2015_zs:heretic4.txt|heretic4.txt}} * **Útěk z hořícího lesa** - kód: {{:courses:a4b36acm:2015_zs:escape.java|escape.java}}, vstupy: {{:courses:a4b36acm:2015_zs:escape1.txt|escape1.txt}}, {{:courses:a4b36acm:2015_zs:escape2.txt|escape2.txt}}, {{:courses:a4b36acm:2015_zs:escape3.txt|escape3.txt}} ===== Seminar 4 ===== V dnešním semináři budeme pokračovat v povídání o grafových algoritmech. Tentokrát probereme řadu algoritmů pro hledání nejkratší cesty v grafu a určení jeho minimální kostry. * Dijkstrův algoritmus (nejkratší cesta) [[http://www.spoj.com/problems/EZDIJKST/|Easy Dijkstra Problem]] {{:courses:a4b36acm:2017_ls:ezdijkst.txt|(Řešení v C++)}} * Dijkstrův algoritmus (téměř nejkratší cesta) [[http://www.spoj.com/problems/SAMER08A/|Almost Shortest Path]] {{:courses:a4b36acm:2017_ls:samer08a.txt|(Řešení v C++)}} * Dijkstrův algoritmus (minimální kostra) [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2678|Dark roads (UVa)]] {{:courses:a4b36acm:2017_ls:dark_roads.txt|(Řešení v C++)}} * Bellman-Fordův algoritmus [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=499|Wormholes]] {{:courses:a4b36acm:2017_ls:wormholes.txt|(Řešení v C++)}} * Floyd-Warshallův algoritmus [[http://www.spoj.com/problems/ARBITRAG/|Arbitrage (SPOJ)]] {{:courses:a4b36acm:2017_ls:arbitrage.txt|(Řešení v C++)}} ===== Seminář 6: Dynamické programování I ===== Učební materiály a pár jednodušších úloh na doma. * [[https://cw.fel.cvut.cz/wiki/_media/courses/a4b36acm/2013_ls/dp.pdf|Ukázky klasických úloh TT&MB]] * {{:courses:a4b36acm:2016_zs:ukazkaprez.pdf| Voda v rourách}} * {{:courses:a4b36acm:2016_zs:dag.pdf| Základní všechno možné průchodem DAG }} * {{:courses:a4b36acm:2016_zs:lisnlogn.pdf| nejdelší rostoucí podposloupnost v čase O(N log N) }} * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=841|900 - Brick Wall Patterns]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1275 * |10334 - Ray Through Glasses]] * [[http://www.spoj.com/problems/MMAXPER/| MMAXPER, Rectangles Perimeter - max upper envelope length]] [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm/2016_zs/code#elementary_dag_manipulation| Ukázka kódu -- manipulace s DAG]] ===== Seminář 8: ===== **Cycle finding** \\ Algorithm:\\ [[https://en.wikipedia.org/wiki/Cycle_detection#Floyd.27s_Tortoise_and_Hare|Floyd's Tortoise and Hare]]\\ Problems:\\ [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=286|350 - Pseudo-Random Numbers]] \\ [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1532|10591 - Happy Number ]]\\ [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2544|11549 - Calculator Conundrum]]\\ **String Matching** \\ [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=505&page=show_problem&problem=1960|11019 - Matrix Matcher]]\\ [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=505&page=show_problem&problem=4074|1328 - Period]]\\ [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=506&page=show_problem&problem=4265|1519 - Dictionary Size]]\\ [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=506&page=show_problem&problem=1828|10887 - Concatenation of Languages]]\\ [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=524&page=show_problem&problem=4060|1314 - Hidden Password]]\\ **Automata**\\ [[http://www.stringology.org/athens/TextSearchingAlgorithms/| Textbook Melichar et al.]] {{:courses:a4b36acm:2017_ls:atasearch.pptx| Text Search with Automata }} {{:courses:a4b36acm:2017_ls:gregor4840.ppt| Example calendar automaton}} ===== Seminář 10 - Aritmetika a kombinatorika, teorie čísel ===== Odkazy na materiály: * [[https://math.feld.cvut.cz/habala/teaching/dma/dmknih11.pdf|Habalova kombinatorická skripta]]! * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=305|369 - Combinations]] *[[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1244|10329 - Combinatorial Expression]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1316|10375 - Choose and divide]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1154|10213 - How Many Pieces of Land ?]] Eulerova formule V+F = E+2 * {{:courses:a4b36acm:2016_ls:primes.pptx| Prvočísla, Eratosthenovo síto a kód}} * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2403|11408 - Count DePrimes]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2322|11347 - Multifactorials]] * [[http://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/|Výpočet multiplikativní inverse]] * [[http://www.geeksforgeeks.org/basic-and-extended-euclidean-algorithms/|Rozšířený Euclidův algoritmus]] * [[http://www.di-mgt.com.au/euclidean.html| ... A ještě přehledněji!!]] * [[https://en.wikipedia.org/wiki/Fermat%27s_little_theorem|Malá Fermatova věta]] * Eulerova věta a funkce ([[https://en.wikipedia.org/wiki/Euler%27s_theorem|1]], [[https://en.wikipedia.org/wiki/Euler%27s_totient_function|2]], [[http://www.geeksforgeeks.org/eulers-totient-function/|3]]) * [[http://www.geeksforgeeks.org/chinese-remainder-theorem-set-2-implementation/|Čínská věta o zbytcích]] * Čísla všeho druhu: * [[https://en.wikipedia.org/wiki/Combination|Kombinační]] * [[https://en.wikipedia.org/wiki/Fibonacci_number|Fibonacciho]] * [[https://en.wikipedia.org/wiki/Catalan_number|Catalanova]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1244|10303 - How Many Trees?]] * [[https://en.wikipedia.org/wiki/Motzkin_number|Motzkinova]] * Úloha spojující poslední dva jmenované druhy: [[https://www.codechef.com/problems/MAXGAME|Game Count]] * [[http://fusharblog.com/solving-linear-recurrence-for-programming-contest/|Řešení lineárních rekurentních rovnic s konstantními koeficienty]] * Úloha: [[https://www.codechef.com/problems/HAREJUMP|Chefs new Pet]] ===== Seminar 10: Segmentove stromy (Pokrocili) ===== Studijni materialy: * [[https://docs.google.com/presentation/d/1RAlGfpEOoLyStTHpWnXdzj8E08D_KYShEu54i4mB4NA/edit#slide=id.p|Range Minimum Query, Lowest Common Ancestor, Heavy-Light Decomposition]] * [[https://docs.google.com/presentation/d/1CYN9f18bB2rZT0UtriKWoBh2IegniOvNdQvUT1fxaQY/edit#slide=id.g1733a99d18_0_161|Range Minimum Query]] * [[https://docs.google.com/presentation/d/1352wnxlrrj9Z_CbBiDJvYYzlzFeewXV2x1jDkFee3aQ/edit#slide=id.p|Static Interval Tree]] * [[https://docs.google.com/presentation/d/1D4beTIdSdPyBD_6ClYpxAhpIFweIwSxHErxwuLa0Glg/edit#slide=id.p|Binary Index Tree]] Nekolik uloh na doma: * [[http://www.spoj.com/problems/COT/|COT - Count on a tree]] * [[http://www.spoj.com/problems/GRASSPLA/|GRASSPLA - Grass Planting]] * [[http://www.spoj.com/problems/YODANESS/|YODANESS - Yodaness Level]] * [[http://www.spoj.com/problems/DCEPC11I/|DCEPC11I - Impossible Boss]] * [[http://www.spoj.com/problems/RACETIME/|RACETIME - Race Against Time]] * [[http://www.spoj.com/problems/BRCKTS/|BRCKTS - Brackets]] * [[http://www.spoj.com/problems/COURAGE/|COURAGE - Living with Courage]] ===== Seminář 14: Kombinatorické hry ===== viz. [[courses:a4b36acm:maraton2016|ACM Maraton 2016]] Pár kousků pro pokročilé posluchače: * [[http://www.spoj.com/problems/PT07A/|Play with a Tree (SPOJ)]] * [[http://www.spoj.com/problems/BNWNIM/en/|Black and White Nim (SPOJ)]] * [[http://contest.felk.cvut.cz/11cerc/solved/trail.pdf|Racing Car Trail (CERC Regional 2011)]] - [[http://contest.felk.cvut.cz/11cerc/solved/trail.in.gz|trail.in.gz]] (input data) - [[http://contest.felk.cvut.cz/11cerc/solved/trail.out.gz|trail.out.gz]] (correct output) * [[https://www.codechef.com/problems/CHN07|Malvika and Animesh play Red-Blue cards Game (Codechef]] * [[https://www.codechef.com/problems/ADDMULT|To add or to multiply game (Codechef)]]