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

DatumKódBodyZadání
1. 10. funf5Co dělá funkce f() z letáčku? Odpověď nezapomeňte zdůvodnit.
funb5Co dělá funkce bc() z letáčku? Odpověď nezapomeňte zdůvodnit.
2mis10Princezně 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. mdpx10Vymyslete 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. imed8Ukaž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. gcolor10Uvaž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. extra0Dodatečné úkoly.

Výsledky

JménoTeoretické příkladyReCodExBodůZápočťák
Patrik Beliansky9797 Maticová knihovna
Filip Čermák2mis(10) funf(5) mdpx(10) funb(5) gcolor(10)64104 Binomiální halda  OK Z
Peter Fačko2828
Petr Gebauer2mis(10) funf(5) funb(5) mdpx(10)74104 Intervalové stromy  OK Z
Nodari Gogatishvili2mis(10)1828 Pexeso
Břetislav Hájekfunb(5) funf(5)90100 Doplňování diakritiky
Miroslav Hrabal7777 Piškvorky
Michal Hýsek6666 Nejbližší dvojice bodů
Viktor Jančík2mis(10)7484 Pružinkový model grafu
Martin Koreček2mis(10) funf(5) funb(5) mdpx(10) imed(8)95133 Lineární rovnice  OK Z
Tomáš Korenýfunf(5)6671
Jakub Kozel88
Tomáš Kubíček2mis(10) funf(5) funb(5) mdpx(10)76106 Lore editor pro LARPy  OK Z
Filip Masár102102 Intervalový strom  OK Z
Jakub Medekfunf(5) funb(5) gcolor(10)83103 Logik  OK Z
Matěj Míčekfunf(5) funb(5) 2mis(10) gcolor(10) mdpx(10) imed(8) extra(2)50100 Simulace rostlin  OK Z
Ondřej Mózesfunf(5)5055 Hangman
Jakub Pelcfunf(5) funb(5) mdpx(10) imed(8)90118 Aurora Renderer  OK Z
Jiří Škrobánekfunf(5) funb(5) 2mis(10) mdpx(10) imed(8) gcolor(10)64112 (a,b)-stromy  OK Z
Tomáš Zeman2mis(10) funf(5) funb(5) mdpx(10) gcolor(10)4080 Netradiční kalkulačka

Pokud chcete být uvedeni pod přezdívkou, nebo dokonce vůbec, dejte nám vědět.

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.
Stránku spravuje Martin Mareš