Cvičení z Programování 2 pro pokročilé
V letním semestru 2024/2025 vedeme s Danem Skýpalou speciální cvičení z předmětu Programování 2 [NPRG031] pro pokročilé studenty, kteří již nasbírali nějaké zkušenosti z programování (třeba v olympiádách a korespondenčních seminářích) a chtěli by se naučit víc. Tematicky bude navazovat na Programování I pro pokročilé z minulého semestru, ale jeho absolvování určitě nebude nutné pro účast na tomto cvičení.
Cvičení se koná ve úterý od 9:00 v N4.
Podmínky na získání zápočtu najdete v pravidlech hry.
Svým cvičícím pište na adresu p2x@ucw.cz.
Co jsme dělali
| datum | co se cvičilo |
|---|---|
| 18. 2. | Dynamické programování poprvé – úlohy o knihovnách: plnění zadané knihovny, nejnižší a nejužší knihovna. |
| 25. 2. | Dynamické programování podruhé: editační vzdálenost, nejdelší společný podřetězec, nejkratší společný nadřetězec. |
| 4. 3. | Řešení knihovny v O(n log n). Dynamické programování potřetí: randomizovaný algoritmus pro nejužší knihovnu, optimální vyhledávací stromy, nejkratší triangulace mnohoúhelníku. |
| 11. 3. | Řezání trámu. Trampoty obchodního cestujícího. Koláč s ropuchou. |
| 18. 3. | { počet trojúhelníků, počet čtyřcyklů, existence čtyřcyklu } × grafy { obecné, s omezenými stupni, rovinné }. |
| 25. 3. | Trojúhelníky a čtyřcykly v rovinných grafech. |
| 1. 4. | Prázdný trojúhelník v rovině. Rozpoznávání středově symetrických množin. Rozklad na dvě středově symetrické množiny. |
| 8. 4. | Geometrie podruhé: obsah mnohoúhelníka a mřížové body. |
| 15. 4. | Kvadrantová komprese a dekomprese obrázků. Transformování kvadrantových obrázků. RLE komprese a hledání největší souvislé oblasti. Souvislá oblast v kvadrantové kompresi. |