Místo a čas konání
KN:E-311, čtvrtek od 14:30, a 17:00.
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
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:
Po vytvoření účtů se můžete registrovat do soutěže na A2 Online Judge, klikněte zde.
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í
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
Úlohy
Ulohy na nejkratsi cesty a min. kostry:
A na dfs a spol:
Reference:
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
Odkazy na materiály:
Vyzkoušejte si:
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í:
Ř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/
Materiály pro dnešní cvičení: kombinatoricke_hry