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. |