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

Ve školním roce 2010/2011 vedeme s Milanem Strakou 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ždé pondělí od 12:20 v S10, kdo chcete chodit, přihlašte se, prosíme, v SISu, případně nám pošlete mail, pokud vám to SIS nedovolí.

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 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: 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 listopadu. 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/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, 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
4. 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é?
	ocko	5	Proč je v definici "velkého O" kvantifikováno přes "skoro všechna N", namísto přes všechna? Co se pokazí, když tam napíšeme jen ∀N? Pro jistotu definici zopakujeme: f=O(g) právě tehdy, když ∃c>0 ∀*N f(N) ≤ c*g(N).
11. 10.	real	10	Představte si, že máte počítač, který umí počítat v konstantním čase s neomezeně velkými a neomezeně přesnými reálnými čísly: sčítat, odčítat, násobit, dělit, umocňovat, počítat celé části apod. Jak na tomto počítači hledat N-té prvočíslo v konstantním čase?
8. 11.	dice	15	Házíme 20stěnnou kostkou a chceme generovat čísla od 1 do 90. Označme h(N) počet hodů kostkou průměrně spotřebovaný na vygenerování N čísel. Opakováním algoritmu ze cvičení získáme h(N)=20/9*N. Vymyslete algoritmus s menším h(N). Umíte méně než 1.6*N?
15. 11.	mink	15	Je dána posloupnost délky N a číslo K. Spočítejte v čase O(N) (kde konstanta v O nezávisí na K) minima všech úseků délky K.
	rsel	15	Na vstupu je libovolně dlouhá posloupnost řádků (dopředu nevíte, jak dlouhá) a číslo k. Váš program má z této posloupnosti vybrat náhodnou k-tici řádků tak, aby všechny k-tice měly stejnou pravděpodobnost. Číslo k je dostatečně malé, takže vybrané řádky se určitě do paměti vejdou, vstupní posloupnost ovšem nemusí.
22. 11.	kjed	10	Dopočítejte časovou složitost algoritmu z cvičení pro generování všech posloupností n nul a jedniček, které obsahují právě k jedniček. Zkuste navrhnout rychlejší algoritmus.
29. 11.	fill	20	Uvažujme vyplňování rovinného obrázku v mřížce n×n pomocí prohledávání do šířky. Říká se, že pro to stačí fronta velikosti O(n). Dokažte to nebo vyvraťce.

Co jsme dělali

datum	co se cvičilo
4. 10.	Pár příkladů na úvod: Měli jsme posloupnost 1…N. Někdo ji zamíchal a jedno číslo škrtnul. Jak v lineárním čase a konstantní paměti zjistit, které? Je dána posloupnost přirozených čísel, ve které se všechna čísla vyskytují sudě-krát až na jedno nezbedné. Které? Robin Hood s kouzelným lukem: V rovině je N bodů, najděte polopřímku, na které leží nejvíce z nich. R. H. s kouzelnějším lukem: … najděte kružnici, na které leží nejvíce z nich. Je dána matice celých čísel a parametry a,b. Najděte (souvislou) podmatici velikosti a×b, jejíž medián je největší možný. Uvažte i jednorozměrnou, nebo naopak vícerozměrnou verzi úlohy. Tentýž vstup. Najděte podmatici velikosti a×b s co největším součtem. Matice celých čísel. Najděte podmatici (tentokrát libovolně velkou) s co největším součtem.
11. 10.	O Robinu Hoodovi a jiných geometrech. Úlohy o posloupnostech: dvojice se zadaným součtem, úsek s maximálním součtem.
18. 10.	Úlohy o posloupnostech: úsek se zadaným součtem nebo se součtem nejblížším zadanému; nejdejší vyvážený úsek; nejdelší rostoucí podposloupnost.
25. 10.	Módní přehlídka třídících algoritmů. Jak zacházet s haldou.
1. 11.	Přihrádkové třídění. Kompromisy mezi časem a pamětí: spočtěte všechna yk = x1 * … * xk-1 * xk+1 * … xn (kde * je nějaká asociativní operace).
8. 11.	Budou volby. Hrátky s pravděpodobností: randomizované řešení na volby, míchání karet, převody mezi kostkami, generování s danými vahami.
15. 11.	Generování všech objektů daného typu a související problémy: hledání následníka, počítání objektů, ranky a unranky.
22. 11.	Ještě jednou generování: Fibonacciho řetězce, posloupnosti s právě k jedničkami.
29. 11.	Rankování permutací. Prohledávání do šířky: bludiště, kulhavý kůň, kulhavé autíčko, Théseus s Minotaurem (a pokladem a mečem). Nuly a jedničky.
6. 12.	O nulách, jedničkách a grafech. Několik dalších grafových úloh: asfaltování, šéf agentů, hledání mostu, strážníci ve stromovém městě, mafiáni ve stokách, uzavřená společnost.
13. 12.	Strážníci, mafiáni a stromy.
20. 12.	Asfaltování a hledání šéfa agentů. Jak se hledají mosty?
3. 1.	Barvení rovinných grafů 6 i 5 barvami.
10. 1.	Jeřábníkův problém, intervalové i jiné stromy nad (ne)komutujícími transformacemi. BB-2 stromy.