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:

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]

DatumIDBodyPříklady
19. 2. perc2Napište funkce pro převod permutace na její pořadí v lexikografickém uspořádání a zpátky. [O(n2)]
[+1 bod] Zvolte šikovnější uspořádání, ve kterém budete umět převod v lineárním čase.
eigt2Pomocí 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. loop2Napiš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).
padd1Napiš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)]
pmul2Napište násobení polynomů v téže reprezentaci. [O(n2) / O(n)]
[+1 bod] ... v lepším než kvadratickém čase (viz přednáška z ADS1).
5. 3. lmrg1Naprogramujte 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)]
lsel1Stvoř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.
cbra1Hříč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. bstr2Naprogramujte insert a delete na binárním vyhledávacím stromu (bez vyvažování). [O(hloubka)]
quad2Napiš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ů.
pali1Hříč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. isec2Je 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.
mors1Napište program pro převod do Morseovy abecedy a zpět pomocí binárních stromů kódovaných v poli.
trpt1Nalezněte v zadaném stromu nejdelší cestu.
tcov2Nalezně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)]
huse2Housenka 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)]
self2Další hříčka: Sestrojte program, který vypíše svůj vlastní zdrojový text.
2. 4. linp1Je 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)]
lini2Totéž 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. cpat2Je 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)]
bfsr2Etuda: nalezení nejkratší cesty v orientovaném grafu pomocí prohledávání do šířky. [O(m+n)]
brdg2Etuda: nalezení mostu v neorientovaném grafu pomocí prohledávání do hloubky. [O(m+n)]
30. 4. ktah2Nakreslete zadaný graf nejmenším možným počtem tahů. Můžete předpokládat, že graf neobsahuje jednovrcholové komponenty. [O(m+n)]
balo2Je 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)]
5col2Naprogramujte barvení rovinného grafu pěti barvami. [O(poly(n))]
[+1 bod] ... v lineárním čase.
7. 5. iseq1Napište co nejefektivnější program, který v zadané posloupnosti čísel nalezne nejdelší neklesající vybranou podposloupnost.
[+1 bod] ... v čase O(n*log n).
foun2Problé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. edst2Problé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)]
iseq2Napište co nejefektivnější program, který v zadané posloupnosti čísel nalezne nejdelší rostoucí vybranou podposloupnost. [O(n2]
[+1 bod] ... v čase O(n*log n).
21. 5. lcsq2Naprogramujte funkci, která pro dvě posloupnosti nalezne jejich nejdelší společnou vybranou podposloupnost. [O(poly)]
inco2Jsou 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. [O(poly)]

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

Stránku spravuje Martin Mareš