Table of Contents

Místo a čas konání

KN:E-311, čtvrtek od 14:30, a 17:00.

Rozvrh

Seminář Datum Náplň Úlohy/odkazy/prezentace
viz také pod tabulkou
1. 5.10. Servery, konta, ukázkové úlohy a témata, cvičná odevzdání Úlohy na A2OJ (Výsledky)
Základní grafový přehled, dohoda témat s pokročilými účastníky
pokročilé náměty na A2OJ
2. 12.10 Průchody grafem Minisoutěž I Úlohy na A2OJ (Výsledky)
Úlohy na A2OJ (pokročilí) (Výsledky)
3. 19.10. Nejkratší cesty, aplikace dfs ..
Úlohy na A2OJ (pokročilí)
4. 26.10. Grafové algoritmy Minisoutěž II Úlohy na A2OJ (Výsledky)
Úlohy na A2OJ (pokročilí)
5. 2.11. Dynamické programování I
6. 9.11. Dynamické programování II Minisoutěž III Úlohy na A2OJ (Výsledky)
Úlohy na A2OJ (pokročilí) (Výsledky)
7. 16.11. Kombinatorika, torie čísel
8. 23.11. Kombinatorika, torie čísel Minisoutěž IV Úlohy na A2OJ (Výsledky)
Úlohy na A2OJ (pokročilí) (Výsledky)
9. 30.11 Výpočetní geometrie, zametací přímka
10. 7.12. Výpočetní geometrie, zametací přímka Minisoutěž V Úlohy na A2OJ (Výsledky)
Úlohy na A2OJ (pokročilí) (Výsledky)
11. 14.12. Opakování, DP, MST, různé
hledání v textu
12. 21.12 DP, MST, různé Minisoutěž VI
Stav
Úlohy na A2OJ (Výsledky)
Úlohy na A2OJ (pokročilí) (Výsledky)
13. 4.1. Kombinatoricke hry Úlohy na A2OJ (pokročilí) (Výsledky)
14. 11.1. Kombinatoricke hry Minisoutěž VII Úlohy na A2OJ (Výsledky)
CELKEM ZS 2017 Průběžný stav Tabulka

Výsledky mimo a2oj

https://docs.google.com/spreadsheets/d/1wVWH31wBLCZieYniuBHBZRmYA69n8963iGUDRNyZNxs/edit?usp=sharing

Seminář 1


Provoz a administrace


Ahmed Aly Online Judge

V průběhu praktických cvičení (sudé výukové týdny) svá řešení budete odevzdávat do A2 Online Judge. Prosíme, vytvořte si každý svůj vlastní účet sledováním následujícího linku: Sign Up. Vzhledem k tomu, že A2 Online Judge je pouze tzv. agregátor výsledků, musíte si vytvořit účty v příslušných judgích, které skutečně ověřují správnost vašich řešení, a to: Sphere Online Judge, UVa Online Judge a ACM-ICPC Live Archive.

Aby A2OJ věděl o odevzdaných úlohách, musíte vyplnit ve svém profilu ID, které jste si vytvořili či vám bylo přiděleno u výše uvedených judgů. Zde je shrnut postup, jak se k nim dostat:

Sphere Online Judge (SPOJ)

  1. Neuvěřitelné, ale login je vaše ID.

UVA Online Judge

  1. V hlavním menu po přihlášení ťukněte na [My Account]
  2. Ve vašem profilu na řádku Online Judge ID: je Vaše UVA ID.

ACM-ICPC Online Judge

Test odevzdávacího systému

Po vytvoření účtů se můžete registrovat do soutěže na A2 Online Judge, klikněte zde.


Tématické přehledy a úlohy


Návodník na řešení

malá kategorizace grafových úloh

Dot product - Skalární součin

Ukázkové úlohy k základnímu ovládání grafů

V první části semináře si zopakujeme standardní grafové úlohy řešitelné pomocí algoritmu prohledávání do hloubky, a to zejména ulohy:

Dále:

Tabulky grafových úloh a složitostí

Poznámky k minimálním kostrám

Floyd-Warshall algorithm example

Bellman-Ford algorithm demo

Seminář 2: Grafové algoritmy


Náměty pro pokročilejší řešitele:

Přehledy – Maximální tok a párování

Geeksforgeeks - Ford-Fulkerson Max flow

Geeksforgeeks - Maximum bipartite matching

Stanford Code

Úlohy

TAXI

MATCHING

COCONUTS

4333 - Paper Presentation

11045 - My T-shirt suits me

Seminář 3:

Ulohy na nejkratsi cesty a min. kostry:

A na dfs a spol:

Reference:

Seminář 5: DP I

Přehledy a pár jednodušších úloh.

Ukázky k vyzkoušení si:

Ukázka kódu -- manipulace s DAG

Ad FFT:

Přehled a výklad: - FFT: Kap. 17. na stránkách T.Vally, Pruvodce_labyrintem_algoritmu- celá kniha

Seminář 7 - Aritmetika a kombinatorika, teorie čísel

Odkazy na materiály:

Vyzkoušejte si:

Seminář 9 - Geometrie / segm. stromy

Pokročilí:

Segmentové stromy (pro někoho částečné opakování)

Popsány pěkně v průvodci, kap. 4.5. (není dlouhá :-) )

Také v kuchařce KSP: Intervalové stromy.

Rozšířené ukázky: https://cw.fel.cvut.cz/wiki/courses/a4b36acm/2017_ls/seminare#seminar_10segmentove_stromy_pokrocili

Úlohy k vyzkoušení:

Seminář 11 - Opáčko a řetězce

Řetězcové (hledací v řetězcích) úlohy pro pokročilce a klidně i základníky:

KMP code: http://www-igm.univ-mlv.fr/~lecroq/string/node8.html

Aho-Corasick code: http://www.geeksforgeeks.org/aho-corasick-algorithm-pattern-searching/

Seminář 13 - Kombinatoricke hry

Materiály pro dnešní cvičení: kombinatoricke_hry