Cvičení z Programování 1 pro pokročilé
Ve školním roce 2019/2020 vedeme s Richardem Hladíkem speciální cvičení z předmětu Programování 1 [NPRG030] 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. Podívejte se na reklamní letáček.
Cvičení se koná každý čtvrtek od 14:00 v S8. Kdo chcete chodit, přihlašte se, prosíme, 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í |
|---|---|---|---|
| 3. 10. | funf | 5 | Co dělá funkce f() z letáčku? Odpověď nezapomeňte zdůvodnit. |
| funb | 5 | Co dělá funkce bc() z letáčku? Odpověď nezapomeňte zdůvodnit. | |
| 2mis | 10 | Princezně se rozsypaly perly z náhrdelníku (očíslované 1 až N) a dvě z nich se ztratily. Jak v lineárním čase a konstantní paměti zjistit, které? | |
| 24. 10. | mdpx | 10 | Vymyslete d-rozměrnou variantu prefixových součtů, tedy strukturu, která si pro d-rozměrnou matici v lineárním čase něco předpočítá a pak bude umět v konstantním čase vypočíst součet libovolné d-rozměrné souvislé podmatice. Předpokládejte, že d je konstanta. |
| 9. 1. | mafi | 10 | Občané městečka očíslovaní od 1 do N přišli k výslechu. Dostali jsme množinu výpovědí typu "Občan X tvrdí, že Y je/není mafián." (Ne všechny dvojice X, Y se ve výpovědích vyskytují.) Mafiáni vždy lžou, poctivci vždy mluví pravdu. Zjistěte, kteří občané jsou mafiáni, případně že množina výpovědí není konsistentní. |
| rank | 10 | Vymyslete uspořádání na množině všech permutací množiny {1,…N}, ve kterém půjde provádět rank i unrank v lineárním čase. |
Co jsme dělali
| datum | co se cvičilo |
|---|---|
| 3. 10. | Jedno chybějící číslo. Házení vajíček z mrakodrapu. Nejmenší chybějící číslo v setříděné posloupnosti. Robin Hood a euklidovská lukostřelba. Robin Hood a billboardy. |
| 10. 10. | Nejdelší úsek bez opakování. Úsek s maximálním součtem. Úsek se zadaným součtem. Počet takových úseků. |
| 17. 10. | Nejdelší vyvážený úsek. Úsek se zadaným průměrem. Nejdelší bílý úsek. |
| 24. 10. | Podmatice s maximálním součtem (zadané velikosti, zadané výšky, libovolná). Největší podmatice bez nuly, čtvercová verze. |
| 31. 10. | Okénkova minima a mediány. |
| 7. 11. | Ještě k minimům a mediánům. |
| 14. 11. | Jak poznat skóre grafu. |
| 21. 11. | Cvičení se nekonalo, otevírali jsme dveře. |
| 28. 11. | Náhodné permutace a k-tice. Randomizované třídicí algoritmy. |
| 5. 12. | O stromech, strážnících, mafiánech a asfaltérech váženě i neváženě. |
| 12. 12. | Mafiáni doděláni. Asfaltéři zůstávají, k tomu navíc nejdelší cesta ve stromu. |
| 19. 12. | Asfaltéři v obecných grafech. Mafiánský kápo. |
| 9. 1. | Permutace: generování všech, generování s právě jednou změnou, lexikografický následník, rank a unrank. |