Table of Contents

Letní Algoritmické Soustředění LASO 2016

.

Pokročilí

Kde: Laboratoř KN:E-230

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: Reakce účastníků LASO ..

Pondělí

Prezentace k přednášce: Hledání nejkratší cesty

Úlohy k přednášce:

  1. 104 - Arbitrage
  2. 436 - Arbitrage (II)
  3. 186 - Trip Routing
  4. 423 - MPI Maelstrom
  5. 523 - Minimum Transport Cost
  6. 929 - Number Maze
  7. 3340 - Hour Glass
  8. 10801 - Lift Hopping
  9. 558 - Wormholes
  10. 544 - Heavy Cargo

Alternativní program:

Graphviz:

Úterý

Prezentace:

  1. Cesty v acyklickém grafu
  2. bez slidů - DecreaseKey v prioritní frontě nestačí pro Dijkstrův alg.

Úlohy:

  1. https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=longslopes2
  2. https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=increasingload
  3. 10305 - Ordering Tasks
  4. 926 - Walking Around Wisely
  5. https://projecteuler.net/problem=15
  6. https://projecteuler.net/problem=18
  7. https://projecteuler.net/problem=67

Středa

Prezentace:

  1. Minimální kostry
  2. MST a Dijkstrův alg.
  3. Jádro grafu
  4. bez slidů - grafy bipartitní

Úlohy:

  1. 10034 - Freckles
  2. 10147 - Highways
  3. 10048 - Audiophobia
  4. 544 - Heavy Cargo
  5. 10369 - Arctic Network
  6. 11733 - Airports
  7. Asfaltové silnice
  8. 10004 - Bicoloring
  9. 10165 - Stone Game
  10. 10404 - Bachet's Game
  11. 847 - A Multiplication Game