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. | 26.9. (2) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání, jednoduchá opakování | |
| 2. | 3.10. (4) | Minisoutěž I - úlohy na informatický postřeh a zkušenost | |
| 3. | 10.10. (2) | Dynamické programování I | |
| 4. | 17.10. (4) | Minisoutěž II | |
| 5. | 24.10. (2) | Dynamické programování II | |
| 6. | 31.10. (4) | Minisoutěž III | |
| 7. | 7.11. (2) | Cesty v grafech | |
| 8. | 14.11. (4) | Minisoutěž IV | |
| 9. | 21.11. (2) | Aritmetika a kombinatorika, teorie čísel | |
| 10. | 28.11. (4) | Minisoutěž V | |
| 11. | 5.12. (2) | Výpočetní geometrie, mřížky | |
| 12. | 12.12. (4) | Minisoutěž VI | |
| 13. | 19.12. (4) | Minisoutěž VII opakování témat | |
| 14. | 9.1. (2) | odpadá | |
| CELKEM | ZS 2024 . . . . | 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.
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.
Začínající zkusí
pokročilí nebo začínající zkusí
Komentáře k minulým úlohám.
Ukázky typických postupů a úloh.
Doporučené úvodní přehledové a úctyhodné publikace, asi nejpřístupněji napsané:
Jednotlivé metody:
Úlohy pro rozmyšlení
147 - Dollars (2D Tab)
10066 - The Twin Towers (LCS)
11432 - Busy Programmer
PT07X - Vertex Cover
M3TILE - LATGACH3
SQRBR - Square Brackets
116 - Unidirectional TSP
11137 - Ingenuous Cubrency
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.
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.
pokročilí nebo začínající zkusí
S využitím materiálů v semináři 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.
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.
Začínající zkusí
Pokročilí nebo začínající zkusí
Především BFS, DFS, Dijkstra, odkazy viz níže.
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.
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.
Začínající zkusí
Pokročilí nebo začínající zkusí
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.
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.
Začínající zkusí
Pokročilí nebo začínající zkusí
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
Jednoduchá aplikace 438 - The Circumference of the Circle, 10335 - Ray Inside a Polygon
Poloha bodu a polygonu (Hack: místo paprsku může postačit dostatečně dlouhá úsečka)
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/classic (http://www.geogebra.org/ ??) (začni variantou “classic”).
Zkuste samostatně:
Nejprve plán na příští týden
Hlasujte pro organizaci semináře v příštím týdnu 19.12. Hlasujte zde co nejdříve.
Dále jako obvykle
Svoje výkony zapisujte samostatně do tabulky
Výkony v minisoutěži VI,
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.
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.
Začínající zkusí
Pokročilí nebo začínající zkusí
Svoje výkony zapisujte samostatně do tabulky
Výkony v minisoutěži VII,
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.
Tentokrát, na závěr semestru, máme jen jedinou sadu, společnou pro začínající i pokročilé, 3 body získá každý za každou vyřešenou úlohu.
Sada společná