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

Ve letním semestru 2014/2015 vedeme s Jirkou Setničkou 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é pondělí od 9: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.

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

Teoretické úkoly

DatumKódBodyZadání
17. 2. funrb7Co a proč dělá funkce rb() z letáčku?
funm10Co a proč dělá funkce main() z letáčku?
9. 3. tram12Jak se změní úloha o řezání trámu z cvičení, pokud vyžadujeme konkrétní pořadí nařezaných částí?
13. 4. pmc9Variace na úlohu z cvičení: je dáno X a N. Kolik existuje způsobů, jak čísla 1,…N opatřit znaménky +/- tak, aby se sečetla na X? Vymyslete algoritmus, který to spočte.
4. 5. cmod12Vymyslete, jak spočítat kombinační číslo modulo M. Na cvičení jsme vyřešili případ, kdy M je prvočíslo, dořešte úlohu podobně efektivně pro obecné M.

Co jsme dělali

datum co se cvičilo
17. 2. Okénková maxima v 1D i 2D. Dynamické programování poprvé: rozklad textu na slova.
24. 2. DP podruhé: optimalizování klávesnice mobilu. DÚ: Napsat pseudokód.
2. 3. Knihovna na mnoho způsobů.
9. 3. Řezání trámu.
16. 3. Hrátky s kvadrantovými kódy. Komprese a dekomprese. Transformování kvadrantových obrázků.
23. 3. RLE komprese a hledání největší souvislé oblasti.
30. 3. Šíření zprávy po grafu. Jehla rozlámaná v seně (existence, počet výskytů, online verze).
6. 4. Ēostre, Paasfees, Великден, Ülestõusmispühad, Πάσχα, Páskar, 復活祭, Pace.
13. 4. Body v rovině a jejich rozklad na dvě středově symetrické množiny. ±1 + ±2 + … ±N = X.
20. 4. Věže v obdélnících. Intermezzo o van Emde Boasových stromech. Kombinační čísla.
27. 4. Doly a pásové dopravníky. Kombinační čísla podruhé, tentokrát modulo prvočíslo.
4. 5. Největší bílý obdélník.
11. 5. O randomizaci, derandomizaci a hladových algoritmech: šroubky a matičky, řezy v grafech a MAX-SAT.
18. 5. Kráva za plotem. Roboti v Dimenzi X. Opice na stromě.
Stránku spravuje Martin Mareš