===== Bakalář ===== ---- **Rozvrh denně dopoledne 9.00 - 11.45, odpoledne 12.30 - 14.30, 14.45 - 16.00.** \\ // Úpravy možné po dohodě s lektorem.// **Učebna E-126 v areálu FEL ČVUT na Karlově náměstí.** \\ ---- ____________________________________________________________________________________________ ==== Pondělí 12.9. dopoledne a odpoledne ==== //Vedou a asistují// **Petr Ryšavý, Adam Jáneš**\\ \\ ===Orientovaný acyklický graf (DAG), optimální cesty v DAG.. === **Prezentace:** - {{courses:laso2022:20220912_dp_in_dags.pdf|Slidy}}, - dále {{courses:laso2017:dag.pptx|Cesty v acyklickém grafu }}, ({{courses:laso2017:dag.pdf| pdf}}} **Další zdroje** * {{ :courses:laso2019:dag_topsort.pptx | Topsort, jednoduchá ukázka}} * [[https://www.cs.usfca.edu/~galles/visualization/TopoSortIndegree.html| Animace -- Topsort pomocí snižování vstupních stupňů]] * [[https://www.cs.usfca.edu/~galles/visualization/TopoSortDFS.html| Animace -- Topsort pomocí DFS]] **Úlohy (DAG):** - https://projecteuler.net/problem=15 {{ :courses:laso2016:euler_p015.gif?150 |}} - https://projecteuler.net/problem=18 {{ :courses:laso2016:euler_p018.gif |}} - https://projecteuler.net/problem=67 {{ :courses:laso2016:euler_p067.gif?300 |}} - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1246|10305 - Ordering Tasks]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=867|926 - Walking Around Wisely]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=143&page=show_problem&problem=2078|11137 - Ingenuous Cubrency]] - [[http://www.spoj.com/problems/COINS/|COINS - Bytelandian gold coins]] - https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=longslopes2 {{ :courses:laso2016:img1.png?300 |}} - https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=increasingload {{ :courses:laso2016:img1_load.png?200 |}} ===Párování v bipartitních grafech=== **Prezentace:** - {{courses:laso2022:20220912_bipartite_matching.pdf|Bipartitní párování}} **Úlohy (Bipartitní párování):** - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1986|11045 - My T-shirt suits me]] - [[https://uva.onlinejudge.org/index.php?Itemid=8&option=com_onlinejudge&page=show_problem&problem=1033|10092 - The Problem with the Problem Setter]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1021|10080 - Gopher II]] ____________________________________________________________________________________________ ==== Úterý 13.9. dopoledne ==== //Vedou a asistují// **Petr Ryšavý, Adam Jáneš**\\ . === DFS s časovými značkami, silně souvislé komponenty === **Poučení** * {{ :courses:laso2022:20220913_sccs.pdf | Silně souvislé komponenty }} * {{ :courses:laso2019:dfs.pptx | DFS s časovými značkami }} * [[https://www.geeksforgeeks.org/strongly-connected-components/|Kosaraju-Sharir algoritmus na Geeks for Geeks]] * [[https://www.cs.usfca.edu/~galles/JavascriptVisual/ConnectedComponent.html|Kosaraju-Sharir řiditelná animace]] * [[https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/|Tarjanův algoritmus na Geeks for Geeks]] * **Úlohy** * [[https://www.spoj.com/problems/WEBISL/|WEBISL - Web islands]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=377&page=show_problem&problem=183|247 - Calling Circles]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=377&page=show_problem&problem=2499|11504 - Dominos]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=377&page=show_problem&problem=2938|11838 - Come and Go]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=377&page=show_problem&problem=2870|11770 - Lighting Away]] * [[https://www.spoj.com/problems/CAPCITY/|CAPCITY - Capital City]] ____________________________________________________________________________________________ ==== Úterý 13.9. odpoledne ==== //Vedou a asistují// **Petr Ryšavý, Adam Jáneš**\\ . === Mosty, artikulace (cutvertices) === * {{ :courses:laso2022:20220913_articulation_bridges.pdf | Slidy }} **Ukázky**\\ Artikulace na GeeksForGeeks https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/ \\ Mosty GeeksForGeeks https://www.geeksforgeeks.org/bridge-in-a-graph/ \\ **Úložky**\\ * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=153&page=show_problem&problem=1140|10199 - Tourist Guide]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=153&page=show_problem&problem=251|315 - Network]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=153&page=show_problem&problem=737|796 - Critical Links]] * [[https://www.spoj.com/problems/SUBMERGE/|SUBMERGE - Submerging Islands]] * [[https://www.spoj.com/problems/EC_P/|EC_P - Critical Edges]] ____________________________________________________________________________________________ ==== Středa 14.9. dopoledne ==== //Vedou a asistují// **Dan Hubáček, Adam Jáneš**\\ . === Kombinatorické hry, jádro grafu === **Poučení**: * {{ :courses:laso2019:combigames.pptx | krok za krokem základní ukázka jednoduché hry}} * [[http://mks.mff.cuni.cz/library/JakHratANeprohratFH/JakHratANeprohratFH.pdf|(Všeobecné poučení o hrách a Nimu, výtah, česky)]] * [[http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames | TopCoder - The Basic Introduction into Games]] * Geeks for Geeks: [[https://www.geeksforgeeks.org/introduction-to-combinatorial-game-theory/| úvod ]] a [[https://www.geeksforgeeks.org/combinatorial-game-theory-set-2-game-nim/|elementární Nim]] **Příklady**: * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=1345|Bachet's 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/NGM/|A Game with Numbers]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=1309|10368 - Euclid's Game]] * [[https://www.spoj.com/problems/QCJ3/|QCJ3 - The Game]] * [[http://www.spoj.com/problems/MMMGAME/en/|M&M 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]] Příklady mají možná mírně rostoucí obtížnost, pro jistotu začněte s nimi od začátku. **Více odkazů pro vyložené zájemce**: * [[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://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/comb.pdf|Všeobecné poučení o hrách a Nimu 2]] * [[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]] * Nimbers (Sprague-Grundyho čísla) - ukázková úloha [[http://www.codechef.com/problems/BIGPIZA| Socializing Game around Pizza]] * [[http://www.fq.math.ca/Scanned/1-4/whinihan.pdf|Fibonacciho Nim]] ____________________________________________________________________________________________ ==== Středa 14.9. odpoledne ==== //Vedou a asistují// **Petr Ryšavý, Adam Jáneš**\\ . === Kostry === **Slidy:** {{courses:laso2022:20220914_MST.pdf|pdf}} **Ukázky**\\ Prim-Jarník https://www.cs.usfca.edu/~galles/visualization/Prim.html \\ Kruskal https://www.cs.usfca.edu/~galles/visualization/Kruskal.html \\ Union-find na GeeksForGeeks https://www.geeksforgeeks.org/union-find/ \\ Kruskal {{ :courses:laso2019:mst3.pptx | Efektivně krok po kroku }} **Úložky**\\ * [[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=378&page=show_problem&problem=975|10034 - Freckles]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1310|10369 - Arctic Network]] - upravený Kruskal či dfs + binární půlení * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=378&page=show_problem&problem=849|908 - Re-connecting Computer Sites]] * [[https://www.spoj.com/problems/IITWPC4I/|IITWPC4I - Petya and the Road Repairs]] **Jak na to?**\\ Pomůže Union-Find? [[https://www.spoj.com/problems/ONBRIDGE/|ONBRIDGE - Online Bridge Searching]]