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
Benjy Compson0
Michal Jireš9696 Manažer pro online videa
František Kmječfunb(5) funf(5) 2mis(10)80100 Vyhledávátko spojení v PID
Jakub Komárek2mis(10) funf(5) funb(5)6989 AI pro piškvorky
Lenka Kopfová9696 Editor náramků přátelství
Samo Krajčífunf(5) funb(5) 2mis(10)84104 Nejkratší cesta v OSM
Michal Krejčí4343 Sudoku
Matěj Kripnerfunf(5) funb(5) 2mis(10) mdpx(10)74104 Knihovna CSanim
Dávid Kubek4848
Jan Kytkafunf(5) funb(5) 2mis(10)5575 Turingovi mravenci
Martin Mihálik9696 Huffmanovo kódování
Josef Minařík110110 Grafová knihovna
Radek Olšák9696
Jakub Pánekfunf(5) 2mis(10) mafi(10)7095 Elektronická peněženka
Martin Picekfunf(5) funb(5) 2mis(10)86106 Kořeny polynomů
Tadeáš Richtr00
Jakub Růžičkafunf(5)5
Tomáš Sláma2mis(10) funf(5) funb(5) mdpx(10)74104 Vimvaldi
Tomáš Sourada00
Matej Strakafunf(5) funb(5) 2mis(10)84104 Maticové operace
Martin Tréglfunf(5) funb(5) mdpx(10)80100 Loop
Eliška Vlčinskámdpx(10) 2mis(10)2848 Kreslítko L-systémů
Pavel Vodáček00
Tomáš Zeman5050
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š