Cvičení z programování

Ve školním roce 2001/2002 vedu cvičení z předmětu Programování I [NPRG004]. K tomu také patří zadávání a schvalování Ročníkového projektu I [NPRG018].

Zimní semestr

V zimním semestru se cvičení konalo každou středu od 14.00 v posluchárně T4.

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

• Vypracování alespoň tří domácích úkolů, které budou zadávány v průběhu semestru na cvičeních a rovněž se budou objevovat na těchto stránkách.
• Vypracování zápočtového programu v Pascalu

  Požadavky:

  • Téma: libovolné, jaké si vymyslíte, má-li odpovídající obtížnost. 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 zimní semestr jsou úlohy obtížnosti 3 a vyšší, ostatní berte jako návnadu pro vaši fantazii; vlastní nápady jsou ovšem vřele vítány. 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, stránka Dana Kráľe.
  • Do konce semestru mne kontaktujte a sdělte mi, jaké téma jste si vybrali. Předejdete tak tomu, že váš zápočtový program bude hodnocen jako příliš jednoduchý či že vám bude vytýkáno, že programujete totéž co kolega. Toto "přihlášení" zápočtového programu je povinné!
  • 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).
  • 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ě, CD či ZIP disku 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í.

Letní semestr

V letním semestru se cvičení koná každé úterý od 10.40 v posluchárně E3.

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

• Vyřešení alespoň tří domácích úkolů (viz seznam).
• Vypracování zápočtového programu v libovolném vyšším procedurálním programovacím jazyku (preferován Pascal či C, v případě méně obvyklých jazyků se se mnou předem domluvte). Požadavky stejné jako v ZS, pouze obtížnost minimálně 5.
• Zápočet není nutnou podmínkou ke zkoušce.

Ročníkový projekt I

V rámci cvičení rovněž zadávám (čtěte: schvaluji zadání, stejně jako u zápočtových programů) a hodnotím Ročníkový projekt I, za který je ovšem samostatný klasifikovaný zápočet, jehož získání není ke zkoušce nutné.

Vaším projektem by měl být nějaký větší a složitější program včetně odpovídajícího uživatelského rozhraní. Může to také být patřičně rozšířená verze zápočtového programu (např. zápočťák: šachová strategie, projekt: šachový program s grafickou šachovnicí používající tuto strategii).

Ročníkové projekty se obvykle píší v Delphi, pokud byste si rádi vybrali jiné prostředí, ozvěte se mi.

Úkoly ze zimních cvičení

Datum	Úkoly
3. 10.	Je dáno 12 kuliček stejných hmotností až na jednu, která je lehčí nebo těřší než ostatní. Popište postup, jak pomocí 3 vážení na rovnoramenných vahách zjistit, která to je a zda je lehčí či těžší.
	Dokažte, že pro 13 kuliček jsou již potřeba 4 vážení.
10. 10.	Napište program, který v zadané posloupnosti přirozených čísel nalezne nejdelší neklesající úsek.
	Je dána posloupnost obsahující přirozená čísla od 1 do n, každé z nich právě jednou, jen jedno chybí. Napište program, který vypíše, které chybí.
	Je dána posloupnost, ve které se každý člen vyskytuje právě dvakrát, až na jeden, který právě jednou. Napište program, který tento člen nalezne.
17. 10.	Cvičení se nekonalo (imatrikulace).
24. 10.	Napište program, který zadané čislo (již uložené v nějaké proměnné) vypíše v soustavě o základu k.
	... a opačně: přečte takto zapsané číslo ze vstupu.
	..., který spočte a umocněno na b, to celé modulo c. Čísla a, b, c jsou celá kladná a jejich součin se vejde do integeru, celá mocnina ovšem ne. Hledejte řešení s logaritmickou časovou složitostí.
	..., který pro funkci f spočte délku periody posloupnosti 1, f(1), f(f(1)), ...; předpokládejte, že posloupnost je periodická.
31. 10.	Napište program, který pro setříděnou posloupnost přirozených čísel a číslo c rozhodne, zda je c součtem nějakých dvou prvků posloupnosti.
	Napište programy generující n-tý člen následujících posloupností. Snažte se o co nejmenší časovou i paměťovou složitost. 1 2 4 8 61 23 46 ... 1 2 4 8 3 6 12 11 9 5 ... 31 41 59 26 53 58 97 93 23 83 ... 0 1 1 2 3 5 8 13 21 34 55 89 ... 1 11 21 1211 111221 312211 13112221 1113213211 ...
7. 11.	Napište program, který v zadané posloupnosti celých čísel nalezne úsek s největším možným součtem.
	Nalezněte v zadané posloupnosti přirozených čísel nejdelší neklesající vybranou podposloupnost. Existuje řešení v čase O(n*log n).
	Opět posloupnost: 1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1 2 1 1 ...
14. 11.	Naprogramujte sčítání, odčítání a násobení dlouhých čísel.
	(*) Napište program, který v čase O(log n) spočte n-té Fibonacciho číslo. Předpokládejte, že typ integer pojme čísla polynomiálně velká vzhledem k velikosti výsledku.
21. 11.	Napište program pro výpočet Eulerova čísla na zadaný počet desetinných míst.
	Hříčka: Jak zapsat libovolné přirozené číslo pomocí tří dvojek a operací sčítání, odčítání, násobení, dělení, umocňování, odmocňování, logaritmů, sinů, cosinů, arcussinů a arcuscosinů?
28. 11.	Výpočet e (eulerova čísla) a pi na n desetinnych mist.
	Je dána šifrovací mřížka, najděte nejmeníš k>0 takové, že pokud libovolnou zprávu zašifrujeme touto mřížkou k-krát, vyjde opět původní zpráva, případně dokažte, že takové k neexistuje.
5. 12.	Napište program, který soubor zadaného jména zkopíruje. Snažte se používat co největší buffer.
	Napište program, který zadaný soubor nahradí tím samým souborem zapsaným pozpátku. Přitom nepoužívejte žádné další soubory (na disku na ně není místo).
	Totéž s pomocnými soubory, ale bez seeku. Snažte se dosáhnout složitosti O(n*log n).
12. 12.	Napište program, který vygeneruje všechny posloupnosti délky n složené z `+' a `-'. Zkuste to jak s použitím rekurze, tak bez ní.
	... který vygeneruje všechny permutace na n-prvkové množině. Opět zkuste jak rekurzivní, tak nerekurzivní verzi.
19. 12.	Dva loupežníci naloupili šperky o cenách c1 až cn. Rozhodněte, zda je možné, aby se o ně rozdělili spravedlivě (má-li být nějaká spravedlnost pro loupežníky :]), tj. zda je možné šperky rozdělit do dvou podmnožin o stejné ceně.
	Je dána šachovnice n krát n políček, rozhodněte, zda je možno na rozestavět na ni k dam tak, aby se navzájem neohrožovaly.
	... totéž pro šachovnici, z níž jsou některá políčka vystřižena. Na takové políčko není možno dámy stavět, ani se skrz ně neohrožují.
	Je možno pomocí k číslic 4, znamének +, -, * a závorek možno dojít k výsledku x?
	Naprogramujte funkci pro třídění posloupnosti celých čísel metodou rozděl a panuj: rozdělte ji na dvě posloupnosti poloviční velikosti, ty rekurzivním zavoláním setřiďte a setříděné posloupnosti v lineárním čase spojte do jedné setříděné. Dokažte, že tak dosáhnete složitosti O(n*log n).
	Naprogramujte rekurzivně násobení dvou dlouhých čísel tak, že jej převedete na násobení 4 dvojic čísel poloviční délky a nějaká ta sčítání. Dokažte, že toto rekurzivní řešení pracuje v čase O(n2).
	(*) Upravte předchozí program tak, aby si vystačil s třemi násobeními místo čtyř za cenu více sčítání. Je teď rychlejší? (Hint: využijte toho, že (a+b)(c+d)=ac+bc+ad+bd.)
	(*) Naprogramujte Hanojské věže nerekurzivně, bez použití zásobníku. Program musí mít prostorovou složitost O(1) s tím, že před každým tahem dostane informace o tom, který disk je právě na vrcholu které z věží.
2. 1.	Bludiště je matice n krát n políček, z nichž každé může být buďto prázdné nebo zazděné. Napište program, který nalezne mezi dvěma body v bludišti nejkratší cestu. (Políčka na cestě musí být všechna prázdná a musí se vždy dotýkat hranou, nestačí rohem.)
	Bílá paní dokáže procházet zdmi, ale od jedné nepříjemné události se tomu snaží vyhnout, jak jen může. Napište pro ni program, který nalezne cestu mezi zadanými body bludiště, která prochází co nejméně zazděnými políčky a mezi takovými cestami je nejkratší.
	Kulhavý kůň je šachová figurka, která každý lichý tah táhne jako kůň a každý sudý jako pěšec (tj. rovně v zadaném směru). Nalezněte mezi dvěma body bludiště nejkratší cestu kulhavým koněm.
	Santa Claus má speciální saně, které dosahují extrémních rychlostí nutných k rozvozu všech vánočních dárků za jedinou noc, ale bohužel dokáží pouze jezdit rovně a zatáčet doprava. Hledejte nejkratší cestu v bludišti splňující tuto podmínku.

Úkoly z letních cvičení

Datum	Úkoly
19. 2.	Naprogramujte funkci, která každé permutaci na n-prvkové množině přiřadí její pořadí v lexikografickém uspořádání všech takových permutací.
	Naprogramujte funkci inverzní k předchozí, tj. takovou, která dostane pořadové číslo permutace a vygeneruje z ní permutaci tohoto čísla.
	Rozmyslete si, zda je možné zvolit si nějaké jiné uspóřádání permutací, ve kterém bude možné obě předchozí funkce počítat v lineárním čase.
	(*) Rozmyslete si, jak pomocí těchto funkcí s permutacemi a prohledávání do šířky řešit hlavolam "Lloydova osmička". A jak to udělat s co nejmenší paměťovou složitostí (za cenu horší časové)?
26. 2.	Naprogramujte funkce pro práci se spojovým seznamem prvků uloženych v poli.
5. 3.	Napište program, který ze zadaných přirozených čísel vytvoří spojový seznam (v libovolném pořadí) a pak obsah tohoto seznamu vypíše.
	Rozmyslete si, jak to provést v opačném pořadí.
	Napište program, který daný jednosměrný spojový seznam změní na seznam s týmiž prvky v opačném pořadí.
12. 3.	Buď F booleovská funkce, která pro každý prvek seznamu odpoví Ano nebo Ne. Napište funkci, která ze zadaného jednosměrného spojového seznamu odstraní všechny prvky funkcí F odmítnuté.
	F a seznam jako v předchozím případě. Napište proceduru, která zadaný seznam rozdělí na dva seznamy podle odpovědi funkce F.
	Napište funkci, která dostane dva setříděné seznamy a jejím výstupem bude jeden setříděný seznam obsahující prvky obou zadaných seznamů.
	(*) Je dán jednosměrný seznam, který může být zacyklený, tj. následníkem posledního prvku nemusí být nil, nýbrž některý z prvků předchozích. Napište funkci, která v lineárním čase rozhodne, zda seznam je zacyklený či nikoliv. Není k dispozici dostatek paměti na jakékoliv značkování prvků; funkce může seznam modifikovat, ale po jejím ukončení musí být v původním stavu.
19. 3.	Naprogramujte základní operace s obousměrnými cyklickými seznamy s hlavou: založení prázdného seznamu, vložení prvků na začátek, na konec, za určený prvek; odebrání prvku, vložení obsahu jednoho seznamu do druhého. Všechny operace by měly mít konstantní časovou složitost a obejít se bez příkazu if.
26. 3.	Napište funkci, která uspořádá jednosměrný spojový seznam vzestupně podle hodnot prvků. Zkuste využít metodu Rozděl a panuj a funkce na rozdělování a spojování seznamů z předminulého cvičení.
2. 4.	Je dána posloupnost n přirozených čísel menších jak n3. Napište program, který tuto posloupnost v lineárním čase uspořádá vzestupně. Hint: Použijte šikovně příhrádkové třídění.
	Z libovolného kvadratického třídícího algoritmu lze snadno odvodit třídící algoritmus s časovou složitostí O(n3/2): posloupnost rozdělíme na O(n1/2) úseků délky O(n1/2), každý z nich setřídíme kvadratickým algoritmem a poté všechny slijeme do jedné setříděné posloupnosti. Naprogramujte tuto metodu s kvadratickým algoritmem dle vlastního výběru.
9. 4.	Sestrojte funkce pro základní operace s haldou (obyčejnou, tj. 2-regulární): vložení nového prvku, nalezení a smazání minima; to vše v čase O(log n).
	Napište proceduru pro konstrukci haldy ze zadaných n prvků v lineárním čase. Hint: už od začátku považujte vstupní pole za haldový strom, takže stačí opravit uspořádání: procházejte pole od konce a každý prvek "zabublávejte" dolů.
	Naprogramujte Heapsort, tj. třídění pomocí haldy, které nejprve ze zadaných prvků vytvoří maximovou haldu a poté opakovaným odebíráním maxima z této haldy získá setříděnou posloupnost. Uvědomte si, že v libovolném okamžiku je v jednom poli délky n místo jak na haldu, tak na již setříděné prvky.
	Naprogramujte Mergesort (čili třídění sléváním) pro pole. Pro slévání použijte pomocné pole lineární velikosti.
	(**) Vymyslete, jak dvě setříděné posloupnosti slít, máte-li k dispozici pouze konstantně velký pomocný prostor. (Máte jedno lineárně velké pole, na počátku obsahuje vstupní posloupnosti zapsané za sebou, na konci v něm má být uložen výsledek.) Dokázali byste to alespoň s pomocným prostorem velikosti O(n1/2)?
	Naprogramujte Quicksort. Dejte si pozor na speciální případy typu "jako pivota jsme si vybrali nejmenší prvek".
16. 4.	Cvičení se nekoná.
23. 4.	Napište proceduru, která ze setříděného pole zkonstruuje dokonale vyvážený binární vyhledávací strom (BVS).
	Napište funkci, která k danému prvku BVS nalezne jeho následníka (tj. nejmenší z větších prvků). Přepokládejte, že každý vrchol BVS obsahuje ukazatele na levého a pravého syna a na otce.
	Napište proceduru, která vypíše všechny prvky BVS vzestupně a použije k tomu pouze konstantní množství pomocné paměti.
	Napište proceduru pro přidání prvku do BVS (bez vyvažování).
	Napište proceduru pro odebrání prvku z BVS (bez vyvažování).