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.

Výsledky

JménoTeoretické příkladyReCodExBodůZápočťák
Patrik Beliansky6464
Filip Čermák1818
Petr Gebauerfunrb(7) optr(10)83100 Toky v sítích  OK Z
Břetislav Hájek7878 Skenovací aplikace
Vojtěch Káně00 Interaktivní geometrie
Martin Korečekfunrb(7)98105 Spravedlivé miny
Jakub Pelcfunrb(7) ksp(29)71107 Entity component system
Jiří Škrobánekfunrb(7) funm(10) optr(10) ksp(10)66103 Programovací jazyk
Tomáš Zeman2222 Webový nástroj na úpravu obrázků

Body z ReCodExu se přepočítávají jednou nočně. Pokud chcete být uvedeni pod přezdívkou, nebo dokonce vůbec, dejte nám vědět.

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š