Cvičení z Programování II

Ve školním roce 2004/2005 vedu cvičení z předmětu Programování II [NPRG031]. Cvičení se koná každou středu od 12:20 v posluchárně S6.

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, stránka Roberta Špalka.
- Odevzdání specifikace programu do 7. 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

Datum	ID	Body	Příklady
23. 2.	lmir	1	Je dán jednosměrný spojový seznam. Napište funkci, která prvky seznamu přeskládá do opačného pořadí. (Prvky přepojujte, nic nekopírujte.)
23. 2.	dyna	1	Implementujte "nafukovací pole", tj. dynamicky alokované pole, které bude na počátku prázdné a postupně do něj budete přidávat zadané prvky, přičemž kdykoliv dojde v poli místo, alokujete nové pole dvojnásobné velikosti a prvky ze starého pole do něj zkopírujete. (Všimněte si, že přidání N prvků stojí čas O(N).)
2. 3.	ldel	1	Napište funkci, které ze zadaného jednosměrného spojového seznamu odstraní všechny prvky se zadanou hodnotou.
	lspl	1	... která zadaný jednosměrný spojový seznam rozdělí na seznam obsahující prvky se sudými a druhý s lichými hodnotami. Prvky nekopírujte, jen přepojujte.
	loop	2	... 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).
	pola	1	Naprogramujte sčítání řídkých polynomů (řídký polynom je seznam dvojic (koeficient, exponent) setříděný vzestupně podle exponentu; žádný z koeficientů není nulový).
	polm	2	Naprogramujte násobení řídkých polynomů.
	swap	2	Pole P se skládá ze dvou různě dlouhých úseků. Napište proceduru, která tyto úseky prohodí a zvládne to v lineárním čase a konstantní pomocné paměti.
	iplm	4	Pole P se skládá ze dvou setřiděných úseků. V lineárním čase tyto úseky slijte do jedné setříděné posloupnosti, aniž byste použili větší než konstantní pomocnou paměť. Není to úplně jednoduché, ale pan Google vám muže pomoci.
9. 3.	lmrg	2	Napište funkci, která setřídí jednosměrný spojový seznam pomocí MergeSortu.
9. 3.	lins	2	Napište funkci, která setřídí jednosměrný spojový seznam některým z triviálních třídících algoritmů (InsertSort, SelectSort, BubbleSort).
16. 3.	tcut	2	Stvořte funkci pro ořezávání binárního vyhledávacího stromu intervalem. Tj. je zadán BVS a interval hodnot <a,b> a je třeba odstranit ze stromu všechny hodnoty, které leží mimo interval.
	twlk	1	Napište proceduru pro nerekursivní projití BVS pomocí hledání následníka prvku.
	bbtr	3	Naprogramujte funkci pro vložení prvku do BB-1/2-stromu. Takové stromy fungují tak, že si v každém vrcholu udržují velikost podstromu a kontrolují, že velikost levého a pravého podstromu se liší nejvýše 2-krát. Při insertu stačí updatovat velikosti podstromů, zkontrolovat, jestli někde není podmínka porušena a pokud ano, najít nejvyšší takové místo, celý podstrom rozebrat a postavit optimálně vyvážený. Ačkoliv jedna operace může být pomalá, v průměru trvají O(log n). Přesněji: Pokud každý insert přispěje časem O(log n), zaplatí se tím všechna vyvažování.
23. 3.	avli	3	Naprogramujte funkci pro vložení prvku do AVL-stromu. Hezký popis toho, jak s AVL-stromy zacházet, najdete v Programátorské kuchařce KSP.
23. 3.	iset	2	Vymyslete a naprogramujte algoritmus, který v zadaném zakořeněneném stromu (ne nutně binárním) nalezne největší možnou nezávislou množinu (tj. množinu vrcholů takovou, že mezi žádnými dvěma nevede hrana).
30. 3.	dice	2	Napište program, který bude pomocí hodů k-stěnnou kostkou (kterou považujeme za zdroj rovnoměrně rozložených nezávislých náhodných čísel) simulovat hody kostkou l-stěnnou.
30. 3.	rsel	3	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í.
6. 4.	xpos	1	Naprogramujte funkci, která z orientovaného grafu zadaného pomocí seznamů sousedů vrcholů (ve dvou polích: pole hran setříděné podle zdrojového vrcholu a pole vrcholů ukazující na první hranu vedoucí z daného vrcholu) vytvoří graf obsahující přesně opačné hrany. [+1 bod] ... použijete-li mimo vstupní a výstupní dvojice polí jenom konstantně mnoho pomocné paměti.
6. 4.	comp	1	Naprogramujte funkci, která rozloží neorientovaný graf na komponenty souvislosti.
13. 4.	tsrt	2	Napište program pro topologické třídění orientovaného grafu, tj. program, který k zadanému grafu nalezne topologické pořadí vrcholů ((x,y) je hrana => x<y) nebo odpoví, že graf není acyklický.
13. 4.	imst	2	Napište program, který v zadaném neorientovaném grafu s hranami ohodnocenými přirozenými čísly 1...5 nalezne minimální kostru.
20. 4.	cycr	2	Je dán neorientovaný graf. Nelezněte v lineárním čase takovou jeho orientaci, aby se vstupní a výstupní stupeň každého vrcholu lišily nejvýše o 1.
	eulr	2	Je dán neorientovaný graf. Nalezněte v lineárním čase eulerovský tah v tomto grafu, případně vypište, že neexistuje.
	nump	2	Je dán acyklický orientovaný graf a dvojice vrcholů. Spočtěte v lineárním čase, kolik mezi těmito vrcholy vede cest.
27. 4.	6col	2	Je dán neorientovaný rovinný graf. Nalezněte v lineárním čase jeho obarvení šesti barvami. [+0.5 bodu] obarvení pěti barvami v kvadratickém čase, [+1 bod] obarvení pěti barvami v lineárním čase.
	peri	2	Je dána permutace. Spočtěte, kolik má inverzí, tj. dvojic (i,j) takových, že i<j, ale x_i>x_j. Časová složitost: lepší než kvadratická.
	pero	2	Opět je dána permutace. Zjistěte v lineárním čase, zda je sudá nebo lichá.
	perr	2	Ještě jednou permutace. Najděte nejmenší takové k> 0, že k-té složení permutace se sebou samou dá identitu.
	perx	2	Pro změnu permutace :) Napište funkce, které budou umět k permutaci najít její pořadové číslo v lexikografickém uspořádání, a naopak k číslu najít permutaci. [+1 bod] Vyberte si jiné uspořádání, v němž zvládnete převod v lineárním čase.
4. 5.	3lou	2	Problém tří loupežníků: tři loupežníci společně naloupili n cenností o známých cenách (to jsou celá čísla v rozsahu 1 až 1000) a chtějí se o ně šábnout. Napište program, který zjistí, zda je možné lup rozdělit na 3 stejně cenné části (ceny jsou aditivní a předměty nelze dělit) a pokud ano, tak takové rozdělení vypíše.
11. 5.	Cvičení se nekonalo (Jarní Škola Kombinatoriky)
18. 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ě.
	book	2	Problém knihovníkův: máme N knih o šířkách t_i a výškách h_i a místnost vysokou H (všechno můžeme považovat za rozumně malé celé počty milimetrů). Knihovna se skládá z P stejně širokých polic umístěných nad sebou, každá police má tloušťku 10mm. Vaším úkolem je nalézt rozmístění knih do co nejužší knihovny tak, aby se knihovna vešla do místnosti a knihy byly uspořádány abecedně (tj. v zadaném pořadí).
	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é.
	iseq	2	Napište co nejefektivnější program, který v zadané posloupnosti čísel nalezne nejdelší rostoucí vybranou podposloupnost. [+1 bod] ... v čase O(n*log n).
25. 5.	Žádné domácí úkoly