====== Letní Algoritmické Soustředění LASO 2017 ====== . ====== Pokročilí ====== ^ Kde: Budova E na Karlově Náměstí, místnosti ještě upřesníme, probíhají stavební úpravy. ^ ---- .\\ ^ Výchozí program, může se měnit podle přání a potřeb účastníků: ^ ^ Den ^ Dopoledne 9:00-11:30, odpoledne 13:30 – 17:00 s přestávkou podle potřeby. Průběžně se střídá výklad a programování cca po 60-90 minutách. ^ | **Po** \\ **18.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. | | **Út** \\ **19.9.** | Opáčko DP , Topsort, průchod DAG, Floyd–Warshall, hodně aktivního programování. | | **St** \\ **20.9.** | MST, Prim, Kruskal, Vztah algoritmů Primova a Dijkstrova, Union-Find, \\ Pokud zbyde čas, párování v bipartitním grafu, maďarský algoritmus. | | Celkem | **Napište nám své připomínky a komentáře:** [[https://docs.google.com/forms/d/1HeN5EjUeTxqzo-E8wrth6cUYSOlQVZqKAt_EXk-_04c/edit| Reakce účastníků LASO ]] | ===== Pondělí ===== **Prezentace:** {{:courses:laso2017:20170918_shortest_path.pdf|Hledání nejkratší cesty}} **Úlohy k prezentaci:** - [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1927|UVA 10986 - Sending email]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=164&page=show_problem&problem=1742|UVA 10801 - Lift Hopping]] - [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2682|UVA 11635 - Hotel booking]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=165&page=show_problem&problem=499|UVA 558 - Wormholes]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=377|UVA 436 - Arbitrage (II)]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=762|UVA 821 - Page Hopping]] **Alternativní program:** * [[https://open.kattis.com/problem-sources/2015%20ICPC%20North%20American%20Qualifier%20Contest| North America Qualifier 2015]]. * anebo samostatně [[courses:laso2017:navic| hry navíc ]]. **Graphviz:** * {{:courses:laso2016:graphviz_uvod.pptx| úvodní seznámení }}. * [[http://www.graphviz.org/|Stáhněte si, instalujte a experimentujte]]. * [[http://www.graphviz.org/|Stáhněte si, instalujte a experimentujte]]. ===== Úterý ===== **Prezentace:** - {{:courses:laso2017:dag.pptx|Cesty v acyklickém grafu }}, ({{:courses:laso2017:dag.pdf| pdf}}) **Úlohy:** - 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 |}} **Alternativní program:** * [[https://community.topcoder.com/stat?c=problem_statement&pm=4463&rd=6536|BoxUnion]] s připomenutím [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm/2016_zs/seminare#seminar_10_-_geometrie|sweep line postupu]]. ===== Středa ===== **Prezentace:** - {{:courses:laso2017:mst3.pptx| Minimální kostry - Kruskal}} ( {{:courses:laso2017:mst3.pdf|pdf}}) - {{:courses:laso2017:pal02.pptx| Primův algoritmus }} ([[https://cw.fel.cvut.cz/wiki/_media/courses/laso2016/kostry.pdf| pdf ]]) - [[courses:laso2017:pokrocili:mst_codes|MST a Dijkstrův algoritmus]] - {{:courses:laso2017:combigames.ppt| Hry a Jádro grafu}} ({{:courses:laso2017:combigames.pdf|pdf}}) (další poučení: [[courses:laso2017:navic| samostatně]]) - bez slidů - DecreaseKey v prioritní frontě nestačí pro Dijkstrův alg. - 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]]