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
| Datum | Kód | Body | Zadání |
|---|---|---|---|
| 26. 2. | funrb | 7 | Co a proč dělá funkce rb() z letáčku? |
| funm | 10 | Co a proč dělá druhá funkce main() z letáčku? | |
| ksp | 0 | Sepsání vzorového řešení do KSP (počet bodů po domluvě). | |
| 2. 4. | optr | 10 | Zrychlete 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. | rlef | 10 | Je 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. |