Cvičení z Programování II
Ve školním roce 2003/2004 vedu cvičení z předmětu Programování II [NPRG031]. Cvičení se koná každou středu od 14:00 v posluchárně E1.
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 během semestru, platí počet bodů uvedený v tabulce, jinak se redukuje na polovinu.
- 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 letní semestr jsou úlohy obtížnosti 5 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.
- Odevzdání specifikace programu do konce dubna. 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, 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 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 | ||||
|---|---|---|---|---|---|---|---|
| 18. 2. | grin | 2 | Na vstupu je zadán orientovaný (multi)graf jakožto seznam hran, každá hrana je popsána identifikačními čísly (integerovými) vrcholů, mezi nimiž vede. Napište program, který z tohoto vstupu sestrojí reprezentaci grafu pomocí pointerů: spojový seznam vrcholů setříděný podle id. čísel, ke každému vrcholu je připojen seznam hran vedoucích z tohoto vrcholu a každá hrana ukazuje na vrchol, do nějž vede. Na cvičení jsme vyřešili se složitostí O(M*N), kde M je počet hran a N počet vrcholů, zkuste to efektivněji. | ||||
| grsy | 2 | Mějme graf reprezentovaný jako v minulé úloze, s tím, že hrany vedoucí z vrcholu jsou navíc setříděny podle id. čísel cílových vrcholů. Napište funkci, která v lineárním čase rozhodne, zda je tento graf symetrický (tj. pokud z x do y vede k hran, musí stejný počet hran vést též z y do x). | |||||
| pomu | 2 | Napište program, který vynásobí dva polynomy v řídké reprezentaci (každý polynom je uložen jako spojový seznam dvojic (exponent, koeficient) setříděný vzestupně podle exponentů). | |||||
| mamu | 2 | Napište program, který vynásobí dvě matice v řídké reprezentaci (spojový seznam řádků, každý řádek ukazuje na spojový seznam nenulových prvků v daném řádku; všechny seznamy jsou setříděny podle příslušné souřadnice). | |||||
| 25. 2. | cbtr | 2 | Naprogramujte funkci, která pro zadané N spočítá, kolik existuje různých binárních stromů na N vrcholech, a bude mít lepší než kvadratickou časovou složitost. | ||||
| walk | 2 | Napište proceduru, která vypíše zadaný binární vyhledávací strom (BVS) v inorder pořadí bez použití rekurze, a to v lineárním čase. Můžete předpokládat, že každý vrchol stromu obsahuje ukazatel na svého otce. | |||||
| avgp | 2 | Naprogramujte funkci, která spočítá průměrnou délku všech cest z kořene do vrcholů zadaného BVS (nejen listů). | |||||
| balt | 2 | Napište program, který vytvoří dokonale vyvážený BVS obsahující zadané hodnoty. (Dokonale vývážený je takový strom, v jehož každém vrcholu platí, že počet vrcholů v levém a pravém podstromu se liší maximálně o jedničku.) | |||||
| 3. 3. | fibb | 2 | Naprogramujte funkci, která spočte n-té Fibonacciho číslo v čase O(log n).
Hint:
( x y ) × (
| ||||
| lexi | 3 | Vhodně si předzpracujte zadaný slovník tak, abyste byli schopni na dotazy typu "Dá se string X sestavit ze slovníkových slov a pokud ano, jak to na co nejméně slov provést?" odpovídat v čase O(délka X * maximální délka slova ve slovníku). | |||||
| sack | 2 | Vyřešte problém batohu (je dáno N čísel v rozsahu 1 až M a ptáme se, lze-li z nich vybrat taková, aby jejich součet byl roven zadanému X) v čase O(MN) a prostoru O(M+N). | |||||
| 10. 3. | optr | 2 | Na vstupu jsou dány prvky a1, ..., an uspořádané vzestupně a pravděpodobnosti p1, ..., pn (0<pi<1 a součet všech pi je 1). Zkonstruujte vyhledávací strom obsahující zadané prvky takový, že průměrná délka cesty, kterou musíte projít při vyhledávání náhodného prvku při daných pravděpodobnostech, bude co nejmenší (tato délka je rovna sumě přes všechna i z pi*hi, kde hi je hloubka, ve které se nachází prvek ai). | ||||
| diff | 2 | Na řetězcích znaků je možno provádět editační operace – přidání znaku, smazání znaku a změnu znaku. Editační (neboli Levenstheinova) vzdálenost řetězců x, y je minimální počet editačních operací, jimiž lze z x vyrobit y (nebo z y vyrobit x, to je totéž; ověřte si, že tato vzdálenost je metrika). Napište funkci, která pro zadané dva řetězce spočte jejich editační vzdálenost. | |||||
| para | 3 | Napište formátovátko odstavců: na vstupu je zadán dlouhý řetězec a šířka stránky S. Dále je známa nějaká funkce P(S,k,t), která řádku šířky S, na který jsme umístili k slov o celkové délce t, přiřadí trestné body za ošklivost (bude-li řádek příliš roztažený, přidělí spoustu trestných bodů, bude-li pěkný, málo; nevejdou-li se slova na řádek, vrátí nekonečno) a funkce Q(S,k,t), která počítá totéž pro poslední řádek odstavce. Najděte algoritmus, který rozdělí řetězec do řádků tak, aby celkový počet trestných bodů za všechny řádky byl nejmenší možný. | |||||
| 17. 3. | whly | 2 | Na jednom zámku žije Bílá paní. Umí výtečně procházet zdmi, ale k stáru už se začíná bát, že se jí to jednoho dne nepovede a ve zdi uvízne. Proto se snaží procházet zdmi co nejméně. Zkuste jí pomoci: dostanete plán zámku (matice, v níž jsou vyznačeny volná políčka, zdi a start a cíl) a nalezněte cestu ze startu do cíle takovou, aby procházela co nejméně zdmi a z takových cest byla co nejkratší. | ||||
| brau | 2 | Nalezněte v bludišti (opět reprezentovaném maticí) nejkratší cestu autíčkem, které umí pouze jezdit rovně a zatáčet doprava. | |||||
| kuku | 2 | Nalezněte v bludišti (...) nejkratší cestu kulhavým koněm, což je šachová figurka, která v sudé tahy táhne jako jezdec, v liché jako pěšec (v kladném směru y-ové souřadnice). | |||||
| mino | 3 | Na jednom policku zadaneho labyrintu stoji Theseus, na jinem na nej ciha Minotaurus. Thesea ridite vy, Minotaurus v kazdem tahu udela K kroku smerem k Theseovi (tj. pokud se muze pohnout smerem k Theseovi v x-ove souradnici, udela to, pokud ne [uz je ve stejnem sloupci nebo mu brani zed], pohne se v y-ove, pokud nemuze ani to, stoji). Vasim cilem je dostat se na zadane policko a nenechat se pritom chytit Minotaurem. | |||||
| 24. 3. | hant | 2 | Variace na Hanojské věže: nalezněte nerekurzivní algoritmus na řešení hlavolamu,
tj. takový, který dostane konfiguraci věží a pořadové číslo tahu a odpoví,
jaký tah má být proveden
(*) [+1 bod] totéž bez pořadového čísla tahu. | ||||
| xpos | 1 | Je dán orientovaný graf reprezentovaný seznamy sousedů vrcholů. Napište proceduru, která v lineárním čase vytvoří analogickou reprezentaci transpozice tohoto grafu, tj. takového grafu, který obsahuje tytéž hrany v opačném směru. | |||||
| xfor | 2 | Vyřešte libovolnou z úloh o bludištích z předchozího cvičení tak, že bludiště transformujete na graf a ten poté projdete do šířky. | |||||
| 30. 3. | vcon | 3 | Napište funkci, která v zadaném neorientovaném grafu najde všechny artikulace (artikulací nazýváme takový vrchol, jehož odstraněním se zvětší počet komponent souvislosti). Hint: Upravte funkci pro hledání mostů, která se dělala na cvičení. | ||||
| 7. 4. | kran | 1 | Naprogramujte funkci, která ze zadané n-prvkové posloupnosti vybere náhodně
k prvků tak, aby všechny k-tice měly stejnou pravděpodobnost. Můžete předpokládat,
že máte k dispozici generátor rovnoměrně rozložených náhodných čísel
z libovolného intervalu.
(*) [+2 body] totéž, ale všech n prvků se nevejde současně do paměti a navíc dopředu nevíte, kolik jich bude. | ||||
| dice | 2 | Máte-li k-stěnnou kostku, generujte co nejefektivněji (tj. na nejmenší průměrný počet hodů) náhodná přirozená čísla v intervalu [0,n). | |||||
| perc | 2 | Napište dvojici funkcí: Jednu, která pro zadaná N,X nalezne v lexikografickém pořadí
X-tou permutaci na množině 1..N, a druhou, která bude provádět opačný převod.
(*) [+1 bod] zvolte si nějaké jiné uspořádání tak, aby vaše funkce pracovaly v lineárním čase (vzhledem k N). | |||||
| eigh | 3 | Vyřešte Lloydovu devítku – to je hlavolam tvořený krabičkou velikosti 3x3, v níž se pohybuje 8 jednotkových čtverečků označených čísly 1 až 8 (a tedy jedna mezera mezi nimi). Napište program, který pro dvě zadané konfigurace hry najde nejkratší posloupnost tahů mezi nimi, případně odpoví, že mezi nimi nelze legálními tahy přejít. (Tahem se myslí přesunutí čtverečku do volného místa.) | |||||
| 14. 4. | sign | 1 | Napište funkci pro výpočet znaménka zadané permutace v lineárním čase. | ||||
| dsim | 3 | Milanova simulacni uloha | |||||
| 21. 4. | bmin | 1 | Napište program, který pro zadaný ohodnocený strom vypíše u každého vrcholu nejkratší vzdálenost ze zadaného počátečního vrcholu. | ||||
| bmax | 2 | V zadaném neohodnoceném stromě najděte a vypiště nejdelší cestu. | |||||
| beql | 2 | Pro daný ohodnocený strom a konstantu C zjistěte, zda se ve stromě vyskytuje cesta s hodnotou (=součet délek jejích hran) přesně C. Pokud ano, vypiště ji. | |||||
| 27. 4. | inco | 2 | Jsou zadány intervaly <x1,y1> ... <xn,yn>. 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. | ||||
| sect | 2 | Tajná společnost má N agentů očíslovaných 007...N+6. Každý agent může rozkazovat některým dalším agentům. Pokud agent přijme rozkaz, ihned jej předá všem svým podřízeným. Šéfem společnosti nazveme takového agenta, který když vydý rozkaz, obdrží ho postupně všichni ostatní agenti. Napište funkci, které když zadáte, kdo může komu rozkazovat (to je orientovaný graf), najde v lineárním čase některého z šéfů a nebo odpoví, že žádný šéf neexistuje. | |||||
| 5. 5. | Žádné domácí úkoly. | ||||||
| 12. 5. | Cvičení se nekonalo (Rektorský sportovní den). | ||||||
| 19. 5. | Žádné domácí úkoly. | ||||||