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

Ve školním roce 2008/2009 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é úterý od 15:40 v S4, kdo chcete chodit, přihlašte se, prosíme, v SISu.

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/ (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
7. 10.	funf	5	Co dělá funkce f() z letáčku?
	funb	5	Co dělá funkce br() z letáčku?
14. 10.	liar	15	Dokažte, že ve hře "mysli si číslo" s nejvýše jednou lží potřebujeme aspoň log2 + log2 log2 n + konst. tahů.
	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é?
21. 10.	fff0	10	Mějme funkci f(x) přiřazující přirozeným číslům přirozená čísla. Uvažme posloupnost 0, f(0), f(f(0)), f(f(f(0))), ... a předpokládejme, že je periodická. Napište program, který nalezne délku periody, má-li k dispozici pouze konstantně velký prostor.
4. 11.	genk	10	Uvažme následující algoritmus pro generování posloupností nul a jedniček délky N s právě K jedničkami: zkusíme umístit první jedničku na všech N pozic a zavoláme se rekurzivně na podposlupnost vpravo od této jedničky. Pokud už je N=K, doplníme jedničky a vše vypíšeme. Jaká je časová složitost, nepočítáme-li vypisování?
	nxtk	10	Jako předchozí příklad, ale generujte nerekurzivně: vymyslete algoritmus, který najde lexikografického následníka dané posloupnosti.
18. 11.	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í.
25. 11.	next	15	Dokažte, že operace nalezení následníka prvku v binárním vyhledávacím stromu má amortizovanou časovou složitost O(1), pokud do inicializace investujeme amortizovaný čas O(hloubka stromu).
2. 12.	Cvičení kvůli DODu odpadá!
9. 12.	tdel	15	Vymyslete, jak do stromů vyvažovaných pomocí přebudovávání, které jsme dělali na cvičení, dodělat operaci mazání prvku.
13. 1.	diam	10	Dokažte, že následující algoritmus správně spočíta průměr stromu (maximum vzdáleností mezi vrcholy): zvolíme libovolný vrchol v, najdeme vrchol x nejvzdálenější od v, najdeme vrchol y nejvzdálenější od x a prohlásíme za průměr vzdálenost xy.
	mafi	10	Rozhodněte, zda hladový algoritmus pro mafiány, který jsme vymysleli na cvičení, funguje.

Co jsme dělali

datum	co se cvičilo
7. 10.	Rotování pole. Dotřídění knihovny (k knížek špatně zatříděno). Robin Hood a body v rovině. Šifrovací mřížka a cykly v permutacích.
14. 10.	Euklidův algoritmus a jeho přátelé. Jak najít chybějící perlu? (Princezna a zahradník) Jak najít číslo s lichým počtem výskytů? "Mysli si číslo" s lhářem.
21. 10.	Jak čísla 1...N opatřit znaménky, aby byl jejich součet roven K? Jak najít úsek s maximálním součtem a se zadaným součtem? Budou volby.
28. 10.	Slavíme narozeniny našeho státu …
4. 11.	Generování posloupností různých typů aneb první ochutnávka rekurze.
11. 11.	Úklid pole (přehazování prvků, aby tvořily souvislý úsek, se zachováním pořadí nebo bez). Generování a počítaní rozkladů čisla na součet.
18. 11.	Generování náhodných permutací a k-té permutace v lexikografickém či jiném pořadí. Jak kontrolovat, že jsme vygenerovali všechny rozklady? Prohledávání do šířky: cesta koněm, levotočivé autíčko, Théseus a Minotaurus.
25. 11.	Počítání součinů bez i-tého prvku (šetříme prostorem). Vyhledávací stromy a operace s nimi: find, insert, delete, next. Konstrukce dokonale vyváženého stromu a vyvažování pomocí částečné rekonstrukce.
2. 12.	Cvičení kvůli DODu odpadá!
9. 12.	Opět stromy. Analyzujeme stromy z minulé přednášky pomocí penízků. Jak spočítat inverze v permutaci? jak najít v posloupnosti úsek se součtem nejblizším danému číslu?
13. 12.	Ještě jednou stromy. Obsah a obvod sjednocení obdélníků.
6. 1.	Jeřábníkovy starosti. Průsečíky úseček v rovině. Jak najít maximální nezávislou množinu ve stromu?
13. 1.	Prohledávání stromů do hloubky: nezávislé množiny, průměr stromu, problém s mafiány.