Místo a čas konání
KN:E-311, čtvrtek od 16:15, střídavě 2 a 4 hodiny týdně, viz rozpis níže.
Seminář | Datum (hodiny) | Náplň | Úlohy/odkazy/prezentace viz také pod tabulkou | |
---|---|---|---|---|
1. | 23.2. (4) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání | Základní: A2OJ - úlohy a výsledky Pokročilí: Regionals 2005 - Africa/Middle East - Arab and North Africa | |
2. | 2.3 (2) | Základní: Průchody grafem Pokročilí: Trie, suffix tree | ||
3. | 9.3. (4) | Minisoutěž I | Základní: A2OJ - úlohy a výsledky Pokročilí: Regionals 2005 - North America - Rocky Mountain + Pattern Matching | |
4. | 16.3. (2) | Základní: Grafy a nejkratší cesty Pokročilí: Binary trie, radix trie | ||
5. | 23.3. (4) | Minisoutěž II | Základní: A2OJ - úlohy a výsledky Pokročilí: Regionals 2008 - Asia - Beijing | |
6. | 30.3. (2) | Základní: Dynamické programování Pokročilí: Finite automata, Aho-Corasick | ||
7. | 6.4. (4) | Minisoutěž III | Základní: A2OJ - úlohy a výsledky Pokročilí: Regionals 2003 - North America - East Central NA | |
8. | 13.4. (2) | Základní: Aritmetika a kombinatorika, teorie čísel Pokročilí: Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin | ||
9. | 20.4 (4) | Minisoutěž IV | Základní: A2OJ - úlohy a výsledky Pokročilí: Regionals 2001 - Europe - Northwestern | |
10. | 27.4. (2) | Základní: Výpočetní geometrie, mřížky Pokročilí: Segment tree, treap | ||
11. | 4.5. (4) | Minisoutěž V | Základní: A2OJ - úlohy a výsledky Pokročilí: A2OJ - úlohy a výsledky Náhradní tabulka | |
12. | 11.5. (2) | odpadá, pondělní rozvrh | ||
13. | 18.5. (4) | Minisoutěž VI | Základní: A2OJ - úlohy a výsledky Pokročilí: A2OJ - úlohy a výsledky | |
14. | 25.5. (2) | Základní: Anatgonistické hry, Nim Pokročilí: Jiné dle zájmu, dodělávky, ad lib. | ||
CELKEM | LS 2017 | Průběžný stav | Tabulka |
Přibližně návodná ukázka struktury prezentace: Voda v rourách
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 na příslušný odkaz do A2OJ nahoře v tabulce.
Dnešní cvičení bude úvod do grafových algoritmů. Nejprve nás ale čeká diskuze nad úlohami z posledního cvičení. Poté probereme základní pojmy z teorie grafů a popovídáme si o základních úlohách, které lze řešit jedním z nejverzatilnějších algoritmů (z říše grafových algoritmů), a to o prohledávání do hloubky. Ale i mnohem více…
Stěžejní algoritmy a datové struktury:
Motivační úlohy s řešeními (hlavně na příští seminář):
V dnešním semináři budeme pokračovat v povídání o grafových algoritmech. Tentokrát probereme řadu algoritmů pro hledání nejkratší cesty v grafu a určení jeho minimální kostry.
Učební materiály a pár jednodušších úloh na doma.
Cycle finding
Algorithm:
Floyd's Tortoise and Hare
Problems:
350 - Pseudo-Random Numbers
10591 - Happy Number
11549 - Calculator Conundrum
String Matching
11019 - Matrix Matcher
1328 - Period
1519 - Dictionary Size
10887 - Concatenation of Languages
1314 - Hidden Password
Automata
Odkazy na materiály:
Studijni materialy:
Nekolik uloh na doma: