Cvičení z Programování 2 pro pokročilé
V letním semestru 2022/2023 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á v úterý od 9:00 v N4. 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.
Pozor, zápis na cvičení probíhá speciálním způsobem: viz pravidla.
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 |
|---|---|
| 14. 2. | Dynamické programování poprvé – úlohy o knihovnách: plnění zadané knihovny, nejnižší a nejužší knihovna. |
| 21. 2. | Dynamické programování podruhé: opět nejnižší knihovna. Nejdelší společný podřetězec. |
| 28. 2. | Dynamické programování potřetí: nejdelší rostoucí podposloupnost, nejdelší společná podposloupnost, editační vzdálenost. |
| 7. 3. | Randomizovaný algoritmus pro nejužší knihovnu. Optimální stromy. Řezání trámu. |
| 14. 3. | Počítání trojúhelníků a čtyřcyklů v grafech: obecně, s omezenými stupni, v rovinných grafech. Existence čtyřcyklu. |
| 21. 3. | Trojúhelníky a čtyřcykly v rovinných grafech. |
| 28. 3. | Rozpoznávání středově symetrických množin. Rozklad na dvě středově symetrické množiny. |
| 4. 4. | Geometrie podruhé: Hledání obdélníka. Obsah mnohoúhelníka. Záplaty. |
| 11. 4. | Geometrie potřetí: obsah mnohoúhelníka a mřížové body. |
| 18. 4. | Cvičení se nekoná. |
| 25. 4. | Hrátky s kvadrantovými kódy. Komprese a dekomprese. Transformování kvadrantových obrázků. |
| 2. 5. | RLE komprese a hledání největší souvislé oblasti. |
| 9. 5. | Orákula: zdroj v grafu, A[i,j]=i+j, kráva za plotem, hádání čísel se lží. |
| 16. 5. | Trampoty jeřábníkovy. |