Místo a čas konání
T2:C2-84, čtvrtek od 16:15. Rozvrh FEL
Seminář | Datum (hodiny) | Náplň | Úlohy/odkazy/prezentace viz také pod tabulkou |
---|---|---|---|
1. | 21.2. (4) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání | Úlohy na A2OJ (Výsledky) Do zápočtu třetí vyřešená a pak každá další vyřešená úloha v tomto souboru. |
2. | 28.2 (2) | Dynamické programování | |
3. | 7.3. (4) | Minisoutěž I | Úlohy na A2OJ (Výsledky) |
4. | 14.3. (2) | Grafy a nejkratší cesty | |
5. | 21.3. (4) | Minisoutěž II | Úlohy na A2OJ (Výsledky) |
6. | 28.3. (2) | Aritmetika a kombinatorika, teorie čísel | |
7. | 4.4. (4) | Minisoutěž III | Úlohy na A2OJ (Výsledky) |
8. | 11.4. (2) | Výpočetní geometrie, mřížky | |
9. | 18.4 (4) | Minisoutěž IV | Úlohy na A2OJ (Výsledky) |
10. | 25.4. (2) | Anatgonistické hry, Nim | |
11. | 2.5. (4) | Minisoutěž V | Úlohy na A2OJ (Výsledky) |
12. | 9.5. (2) | odpadá, středeční rozvrh | |
13. | 16.5. (4) | Minisoutěž VI | A2OJ je mimo provoz, úlohy jsou dole na stránce v odstavci 13. Otevřete je, řešte a odevzdávejte jako obvykle, tabulku výsledků sestavíme ručně. |
14. | 23.5. (2) | Toky v sítích nebo dodělávky podle potřeby | |
CELKEM | LS 2019 | Průběžný stav | tabulka |
…
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, odkaz většinou bývá nahoře v tabulce u aktuálního data nebo si soutěž vyhledejte samostatně na A2oj.
Ukázky typických postupů a úloh.
Nejdelší společná podposloupnost (LIS - Longest Common Subsequence)
Výklad na GeeksForGeeks
Úlohy
UVA -- 10192 - Vacation
UVA -- 10066 - The Twin Towers
SPOJ -- AIBOHP - Aibohphobia
SPOJ -- ADFRUITS - Advanced Fruits
Problém batohu (Knapsack Problem)
Ukázka 0-1 varianty na GeeksForGeeks
Ukázka neomezené varianty na GeeksForGeeks
Úlohy
UVA -- 562 - Dividing coins
UVA -- 990 - Diving for Gold
UVA -- 10819 - Trouble of 13-Dots
SPOJ -- PIGBANK - Piggy-Bank
Čtěte průvodce: Průvodce labyrintem algoritmů
Nejkratší a nejdelší cesty:
Aplikace prohledávání do hloubky:
Všechny cesty:
Ilustrační úlohy
Úlohy mírně navíc:
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
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 (enable java?)
code: http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
Stanford examples: http://web.stanford.edu/class/cs97si/ (Namely: http://web.stanford.edu/class/cs97si/09-computational-geometry.pdf )
Sweep line rotates:, http://www.spoj.com/problems/CERC07C/ (*_*_*) komentář
Rotate points instead of lines 8258 - Glyph Recognition ( solution idea)
Množství komentovaných základních kódů https://www.geeksforgeeks.org/geometric-algorithms/
Kreslítko GeoGebra online http://www.geogebra.org/
Seznamy geometrických kreslítek https://en.wikipedia.org/wiki/List_of_interactive_geometry_software#2D_programs, http://mathforum.org/geometry/geometry.software.html
Něco navíc:
Příklady:
Něco navíc:
Úlohy do minisoutěže:
1. 116 - Unidirectional TSP
2. 121 - Pipe Fitters
3. 201 - Squares
4. 254 - Towers of Hanoi
5. 839 - Not so Mobile
6. 861 - Little Bishops
7. 10305 - Ordering Tasks
8. 10696 - f91
9. 10704 - Traffic!
10. 10862 - Connect the Cable Wires
11. 10954 - Add All
12. 11049 - Basic wall maze
13. 11195 - Another n-Queen
14. 11232 - Cylinder
15. 11995 - I Can Guess the Data Structure!