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

Ve školním roce 2012/2013 vedeme s Vojtou Tůmou speciální cvičení z předmětu Programování I [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. Viz též letáček :-)

Cvičení se koná každou středu od 15:40 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í.

Zápočet získáte za vypracování zápočtového programu a domácích úkolů za alespoň 100 bodů.

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

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. Přiměřené pro zimní semestr jsou úlohy obtížnosti 3 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: libovolný přiměřený úloze, kterou řešíte. Ale na čemkoliv exotickém se prosím předem domluvte.
Specifikace: Tím myslíme krátký popis toho, co všechno by program měl umět a v jakém jazyce by měl být napsán. 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ů. Nutno dodat do konce listopadu.
Dokumentace: 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).
Odevzdání textu: Specifikaci i dokumentaci odevzdávejte buďto v papírové podobě nebo elektronicky v libovolném rozumném formátu (nejlépe jako čistý text nebo PDF; naproti tomu MS Word rozumný není).
Odevzdání programu: Ideálně e-mailem nebo uploadem do ftp://atrey.karlin.mff.cuni.cz/pub/priv/p1x/ (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 raději ne). Pokud program neběží pod Linuxem, prosíme o osobní předvedení.
Odolost: 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	Kód	Body	Zadání
3. 10.	funf	5	Co dělá funkce f() z letáčku?
	funb	5	Co dělá funkce bc() z letáčku?
	2mis	15	Princezně 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é?
31. 10.	mlowz	7	Dokažte, že úloha "A[i,j]=i+j" z cvičení není řešitelná v lepším čase než Θ(n).
31. 10.	mlowr	7	Dokažte, že úloha "A[i,j]=i+j" není pro matice reálných čísel řešitelná v lepším čase než Θ(n²).
28. 11.	rgb	15	Dořešte úlohu o RGB třídění z cvičení. Ukažte dolní i horní odhad 2/3*n prohození.
9. 1.	jerab	20	Vymyslete 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".

Co jsme dělali

datum	co se cvičilo
3. 10.	Pár příkladů na úvod: Chybějící číslo (aneb princeznin náhrdelník). Číslo s lichým počtem výskytů. Amor a princezny: V rovině je N bodů, najděte polopřímku, na které leží nejvíce z nich.
10. 10.	Nejdelší úsek bez opakování znaků (nebo slov). Úlohy o posloupnostech: dvojice s daným součtem, úsek s daným součtem. Také jejich verze pro monotónní nebo nezápornou posloupnost.
17. 10.	Ještě posloupnosti: úsek se součtem co nejbližším zadanému, nejdelší vyvážený úsek. Největší nulová podmatice (dané velikosti, čtvercová, jakákoliv).
24. 10.	Podmatice: největší nulová, s maximálním součtem. Hledání v setříděné matici. Budou volby…
31. 10.	Volby na mnoho způsobů: půlení, bity, randomizace a konečně i lineární řešení. Házíme vajíčka.
7. 11.	Cvičení se nekoná, jsouc imatrikulace. Gaudeamus igitur!
14. 11.	Kompromisy mezi časem a pamětí: spočtěte všechna y_k = x₁ * … * x_k-1 * x_k+1 * … x_n (kde * je nějaká asociativní operace). Generování posloupností nul a jedniček.
21. 11.	Další generování: změna na právě jedné pozici (Grayův kód), právě k jedniček, všechna dobrá uzávorkování. Do příště: generování permutací a N dam na šachovnici.
28. 11.	Ještě trocha generování. RGB třídění.
5. 12.	Třídění: Šroubky a matičky aneb o síle randomizace. Třidíme n čísel od 1 do n³. Nebo posloupnost, v níž je jen O(log n) různých hodnot. Dotřiďujeme knihovnu.
12. 12.	O stromech, strážnících, mafiánech a vojenských posádkách – obyčejně, váženě i (vy)počítavě. Asfaltéři na stromech.
19. 12.	Prohledávání grafů: Indiana Jones v bludišti. Přihrádkové struktury. Wanted: kostra grafu. Agenti a jejich šéf (TODO).
2. 1.	Šéf agentů na mnoho způsobů. Asfaltéři v neorientovaném městě. Symetrická a skoro symetrická orientace grafu.
9. 1.	Jeřábníkovy starosti. Jak najít pozici háku? Jak dostat hák na danou pozici? Co když je jeřáb strom? Kdy se jeřáb protne?