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
| Datum | Kód | Body | Zadání |
|---|---|---|---|
| 17. 2. | funrb | 7 | Co a proč dělá funkce rb() z letáčku? |
| funm | 10 | Co a proč dělá funkce main() z letáčku? | |
| 9. 3. | tram | 12 | Jak 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. | pmc | 9 | Variace 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. | cmod | 12 | Vymyslete, 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ě. |