Cvičení z Programování II pro pokročilé
Ve letním semestru 2016/2017 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. | bug | 0 | Ke konci semestru vydáváme knížku o ADS. Budu rád, když se na ni podíváte a upozorníte na všechny chyby, na které narazíte. Za každou novou faktickou chybu dostanete 1 bod. |
| funrb | 7 | Co a proč dělá funkce rb() z letáčku? | |
| funm | 10 | Co a proč dělá funkce main() z letáčku? | |
| 23. 5. | nkm | 15 | Vymyslete algoritmus, který spočítá kombinační číslo "n nad k" modulo m v čase lepším než lineárním s n, k. |
| 15. 7. | base | 15 | Vymyslete algoritmus pro převod dlouhého čísla mezi soustavami o různém základu. Číslo se nevejde do integeru, cokoliv omezené polynomem v základu soustavy ano. Dosáhněte lepší než kvadratické složitosti v počtu cifer. Hint: Metoda Rozděl a panuj. |
| 31. 8. | ksp | 15 | Sepsání vzorového řešení do KSP. (Pouze po předchozí domluvě.) |
| 22. 9. | book | 0 | Vyřešení sady cvičení z Průvodce labyrintem algoritmů. (Pouze po předchozí domluvě.) |
Co jsme dělali
| datum | co se cvičilo |
|---|---|
| 21. 2. | Počítání trojúhelníků v rovinných grafech. Trampoty jeřábníkovy. |
| 28. 2. | Programátorská rozcvička. |
| 7. 3. | Dynamické programování poprvé: rozklad textu na slova. |
| 14. 3. | Dynamické programování podruhé: optimalizace klávesnice mobilu, nejnižší knihovna s pořadím a bez. |
| 21. 3. | Nejužší knihovna s celými čísly i bez. Řezání trámu. |
| 28. 3. | Trám řezaný, s uspořádáním i bez. |
| 4. 4. | Dvojice, trojice, čtveřice. |
| 11. 4. | Vykopávky. Počet obdélníků obsahujících bod mřížky. Rozpoznávání středově symetrických množin. |
| 18. 4. | Úterní chvilka geometrie: rozklad na dvě středově symetrické množiny. |
| 25. 4. | Obsah mnohoúhelníka a počet mřížových bodů. |
| 2. 5. | Cvičení se nekoná (soustředění KSP) |
| 9. 5. | Programátorská rozcvička II: Problém malíře kvadrantisty. |
| 16. 5. | Kráva za plotem. Permutace s co nejkratšími monotónními podposloupnostmi. Mlýnek na čísla a hledání cyklu. |
| 23. 5. | Kombinační čísla modulo prvočíslo. Cesta dané délky ve stromu. |