**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.** | **6.10.** (4) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání | [[https://a2oj.com/standings?ID=28239| Úlohy a výsledky na A2OJ ]] | | **2.** | **13.10** (2) | Průchody grafem | | | **3.** | **20.10.** (4) |** Minisoutěž I** | [[https://a2oj.com/standings?ID=28483|Úlohy a výsledky na A2OJ]] \\ [[http://contest.felk.cvut.cz/16prg/rank.html|CTU Open výsledky ]] | | **4.** | **27.10.** (2) | DP I | | | **5.** | **3.11.** (4) |** Minisoutěž II** | [[https://a2oj.com/standings?ID=28758|Úlohy a výsledky na A2OJ]] \\ [[https://docs.google.com/a/fel.cvut.cz/spreadsheets/d/1ed5eH0hbSjIn0HCr3k54b61P7LW_OrsaDkjIDGV6wYA/edit?usp=sharing|Prubezny stav]] | | **6.** | **10.11.** (2) | Pokračování DP plus grafy | | | //7.// | //17.11. (4)// | //odpadá, státní svátek// | | | **8.** | **24.11.** (2) | Aritmetika a kombinatorika, teorie čísel | | | **9.** | **1.12** (4) |** Minisoutěž III** | [[https://a2oj.com/standings?ID=29154|Úlohy a výsledky na A2OJ]] | | **10.** | **8.12.** (2) | Výpočetní geometrie, mřížky | | | **11.** | **15.12.** (4) | **Minisoutěž IV** | [[https://a2oj.com/standings?ID=29329| Úlohy a výsledky na A2OJ]] | | **12.** | **22.12** (2) | Anatgonistické hry, Nim | | | **13.** | **5.1.** (4) | **Minisoutěž V** | [[https://a2oj.com/standings?ID=29509|Úlohy a výsledky na A2OJ]] | | **14.** | **12.1.** (2) | Opakování a doplnění restů | | | **CELKEM** | ZS 2016 | **Průběžný stav** | [[https://docs.google.com/spreadsheets/d/1EyJpIpg-mUnzD2f688rg6CqJmQ38Uvq0jsH6zCNXGK8/edit?usp=sharing| tabulka ]] | ---- **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 }} Další úlohy pro zájemce nebo domácí studium: * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=400|459 - Graph Connectivity]] * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2682|11635 - Hotel booking]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=60|Following Orders]] * [[http://www.spoj.com/problems/CATM/|CATM - The Cats and the Mouse]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2733|11686 - Pick up sticks]] * [[http://www.spoj.com/problems/TFRIENDS/|TFRIENDS - True Friends]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=40|104 - Arbitrage]] * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=762|821 - Page Hopping]] * [[http://www.spoj.com/problems/CERC07K/|CERC07K - Key Task]] * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2671|11624 - Fire!]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=132|Spreadsheet]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=499|558 - Wormholes]] ==== 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 [[http://a2oj.com/register?ID=28239|zde]]. ===== Seminář 2: Grafové algoritmy ===== 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/topological-sorting/|Nalezení (libovolného) topologického uspořádání vrcholů v grafu.]] * [[http://www.geeksforgeeks.org/strongly-connected-components/|Nalezení silně souvislých komponent.]] * [[http://www.geeksforgeeks.org/bridge-in-a-graph/|Identifikování mostů.]] (*_*_*) * [[http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/|Identifikování artikulací.]] (*_*_*) Dále: {{:courses:a4b36acm:2016_zs:grafy-ulohy.pdf| Tabulky grafových úloh a složitostí }} {{:courses:a4b36acm:2016_zs:mst2.pdf| 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ář 3: Grafové algoritmy - minisoutěž ===== COntest na A2OJ: https://a2oj.com/contest?ID=28483 Seznam úloh: * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=1310|10369 - Arctic Network]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=159&page=show_problem&problem=2678|11631 - Dark roads]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=513|572 - Oil Deposits]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=164&page=show_problem&problem=870|929 - Number Maze]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=383&page=show_problem&problem=364|423 - MPI Maelstrom]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=216|280 - Vertex]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=136|200 - Rare Order]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2499|11504 - Dominos]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1351|10410 - Tree Reconstruction]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1867|10926 - How Many Dependencies?]] ===== Seminář 4: DP I ===== Ilustrační jednodušší 1D varianty DP úloh * [[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]] * {{:courses:a4b36acm:2016_zs:ukazkaprez.pdf| Voda v rourách}} * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1803|10862 - Connect the Cable Wires]], čím se liší od Vody v rourách? * [[http://www.spoj.com/problems/FARIDA/| FARIDA, Princess Farida - max sum with limitations]] * [[http://www.spoj.com/problems/MMAXPER/| MMAXPER, Rectangles Perimeter - max upper envelope length]] * {{: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://cw.fel.cvut.cz/wiki/courses/a4b36acm/2016_zs/code#elementary_dag_manipulation| Ukázka kódu -- manipulace s DAG]] ===== Seminář 6: DP II ===== Základní úloha "lámání klacku" [[https://uva.onlinejudge.org/external/100/p10003.pdf|10003 - Cutting Sticks]] DP lze řešit pomocí Excelu {{:courses:a4b36acm:2016_zs:uva10081_table.xlsx| 10081 - Tight Words}} ===== Seminář 8 - Aritmetika a kombinatorika, teorie čísel ===== Dnešní téma: Aritmetika, Kombinatorika a 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=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}} * [[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]] * [[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://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]] ===== Seminář 10 - Geometrie ===== **{{:courses:a4b36acm:2016_zs:geombas1.pptx| Některé základní výpočty }}** **[[https://en.wikipedia.org/wiki/Intersection_(Euclidean_geometry)| Počítání průsečíků]]** **[[https://en.wikipedia.org/wiki/List_of_trigonometric_identities|Reminder: Trigonometric identities]]** **[[https://en.wikipedia.org/wiki/Pick's_theorem|Pick's_theorem]]** http://jwilson.coe.uga.edu/emat6680fa05/schultz/6690/pick/pick_main.htm **Všeobecný přehled na MFF** (Programátorské kuchařky) http://ksp.mff.cuni.cz/tasks/24/cook5.html\\ **Seznamy geometrických kreslítek** https://en.wikipedia.org/wiki/List_of_interactive_geometry_software#2D_programs, http://mathforum.org/geometry/geometry.software.html **Kreslítko GeoGebra online** http://www.geogebra.org/ **Polygon area** example: https://www.mathsisfun.com/geometry/area-irregular-polygons.html, code: http://www.codeproject.com/Articles/13467/A-JavaScript-Implementation-of-the-Surveyor-s-Form **Sweep line example** {{:courses:a4b36acm:2016_ls:sweepline.pptx| Touching rectangles }} **Graham Scan** demo: http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/GrahamScan.html \\ code: http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/\\ Stanford examples: http://web.stanford.edu/class/cs97si/ **Ideas_in_Geometry** https://en.wikiversity.org/wiki/Ideas_in_Geometry/Area **Cyclic quadrilateral**, https://en.wikipedia.org/wiki/Cyclic_quadrilateral **Sweep line rotates:**, http://www.spoj.com/problems/CERC07C/ (*_*_*){{:courses:a4b36acm:2016_zs:spojcerc07c.pptx| komentář }} ===== Seminář 12 - Kombinatorické hry ===== viz. [[courses:a4b36acm:maraton2016|ACM Maraton 2016]]