====== Letní Algoritmické Soustředění LASO 2016 ====== . ====== Pokročilí ====== ^ Kde: Laboratoř KN:E-230 ^ [[http://www.fel.cvut.cz/cz/glance/rooms.html|Situační plánek]] **Program** ^ Den ^ Dopoledne 9:00-12:15 \\ teorie - výklady - ukázky ^ Odpoledne 13:30 – 17:00 \\ praxe - programování - diskuse ^ | **Po** \\ **19.9.** | Opakování grafové reprezentace, vhodné datové struktury. \\ Dijkstrův algoritmus ve variantách pro husté a řídké grafy. \\ Patálie s prioritní frontou. \\ Problém záporných cyklů, algoritmy Bellmanův-Fordův (Arbitrage) a Johnsonův | Seznámení s Graphviz, úlohy k dopoledni. | | **Út** \\ **20.9.** | Opáčko DP , Topsort, průchod DAG, Floyd–Warshall \\ Komentáře k včerejším úlohám. | Úlohy k dopoledni a z včerejška, bude toho dost. | | **St** \\ **21.9.** | MST, Prim, Kruskal, (Prim ~ Dijkstra !!), Union-Find, \\ Pokud zbyde čas, párování v bipartitním grafu, maďarský algoritmus. | Úlohy k dopoledni | | Celkem | **Napište nám své připomínky a komentáře:** [[https://docs.google.com/a/fel.cvut.cz/forms/d/1qryIB5xyRc2ckoo5hxDPVve1TmiWZslCkCu6axW896A| Reakce účastníků LASO ]] | .. | ===== Pondělí ===== **Prezentace k přednášce:** {{:courses:laso2016:20160919_shortest_path.pdf|Hledání nejkratší cesty}} **Úlohy k přednášce:** - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=40|104 - Arbitrage]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=377|436 - Arbitrage (II)]] - [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=122|186 - Trip Routing]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=364|423 - MPI Maelstrom]] - [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=464|523 - Minimum Transport Cost]] - [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=870|929 - Number Maze]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=134|3340 - Hour Glass]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=164&page=show_problem&problem=1742|10801 - Lift Hopping]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=165&page=show_problem&problem=499|558 - Wormholes]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=168&page=show_problem&problem=485|544 - Heavy Cargo]] **Alternativní program:** * [[https://open.kattis.com/problem-sources/2015%20ICPC%20North%20American%20Qualifier%20Contest| North America Qualifier 2015]]. **Graphviz:** * {{:courses:laso2016:graphviz_uvod.pptx| úvodní seznámení }}. * [[http://www.graphviz.org/|Stáhněte si, instalujte a experimentujte]]. ===== Úterý ===== **Prezentace:** - {{:courses:laso2016:dag.pptx|Cesty v acyklickém grafu }} - bez slidů - DecreaseKey v prioritní frontě nestačí pro Dijkstrův alg. **Úlohy:** - 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 |}} - [[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://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 |}} ===== Středa ===== **Prezentace:** - {{:courses:laso2016:kostry.pdf| Minimální kostry}} - [[courses:laso2016:sklad| MST a Dijkstrův alg.]] - {{:courses:laso2016:combigames.ppt| Jádro grafu }} - bez slidů - grafy bipartitní **Úlohy:** - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=975|10034 - Freckles]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1088|10147 - Highways]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=989|10048 - Audiophobia]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=485|544 - Heavy Cargo]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1310|10369 - Arctic Network]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2833|11733 - Airports]] - [[https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=asfalt|Asfaltové silnice]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=945|10004 - Bicoloring]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1106|10165 - Stone Game]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1345|10404 - Bachet's Game]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=788|847 - A Multiplication Game]]