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

Výsledky

JménoTeoretické příkladyReCodExBodůZápočťák
Jiří Škrobánekfunrb(7) funm(10) optr(10)4572
Petr Gebauer3131
Patrik Beliansky2020
Filip Čermák1818
Vojtěch Káně00
Jakub Pelc3131
Břetislav Hájek3131
Martin Korečekfunrb(7)1724
Tomáš Zeman44

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í.
Stránku spravuje Martin Mareš