**Místo a čas konání** KN:E-311, čtvrtek od 14:30, a 17:00. ===== Rozvrh ===== ^ Seminář ^ Datum ^ Náplň ^ Úlohy/odkazy/prezentace \\ viz také pod tabulkou ^ | **1.** | **5.10.** | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání | [[https://a2oj.com/register?ID=33833|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=33833| (Výsledky)]]\\ Základní grafový přehled, dohoda témat s pokročilými účastníky \\ [[https://a2oj.com/register?ID=33826|pokročilé náměty na A2OJ ]]| | **2.** | **12.10** | Průchody grafem ** Minisoutěž I** ... | [[https://a2oj.com/register?ID=33992|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=33992| (Výsledky)]]\\ [[https://a2oj.com/register?ID=33994|Úlohy na A2OJ (pokročilí)]] [[https://a2oj.com/standings?ID=33994| (Výsledky)]]| | **3.** | **19.10.** | Nejkratší cesty, aplikace dfs | ..\\ [[https://a2oj.com/register?ID=34082|Úlohy na A2OJ (pokročilí)]] | | **4.** | **26.10.** | Grafové algoritmy **Minisoutěž II** | [[https://a2oj.com/register?ID=34206|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=34206| (Výsledky)]] \\ [[https://a2oj.com/register?ID=34214 |Úlohy na A2OJ (pokročilí)]] | | **5.** | **2.11.** | Dynamické programování I | | | **6.** | **9.11.** | Dynamické programování II **Minisoutěž III** | [[https://a2oj.com/register?ID=34429|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=34429| (Výsledky)]]\\ [[https://a2oj.com/register?ID=34431 |Úlohy na A2OJ (pokročilí)]] [[https://a2oj.com/standings?ID=34431| (Výsledky)]] | | **7.** | **16.11.** | Kombinatorika, torie čísel | | | **8.** | **23.11.** | Kombinatorika, torie čísel **Minisoutěž IV** | [[https://a2oj.com/register?ID=34592|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=34592| (Výsledky)]]\\ [[https://a2oj.com/register?ID=34593 |Úlohy na A2OJ (pokročilí)]] [[https://a2oj.com/standings?ID=34593| (Výsledky)]] | | **9.** | **30.11** | Výpočetní geometrie, zametací přímka | | **10.** | **7.12.** | Výpočetní geometrie, zametací přímka **Minisoutěž V** | [[https://a2oj.com/register?ID=34757|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=34757| (Výsledky)]]\\ [[https://a2oj.com/register?ID=34758 |Úlohy na A2OJ (pokročilí)]] [[https://a2oj.com/standings?ID=34758| (Výsledky)]] | | **11.** | **14.12.** | Opakování, DP, MST, různé \\ hledání v textu | | | **12.** | **21.12** | DP, MST, různé **Minisoutěž VI** \\ [[https://docs.google.com/spreadsheets/d/1nOCQTXdrVbzALQ5LzXhoagOnPzFk2Km9MDir60-6Tys/edit?usp=sharing | Stav ]] | [[https://a2oj.com/register?ID=34890|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=34890| (Výsledky)]] \\ [[https://a2oj.com/register?ID=34892 |Úlohy na A2OJ (pokročilí)]] [[https://a2oj.com/standings?ID=34892| (Výsledky)]] | | **13.** | **4.1.** | Kombinatoricke hry | [[https://a2oj.com/register?ID=34949 |Úlohy na A2OJ (pokročilí)]] [[https://a2oj.com/standings?ID=34949| (Výsledky)]] | | **14.** | **11.1.** | Kombinatoricke hry **Minisoutěž VII** | [[https://a2oj.com/register?ID=34998|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=34998| (Výsledky)]] | | **CELKEM** | ZS 2017 | **Průběžný stav** | [[https://docs.google.com/spreadsheets/d/1pVNBUdps0Db98mm42YwSM1Xws2fv4Z61qPwC6x-0jqE/edit?usp=sharing|Tabulka]] | ---- Výsledky mimo a2oj https://docs.google.com/spreadsheets/d/1wVWH31wBLCZieYniuBHBZRmYA69n8963iGUDRNyZNxs/edit?usp=sharing ===== Seminář 1 ===== ---- ==== Provoz a administrace ==== ---- === 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 === * Odevzdejte libovolnou úlohu (klidně prázný soubor). * Přejděte na stránku **[[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&Itemid=19|Live Archive: Posledních 50 Odevzdání]]** * Najděte řádku přislušící vaší odevzdané úloze a klikněte na své uživatelské jméno. * V parametrech URL naleznete své __userid__. === Test odevzdávacího systému === Po vytvoření účtů se můžete registrovat do soutěže na A2 Online Judge, klikněte [[http://a2oj.com/register?ID=28239|zde]]. ---- ==== Tématické přehledy a úlohy ==== ---- [[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 }} [[https://en.wikipedia.org/wiki/Dot_product|Dot product - Skalární součin]] ==== Ukázkové úlohy k základnímu ovládání grafů ==== V první části semináře si zopakujeme standardní grafové úlohy řešitelné pomocí algoritmu prohledávání do hloubky, a to zejména ulohy: * [[http://www.geeksforgeeks.org/detect-cycle-undirected-graph/|Detekce cyklu v grafu]] * [[http://www.geeksforgeeks.org/topological-sorting/|Nalezení topologického uspořádání vrcholů v grafu]] * [[http://www.geeksforgeeks.org/bridge-in-a-graph/|Identifikace mostů.]] (*_*_*) * [[http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/|Identifikace artikulací]] (*_*_*) * [[http://www.geeksforgeeks.org/biconnected-components/|Detekce bloků, tj. 2-souvislých komponent]] * [[http://www.geeksforgeeks.org/strongly-connected-components/|Nalezení silně souvislých komponent]] Dále: {{:courses:a4b36acm:2016_zs:grafy-ulohy.pdf| Tabulky grafových úloh a složitostí }} {{:courses:a4b36acm:2017_zs:mst3.pptx|Poznámky k minimálním kostrám }} [[http://wikistack.com/all-pair-shortest-path-floyd-warshall-algorithm/|Floyd-Warshall algorithm example]] [[https://www-m9.ma.tum.de/graph-algorithms/spp-bellman-ford/index_en.html#tab_ta|Bellman-Ford algorithm demo]] ===== Seminář 2: Grafové algoritmy ===== ---- **Náměty pro pokročilejší řešitele:** **Přehledy -- Maximální tok a párování ** [[http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/ | Geeksforgeeks - Ford-Fulkerson Max flow ]] [[http://www.geeksforgeeks.org/maximum-bipartite-matching/ | Geeksforgeeks - Maximum bipartite matching ]] [[https://github.com/jaehyunp/stanfordacm/tree/master/code| Stanford Code ]] **Úlohy** [[http://www.spoj.com/problems/TAXI/|TAXI]] [[http://www.spoj.com/problems/MATCHING/|MATCHING]] [[http://www.spoj.com/problems/COCONUTS/|COCONUTS]] [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2334|4333 - Paper Presentation]] [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=685&page=show_problem&problem=1986|11045 - My T-shirt suits me]] ===== Seminář 3: ===== Ulohy na nejkratsi cesty a min. kostry: * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1310|10369 - Arctic Network]] - upraveny Kruskal ci dfs + binarni puleni * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1187|10246 - Asterix and Obelix]] - Floyd-Warshall + post-processing * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1210|10269 - Adventure of Super Mario]] - netrivialni Dijsktra * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=40|104 - Arbitrage]] - klasicka uloha na detekci negativniho/positivniho cyklu A na dfs a spol: * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=251|315 - Network ]] Artikulace * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=737|796 - Critical Links]] Mosty * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=551|610 - Street Directions]] Mosty * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2499|11504 - Dominos ]] Silně souvislé komponenty * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1451|10510 - Cactus ]] Silně souvislé komponenty Reference: * [[http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/|Kruskaluv algoritmus]] * [[http://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/|Floyd-Warshalluv algoritmus]] * [[http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/|Dijkstruv algoritmus]] * [[http://www.geeksforgeeks.org/detect-negative-cycle-graph-bellman-ford/|Bellman-Forduv algoritmus]] * [[http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/|DFS pro hledani artikulaci]] * [[http://www.geeksforgeeks.org/bridge-in-a-graph/|DFS pro hledani mostu]] * [[http://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/|DFS pro hledani silne souvislych komponent]] ===== Seminář 5: DP I ===== Přehledy a pár jednodušších úloh. * [[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) }} Ukázky k vyzkoušení si: * [[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 * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1022|10081 - Tight Words]] * [[http://www.spoj.com/problems/FARIDA/|FARIDA - Princess Farida]] * [[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://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=929|Many Paths, One Destination]] * [[http://www.spoj.com/problems/SUBP/|Subsequence Problem]] * [[http://www.spoj.com/problems/BABTWR/|Tower of Babylon]] * [[http://www.spoj.com/problems/WACHOVIA/|Wachovia Bank]] * [[http://www.spoj.com/problems/MFISH/|Catch Fish]] * [[http://www.spoj.com/problems/GCJ1C09C/|Bribe the Prisoners]] * [[http://www.spoj.com/problems/BORW/|Black or White]] [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm/2016_zs/code#elementary_dag_manipulation| Ukázka kódu -- manipulace s DAG]] Ad FFT: Přehled a výklad: [[https://turing.cz/tom/pruvodce/17-fft|- FFT: Kap. 17. na stránkách T.Vally]], [[https://knihy.nic.cz/files/edice/Pruvodce_labyrintem_algoritmu.pdf|Pruvodce_labyrintem_algoritmu- celá kniha]] * [[http://www.spoj.com/problems/MUL/|MUL - Fast Multiplication]] * [[http://www.spoj.com/problems/POLYMUL/|POLYMUL - Polynomial Multiplication]] * [[http://www.spoj.com/problems/MAXMATCH/|MAXMATCH - Maximum Self-Matching]] * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=4744|12879 - Golf Bot]] * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=4791|1718 - Tile Cutting]] * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=4929|1733 - Design New Capital]] ===== Seminář 7 - 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]] Vyzkoušejte si: * http://www.spoj.com/problems/AMR11E/ * http://www.spoj.com/problems/APS/ * http://www.spoj.com/problems/LCMSUM/ ===== Seminář 9 - Geometrie / segm. stromy ===== Pokročilí: **Segmentové stromy** (pro někoho částečné opakování) Popsány pěkně v [[http://pruvodce.ucw.cz/static/pruvodce.pdf|průvodci]], kap. 4.5. (není dlouhá :-) ) Také v kuchařce KSP: [[http://ksp.mff.cuni.cz/study/cooks/cookbook-chapters/16-intervalove-stromy.pdf|Intervalové stromy]]. Rozšířené ukázky: https://cw.fel.cvut.cz/wiki/courses/a4b36acm/2017_ls/seminare#seminar_10segmentove_stromy_pokrocili Úlohy k vyzkoušení: * [[http://www.spoj.com/problems/QUERYIT/|QUERYIT - SLIS]] * [[http://www.spoj.com/problems/NDS/|NDS - Increasing numbers]] * [[http://www.spoj.com/problems/GSS1/|GSS1 - Can you answer these queries I]] * [[http://www.spoj.com/problems/GSS3/|GSS3 - Can you answer these queries III]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2176|11235 - Frequent values]] ===== Seminář 11 - Opáčko a řetězce ===== Řetězcové (hledací v řetězcích) úlohy pro pokročilce a klidně i základníky: * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=396|455 - Periodic Strings]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=843|902 - Password Search]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1620|10679 - I Love Strings!!]] * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1960|11019 - Matrix Matcher]] * [[http://www.spoj.com/problems/FILRTEST/|FILRTEST - File Recover Testing]] * [[http://www.spoj.com/problems/NHAY/|NHAY - A Needle in the Haystack]] * [[http://www.spoj.com/problems/PERIOD/|PERIOD - Period]] * [[http://www.spoj.com/problems/SUB_PROB/|SUB_PROB - Substring Problem]] KMP code: http://www-igm.univ-mlv.fr/~lecroq/string/node8.html Aho-Corasick code: http://www.geeksforgeeks.org/aho-corasick-algorithm-pattern-searching/ ===== Seminář 13 - Kombinatoricke hry ===== Materiály pro dnešní cvičení: [[courses:a4b36acm:kombinatoricke_hry|]]