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

Ve školním roce 2008/2009 vedeme s Milanem Strakou 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 S8, kdo chcete chodit, přihlašte se, prosíme, v SISu.

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
2. 3.	lcsx	15	Vymyslete algoritmus na nalezení nejdelší společné posloupnosti, který bude efektivnější v případech, kdy do hledané posloupnosti padne většina vstupu.
9. 3.	mtri	15	Je dán konvexní mnohoúhelník. Chceme jej triangulovat, tj. rozdělit nekřížícími se úhlopříčkami na trojúhelníky. Jak najít minimální triangulaci co do celkové délky použitých úhlopříček?
16. 3.	tspx	20	Jistý obchodní cestující nabízí následující problém: mějme neorientovaný graf s ohodnocenými hranami a hledejme v něm nejkratší kružnici, na níž leží všechny vrcholy. Polynomiálně to zatím nikdo neumí, ale zkuste najít algoritmus, který beží v čase O(2^N*N^k) pro co nejmenší k.
11. 5.	2sat	20	Jak vyřešit 2-SAT v lineárním čase?

Co jsme dělali

datum	co se cvičilo
23. 2.	Jak spočítat N nad K modulo M?
2. 3.	Dynamické programování poprvé: dělíme text na slova, optimalizujeme mobilnici, hledáme nejdelší společnou podposloupnost.
9. 3.	DP podruhé – úlohy o knihovně: 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. 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ší. Jako 2., ale na pořadí knih nezáleží. Jako 3., ale smíme použít nejvýše K polic. Jako 1., ale smíme knihy klást i do sloupečků.
16. 3.	DP po3.: nejdelší vybraný kopec, optimální binární vyhledávací strom (včetně triku pro redukci na N² operací), dlaždičkování dálnice.
23. 3.	Geometrické algoritmy: problém obchodního cestujícího pro body v konvexní poloze, obsah mnohoúhelníka, těžiště a počítání mřížových bodů.
30. 3.	Hamiltonovské kružnice a prostorová složitost. Ze života vánočních dárků. Nejkratší program pro RPN kalkulačku generující dané číslo. Nejdelší čtyřcyklus. Nejdelší úsek posloupnosti, jehož součet je dělitelný daným číslem.
6. 4.	Hledáme průsečíky úseček zametáním roviny. Útěk robota z bludiště. Algoritmy pracující s komprimovanými daty.
20. 4.	Transformování kvadrantových stromů. Problém malíře kvadrantisty. Ještě komprese. Jak přeuspořádat posloupnost, aby součet každých dvou (tří?) sousedních prvků nebyl dělitelný třemi?
27. 4.	Polosouvislost orientovaných grafů. Uklízení kostek do obdélníku. Fibonacciho soustava.
4. 5.	Řetězce na spoustu způsobů. Wildcardy, regulární výrazy a automaty a spleť vztahů mezi nimi.
11. 5.	2-SAT.
18. 5.	Max-2-SAT a jeho pravděpodobnostní aproximace. Derandomizace pomocí podmíněných pravděpodobností. Aproximace Max-Cutu.