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. | 23.9. (2) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání, jednoduchá opakování | |
2. | 30.9. (4) | Minisoutěž I - úlohy na informatický postřeh a zkušenost | |
3. | 7.10. (2) | Dynamické programování I | |
4. | 14.10. (4) | Minisoutěž II | |
5. | 21.10. (2) | Dynamické programování II | |
6. | 28.10. (0) | odpadá, je státní svátek | |
7. | 4.11. (4) | Minisoutěž III | |
8. | 11.11. (2) | Cesty v grafech | |
9. | 18.11. (4) | Minisoutěž IV | |
10. | 25.11. (2) | Aritmetika a kombinatorika, teorie čísel | |
11. | 2.12. (4) | Minisoutěž V | |
12. | 9.12. (2) | Výpočetní geometrie, mřížky | |
13. | 16.12. (4) | Minisoutěž VI | |
14. | 6.1. (2) | Anatgonistické hry, Nim, případné dodělávky | |
CELKEM | ZS 202` . . . . | TABULKA - VÝSLEDKY | Tady je celkový stav |
V průběhu praktických cvičení a také při domácí aktivitě svá řešení budete odevzdávat do serverů
Na každém z těchto serverů si zřiďte konto, pokud ho tam ještě nemáte.
Komentáře k úlohám na Project Euler.
Vyzkoušejte si:
TEST - Life, the Universe, and Everything
100 - The 3n + 1 problem
PERMUT2 - Ambiguous Permutations
Bouncy numbers
Exploring strings for which only one character comes lexicographically after its neighbour to the left
MARTIAN - Martian Mining
Pokročilí zkusí
Svoje výkony zapisujte samostatně do tabulky
Výkony v minisoutěži I,
po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz.
Sada začínající
Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady “začínající” nezískají body.
Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady.
V této sadě je několik úloh na dynamické programování, ostatní slouží jako rozcvičkové ad hoc úlohy s různorodými metodami řešení.
Sada pokročilá
Všechny úlohy ve dvou minulých soutěžích v letech 2006 a 2013.
Ukázky typických postupů a úloh.
Svoje výkony zapisujte samostatně do tabulky
Výkony v minisoutěži II,
po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz.
Sada začínající
Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady “začínající” nezískají body.
Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady.
Sada pokročilá
Dokončení námětů ze semináře 03.
Svoje výkony zapisujte samostatně do tabulky
Výkony v minisoutěži III,
po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz.
Sada začínající
Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady “začínající” nezískají body.
Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady.
Sada pokročilá
Nejkratší a nejdelší cesty:
Cesty v stromech (nejdelší, nejkratší i jiné) bývají řešitelné pomocí DP,
to jest zakořeněním stromu a aplikací postorder průchodu stromem.
Aplikace prohledávání do hloubky:
Negativní cykly:
Cesty mezi všemi páry uzlů:
Dalších 200+ ukázek a úloh:
Svoje výkony zapisujte samostatně do tabulky
Výkony v minisoutěži IV,
po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz.
Sada začínající
Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady “začínající” nezískají body.
Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady.
Sada pokročilá
Vyzkoušejte si:
Další odkazy související s úlohami
Catalanova čísla
https://en.wikipedia.org/wiki/Catalan_number
Euklidův algoritmus (největší společný dělitel)
http://mathworld.wolfram.com/EuclideanAlgorithm.html
Prvočísla
http://www.geeksforgeeks.org/sieve-of-eratosthenes/
Svoje výkony zapisujte samostatně do tabulky
Výkony v minisoutěži V,
po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz.
Sada začínající
Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady “začínající” nezískají body.
Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady.
Sada pokročilá
Determinant matice, většinou stačí 2×2.
Některé základní výpočty (pdf verze )
Počítání průsečíků Soustava lin. rovnic, Cramerovo pravidlo
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
Very Brute force Binary Search: https://onlinejudge.org/external/105/10566.pdf
Sweep line example Touching rectangles
Sweep line rotates:, http://www.spoj.com/problems/CERC07C/ (*_*_*) komentář
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 )
Rotate points instead of lines 8258 - Glyph Recognition (ICPC Live Archive | Regionals 2017 | Europe-Northwestern), solution idea
Množství komentovaných základních kódů https://www.geeksforgeeks.org/geometric-algorithms/
Kreslítko GeoGebra online https://www.geogebra.org/graphing?lang=en (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
Svoje výkony zapisujte samostatně do tabulky
Výkony v minisoutěži VI,
po skončení minisoutěže v 19:45, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz.
Sada začínající
Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady “začínající” nezískají body.
Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady.
Sada pokročilá
Příklady: