Cvičení z Programování I pro pokročilé
Ve školním roce 2018/2019 vedeme s Jirkou Sejkorou speciální cvičení z předmětu Programování I [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é pondělí od 14:00 v S10. 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í |
|---|---|---|---|
| 1. 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é? | |
| 22. 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. |
| 29. 10. | imed | 8 | Ukažte, jak pomocí výpočtu okénkového mediánu třídit. Přesněji řečeno dokažte, že máme-li algoritmus pro medián okénka velikosti k pracující v čase lepším než Θ(log k), lze z něj sestrojit třídicí algoritmus se složitostí lepší než Θ(n log n). |
| 7. 1. | gcolor | 10 | Uvažujme hladový algoritmus pro barvení grafu: Na počátku vrcholy nemají barvy. V každém kroku vybereme nějaký neobarvený vrchol a přiřadíme mu barvu s nejnižším číslem, kterou ještě nepoužívají jeho sousedé. Dokažte, že pro každé K existuje rovinný graf a pořadí výběru jeho vrcholů, při kterém hladové barvení spotřebuje aspoň K barev. |
| 1. 1. | extra | 0 | Dodatečné úkoly. |
Co jsme dělali
| datum | co se cvičilo |
|---|---|
| 1. 10. | Jedno chybějící číslo. Házení vajíček z mrakodrapu. |
| 8. 10. | Nejdelší úsek bez opakování. Úsek s maximálním součtem. Úsek se zadaným součtem. |
| 15. 10. | Nejdelší vyvážený úsek. Úsek se zadaným průměrem. Nejdelší bílý úsek, komplexní čísla a přihrádkové třídění. |
| 22. 10. | Největší jedničková podmatice na mnoho způsobů (zadané velikosti, zadané výšky, čtvercová, libovolná). Podmatice s maximálním součtem. |
| 29. 10. | Okénkova minima a mediány. |
| 5. 11. | Náhodné permutace a k-tice. Randomizované třídicí algoritmy. |
| 12. 11. | Nápovědy k praktickým úkolům. Rozvrhování přednášek a intervalové grafy. |
| 19. 11. | Generování všech objektů s danou vlastností: posloupnosti nul a jedniček, právě jedna změna, nejvýše k jedniček za sebou. |
| 26. 11. | Rank a unrank permutace, konstrukce lexikograficky následující permutace. (Zaskakoval Pavel Turinský.) |
| 3. 12. | O stromech, strážnících a mafiánech váženě i neváženě. |
| 10. 12. | Ještě o strážnících a mafiánech. |
| 17. 12. | Asfaltéři ve stromech i obecných grafech. Mazání hran podle požadavků na paritu stupňů. Mafiánský kápo. |
| 7. 1. | Hledání v monotónní matici. Barvení rovinných grafů 6 a 5 barvami. |