Místo a čas konání
Místo a čas konání
T2:C2-84, čtvrtek od 16:15. Rozvrh FEL
| Seminář (hodiny) | Datum | Náplň | Úlohy/odkazy/prezentace viz také pod tabulkou |
|---|---|---|---|
| 1.(2) | 26.9. (2) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání, dohoda témat se začátečníky a pokročilými účastníky | Úlohy na A2OJ (Výsledky) pokročilé náměty na A2OJ (Výsledky) |
| 2.(4) | 3.10 | Průchody grafem Minisoutěž I … | Úlohy na A2OJ (Výsledky) mírně(!) pokročilé náměty na A2OJ (Výsledky) |
| 3.(2) | 10.10.(2) | Nejkratší cesty, aplikace dfs | |
| 4.(4) | 17.10. | Grafové algoritmy Minisoutěž II | Úlohy na A2OJ (Výsledky) pokročilejší náměty na A2OJ (Výsledky) |
| 5.(2) | 24.10. | Dynamické programování I | |
| 6.(4) | 31.10. | Dynamické programování II Minisoutěž III | Úlohy na A2OJ (Výsledky) pokročilejší náměty na A2OJ (Výsledky) |
| 7.(2) | 7.11. | Kombinatorika, teorie čísel, byly spíše komentáře k DP | |
| 8.(4) | 14.11. | Základní: stále DP, Pokročilí: Kombinatorika, teorie čísel Minisoutěž IV | Úlohy na A2OJ (Výsledky) pokročilejší náměty na A2OJ (Výsledky) |
| 9.(2) | 21.11 | Kombinatorika, teorie čísel | |
| 10.(4) | 28.11. | Kombinatorika, teorie čísel Minisoutěž V | Úlohy na A2OJ (Výsledky) pokročilejší náměty na A2OJ (Výsledky) |
| 11.(2) | 5.12. | Geometrie. | |
| 12.(4) | 12.12 | Geometrie Minisoutěž VI | Úlohy na A2OJ (Výsledky) pokročilejší náměty na A2OJ (Výsledky) |
| 13.(2) | 19.12. | Kombinatoricke hry | |
| 14.(4) | 9.1. | Kombinatoricke hry Minisoutěž VII | A2OJ skončil, společné zadání úloh viz dole na stránce |
| CELKEM | ZS 2017 | 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, klikněte na odkaz nahoře v prvním řádku tabulky.
Začátečníci: Steven S. Skiena, Miguel A. Revilla: http://acm.cs.buap.mx/downloads/Programming_Challenges.pdf
Klasický úvod a komentář ke cca 100 vybraným úlohám z UVA Online Judge, i s nezbytnými teoretickými souvislostmi.
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í
Čtěte průvodce: Průvodce labyrintem algoritmů
Nejkratší a nejdelší cesty:
V kterési úloze se může hodit: https://www.geeksforgeeks.org/2-satisfiability-2-sat-problem/
1.
https://www.geeksforgeeks.org/dynamic-programming/ (ukázky a příklady). Server GeeksForGeeks mivá přehledná a jednoduchá vysvětlení, nezatížená akademickou abstrakcí.
Projděte ukázky a vyzkoušejte si některé příklady, je jich tam přes 300. V příkladech bývá rovněž vysvětlené řešení, což dost pomáhá.
2.
http://pruvodce.ucw.cz/ V Průvodci labyrintem algoritmů je kapitola 12 o dynamickém programování.
Je to jeden z nejlepších českých učebních textů v informatice, vyplatí se alespoň zkusit si ho přečíst.
Ukázky typických postupů a úloh
Některé kanonické úlohy DP
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
Zalozni seznam:
Cisla jsou na Uva , jinak SPOJ
Příklady:
Minisoutěž VII
Začátečnící i pokročilí jsou tentokrát sloučeni do jedné sady, každý si musí vhodně vybrat.