Cvičení z Programování II pro pokročilé
Ve letním semestru 2015/2016 vedeme s Ondrou Hlavatý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í |
|---|---|---|---|
| 23. 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? | |
| 29. 3. | fib | 10 | Naprogramujte výpočet n-tého Fibonacciho čísla pomocí čísel tvaru a+sqrt(5)·b. (Viz návod na cvičení.) |
Co jsme dělali
| datum | co se cvičilo |
|---|---|
| 23. 2. | Obr v lese. |
| 1. 3. | Datové struktury pro okénková minima, součty a mediány. |
| 8. 3. | Počítání trojúhelníků v rovinných grafech. Splňování relací mezi čísly. Vlk a lovci. Barvení hran grafu dvěma barvami, aby každý vrchol viděl obě. |
| 15. 3. | Pokračování z minula. Testování existence hrany v konstantním čase. |
| 22. 3. | Dynamické programování poprvé: rozklad textu na slova, optimalizace klávesnice mobilu. |
| 29. 3. | Knihovna na mnoho způsobů. Řezání trámu. Iracionální odbočka. |
| 5. 4. | Trám řezaný, s uspořádáním i bez. |
| 12. 4. | Hrátky s kvadrantovými kódy. Komprese a dekomprese. Transformování kvadrantových obrázků. Problém malíře kvadrantisty. RLE komprese a hledání největší souvislé oblasti. |
| 19. 4. | Cvičení odpadá (vaši cvičící organizují soustředění KSP) |
| 26. 4. | Úterní chvilka geometrie: Obdélník obsahující na obvodu zadané body. Body v rovině a jejich rozklad na dvě středově symetrické množiny. Obsahy mnohoúhelníků a mřížové body. |
| 3. 5. | Počítání mřížových bodů, triangulace mnohoúhelníků a tajuplná Pickova formule. |
| 10. 5. | Kráva za plotem. Udržování lineárního uspořádání. |
| 17. 5. | Trocha praktického programování. |
| 23. 5. | Cesta dané délky ve stromu. Druhá nejmenší kostra. |