===== Nováček ===== ---- ** Rozvrh denně //přibližně// dopoledne 9.00 - 11.45, odpoledne 12.30 - 14.30, 14.45 - 16.00.** \\ //. Úpravy možné po dohodě s lektorem.// ** Učebna: E-132** Budova E v areálu FEL ČVUT na Karlově náměstí. \\ ____________________________________________________________________________________________ ---- ==== Pondělí 12.9. dopoledne i odpoledne ==== Vede a na praktikách asistuje: **Jan Blaha** \\ . === Seznámení s grafovými úlohami === **Slidy:** {{:courses:laso2017:grafy_uvod.pptx| Úvodní grafový přehled}} ({{:courses:laso2017:grafy_uvod.pdf| pdf}}). **Vzorová úloha** Lokální zpracování a prohledávání grafu, bezprostřední okolí vrcholů grafu, typická úloha: počet trojúhelníků. ^ Graf na vstupu -- Formát dat ^ Data ^ Graf ^ | První řádek vstupu obsahuje dvě celá kladná čísla N a M oddělená mezerou představující po řadě počet uzlů a počet hran grafu. Předpokládáme, že uzly grafu jsou číslovány 0, 1, 2, ..., N−1.\\ Následuje M řádků, každý popisuje jednu hranu. Pokud graf není vážený, jsou na řádku dvě celá čísla oddělená mezerou -- čísla krajních uzlů hrany. Pokud je graf vážený, jsou na řádku tři celá čísla oddělená mezerou -- čísla krajních uzlů hrany a váha hrany.\\ Pořadí uzlů na řádku i pořadí hran na vstupu může být libovolné.| 7 13 4 0 5 0 0 6 3 4 4 2 4 6 3 5 6 3 1 6 4 1 5 6 1 5 0 3 | {{ :courses:laso2016:g3_1.jpg?150 |}} | **Úloha 1.** Načtěte nevážený graf ze souboru a vypište k každému uzlu jeho seznam hran. Stáhněte si {{:courses:laso2016:g1.zip| data s obrázky}}. **Úloha 2.** Načtěte vážený graf ze souboru a vypište k každému uzlu jeho seznam hran. Stáhněte si {{:courses:laso2016:g2.zip| data s obrázky}}. **Úloha 3.** V daném grafu zjistěte pro každý možný stupeň uzlu D, kolik je takových hran, jejichž oba koncové uzly mají tento stupeň D. Pro každý stupeň tento počet hran vypište. Porovnejte své výsledky s ukázkovými. Stáhněte si {{:courses:laso2016:g3.zip| data s obrázky}}. **Úloha 4.** Jindra vyrazí z uzlu A, který má určitý stupeň D. Pak jde do některého jeho sousedního uzlu B a nezajímá se o stupeň uzlu B. Z uzlu B se přesune do uzlu C, který je sousedem B a není to A. Jindra trvá na tom, že stupeň D startovního uzlu A i stupeň cílového uzlu C musejí být stejné. Určete, kolik je v daném grafu možností procházek podle Jindrových pravidel. Vypište toto jediné číslo na výstup. Stáhněte si {{:courses:laso2016:g4.zip| data s obrázky}}. **Úloha 5.** Řekneme, že hrana H je lokálně minimální, pokud její váha je striktně menší než váha kterékoli hrany, která s H sdíli jeden uzel. Najděte v daném váženém grafu všechny lokálně minimální hrany a vypište je v rostoucím lexikografickém pořadí jejich krajních uzlů. Stáhněte si {{:courses:laso2016:g5.zip| data s obrázky}}. **Úloha 6.** Určete, kolik je trojúhelníků v každém grafu úlohy 4. Trojúhelník je trojice uzlů, v níž každý uzel sousedí se zbylými dvěma uzly. {{courses:laso2017:counttriangles.java|vzorová implementace}} **Úloha 7.** Určete, kolik je kružnic délky 4 v každém grafu úlohy 4. Kružnice nesmí obsahovat příčku, tj. první a třetí uzel v kružnici nesmí spolu sousedit a druhý a čtvrtý uzel v kružnici spolu nesmí sousedit. **Další úložky:** * https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=769&page=show_problem&problem=5973 * http://codeforces.com/contest/813/problem/C * https://www.spoj.com/problems/MAKEMAZE/ * https://www.spoj.com/problems/ADASEA/ * https://www.spoj.com/problems/SPIKES/ * http://codeforces.com/contest/710/problem/E * http://codeforces.com/gym/101879/problem/C K těmto úložkám se lze vracet i později a slouží jako záchytný bod pro ty, kdo už vše zvládli nebo znají z dřívějška apod. Pokaždé je vhodné si úlohu maximálně rozmyslet bez klávesnice a formulovat abstraktně (v grafu daném tak a tak hledáme to či onou pomocí určité metody). Konzultace vlastních nápadů s kolegy (lektory) je doporučena. ____________________________________________________________________________________________ ==== Úterý 13.9. dopoledne ==== Vede a na praktikách asistuje: **Jan Blaha** \\ . === BFS a DFS (= Breadth-First Search a Depth-First Search), fronta a zásobník, BFS a vzdálenosti v grafu. === **Slidy:** {{:courses:laso2020:20200915_BSF_DFS_queue_stack.pdf| Prohledávání grafu }} - Stáhněte soubor s {{:courses:laso2016:20160920_data_laso_zac.zip| daty}}, se kterými budete pracovat. - Nalezněte výchozí implementaci zásobníku ve vašem oblíbeném jazyce. Poté načtěte soubor ''seq.txt''. Na každém řádku máte jeden z příkazů ''insert '' a ''remove''. Příkaz ''insert '' vloží číslo '''' do zásobníku. Příkaz ''remove'' odstraní prvek ze zásobníku a vypíše ho na standardní výstup. - [Dobrovolné] Sami naimplementujte zásobník a zopakujte úkoly z bodu 2. s vaší implementací. Zkontrolujte, že se výsledky shodují. - To samé jako 2., pouze použijte frontu. - [Dobrovolné] To samé jako 3., pouze implementujte frontu. - Načtěte graf ''graph.txt'' jako neorientovaný graf. Ten je definovaný ve stejném formátu jako včera. - Určete jaké vrcholy lze navštívit z vrcholu 0. Kolik jich je? - Jaká je délka nejkratší cesty z vrcholu 0 do vrcholu 7. - Kolik je komponent souvislosti v grafu? Komponenta souvislosti je množina vrcholů, že mezi každou dvojicí z nich vede cesta. Přitom platí, že do komponenty souvislosti již nelze přidat žádný další vrchol grafu tak, aby tato vlastnost zůstala zachována. Více detailů {{http://mathworld.wolfram.com/WeaklyConnectedComponent.html | zde}} a {{https://en.wikipedia.org/wiki/Connected_component_(graph_theory) | zde}}. - Nyní načtěte graf ''graph.txt'' jako orientovaný graf. - Zopakujte úkoly 7. a 8. (abychom zvládli 9. pro orientovaný graf, museli bychom umět buď {{https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm | Tarjanův algoritmus}} nebo {{https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm | Kosarajiho algoritmus}}) ____________________________________________________________________________________________ ==== Úterý 13.9. odpoledne ==== Vede a na praktikách asistuje: **Jan Blaha** \\ . === Prioritní fronta, halda. === **Slidy:** {{:courses:laso2020:20200915_heap.pdf| Prioritní fronta, halda }} **Poučení:** * [[https://www.cs.usfca.edu/~galles/visualization/Heap.html|Vizualizace]] * [[https://www.geeksforgeeks.org/binary-heap/|Ukázka na Geeks for Geeks]] **Úkoly:** - Zopakujte úkol 2. z rána, pouze místo zásobníku použijte haldu. Operaci ''remove'' chápejte jako ''extract-min''. - Zopakujte předchozí úkol, ale místo haldy použijte pole. Prvky přidávejte nakonec a při implementaci ''extract-min'' hledejte minimum naivně pomocí procházení celého pole. - Porovnejte časy běhu z kroků 1. a 2. - Naimplementujte //Median Maintenance//, o kterém jsme mluvili na přednášce. Jako vstup můžete použít čísla ze souboru ''seq.txt'', operace ''remove'' ignorujte. - Naimplementuje sami haldu. Zkuste dodržet kostru z {{:courses:laso2017:20170919_heap.zip|20170919_heap.zip}}. Zkuste poté použít vaší implementaci v předchozích úkolech a zkontrolujte, že dává stejné výsledky. - Zkontrolujte {{:courses:laso2017:20170919_solutions.zip | výsledky}}. Můžete se podívat také na implementaci. Kódy z roku 2019 v Pythonu jsou k dispozici {{:courses:laso2019:20190917solutions_python.zip | zde}}, také z {{:courses:laso2020:20200915_solutions.zip | roku 2020}}. **Další úlohy:** https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3644 https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1895 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3146 ____________________________________________________________________________________________ ==== Středa 14.9. dopoledne ==== Vede a na praktikách asistuje: **Marko Berezovský ** \\ . === Dijkstrův algoritmus bez prioritní fronty v čase $\mathcal{O}(m\cdot n)$. === **Poučení** * [[https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/| Výklad na Geeks for Geeks]] **Slidy:** {{:courses:laso2019:20190918_Dijkstra.pdf| Dijkstrův algoritmus }} **Data pro testování Dijkstry:** {{:courses:laso2016:graphWeighted.txt | txt}}, {{:courses:laso2016:result.txt | výsledek (jako pro neorientovaný graf)}}, {{:courses:laso2018:20180926_solutions.zip | implementace v Javě (2018)}} a {{:courses:laso2019:20190917solutions_python.zip | Pythonu (2019)}}. ____________________________________________________________________________________________ ==== Středa 14.9. odpoledne ==== Vede a na praktikách asistuje: **Max Hollmann** \\ . === Dijkstrův algoritmus s prioritní frontou v čase $\mathcal{O}((m+n) \cdot \log n)$, možná souvislost s Primovým algoritmem. === ** Data a slidy stejné jako ráno. ** **Poučení** * [[https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html|Animace]] * [[https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/| Kód v Cpp na Geeks for Geeks]], další jazyky v odkazech.