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):
- vypracování domácích úkolů za alespoň 100 bodů
- vypracování zápočtového programu
Kontakt
Svým cvičícím pište na adresu mami@ucw.cz (Martin+Milan).
Zápočtový program
- Téma: libovolné, jaké si vymyslíte, má-li odpovídající obtížnost. Pokud vás ještě múza nepolíbila, podívejte se na náš seznam témat (na skladě též zdrojový text v TeXu a pěkně vysázená verze v PDF); přiměřené pro letní semestr jsou úlohy obtížnosti 5 a vyšší. Jinými zajímavými zdroji inspirace mohou být: archiv programátorského korespondenčního semináře a archiv Matematické Olympiády kategorie P.
- Jazyk: nejlépe Pascal nebo C; pokud máte dobrý důvod použít něco jiného, ozvěte se, lze se domluvit.
- Odevzdání specifikace programu do konce dubna. Tím máme na mysli krátký popis toho, co všechno by program měl umět. Vyhnete se tak tomu, že by váš zápočtový program odevzdaný den před koncem zkouškového období byl odmítnut jako příliš triviální nebo příliš podobný programu někoho z vašich kolegů.
- Nedílnou součástí zápočtového programu je dokumentace, a to jak uživatelská (vysvětující, jak se program ovládá), tak programátorská (ta popisuje, jak program uvnitř funguje; postrádá smysl popisovat každou funkci či proměnnou, zaměřte se spíš na celkový návrh programu a použité algoritmy, pokud jste je sami nevymysleli, je moudré uvést odkazy na zdroje, z nichž jste čerpali).
- Specifikaci i dokumentaci odevzdávejte buďto v papírové podobě nebo chcete-li šetřit naše lesy, elektronicky v libovolném otevřeném formátu (tím se myslí formát, jehož struktura je všeobecně známa a na jehož prohlížení není potřeba žádný komerční software; speciálně tedy ne MS Word!), nejlépe jako čistý text, HTML, PostScript či PDF.
- Hotový program nám mužete předat buďto na cvičení nahraný na CD či v lahvi (totiž USB flašce)
nebo jej poslat po Internetu, buďto e-mailem nebo (pokud je poněkud
větších rozměrů, řekněme nad 0.5MB) uploadem do
ftp://atrey.karlin.mff.cuni.cz/pub/priv/(ale pak pošlete mail se jménem souboru). Pokud se zápočťák skládá z většího množství souborů, raději jej předtím zabalte ZIPem nebo TARem (RAR, prosím, ne). - Zápočtový program musí mít přiměřeně ošetřené vstupy. Tím se myslí, že komunikuje-li s uživatelem, měl by počítat s tím, že uživatel je nešika a občas zadá špatný vstup a nenechat se tím zmást a bez zaváhání je odmítnout. Naopak, pokud programujete knihovnu funkcí, můžete předpokládat, že všechny vstupy jsou korektní.
Domácí úkoly
Domácí úkoly jsou dvou druhů:
- Praktické – odladěné programy řešící jednoduché problémy. Odevzdávají se do CodExu, který je automaticky testuje. Jakmile si v CodExu založíte účet (pokud možno si jako kroužek nastavte 99), napište nám a my vás přidáme do naší skupiny I99 a uvidíte všechny již zadané úlohy. Pozor, některé úlohy bude možné řešit pouze nějakou dobu (např. měsíc) po zadání.
- Teoretické – těžší problémy, kde jde daleko víc o efektivní algoritmus než implementační detaily. Řešení nám posílejte mailem, a to buď v těle zprávy nebo jako textovou přílohu. U některých úkolů je v hranatých závorkách zmíněna časová složitost, které (případně lepší) byste měli dosáhnout.
Na získání kýžené stovky bodů bohatě stačí praktické úlohy, pokud je řešíte včas.
Teoretické úkoly
| Datum | ID | Body | Příklady |
|---|---|---|---|
| 1. 3. | plor | 20 | Je 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. | libr | 20 | Vymyslete polynomiální algoritmus na 5. úlohu o knihovně. |
| 22. 3. | sack | 10 | Jak ř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. | lzhi | 20 | Mě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. | prgn | 7 | Co dělá funkce numbers z letáčku? |
| prgr | 7 | … a funkce rb()? | |
| prgm | 7 | … a co třeba funkce main()? | |
| prgz | 7 | … a ta čtvrtá funkce? |
Výsledky
| Jméno | Teoretické příklady | CodEx | Bodů | Zápočťák | Z |
|---|---|---|---|---|---|
| Marek Fišer | prgn(7) prgz(7) sack(15) prgr(7) bonus(12) | 52 | 100 | L-systémy II OK | Z |
| Miloslav Hlaváč | prgr(7) sack(10) lzhi(20) prgz(7) plor(20) prgn(7) libr(20) | 10 | 101 | (a,b)-stromy OK | Z |
| Jiří Maršík | sack(10) prgr(7) prgz(7) | 78 | 102 | Křížové reference OK | Z |
| Jan Matějka | prgn(7) prgr(7) prgm(7) prgz(7) lzhi(20) sack(10) bonus(6) libr(20) | 16 | 100 | TeX2HTML OK | Z |
| Jitka Novotná | sack(15) libr(20) lzhi(20) | 48 | 103 | PDF viewer OK | Z |
| Tomáš Pavlík | prgn(7) prgr(7) prgz(7) sack(10) bonus(55) | 38 | 124 | Rozpoznávání jazyka OK | Z |
| Martina Šimůnková | 60 | 60 | |||
| Pavel Veselý | lzhi(20) prgr(7) prgz(7) prgm(7) libr(20) | 42 | 103 | 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ě:
|
| 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. |