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

DatumKódBodyZadání
5. 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é?
26. 10. rep310Je 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.
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.
16. 11. okmin10Je 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.

Výsledky

JménoTeoretické příkladyCodExBodůZápočťák
Vojtěch Antošík2mis(10) funf(5)15
Filip Bialas2mis(10)10
František Deckert2mis(10) funf(5) funb(5)20
Tomáš Domes2mis(10)10
Jakub Hejhal2mis(10)10
Richard Hladík2mis(10) funf(5) funb(5) rep3(10) mdpx(10)40
Tomáš Konečnýfunf(5) funb(5) 2mis(10)20 Problém N těles
Stanislav Lukešfunb(5) funf(5) 2mis(10)20 Prohlížedlo performance testů
Pavel Pakhomov0
Jiří Pelc0
Martin Robovský0
Lukáš Rozsypalfunf(5) funb(5) 2mis(10)20
Petr Salaba0
Václav Steinhauser2mis(10)10
Štěpán Stenchlákfunf(5) funb(5) 2mis(10) rep3(10) mdpx(10)40
Martin Strouhal0
Petr Šimůnekfunf(5) funb(4) 2mis(10) rep3(10)29 Animované bludiště
Václav Šraierfunf(5) funb(5) 2mis(10) mdpx(10)30 Kademlia DHT
Přemysl Šťastný2mis(10) funf(5) rep3(10) funb(5)30 3D miny  OK
Michal Töpferfunb(5) funf(5) 2mis(10) mdpx(10)30 Markovovské texty
Pavel Turinskýfunf(5)5
Václav Volhejnfunf(5) 2mis(10)15 Samorozvrh
Damian Wałoszek2mis(10)10
Vilém Zouhar2mis(10) funf(5) funb(5) rep3(10)30 Rozpoznávání jazyka  OK

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