Cvičení z programování II

Ve školním roce 2006/2007 vedu cvičení z předmětu Programování II [PRG031]. Cvičení se koná každé pondělí od 17:20 v posluchárně S6, konsultace obvykle těsně po cvičení, nebo po domluvě kdykoliv jindy.

Podmínky k získání zápočtu jsou:

Vypracování domácích úkolů za alespoň 8 bodů. Domácí úkoly budou zadávány v průběhu semestru na cvičeních a rovněž se budou objevovat na těchto stránkách. Pokud úkol vyřešíte do 28 dnů od zadání, platí počet bodů uvedený v tabulce, později se redukuje na polovinu.
Vypracování zápočtového programu v Pascalu (případně po domluvě v jiném procedurálním programovacím jazyce). Program by měl splňovat následující:
- Téma: může být libovolné, má-li odpovídající obtížnost. Ideální bude, když s nějakým přijdete sami, nerozhodným nabízím poměrně rozsáhlý 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šší, ostatní berte jako návnadu pro vaši fantazii). Jinými zajímavými zdroji inspirace mohou být: archiv programátorského korespondenčního semináře, archiv Matematické Olympiády kategorie P.
- Odevzdání specifikace programu do 14. května. Tím mám 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, nestyďte se za ně a uveďte 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 mi mužete předat buďto na cvičení nahraný na disketě či CD 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 mi 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

[V hranatých závorkách je u některých úkolů uvedena požadovaná časová/paměťová složitost; některé úlohy jdou samozřejmě vyřešit i efektivněji]

Datum	ID	Body	Příklady
19. 2.	perc	2	Napište funkce pro převod permutace na její pořadí v lexikografickém uspořádání a zpátky. [O(n²)] [+1 bod] Zvolte šikovnější uspořádání, ve kterém budete umět převod v lineárním čase.
19. 2.	eigt	2	Pomocí funkcí z předchozí úlohy vyřešte Lloydovu Osmičku na nejkratší možný počet tahů. Použijte trik z cvičení na omezení spotřeby paměti na 4 bity na stav.
26. 2.	loop	2	Napište funkci, která o zadaném jednosměrném spojovém seznamu určí, zda je či není zacyklený (tj. poslední prvek má jako další nikoliv nil, nýbrž některý z předchozích prvků). Žádá se lineární čas a konstantní pomocná paměť (to speciálně znamená, že zadaný seznam nesmíte nijak modifikovat).
	padd	1	Napište sčítání polynomů v řídké reprezentaci (spojový seznam dvojic (koef, exponent) uspořádaný vzestupně podle exponentu; členy s nulovými koef. chybí. [O(n)]
	pmul	2	Napište násobení polynomů v téže reprezentaci. [O(n²) / O(n)] [+1 bod] ... v lepším než kvadratickém čase (viz přednáška z ADS1).
5. 3.	lmrg	1	Naprogramujte funkci pro spojení dvou setříděných jednosměrných seznamů do jednoho. Prvky nekopírujte, pouze přepojujte. [O(N)/O(1)] [+1 bod] ... a pomocí ní třídění seznamů mergesortem [O(N*log N)/O(log N)]
	lsel	1	Stvořte funkci, která dostane obousměrný seznam integerů a pointer na funkci typu `function (x:integer):boolean` a smaže ze seznamu právě ty prvky, na~něž dodaná funkce odpoví `false`.
	cbra	1	Hříčka: Vymyslete program, který vypíše, zda kompilátor, jímž byl zkompilován, podporuje vnořování komentářů (`{ { komentar } take } uz ne`) nebo nikoliv (`{ komentar { take } uz ne } uz vubec ne`).
12. 3.	bstr	2	Naprogramujte insert a delete na binárním vyhledávacím stromu (bez vyvažování). [O(hloubka)]
	quad	2	Napište funkci pro rotaci čtvercového obrázku určeného kvadrantovým stromem o 90 stupňů v hodinkovém směru. Kvadrantový strom (KS) obrázku, který je celý bílý nebo celý černý, obsahuje jediný vrchol nesoucí jen informaci o barvě. KS ostatních obrázků má kořen, jehož synové jsou KS jednotlivých čtvrtin obrázku. Vstupem a výstupem by měl být KS kódovaný řetězcem znaků: triviální obrázky zapíšeme jako 0 a 1, složený obrázek jako (ABCD), kde A-D jsou zápisy podstromů.
	pali	1	Hříčka: Vymyslete palindromický program, tj. takový, který čten popředu i pozpátku vypadá stejně. Program by měl alespoň něco vypsat. Po cvičení jsme zjistili, že v Pascalu, který ignoruje vše po koncovém `end.`, to je úplně triviální a když si toto zakážeme, úloha už není řešitelná. Tak to zkuste v Céčku (starém dobrém ANSI C bez komentářů typu `//`).
19. 3.	Dobrá zpráva: žádné úkoly. Špatná: příště jich bude dvojnásob.
26. 3.	isec	2	Je zadána množina intervalů na celočíselné přímce. Spočítejte, kolik je dvojic protínajících se intervalů. [O(n log n), ale pozor, samotných dvojic může být víc] Hint: Vyhledávací stromy.
	mors	1	Napište program pro převod do Morseovy abecedy a zpět pomocí binárních stromů kódovaných v poli.
	trpt	1	Nalezněte v zadaném stromu nejdelší cestu.
	tcov	2	Nalezněte minimální vrcholové pokrytí zadaného stromu (to je nejmenší možná množina vrcholů taková, že každá hrana má alespoň jeden ze svých konců v této množině). [O(n)]
	huse	2	Housenka se skládá z páteře (cesta) a nožiček (ke každému vrcholu páteře mohou být navíc připojeny 0-2 listy). Nalezněte v zadaném stromu housenku tvořenou co největším počtem vrcholů. [O(n)]
	self	2	Další hříčka: Sestrojte program, který vypíše svůj vlastní zdrojový text.
2. 4.	linp	1	Je dána cesta s hranami ohodnocenými kladnými čísly. Napište funkci, která zjistí, zda má tato cesta podcestu, jejíž součet ohodnocení je zadané číslo. [O(n)]
2. 4.	lini	2	Totéž jako v předchozí úloze, ale ohodnocení hran jsou libovolná celá čísla. [O(n log n)]
9. 4.	Byly Velikonoce a nezadaly žádné domácí úkoly.
16. 4.	Cvičil Santiago a nezadal žádné domácí úkoly.
23. 4.	cpat	2	Je dán acyklický orientovaný graf a nějaké jeho vrcholy u,v. Spočtěte, kolik vede orientovaných cest z u do v. [O(m+n)]
	bfsr	2	Etuda: nalezení nejkratší cesty v orientovaném grafu pomocí prohledávání do šířky. [O(m+n)]
	brdg	2	Etuda: nalezení mostu v neorientovaném grafu pomocí prohledávání do hloubky. [O(m+n)]
30. 4.	ktah	2	Nakreslete zadaný graf nejmenším možným počtem tahů. Můžete předpokládat, že graf neobsahuje jednovrcholové komponenty. [O(m+n)]
	balo	2	Je dán neorientovaný graf. Zorientujte ho tak, aby se vstupní a výstupní stupeň každého vrcholu lišily nejvýše o 1. [O(m+n)]
	5col	2	Naprogramujte barvení rovinného grafu pěti barvami. [O(poly(n))] [+1 bod] ... v lineárním čase.
7. 5.	iseq	1	Napište co nejefektivnější program, který v zadané posloupnosti čísel nalezne nejdelší neklesající vybranou podposloupnost. [+1 bod] ... v čase O(n*log n).
7. 5.	foun	2	Problém telefonní číselnice: je dána N-znaková abeceda, četnosti jednotlivých znaků abecedy a telefon s K tlačítky. Napište program, který najde optimální rozmístění abecedy na tlačítka, tj. takové, které zachová pořadí znaků v abecedě, a přitom bude vyžadovat nejmenší možný počet zmáčknutí vzhledem k zadaným četnostem (první znak na tlačítku potřebuje jeden stisk, druhý dva atd.). Viz též tabulka četností písmen v češtině. [O(NK)]
14. 5.	edst	2	Problém tiskařského šotka: napište funkci, která spočte editační vzdálenost zadaných dvou slov, což je minimální počet editačních operací (vložení znaku, smazání znaku, přepsání znaku jiným), jimiž lze první slovo přetvořit na druhé. [O(MN)]
14. 5.	iseq	2	Napište co nejefektivnější program, který v zadané posloupnosti čísel nalezne nejdelší rostoucí vybranou podposloupnost. [O(n²] [+1 bod] ... v čase O(n*log n).
21. 5.	lcsq	2	Naprogramujte funkci, která pro dvě posloupnosti nalezne jejich nejdelší společnou vybranou podposloupnost. [O(poly)]
21. 5.	inco	2	Jsou zadány intervaly <x₁,y₁> ... <x_n,y_n>. Obarvením takového systému intervalů k barvami nazveme přiřazení čísla od 1 do k každému intervalu tak, že protínající se intervaly vždy dostanou různá čísla. Napište program, který k zadaným intervalům spočte nejmenší možný počet barev, s nimiž se dají zadané intervaly obarvit. [O(poly)]

Libovolný příklad můžete poslat vícekrát, vždy platí nejvyšší dosažené skóre.