Cvičení z Programování I pro pokročilé
Ve školním roce 2017/2018 vedeme s Filipem Štědronským 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ý čtvrtek od 15:40 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í |
---|---|---|---|
5. 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é? | |
26. 10. | rep3 | 10 | Je dána posloupnost n čísel z rozsahu 0, … n3-1. Nalezněte v čase O(n) nejdelší úsek, v němž se žádné číslo neopakuje. |
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. | |
16. 11. | okmin | 10 | Je dána posloupnost celých čísel. Pro každé k zjistěte, jaké je maximum z minim okének délky k. Existuje řešení v lineárním čase. |
30. 11. | kmaj | 15 | Uvažujme následující variantu úlohy o volbách: je dáno k, chceme najít všechny kandidáty, kteří dostali víc než jednu (k+1)-tinu všech hlasů. Opět chceme lineární čas, spotřeba paměti smí záviset pouze na k. |
14. 12. | perm | 10 | Naprogramujte rekurzivní generátor permutací z cvičení tak, aby měl časovou složitost O(n!) bez vypisování permutací. |
Výsledky
Jméno | Teoretické příklady | CodEx | Bodů | Zápočťák |
---|---|---|---|---|
Vojtěch Antošík | 2mis(10) funf(5) kmaj(15) | 52 | 82 | Luštění substituční šifry OK |
Filip Bialas | 2mis(10) | 82 | 92 | Cherlinova vlastnost |
František Deckert | 2mis(10) funf(5) funb(5) rep3(10) kmaj(15) mdpx(5) | 52 | 102 | Přijímačkové testy OK Z |
Tomáš Domes | 2mis(10) funf(5) rep3(10) kmaj(15) okmin(10) | 52 | 102 | Fibonacciho halda OK Z |
Jakub Hejhal | 2mis(10) perm(10) funb(5) funf(5) mdpx(10) | 62 | 102 | Harmonické oscilátory OK |
Richard Hladík | 2mis(10) funf(5) funb(5) rep3(10) mdpx(10) | 78 | 118 | Předimenzovaná ladička |
Tomáš Konečný | funf(5) funb(5) 2mis(10) rep3(10) | 74 | 104 | Problém N těles OK Z |
Stanislav Lukeš | funb(5) funf(5) 2mis(10) mdpx(10) | 75 | 105 | Prohlížedlo performance testů OK Z |
Pavel Pakhomov | – | 0 | ||
Jiří Pelc | 41 | 41 | Grafová knihovna | |
Martin Robovský | 16 | 16 | ||
Lukáš Rozsypal | funf(5) funb(5) 2mis(10) perm(10) mdpx(10) | 62 | 102 | Hot and Cold OK Z |
Petr Salaba | 15 | 15 | Maticová knihovna | |
Václav Steinhauser | 2mis(10) | 6 | 16 | Šachová úloha |
Štěpán Stenchlák | funf(5) funb(5) 2mis(10) rep3(10) mdpx(10) okmin(10) perm(10) | 42 | 102 | Vizualizace třídění OK Z |
Martin Strouhal | 0 | 0 | ||
Petr Šimůnek | funf(5) funb(5) 2mis(10) rep3(10) okmin(10) mdpx(10) kmaj(15) | 47 | 112 | Animované bludiště OK Z |
Václav Šraier | funf(5) funb(5) 2mis(10) mdpx(10) perm(10) | 62 | 102 | Kademlia DHT OK Z |
Přemysl Šťastný | 2mis(10) funf(5) rep3(10) funb(5) perm(10) | 62 | 102 | 3D miny OK Z |
Michal Töpfer | funb(5) funf(5) 2mis(10) mdpx(10) kmaj(15) perm(10) | 52 | 107 | Markovovské texty OK Z |
Pavel Turinský | funf(5) rep3(10) funb(5) | 52 | 72 | Supercron |
Václav Volhejn | funf(5) 2mis(10) | 92 | 107 | Samorozvrh OK Z |
Damian Wałoszek | 2mis(10) rep3(10) mdpx(10) funf(5) funb(5) okmin(10) | 50 | 100 | Skládání rubikovky OK Z |
Vilém Zouhar | 2mis(10) funf(5) funb(5) rep3(10) kmaj(15) perm(10) | 52 | 107 | Rozpoznávání jazyka OK Z |
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 |
---|---|
5. 10. | Jedno chybějící číslo. Číslo s lichým počtem výskytů. Robin Hood a euklidovská lukostřelba. Robin Hood a předvolební billboardy. |
12. 10. | Nejdelší úsek bez opakování. Úsek se zadaným součtem. |
19. 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í. |
26. 10. | Nejkratší úsek obsahující všechny prvky. Největší edničková podmatice na mnoho způsobů (zadané velikosti, zadané výšky, čtvercová, libovolná). Okénková minima. |
2. 11. | Pokračování z minula. |
9. 11. | Okénkové mediány. Jak pro každou velikost okénka zjistit maximum z minim. Předvýpočet: nejbližší vyšší prvek oběma směry. |
16. 11. | Náhodné permutace a k-tice. Randomizované třídicí algoritmy. |
23. 11. | Cvičení se nekoná, dnes otevíráme dveře. |
30. 11. | Volby na mnoho způsobů: randomizace, různé druhy půlení intervalu, lineární řešení. |
7. 12. | 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. |
14. 12. | Generování permutací: rekurze, lexikografický následník, rank a unrank. |
21. 12. | O stromech a strážnících váženě i neváženě. |
4. 1. | O strážnících, mafiánech a asfaltérech. |
11. 1. | Asfaltování obecných grafů. Mafiánský kápo. Barvení rovinných grafů 6 a 5 barvami. |