===== Semináře ===== **Místo a čas konání** T2:C2-84, čtvrtek od 16:15. [[https://www.fel.cvut.cz/cz/education/rozvrhy-ng.B181/public/html/predmety/21/98/p2198806.html|Rozvrh FEL]] [[https://cw.fel.cvut.cz/old/courses/a4b36acm/start| Staré stránky - přehlednější ]] ===== Rozvrh ===== ^ Seminář \\ (hodiny) ^ Datum ^ Náplň ^ Úlohy/odkazy/prezentace \\ viz také pod tabulkou ^ | //1.// (4) | //4.10.// | // Odpadá pro nepřítomnost vyučujícího // | | | **2.** (2) | **11.10** | Základní přehled, dohoda témat se začínajícími i pokročilými účastníky. Servery, konta, cvičná odevzdání, viz úlohy níže pod tabulkou | | | **3.** (4) | **18.10.** | (Převážně) průchody grafem ** Minisoutěž I** |[[https://a2oj.com/register?ID=38013|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=38013| (Výsledky)]] \\ [[https://a2oj.com/register?ID=38011 |(Pokročilí - úlohy na A2OJ ]] [[https://a2oj.com/standings?ID=38011 | (Výsledky)]] | | **4.** (2) | **27.10.** | Nejkratší cesty, aplikace dfs | | | **5.** (4) | **1.11.** | Grafové algoritmy \\ **Minisoutěž II** |[[https://a2oj.com/register?ID=38138|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=38138| (Výsledky)]] \\ [[https://a2oj.com/register?ID=38139 |(Pokročilí - úlohy na A2OJ ]] [[https://a2oj.com/standings?ID=38139 | (Výsledky)]] | | **6.** (2) | **8.11.** | Dynamické programování I | | | **7.** (4) | **15.11.** | Dynamické programování II **Minisoutěž III** |[[https://a2oj.com/register?ID=38227|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=38227| (Výsledky)]] \\ [[https://a2oj.com/register?ID=38228|(Pokročilí - úlohy na A2OJ ]] [[https://a2oj.com/standings?ID=38228| (Výsledky)]] | | **8.** (2) | **22.11.** | //Odpadlo// | | | **9.** (4) | **29.11** | Dynamické programování **Minisoutěž IV**| [[https://a2oj.com/register?ID=38304|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=38304|(Výsledky)]] \\ [[https://a2oj.com/register?ID=38306|(Pokročilí - úlohy na A2OJ]] [[https://a2oj.com/standings?ID=38306|(Výsledky)]]| | **10.** (2) | **6.12.** | Kombinatorika, teorie čísel | | | **11.** (4) | **13.12.** | Kombinatorika, teorie čísel **Minisoutěž V** | [[https://a2oj.com/register?ID=38401|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=38401|(Výsledky)]] \\ [[https://a2oj.com/register?ID=38402|(Pokročilí - úlohy na A2OJ]] [[https://a2oj.com/standings?ID=38402|(Výsledky)]] | | **12.** (2) | **20.12** | Výpočetní geometrie | | | **13.** (2) | **3.1.** | Kombinatoricke hry | | | **14.** (4) | **10.1.** | Kombinatoricke hry **Minisoutěž VII** | [[https://a2oj.com/register?ID=38534|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=38534|(Výsledky)]] \\ [[https://a2oj.com/register?ID=38535|(Pokročilí - úlohy na A2OJ]] [[https://a2oj.com/standings?ID=38535|(Výsledky)]] | | **CELKEM** | ZS 2018 | **Průběžný stav** |[[https://docs.google.com/spreadsheets/d/1sz7PXqxY-P_fTrpSLyqcsDt9QnmK1niM76RtnsskRQA/edit?usp=sharing|Tabulka]] | ===== Seminář 1 ===== ===== Seminář 2 ===== ---- ==== 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]]. ---- ==== Úlohy pro ty, co jsou na semináři poprvé ==== === University of Valladolid (UVA) === [[http://uva.onlinejudge.org/|Online Judge]] * 120 - Stacks of Flapjacks[[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=56|Link]] * 138 - Street Numbers [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=74| Link]]. * 11461 - Square Numbers [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2456| Link]] \\ === Polský Sphere === [[http://www.spoj.com/| Sphere]] * 12880. Sheep [[http://www.spoj.com/problems/KOZE/|Link]] * 3979. Whirligig number [[http://www.spoj.com/problems/MZVRK/|Link]] * 178. Road net [[http://www.spoj.com/problems/ROADNET/|Link]] \\ === Live Archive na Baylor University === [[https://icpcarchive.ecs.baylor.edu/index.php| Live Archive ]] * 2052 - Number Steps [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=65&page=show_problem&problem=53| Link ]] * 2116 - The Mobius Function [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=79&page=show_problem&problem=117| Link ]] * 2202 - Vito's Family [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=70&page=show_problem&problem=203| Link]] \\ ==== Úlohy pro zkušené ==== [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=78|Sada 1]] a [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=262|Sada 2]] \\ Pozor, dvě nejlehčí úlohy v každé sadě se nezapočítávají! Jsou to 2061, 2062, 3392, 3498. Zbývá tak 11 úloh, ze kterých si vybírejte. ---- ===== Seminář 4: Nejkratší a nejdelší cesty v grafech ===== Čtěte průvodce: [[http://pruvodce.ucw.cz/|Průvodce labyrintem algoritmů]] Nejkratší a nejdelší cesty: * {{ :courses:a4b36acm2:2018_ls:grafy-cesty.pdf | nejkratší a nejdelší cesty -- celkový přehled }} * {{ :courses:a4b36acm2:2018_ls:dag.pdf | nejkratší a nejdelší cesty v DAG }} Aplikace prohledávání do hloubky: * [[https://www.geeksforgeeks.org/topological-sorting-using-departure-time-of-vertex/| topsort by DFS]] * [[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]] {{https://cw.fel.cvut.cz/old/_media/courses/a4b36acm/2017_zs/mst3.pptx|Poznámky k minimálním kostrám }} Všechny cesty: * [[https://www.geeksforgeeks.org/detect-negative-cycle-graph-bellman-ford/|Bellman-Ford]] * [[https://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/|Floyd-Warshall]] * [[http://wikistack.com/all-pair-shortest-path-floyd-warshall-algorithm/|Floyd-Warshall algorithm example]] [[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html|další vizualizace]] ===== Seminář 6: Dynamické programování I ===== Učební materiály a pár jednodušších úloh na doma. * {{ :courses:a4b36acm2:2018_ls:dag.pdf | Základní všechno možné průchodem DAG }} * [[https://cw.fel.cvut.cz/wiki/_media/courses/a4b36acm/2013_ls/dp.pdf|Ukázky klasických úloh TT&MB]] * [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm2/2016_zs/code#elementary_dag_manipulation| Ukázka kódu -- manipulace s DAG]] * {{ :courses:a4b36acm2:2018_ls:ukazkaprez3.pdf | Ukázka řešení -- Voda v rourách}} * {{ :courses:a4b36acm2:2018_ls:lisnlogn.pdf | LIS - nejdelší rostoucí podposloupnost v čase O(N log N) }} * [[https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/|LIS na GeeksforGeeks ]] * [[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]] ===== Seminář 8: Dynamické programování II ===== * Násobení Matic: https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/ * Řezání tyče: https://www.geeksforgeeks.org/cutting-a-rod-dp-13/ * Nejdelší společná podposloupnost (LCS): https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/ * Online výpočet LCS: https://www.cs.usfca.edu/~galles/visualization/DPLCS.html * Úloha batohu 0/1: https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/ * Úloha batohu neomezená: https://www.geeksforgeeks.org/unbounded-knapsack-repetition-items-allowed/ ===== Seminář 10: Kombinatorika, čísla, prvočísla ===== * [[https://math.feld.cvut.cz/habala/teaching/dma/dmknih11.pdf|Habalova kombinatorická skripta]]! * {{ :courses:a4b36acm2:2018_ls:primes.pptx | Prvočísla, Eratosthenovo síto a kód}} * Čísla různých druhu: * [[https://en.wikipedia.org/wiki/Combination|Kombinační]] * [[https://en.wikipedia.org/wiki/Fibonacci_number|Fibonacciho]] * [[https://www.geeksforgeeks.org/applications-of-catalan-numbers/|Catalanova]] , [[http://mathworld.wolfram.com/CatalanNumber.html|na Mathworld]] * **OEIS** Vynikající všeobecná referenční příručka [[https://oeis.org/|The On-Line Encyclopedia of Integer Sequences]] * Rychlé mocnění * https://www.geeksforgeeks.org/exponential-squaring-fast-modulo-multiplication/ * https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/ Ilustrační úlohy * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=934|993 - Product of digits]] * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1316|10375 - Choose and divide]] * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1176|10235 - Simply Emirp]] * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2262|11287 - Pseudoprime Numbers]] ===== Seminář 12 - Geometrie ===== **{{ :courses:a4b36acm2:2018_ls: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\\ **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:a4b36acm2:2018_ls:sweeplinexx.pptx | Touching rectangles}} **Graham Scan** demo: http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/GrahamScan.html (//enable java?//)\\ code: http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/\\ Stanford examples: http://web.stanford.edu/class/cs97si/ **Sweep line rotates:**, http://www.spoj.com/problems/CERC07C/ (*_*_*) {{ :courses:a4b36acm2:2018_ls:spojcerc07c.pptx | komentář }} **Množství komentovaných základních kódů** https://www.geeksforgeeks.org/geometric-algorithms/ **Kreslítko GeoGebra online** http://www.geogebra.org/ **Seznamy geometrických kreslítek** https://en.wikipedia.org/wiki/List_of_interactive_geometry_software#2D_programs, http://mathforum.org/geometry/geometry.software.html ===== Seminář 13 - Kombinatoricke hry ===== * [[http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/intro.pdf|Všeobecné poučení o hrách a Nimu]] [[http://mks.mff.cuni.cz/library/JakHratANeprohratFH/JakHratANeprohratFH.pdf|(výtah, česky)]] * [[http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames | TopCoder - The Basic Introduction into Games]] * [[http://teorie-grafu.cz/zakladni-pojmy/jadro-grafu.php | Jádro grafu]] * Teorie her na CMU - [[http://www.math.cmu.edu/~mlavrov/arml/12-13/games-02-10-13.pdf|Combinatorial Game Theory]],[[http://www.math.cmu.edu/~mlavrov/arml/12-13/games-02-24-13.pdf|Even More Games]] * Kombinatorické hry - krátká ilustrace {{ :courses:a4b36acm2:2018_zs:combigames.pdf | pdf}}. * Nimbers (Sprague-Grundyho čísla) - ukázková úloha ([[http://www.codechef.com/problems/BIGPIZA| Socializing Game around Pizza]], {{ :courses:a4b36acm2:2018_zs:pizza.pdf | kód? }}) * [[http://www.fq.math.ca/Scanned/1-4/whinihan.pdf|Fibonacciho Nim]] Příklady: * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=1345|Bachet's Game]] * [[http://www.spoj.com/problems/CLK/|Chomp]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=1309|Euclid's Game]] * [[http://www.spoj.com/problems/QCJ3/|The Game]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=2484|Integer Game]] * [[http://www.spoj.com/problems/MATGAME/|Matrix Game]] * [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=398&page=show_problem&problem=2824|Game]] * [[http://www.spoj.com/problems/QWERTY04/|TRIVIADOR]] * [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=3060|Playing With Stones]] * [[http://www.spoj.com/problems/MMMGAME/en/|M&M Game]] * [[http://www.spoj.com/problems/NGM/|A Game with Numbers]] * [[http://www.spoj.com/problems/PT07A/|Play with a Tree]]: How to tackle a problem of this sort was not covered in the lecture, but if you are interested, see [[http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf|Ferguson's Game Theory]] (lecture 6, specifically, the colon and fusion principles). * [[http://www.spoj.com/problems/BNWNIM/en/|Black and White Nim]]: Difficult, yet intriguing problem. *