**Místo a čas konání** **Místo a čas konání** T2:C2-84, čtvrtek od 16:15. [[https://www.fel.cvut.cz/cz/education/rozvrhy-ng.B191/public/html/predmety/21/98/p2198806.html|Rozvrh FEL]] ===== Rozvrh ===== ^ Seminář \\ (hodiny) ^ Datum ^ Náplň ^ Úlohy/odkazy/prezentace \\ viz také pod tabulkou ^ | **1.**(2) | **26.9.** (2) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání, \\ dohoda témat se začátečníky a pokročilými účastníky | [[https://a2oj.com/register?ID=40649|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=40649| (Výsledky)]]\\ [[https://a2oj.com/register?ID=40650|pokročilé náměty na A2OJ]] [[https://a2oj.com/standings?ID=40650| (Výsledky)]]| | **2.**(4) | **3.10** | Průchody grafem ** Minisoutěž I** ... | [[https://a2oj.com/register?ID=40701|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=40701| (Výsledky)]]\\ [[https://a2oj.com/register?ID=40702| mírně(!) pokročilé náměty na A2OJ]] [[https://a2oj.com/standings?ID=40702| (Výsledky)]] | | **3.**(2) | **10.10.**(2) | Nejkratší cesty, aplikace dfs | | | **4.**(4) | **17.10.** | Grafové algoritmy **Minisoutěž II** | [[https://a2oj.com/register?ID=40815|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=40815| (Výsledky)]]\\ [[https://a2oj.com/register?ID=40816| pokročilejší náměty na A2OJ]] [[https://a2oj.com/standings?ID=40816| (Výsledky)]] | | **5.**(2) | **24.10.** | Dynamické programování I | | | **6.**(4) | **31.10.** | Dynamické programování II **Minisoutěž III** | [[https://a2oj.com/register?ID=40907|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=40907| (Výsledky)]]\\ [[https://a2oj.com/register?ID=40908| pokročilejší náměty na A2OJ]] [[https://a2oj.com/standings?ID=40908| (Výsledky)]]| | **7.**(2) | **7.11.** | Kombinatorika, teorie čísel, byly spíše komentáře k DP | | | **8.**(4) | **14.11.** | Základní: stále DP, Pokročilí: Kombinatorika, teorie čísel **Minisoutěž IV** | [[https://a2oj.com/register?ID=40958|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=40958| (Výsledky)]]\\ [[https://a2oj.com/register?ID=40957| pokročilejší náměty na A2OJ]] [[https://a2oj.com/standings?ID=40957| (Výsledky)]] | | **9.**(2) | **21.11** | Kombinatorika, teorie čísel | | **10.**(4) | **28.11.** | Kombinatorika, teorie čísel **Minisoutěž V** | [[https://a2oj.com/register?ID=40988|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=40988| (Výsledky)]]\\ [[https://a2oj.com/register?ID=40987| pokročilejší náměty na A2OJ]] [[https://a2oj.com/standings?ID=40987| (Výsledky)]] | | **11.**(2) | **5.12.** | Geometrie. Opakování, DP, MST, hledání v textu, různé | | | **12.**(4) | **12.12** | Geometrie **Minisoutěž VI** | [[https://a2oj.com/register?ID=41008 |Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=41008| (Výsledky)]]\\ [[https://a2oj.com/register?ID=41009| pokročilejší náměty na A2OJ]] [[https://a2oj.com/standings?ID=41009| (Výsledky)]] | | **13.**(2) | **19.12.** | Kombinatoricke hry | | | **14.**(4) | **9.1.** | Kombinatoricke hry **Minisoutěž VII** | A2OJ skončil, společné zadání úloh viz dole na stránce | | **CELKEM** | ZS 2017 | **Průběžný stav** | [[https://docs.google.com/spreadsheets/d/1TZ-fRCY3lfYGXjTe3uMDVQle7suLD_HDLgEIPmgXpiM/edit?usp=sharing |Tabulka]] | ---- ===== 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 na odkaz nahoře v prvním řádku tabulky. ---- ==== Tématické přehledy a úlohy ==== ---- **Začátečníci:** Steven S. Skiena, Miguel A. Revilla: [[http://acm.cs.buap.mx/downloads/Programming_Challenges.pdf]] \\ ''Klasický úvod a komentář ke cca 100 vybraným úlohám z UVA Online Judge, i s nezbytnými teoretickými souvislostmi.''\\ [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm/trenink?&#jak_na_reseni| Návodník na řešení ]] [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm1/intro_basic|Ukázka kompletního řešení a odevzdání]] ===== --------------------------------------------------------------------------------- ===== ===== Později: ===== ==== Seminář 2 a 3 ==== 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 }} * [[https://www.geeksforgeeks.org/detect-negative-cycle-graph-bellman-ford/|Bellman-Ford]] * [[https://www-m9.ma.tum.de/graph-algorithms/spp-bellman-ford/index_en.html#tab_ta|Bellman-Ford algorithm demo]] * [[https://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/|Floyd-Warshall]] Č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 }} ==== Seminář 4 ==== V kterési úloze se může hodit: https://www.geeksforgeeks.org/2-satisfiability-2-sat-problem/ ==== Seminář 5 Dynamické programování (odpadá ... samostudium...) ==== **1.**\\ https://www.geeksforgeeks.org/dynamic-programming/ (ukázky a příklady). Server GeeksForGeeks mivá přehledná a jednoduchá vysvětlení, nezatížená akademickou abstrakcí. Projděte ukázky a vyzkoušejte si některé příklady, je jich tam přes 300. V příkladech bývá rovněž vysvětlené řešení, což dost pomáhá. **2.**\\ http://pruvodce.ucw.cz/ V Průvodci labyrintem algoritmů je kapitola 12 o dynamickém programování.\\ Je to jeden z nejlepších českých učebních textů v informatice, vyplatí se alespoň zkusit si ho přečíst. ===== Seminář 7: Dynamické programování ===== Ukázky typických postupů a úloh * {{ :courses:a4b36acm2:2018_ls:dag.pdf | Základní všechno možné průchodem DAG }} * [[https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/|LIS na GeeksforGeeks ]] * [[https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/| GeeksForGeeks - Nejdelší společná podposloupnost (LCS - Longest Common Subsequence]]\\ * [[https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/| GeeksForGeeks (Knapsack Problem) Problém batohu 0-1 varianta ]]\\ * [[https://www.geeksforgeeks.org/unbounded-knapsack-repetition-items-allowed/| GeeksForGeeks (Knapsack Problem) Neomezená varianta ]]\\ * {{ :courses:a4b36acm2:2018_ls:lisnlogn.pdf | LIS - 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]] Některé kanonické úlohy DP * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1133|UVA -- 10192 - Vacation]]\\ * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1007|UVA -- 10066 - The Twin Towers]]\\ * [[https://www.spoj.com/problems/AIBOHP/|SPOJ -- AIBOHP - Aibohphobia]]\\ * [[https://www.spoj.com/problems/ADFRUITS/|SPOJ -- ADFRUITS - Advanced Fruits]]\\ * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=503|UVA -- 562 - Dividing coins]]\\ * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=931|UVA -- 990 - Diving for Gold]]\\ * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1760|UVA -- 10819 - Trouble of 13-Dots]]\\ * [[https://www.spoj.com/problems/PIGBANK/|SPOJ -- PIGBANK - Piggy-Bank]]\\ * [[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=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]] ===== Seminář 9: 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/ ===== Seminář 11: 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/ (Namely: http://web.stanford.edu/class/cs97si/09-computational-geometry.pdf ) **Sweep line rotates:**, http://www.spoj.com/problems/CERC07C/ (*_*_*) {{ :courses:a4b36acm2:2018_ls:spojcerc07c.pptx | komentář }} **Rotate points instead of lines** [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=6280| 8258 - Glyph Recognition]] ({{ :courses:a4b36acm1:2019_ls:glyphs.pptx | solution idea}}) **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ář 12: Geometrie ===== Zalozni seznam: Cisla jsou na Uva , jinak SPOJ * 121 - Pipe Fitters * 356 - Square Pegs And Round Holes * 10078 - The Art Gallery * 10387 - Billiard * 11232 - Cylinder * 11355 - Cool Points * 11639 - Guard the Land * 11648 - Divide The Land * 11796 - Dog Distance * https://www.spoj.com/problems/AE5B1/ * https://www.spoj.com/problems/KPPOLY/ * https://www.spoj.com/problems/QUADAREA/ ===== 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. * ===== Seminář 14 - Kombinatorické hry a trochu všehochuť ===== **Minisoutěž VII** Začátečnící i pokročilí jsou tentokrát sloučeni do jedné sady, každý si musí vhodně vybrat. - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1078|10137 The Trip]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1519|E10578 The Game of 31]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1561|10620 A flea on a chessboard]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2286|11311 - Exclusively Edible]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2661|11614 Etruscan Warriors Never Play Ches]] - [[https://www.spoj.com/problems/DANGER/|DANGER - In Danger]] - [[https://www.spoj.com/problems/EQBOX/|EQBOX - Equipment Box]] - [[https://www.spoj.com/problems/GAME2/|GAME2 - Looks like Nim - but it is not]] - [[https://www.spoj.com/problems/HC/|HC - Happy Coins]] - [[https://www.spoj.com/problems/IITKWPCN/|IITKWPCN - Playing With Balls]] - [[https://www.spoj.com/problems/KMOVES/|KMOVES - Knight Moves]] - [[https://www.spoj.com/problems/MCOINS/|MCOINS - Coins Game]] - [[https://www.spoj.com/problems/NOTATRI/|NOTATRI - Not a Triangle]] - [[https://www.spoj.com/problems/PALNUM/|PALNUM - Palindromic Number]] - [[https://www.spoj.com/problems/SHAKTI/|SHAKTI - SHAKTIMAN AND KILWISH]] - [[https://www.spoj.com/problems/TWENDS/|TWENDS - Two Ends]]