Rozvrh denně dopoledne 9.00 - 11.45, odpoledne 12.30 - 14.30, 14.45 - 16.00.
Úpravy možné po dohodě s lektorem.

Učebna E-126 v areálu FEL ČVUT na Karlově náměstí.

  ____________________________________________________________________________________________

Vedou a asistují Petr Ryšavý, Adam Jáneš

Prezentace:

1. Slidy,
2. dále Cesty v acyklickém grafu , ( pdf}

Další zdroje

• Topsort, jednoduchá ukázka
• Animace -- Topsort pomocí snižování vstupních stupňů
• Animace -- Topsort pomocí DFS

Úlohy (DAG):

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

Prezentace:

1. Bipartitní párování

Úlohy (Bipartitní párování):

1. 11045 - My T-shirt suits me
2. 10092 - The Problem with the Problem Setter
3. 10080 - Gopher II

  ____________________________________________________________________________________________

Vedou a asistují Petr Ryšavý, Adam Jáneš
.

Poučení

• Silně souvislé komponenty
• DFS s časovými značkami
• Kosaraju-Sharir algoritmus na Geeks for Geeks
• Kosaraju-Sharir řiditelná animace
• Tarjanův algoritmus na Geeks for Geeks

Úlohy

• WEBISL - Web islands
• 247 - Calling Circles
• 11504 - Dominos
• 11838 - Come and Go
• 11770 - Lighting Away
• CAPCITY - Capital City

  ____________________________________________________________________________________________

Vedou a asistují Petr Ryšavý, Adam Jáneš
.

• Slidy

Ukázky

Artikulace na GeeksForGeeks https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/
Mosty GeeksForGeeks https://www.geeksforgeeks.org/bridge-in-a-graph/

Úložky

• 10199 - Tourist Guide
• 315 - Network
• 796 - Critical Links
• SUBMERGE - Submerging Islands
• EC_P - Critical Edges

  ____________________________________________________________________________________________

Vedou a asistují Dan Hubáček, Adam Jáneš
.

Poučení:

• krok za krokem základní ukázka jednoduché hry
• (Všeobecné poučení o hrách a Nimu, výtah, česky)
• TopCoder - The Basic Introduction into Games
• Geeks for Geeks: úvod a elementární Nim

Příklady:

• Bachet's Game
• Integer Game
• A Game with Numbers
• 10368 - Euclid's Game
• QCJ3 - The Game
• M&M Game
• Game
• TRIVIADOR
• Playing With Stones

Příklady mají možná mírně rostoucí obtížnost, pro jistotu začněte s nimi od začátku.

Více odkazů pro vyložené zájemce:

• Všeobecné poučení o hrách a Nimu
• Všeobecné poučení o hrách a Nimu 2
• Jádro grafu
• Teorie her na CMU - Combinatorial Game Theory,Even More Games
• Nimbers (Sprague-Grundyho čísla) - ukázková úloha Socializing Game around Pizza
• Fibonacciho Nim

  ____________________________________________________________________________________________

Vedou a asistují Petr Ryšavý, Adam Jáneš
.

Slidy: pdf

Ukázky

Prim-Jarník https://www.cs.usfca.edu/~galles/visualization/Prim.html
Kruskal https://www.cs.usfca.edu/~galles/visualization/Kruskal.html
Union-find na GeeksForGeeks https://www.geeksforgeeks.org/union-find/
Kruskal Efektivně krok po kroku

Úložky

• 11631 - Dark roads
• 10034 - Freckles
• 10369 - Arctic Network - upravený Kruskal či dfs + binární půlení
• 908 - Re-connecting Computer Sites
• IITWPC4I - Petya and the Road Repairs

Jak na to?

Pomůže Union-Find? ONBRIDGE - Online Bridge Searching