**Místo a čas konání** T2:C2-84, čtvrtek od 16:15. [[https://www.fel.cvut.cz/cz/education/rozvrhy-ng.B172/public/html/predmety/21/98/p2198806.html|Rozvrh FEL]] [[https://cw.fel.cvut.cz/old/courses/a4b36acm/start| Staré stránky - přehlednější ]] ===== Semináře ===== ^ Seminář ^ Datum \\ (hodiny) ^ Náplň ^ Úlohy/odkazy/prezentace \\ viz také pod tabulkou ^ | **1.** | **22.2.** (4) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání | [[https://a2oj.com/register?ID=35564|Registrace na A2OJ]] a [[https://a2oj.com/standings?ID=35564|Výsledky]] \\ Pokročilí : [[https://a2oj.com/standings?ID=35566|Výsledky]] | | **2.** | **1.3** (2) |Průchody grafem | | | **3.** | **8.3.** (4) |** Minisoutěž I** | Základní: [[https://a2oj.com/standings?ID=35777|Výsledky]] \\ Pokročilí : [[https://a2oj.com/standings?ID=35779|Výsledky]] | | **4.** | **15.3.** (2) |Grafy a nejkratší cesty | | | **5.** | **22.3.** (4) |** Minisoutěž II** | Společná soutěž s FIT: [[https://a2oj.com/standings?ID=35946|Výsledky]] | | **6.** | **29.3.** (2) |Dynamické programování | | | **7.** | **5.4.** (4) | ** Minisoutěž III** | Základní: [[https://a2oj.com/standings?ID=36117|Výsledky]] \\ Pokročilí : [[https://a2oj.com/standings?ID=36118|Výsledky]] | | **8.** | **12.4.** (2) |Aritmetika a kombinatorika, teorie čísel | | | **9.** | **19.4** (4) |**Minisoutěž IV** \\ 2 b za doma do 27.4. | DP: [[https://a2oj.com/standings?ID=36300|Výsledky]] \\ čísla : [[https://a2oj.com/standings?ID=36301 |Výsledky]] | | **10.** | **26.4.** (2) |Výpočetní geometrie, mřížky | | | **11.** | **3.5.** (4) | **Minisoutěž V** | Společná soutěž s FIT | | //12.// | //10.5.// (2) |Anatgonistické hry, Nim | | | **13.** | **17.5.** (4) | //odpadá, úterní rozvrh // | | | **14.** | **24.5.** (2) |Toky v sítích nebo dodělávky podle potřeby | | | **CELKEM** | ZS 2017 | **Průběžný stav** | [[https://docs.google.com/spreadsheets/d/1CJcdJ9Sz8UTSF5J55H2iAULgBaFwvfGeFc0WL4PNehU/edit?usp=sharing|Zde je 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 [[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í ]] {{https://cw.fel.cvut.cz/old/_media/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: {{https://cw.fel.cvut.cz/old/_media/courses/a4b36acm/2016_zs/grafy-ulohy.pdf| Tabulky grafových úloh a složitostí }} {{https://cw.fel.cvut.cz/old/_media/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 ===== ===== Seminář 4: 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 }} [[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]] ( [[https://www.geeksforgeeks.org/topological-sorting-using-departure-time-of-vertex/| topsort by DFS]]) [[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. * [[https://cw.fel.cvut.cz/wiki/_media/courses/a4b36acm/2013_ls/dp.pdf|Ukázky klasických úloh TT&MB]] * {{ :courses:a4b36acm2:2018_ls:ukazkaprez3.pdf | Voda v rourách}} * {{ :courses:a4b36acm2:2018_ls:dag.pdf | Základní všechno možné průchodem DAG }} * {{ :courses:a4b36acm2:2018_ls: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/a4b36acm2/2016_zs/code#elementary_dag_manipulation| Ukázka kódu -- manipulace s DAG]] ===== Seminář 8: Dynamické programování II (přeteklo ze semináře 6) ===== Typické a klasické úlohy vedoucí na 2D tabulku DP: * Základní úloha "lámání klacku" : [[https://uva.onlinejudge.org/external/100/p10003.pdf|10003 - Cutting Sticks]] * Analogickou strukturu má optimální pořadí násobení matic: https://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/ * Klasické plnění batohu (Knapsack problem) * https://www.geeksforgeeks.org/knapsack-problem/ * {{ :courses:a4b36acm2:2018_ls:batoh01.pdf | příklad z ALG }} * Nejdelší společná podposloupnost (LCS - Longest Common Subsequence ) * https://www.geeksforgeeks.org/longest-common-subsequence/ * {{ :courses:a4b36acm2:2018_ls:lcs.pdf | příklad z ALG }} ===== 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\\ **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:a4b36acm2:2018_ls:sweeplinexx.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:a4b36acm2:2018_ls:spojcerc07c.pptx | komentář }}