Cvičení z Programování II pro pokročilé
Ve letním semestru 2017/2018 vedeme s Filipem Štědronským 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 15:40 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í |
|---|---|---|---|
| 28. 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? | |
| 24. 4. | lzf | 10 | Mějme text zkomprimovaný metodou LZ77. Zakódovaný soubor obsahuje posloupnost instrukcí typu "ulož do výstupu tento znak" a "zkopíruj K znaků nacházejících se ve výstupu o P pozic nazpět". Zjistěte pro každý znak, kolikrát se v dekódovaném výstupu vyskytuje. Časová složitost by měla být polynomiální ve velikosti zakódovaného vstupu, nezávisle na velikosti dekódovaného výstupu. |
| 22. 5. | jerab | 20 | Vymyslete datovou strukturu pro zjišťování pozic háků stromového jeřábu. Měla by podporovat operace "otoč úsekem X o Y stupňů okolo kloubu, na němž je připojen" a "zjisti pozici háku H". |
| choose | 15 | Vymyslete algoritmus, který spočítá "n nad k modulo m". Plný počet bodů za obecné m, 10 bodů za prvočíselné. | |
| ksp | 0 | Sepsání vzorového řešení do KSP. |
Co jsme dělali
| datum | co se cvičilo |
|---|---|
| 20. 2. | Počítání trojúhelníků v rovinných grafech a online vs. offline dotazy. Isomorfismus stromů. |
| 28. 2. | Dynamické programování poprvé: rozklad textu na slova. |
| 6. 3. | Dynamické programování podruhé: nejnižší a nejužší knihovna, s pořadím i bez. |
| 13. 3. | Dynamické programování potřetí: nejdelší společná podposloupnost, optimální vyhledávací strom. |
| 20. 3. | Závorkování násobení matic a obecně hledání různých optimálních stromů. Trám řezaný, s uspořádáním i bez. |
| 27. 3. | Ještě jednou o trámech. Nejdelší opakující se podřetězec. |
| 3. 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. |
| 10. 4. | Ještě středově symetrické množiny. Hledání prázdného trojúhelníku. Konvexní obal a testování orientace. |
| 17. 4. | Obsah mnohoúhelníka. |
| 24. 4. | 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. |
| 1. 5. | Slavíme svátek práce tím, že nepracujeme. Zvláštní, že? |
| 8. 5. | Informatici slaví 128. den v roce. |
| 15. 5. | Kráva za plotem. Kombinační čísla. |
| 22. 5. | Ještě o kombinačních číslech a prvočíslech. Mlýnek na čísla a hledání cyklu. Kde srostly spojáky? Trampoty jeřábníkovy. |