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.
30. 11. kmaj15Uvaž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. perm10Naprogramujte rekurzivní generátor permutací z cvičení tak, aby měl časovou složitost O(n!) bez vypisování permutací.

Výsledky

JménoTeoretické příkladyCodExBodůZápočťák
Vojtěch Antošík2mis(10) funf(5) kmaj(15)5282 Luštění substituční šifry  OK
Filip Bialas2mis(10)8292 Cherlinova vlastnost
František Deckert2mis(10) funf(5) funb(5) rep3(10) kmaj(15) mdpx(5)52102 Přijímačkové testy  OK Z
Tomáš Domes2mis(10) funf(5) rep3(10) kmaj(15) okmin(10)52102 Fibonacciho halda  OK Z
Jakub Hejhal2mis(10) perm(10) funb(5) funf(5) mdpx(10)62102 Harmonické oscilátory  OK
Richard Hladík2mis(10) funf(5) funb(5) rep3(10) mdpx(10)78118 Předimenzovaná ladička
Tomáš Konečnýfunf(5) funb(5) 2mis(10) rep3(10)74104 Problém N těles  OK Z
Stanislav Lukešfunb(5) funf(5) 2mis(10) mdpx(10)75105 Prohlížedlo performance testů  OK Z
Pavel Pakhomov0
Jiří Pelc4141 Grafová knihovna
Martin Robovský1616
Lukáš Rozsypalfunf(5) funb(5) 2mis(10) perm(10) mdpx(10)62102 Hot and Cold  OK Z
Petr Salaba1515 Maticová knihovna
Václav Steinhauser2mis(10)616 Šachová úloha
Štěpán Stenchlákfunf(5) funb(5) 2mis(10) rep3(10) mdpx(10) okmin(10) perm(10)42102 Vizualizace třídění  OK Z
Martin Strouhal00
Petr Šimůnekfunf(5) funb(5) 2mis(10) rep3(10) okmin(10) mdpx(10) kmaj(15)47112 Animované bludiště  OK Z
Václav Šraierfunf(5) funb(5) 2mis(10) mdpx(10) perm(10)62102 Kademlia DHT  OK Z
Přemysl Šťastný2mis(10) funf(5) rep3(10) funb(5) perm(10)62102 3D miny  OK Z
Michal Töpferfunb(5) funf(5) 2mis(10) mdpx(10) kmaj(15) perm(10)52107 Markovovské texty  OK Z
Pavel Turinskýfunf(5) rep3(10) funb(5)5272 Supercron
Václav Volhejnfunf(5) 2mis(10)92107 Samorozvrh  OK Z
Damian Wałoszek2mis(10) rep3(10) mdpx(10) funf(5) funb(5) okmin(10)50100 Skládání rubikovky  OK Z
Vilém Zouhar2mis(10) funf(5) funb(5) rep3(10) kmaj(15) perm(10)52107 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.
Stránku spravuje Martin Mareš