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) rep3(10) okmin(10) | 52 | 102 | 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) | 78 | 108 | Problém N těles OK Z |
| Stanislav Lukeš | funb(5) funf(5) 2mis(10) mdpx(10) | 78 | 108 | Prohlížedlo performance testů OK Z |
| Pavel Pakhomov | – | 0 | ||
| Jiří Pelc | 42 | 42 | Grafová knihovna | |
| Martin Robovský | 18 | 18 | ||
| Lukáš Rozsypal | funf(5) funb(5) 2mis(10) perm(10) mdpx(10) | 62 | 102 | Hot and Cold OK Z |
| Petr Salaba | 18 | 18 | Maticová knihovna | |
| Václav Steinhauser | 2mis(10) | 8 | 18 | Š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) | 52 | 117 | 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) | 52 | 102 | 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. |