Cvičení z Programování 2 pro pokročilé

V letním semestru 2023/2024 vedeme s Jirkou Kalvodou 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 středu od 15:40 v N3. Nenechte se prosím zmást překryvem s přednáškou z Úvodu do Linuxu – ve skutečnosti to není přednáška, nýbrž prostor pro konzultace.

Podmínky na získání zápočtu najdete v pravidlech hry.

Přihlašte se prosím do ReCodExu a Poštovní sovy (přihlašovací odkaz).

Svým cvičícím pište na adresu p2x@ucw.cz.

Co jsme dělali

datum	co se cvičilo
21. 2.	Dynamické programování poprvé – úlohy o knihovnách: plnění zadané knihovny, nejnižší a nejužší knihovna.
28. 2.	Dynamické programování podruhé: editační vzdálenost, nejdelší společný podřetězec, nejkratší společný nadřetězec. Řešení knihovny v O(n log n).
6. 3.	Dynamické programování potřetí: randomizovaný algoritmus pro nejužší knihovnu, optimální vyhledávací stromy, nejkratší triangulace mnohoúhelníku.
13. 3.	Řezání trámu. Trampoty obchodního cestujícího. Koláč s ropuchou.
20. 3.	Cvičení se nekoná.
27. 3.	{ počet trojúhelníků, počet čtyřcyklů, existence čtyřcyklu } × grafy { obecné, s omezenými stupni, rovinné }.
3. 4.	Trojúhelníky a čtyřcykly v rovinných grafech. Prázdný trojúhelník v rovině.
10. 4.	Rozpoznávání středově symetrických množin. Rozklad na dvě středově symetrické množiny. Hledání obdélníka.
17. 4.	Geometrie podruhé: obsah mnohoúhelníka a mřížové body.
24. 4.	Hrátky s kvadrantovými kódy. Komprese a dekomprese. Transformování kvadrantových obrázků. RLE komprese a hledání největší souvislé oblasti.
1. 5.	Slavíme výročí první poštovní známky, abdikace císaře Diokleciána a nezávislosti Skotska.
8. 5.	Slavíme konec 2. světové války (který vlastně?).