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

Ve letním semestru 2017/2018 vedeme s Filipem Štědronským speciální cvičení z předmětu Programování II [NPRG031] 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. Tematicky bude navazovat na Programování I pro pokročilé z minulého semestru, ale jeho absolvování určitě nebude nutné pro účast na tomto cvičení.

Cvičení se koná každé úterý od 15:40 v S8, kdo chcete chodit, přihlašte se 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. Také se můžete podívat na reklamní letáček.

Svým cvičícím pište na adresu mami@ucw.cz.

Teoretické úkoly

DatumKódBodyZadání
28. 2. funrb7Co a proč dělá funkce rb() z letáčku?
funm10Co a proč dělá funkce main() z letáčku?
24. 4. lzf10Mějme text zkomprimovaný metodou LZ77. Zakódovaný soubor obsahuje posloupnost instrukcí typu "ulož do výstupu tento znak" a "zkopíruj K znaků nacházejících se ve výstupu o P pozic nazpět". Zjistěte pro každý znak, kolikrát se v dekódovaném výstupu vyskytuje. Časová složitost by měla být polynomiální ve velikosti zakódovaného vstupu, nezávisle na velikosti dekódovaného výstupu.
22. 5. jerab20Vymyslete datovou strukturu pro zjišťování pozic háků stromového jeřábu. Měla by podporovat operace "otoč úsekem X o Y stupňů okolo kloubu, na němž je připojen" a "zjisti pozici háku H".
choose15Vymyslete algoritmus, který spočítá "n nad k modulo m". Plný počet bodů za obecné m, 10 bodů za prvočíselné.
ksp0Sepsání vzorového řešení do KSP.

Výsledky

JménoTeoretické příkladyCodExBodůZápočťák
Filip Bialas5858 Voroného diagramy
František Deckert0
Tomáš Domes4545 (a,b)-stromy
Jakub Hejhal4242
Richard Hladík4545 Polynomová knihovna
Maximilian Kulikov2323 Syntezátor zvuku
Stanislav Lukeš2222 Symbolický interpret
Anh Nguyen Ngoc00 3D plošinovka
Martin Robovský00 Průvodky
Lukáš Rozsypalfunrb(7) funm(10)2946
Václav Steinhauser00
Štěpán Stenchlákfunrb(7) lzf(10) choose(5)6789 Online grafové algoritmy
Petr Šimůnekfunrb(7)4653 3D modely budov  OK
Václav Šraierfunrb(7) ksp(22)78107 Emulátor procesoru MIPS32  OK Z
Přemysl Šťastný3535 Chatovátko
Pavel Turinský2929 Zpěvník
Václav Volhejnjerab(20)5777 Zaostřování čárových kódů

Body z CodExu 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
20. 2. Počítání trojúhelníků v rovinných grafech a online vs. offline dotazy. Isomorfismus stromů.
28. 2. Dynamické programování poprvé: rozklad textu na slova.
6. 3. Dynamické programování podruhé: nejnižší a nejužší knihovna, s pořadím i bez.
13. 3. Dynamické programování potřetí: nejdelší společná podposloupnost, optimální vyhledávací strom.
20. 3. Závorkování násobení matic a obecně hledání různých optimálních stromů. Trám řezaný, s uspořádáním i bez.
27. 3. Ještě jednou o trámech. Nejdelší opakující se podřetězec.
3. 4. Úterní chvilka geometrie: prokládání obdélníka množinou bodů. Rozpoznávání středově symetrických množin. Rozklad na dvě středově symetrické množiny.
10. 4. Ještě středově symetrické množiny. Hledání prázdného trojúhelníku. Konvexní obal a testování orientace.
17. 4. Obsah mnohoúhelníka.
24. 4. Hrátky s kvadrantovými kódy. Komprese a dekomprese. Transformování kvadrantových obrázků. Problém malíře kvadrantisty (a jeho komprimovaná verze). RLE komprese a hledání největší souvislé oblasti.
1. 5. Slavíme svátek práce tím, že nepracujeme. Zvláštní, že?
8. 5. Informatici slaví 128. den v roce.
15. 5. Kráva za plotem. Kombinační čísla.
22. 5. Ještě o kombinačních číslech a prvočíslech. Mlýnek na čísla a hledání cyklu. Kde srostly spojáky? Trampoty jeřábníkovy.
Stránku spravuje Martin Mareš