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

Ve letním semestru 2018/2019 vedeme s Ríšou Hladíkem speciální cvičení z předmětu Programování II [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á každé úterý od 14:00 v S8, kdo chcete chodit, přihlašte se v SISu, případně nám pošlete mail, pokud vám to SIS nedovolí.

Podmínky na získání zápočtu najdete v pravidlech hry. Také se můžete podívat na reklamní letáček.

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

Teoretické úkoly

DatumKódBodyZadání
26. 2. funrb7Co a proč dělá funkce rb() z letáčku?
funm10Co a proč dělá druhá funkce main() z letáčku?
ksp0Sepsání vzorového řešení do KSP (počet bodů po domluvě).
2. 4. optr10Zrychlete algoritmus na konstrukci optimálního vyhledávacího stromu z cvičení na O(n2). Může se hodit nerovnost z cvičení 12.4.6 z Průvodce.
21. 5. rlef10Je dán černobílý obrázek zkomprimovaný pomocí RLE (pro každý řádek rozdělíme na souvislé jednobarevné posloupnosti a zapíšeme jejich barvy a délky). Zjistěte, kolik pixelů má největší souvislá oblast.

Co jsme dělali

datum co se cvičilo
19. 2. Počítání trojúhelníků v grafech: obecně, s omezenými stupni, v rovinných grafech.
26. 2. Cesta s minimálním počtem změn barvy, a k tomu nejkratší. Isomorfismus pěstovaných stromů.
5. 3. Výběr pizzy: tato xor tato. Dynamické programování poprvé: rozklad textu na slova.
12. 3. Dynamické programování druhé: nejnižší knihovna.
19. 3. Dynamické programování potřetí: nejužší knihovna, různé verze knihoven bez uspořádání. Nejdelší společný podřetězec, editační vzdálenost, nejkratší společný nadřetězec.
26. 3. Úlohy o společných řetězcích. Optimální vyhledávací strom.
2. 4. Optimální stromy. Řezání trámu. Čtyřcykly v grafech.
9. 4. Pokračování z minula.
16. 4. Odmocňování permutací.
23. 4. Úterní chvilka geometrie: prokládání obdélníka množinou bodů. Rozpoznávání středově symetrických množin. Rozklad na dvě středově symetrické množiny.
30. 4. Obsah mnohoúhelníka. Leží bod uvnitř? Počítání mřížových bodů. Disjunktnost mnohoúhelníků.
7. 5. Pokračování z minula.
14. 5. Rektorský sportovní den: necvičíme, protože cvičíme :)
21. 5. Hrátky s kvadrantovými kódy. Komprese a dekomprese. Transformování kvadrantových obrázků. Problém malíře kvadrantisty (a jeho komprimovaná verze). RLE komprese a hledání největší souvislé oblasti.
Stránku spravuje Martin Mareš