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

Ve školním roce 2009/2010 vedeme s Milanem Strakou a Vojtou Tůmou 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.

Cvičení se koná každé pondělí od 12:20 v S6, kdo chcete chodit, přihlašte se, prosíme, v SISu, nebo napište mail. Milana tentokrát budete potkávat jen na dálku, přebývá ve staré dobré Anglii a bude se nám starat zejména o úlohy v CodExu.

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í.

Podmínky k získání zápočtu jsou (AND):

Kontakt

Svým cvičícím pište na adresu mami@ucw.cz (Martin+Milan).

Zápočtový program

Domácí úkoly

Domácí úkoly jsou dvou druhů:

Na získání kýžené stovky bodů bohatě stačí praktické úlohy, pokud je řešíte včas.

Teoretické úkoly

DatumIDBodyPříklady
1. 3. plor20Je dán rovinný graf. Zorientujte ho tak, aby z každého vrcholu vycházely nejvýše 3 hrany. Najděte řešení v lepším než kvadratickém čase. Hint: párování.
15. 3. libr20Vymyslete polynomiální algoritmus na 5. úlohu o knihovně.
22. 3. sack10Jak řešit problém batohu (s cenami), když hmotnosti mohou být libovolná kladná reálná čísla, ale víte, že ceny jsou celočíselné a rozumně malé?
[+5 bodů] pokud kromě nejlepší ceny najdete i seznam předmětů (v rozumném čase a paměti).
10. 5. lzhi20Mějme text komprimovaný metodou LZ77 (popsaný posloupností instrukcí typu "zapiš tyto nekomprimované znaky" a "zkopíruj souvislý úsek už vygenerovaného textu"). Navrhněte algoritmus, který spočte četnost zadaného znaku v tomto textu. Časová složitost smí záviset pouze na délce komprimovaného tvaru, a to polynomiálně (může se stát, že původní text je exponenciálně dlouhý).
17. 5. prgn7Co dělá funkce numbers z letáčku?
prgr7… a funkce rb()?
prgm7… a co třeba funkce main()?
prgz7… a ta čtvrtá funkce?
$#

Výsledky

JménoTeoretické příkladyCodExBodůZápočťákZ
Marek Fišerprgn(7) prgz(7) sack(15) prgr(7) bonus(12)52100 L-systémy II  OK Z
Miloslav Hlaváčprgr(7) sack(10) lzhi(20) prgz(7) plor(20) prgn(7) libr(20)10101 (a,b)-stromy  OK Z
Jiří Maršíksack(10) prgr(7) prgz(7)78102 Křížové reference  OK Z
Jan Matějkaprgn(7) prgr(7) prgm(7) prgz(7) lzhi(20) sack(10) bonus(6) libr(20)16100 TeX2HTML  OK Z
Jitka Novotnásack(15) libr(20) lzhi(20)48103 PDF viewer  OK Z
Tomáš Pavlíkprgn(7) prgr(7) prgz(7) sack(10) bonus(55)38124 Rozpoznávání jazyka  OK Z
Martina Šimůnková6060
Pavel Veselýlzhi(20) prgr(7) prgz(7) prgm(7) libr(20)42103 Veselé mapy  OK Z

Co jsme dělali

datum co se cvičilo
22. 2. Barvení rovinných grafů 6 a 5 barvami. Datová struktura pro Union-Find.
1. 3. Hledání nejdelšího 4-cyklu v grafu s omezenými stupni. Hrátky s intervalovými grafy: maximální nezávislá množina (rozvrh z pohledu studenta), barvení (rozvrh z pohledu líného vrátného), rozklad na kliky (chemikálie v ledničkách).
8. 3. Silná souvislost a polosouvislost orientovaných grafů. Dynamické programování poprvé: rozklad textu na slova, krájení borůvkového koláče.
15. 3. DP podruhé: zalamování odstavců. Odbočka: souvislost s nejkratšími cestami v grafech. Odbočka z odbočky: Haldy klasické i d-regulární a HeapSort. Úlohy o knihovně:
  1. Je dána šířka knihovny, spočítat minimální možnou výšku. Pořadí knih je pevné, výšky i šířky knih jsou libovolná kladná čísla.
  2. Je dána maximální výška, spočítat minimální možnou šířku. Opět pevné pořadí knih, všechny knihy jsou stejně široké, výšky se liší.
  3. Jako 2., ale na pořadí knih nezáleží.
  4. Jako 3., ale smíme použít nejvýše K polic.
  5. Jako 1., ale smíme knihy klást i do sloupečků.
22. 3. DP potřetí: pokračujeme s knihovnami. Co způsobí rozdílné požadavky na tloušťku knížek (pevná/celočíselná/reálná). Co si počít s batohem?
29. 3. Problém s jídelníčkem (posloupnosti délky N nad K-prvkovou abecedou, které neobsahují L po sobě jdoucích stejných znaků) a jak souvisí s násobením matic. Mravenčí překážkový běh a kombinační čísla.
5. 4. Ēostre, Paasfees, Великден, Ülestõusmispühad, Πάσχα, Páskar, 復活祭, Pace. Nabídka dne: Oudinův algoritmus pro výpočet data Velikonoc (gregoriánských), spletitá historie dalších algoritmů a Calendar FAQ.
12. 4. Geometrie: Robin Hood a šerifovi poskoci (přímka s největším počtem bodů). Co nejvíce bodů na kružnici. Rozdělujeme množinu bodů na dvě středově symetrické. Krátké odbočky k universálnímu hashování a k turnajům.
19. 4. Opět geometrie: Obsah mnohoúhelníku, počítání mřížových bodů (a Pickova formule). Hledáme v grafu nejkratší cyklus obsahující zadaný vrchol.
26. 4. Rotování matice (umíme rotovat a negovat řádek a sloupec, žádný prvek nesmí být negován dvakrát, chceme dosáhnout co největšího součtu). Inkrementování (na počátku prázdné pole, pak postupně inkrementujeme políčka na pozicích dělitelných d1, …, dk, načež odpovídáme na dotazy na součty úseků). Euklidovský obchodní cestující.
3. 5. Platba dluhu. K-tý nejmenší prvek v intervalech. Holičův problém. Rozdělení práce dělníkům. Je zadán čtverec N×N a jeho K podobdélníků. Spočítejte pro každé políčko, v kolika podobdélnících se vyskytuje.
10. 5. Práce s komprimovanými daty: transformace kvadrantových stromů, problém malíře kvadrantisty, rozklad RLE-komprimovaného obrázku na souvislé oblasti (s Union-Findem i bez něj), frekvence znaků v LZ-komprimovaném textu.
17. 5. Šifrovačkové úlohy: nedělená morseovka (a jak najít nejlepších K řešení namísto jediného optimálního), luštění Vigenérovy šifry.
Stránku spravuje Martin Mareš