Cvičení z Programování 1 pro pokročilé

Ve školním roce 2019/2020 vedeme s Richardem Hladíkem speciální cvičení z předmětu Programování 1 [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 14:00 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í
3. 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é?
24. 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.
9. 1. mafi10Občané městečka očíslovaní od 1 do N přišli k výslechu. Dostali jsme množinu výpovědí typu "Občan X tvrdí, že Y je/není mafián." (Ne všechny dvojice X, Y se ve výpovědích vyskytují.) Mafiáni vždy lžou, poctivci vždy mluví pravdu. Zjistěte, kteří občané jsou mafiáni, případně že množina výpovědí není konsistentní.
rank10Vymyslete uspořádání na množině všech permutací množiny {1,…N}, ve kterém půjde provádět rank i unrank v lineárním čase.

Výsledky

JménoTeoretické příkladyReCodExBodůZápočťák
Michaela Bobeničová00
Michal Jireš110110 Manažer pro online videa
František Kmječfunb(5) funf(5) 2mis(10)7898 Vyhledávátko spojení v PID
Jakub Komárek2mis(10) funf(5) funb(5)81101 AI pro piškvorky
Lenka Kopfováfunf(5)96101 Editor náramků přátelství  OK Z
Samo Krajčífunf(5) funb(5) 2mis(10)20 Nejkratší cesta v OSM  OK Z
Michal Krejčí4343 Sudoku
Matěj Kripnerfunf(5) funb(5) 2mis(10) mdpx(10)74104 Knihovna CSanim  OK Z
Dávid Kubek4848
Jan Kytkafunf(5) funb(5) 2mis(10)7191 Turingovi mravenci
Martin Mihálik9696 Huffmanovo kódování
Josef Minařík106106 Grafová knihovna  OK Z
Radek Olšákfunf(5)96101 Webová databáze úloh
Jakub Pánekfunf(5) 2mis(10) mafi(10) mdpx(10)65100 Elektronická peněženka
Martin Picekfunf(5) funb(5) 2mis(10)85105 Kořeny polynomů  OK
Tadeáš Richtr00
Tomáš Sláma2mis(10) funf(5) funb(5) mdpx(10)74104 Vimvaldi
Tomáš Sourada00
Matej Strakafunf(5) funb(5) 2mis(10)20 Maticové operace  OK Z
Martin Tréglfunf(5) funb(5) mdpx(10)80100 Loop
Eliška Vlčinskámdpx(10) 2mis(10)2747 Kreslítko L-systémů
Pavel Vodáček00
Tomáš Zeman4949
Martin Zimen2mis(10) funf(5) funb(5) mdpx(10)86116 Lesní Minesweeper  OK Z

Body z ReCodExu se přepočítávají jednou nočně. 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
3. 10. Jedno chybějící číslo. Házení vajíček z mrakodrapu. Nejmenší chybějící číslo v setříděné posloupnosti. Robin Hood a euklidovská lukostřelba. Robin Hood a billboardy.
10. 10. Nejdelší úsek bez opakování. Úsek s maximálním součtem. Úsek se zadaným součtem. Počet takových úseků.
17. 10. Nejdelší vyvážený úsek. Úsek se zadaným průměrem. Nejdelší bílý úsek.
24. 10. Podmatice s maximálním součtem (zadané velikosti, zadané výšky, libovolná). Největší podmatice bez nuly, čtvercová verze.
31. 10. Okénkova minima a mediány.
7. 11. Ještě k minimům a mediánům.
14. 11. Jak poznat skóre grafu.
21. 11. Cvičení se nekonalo, otevírali jsme dveře.
28. 11. Náhodné permutace a k-tice. Randomizované třídicí algoritmy.
5. 12. O stromech, strážnících, mafiánech a asfaltérech váženě i neváženě.
12. 12. Mafiáni doděláni. Asfaltéři zůstávají, k tomu navíc nejdelší cesta ve stromu.
19. 12. Asfaltéři v obecných grafech. Mafiánský kápo.
9. 1. Permutace: generování všech, generování s právě jednou změnou, lexikografický následník, rank a unrank.
Stránku spravuje Martin Mareš