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. | 6.10. (4) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání | Úlohy a výsledky na A2OJ |
2. | 13.10 (2) | Průchody grafem | |
3. | 20.10. (4) | Minisoutěž I | Úlohy a výsledky na A2OJ CTU Open výsledky |
4. | 27.10. (2) | DP I | |
5. | 3.11. (4) | Minisoutěž II | Úlohy a výsledky na A2OJ Prubezny stav |
6. | 10.11. (2) | Pokračování DP plus grafy | |
7. | 17.11. (4) | odpadá, státní svátek | |
8. | 24.11. (2) | Aritmetika a kombinatorika, teorie čísel | |
9. | 1.12 (4) | Minisoutěž III | Úlohy a výsledky na A2OJ |
10. | 8.12. (2) | Výpočetní geometrie, mřížky | |
11. | 15.12. (4) | Minisoutěž IV | Úlohy a výsledky na A2OJ |
12. | 22.12 (2) | Anatgonistické hry, Nim | |
13. | 5.1. (4) | Minisoutěž V | Úlohy a výsledky na A2OJ |
14. | 12.1. (2) | Opakování a doplnění restů | |
CELKEM | ZS 2016 | 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 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í
Ilustrační jednodušší 1D varianty DP úloh
Základní úloha “lámání klacku” 10003 - Cutting Sticks
DP lze řešit pomocí Excelu 10081 - Tight Words
Dnešní téma: Aritmetika, Kombinatorika a Teorie Čísel
Odkazy na materiály:
Reminder: Trigonometric identities
Pick's_theorem http://jwilson.coe.uga.edu/emat6680fa05/schultz/6690/pick/pick_main.htm
Všeobecný přehled na MFF (Programátorské kuchařky) http://ksp.mff.cuni.cz/tasks/24/cook5.html
Seznamy geometrických kreslítek https://en.wikipedia.org/wiki/List_of_interactive_geometry_software#2D_programs, http://mathforum.org/geometry/geometry.software.html
Kreslítko GeoGebra online http://www.geogebra.org/
Polygon area example: https://www.mathsisfun.com/geometry/area-irregular-polygons.html, code: http://www.codeproject.com/Articles/13467/A-JavaScript-Implementation-of-the-Surveyor-s-Form
Sweep line example Touching rectangles
Graham Scan demo: http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/GrahamScan.html
code: http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
Stanford examples: http://web.stanford.edu/class/cs97si/
Ideas_in_Geometry https://en.wikiversity.org/wiki/Ideas_in_Geometry/Area
Cyclic quadrilateral, https://en.wikipedia.org/wiki/Cyclic_quadrilateral
Sweep line rotates:, http://www.spoj.com/problems/CERC07C/ (*_*_*) komentář
viz. ACM Maraton 2016