Table of Contents

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

Pondělí

Prezentace: Hledání nejkratší cesty

Úlohy k prezentaci:

  1. UVA 10986 - Sending email
  2. UVA 10801 - Lift Hopping
  3. UVA 11635 - Hotel booking
  4. UVA 558 - Wormholes
  5. UVA 436 - Arbitrage (II)
  6. UVA 821 - Page Hopping

Alternativní program:

Graphviz:

Úterý

Prezentace:

  1. Cesty v acyklickém grafu , ( pdf)

Úlohy:

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

Alternativní program:

Středa

Prezentace:

  1. Minimální kostry - Kruskal ( pdf)
  2. Primův algoritmus ( pdf )
  3. MST a Dijkstrův algoritmus
  4. Hry a Jádro grafu (pdf) (další poučení: samostatně)
  5. bez slidů - DecreaseKey v prioritní frontě nestačí pro Dijkstrův alg.
  6. 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