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ě?).
15. 5. Orákula: zdroj v grafu, A[i,j]=i+j, kráva za plotem, hádání čísel se lží.
22. 5. Trampoty jeřábníkovy. Volby.
Stránku spravuje Martin Mareš