1 Doba běhu daného algoritmu/programu 1. Který fragment programu z následujících dvou proběhne rychleji? int n = 100; int sum = 0; for (i = 0; i < n; i++) for (j = 0; j < i; j++) sum += i+j;
int n = 75; int sum = 0; for (i = 0; i < n; i++) for (j = 0; j < n; j++) sum += i+j;
Řešení V prvním fragmentu proběhne vnější cyklus 100 kráte, vnitřní však proběhne nejprve 0 kráte, pak 1 kráte, 2 kráte a nakonec 99 kráte. Tělo vnitřního cyklu se tedy provede 0 + 1 + 2 + ... + 99 = (100/2)·(0+99) = 50 · 99 = 4950 kráte. Ve druhém fragmentu není počet provádění vnitřního cyklu závislý na proměnné vnějšího cyklu, vnější cyklus proběhne 75 kráte a v jeho tělě pokaždé proběhne vnitřní cyklus rovněž 75 kráte. Celkem se tedy tělo vnitřního cyklu provede 75·75 = 5625 kráte. Rychleji proběhne první fragment.
2. Do následujícího kódu doplňte chybějící konstantu v podmínce tak, aby byla procedura xyz() volána právě 2100 krát. for (i=0; i < 70; i++) { j = 0; do { if (j > ___ ) xyz(); j++; } while (j < 90); } Řešení Vnější cyklus probíhá od 0 do 69, celkem 70 krát. Musíme proto zajistit, aby ve vnitřním cyklu byla procedura xyz() volána právě 2100/70 = 30 krát. Toho docílíme pro hodnoty řídící proměnné j: 60, 61, ..., 88, 89. Chybějící konstanta je tedy 59.
3. Do následujícího kódu doplňte chybějící konstantu v podmínce tak, aby byla procedura xyz() volána právě 2000 krát. i = 50; do { for (j=0; j < 70; j++) if (j > ___ ) xyz(); i++; } while (i < 150);
2 Řešení Vnější cyklus probíhá od 50 do 149, celkem 100 krát. Musíme proto zajistit, aby ve vnitřním cyklu byla procedura xyz() volána právě 2000/100 = 20 krát. Toho docílíme pro hodnoty řídící proměnné j: 50, 51, ..., 68, 69. Chybějící konstanta je tedy 49.
4. Do následujícího kódu doplňte chybějící výraz v podmínce tak, aby byla procedura uvw() volána právě 49 krát. for (i = 0; i < 7; i++) { j = i; while (j < ___) { uvw(); j++; } } Řešení Vnější cyklus probíhá celkem 7 krát. Musíme proto zajistit, aby ve vnitřním cyklu byla procedura uvw() volána právě 49/7 = 7 krát. Protože počítání ve vnitřním cyklu začíná pokaždé od aktuální hodnoty i, stačí do podmínky doplnit výraz i+7.
5. Do následujícího kódu doplňte chybějící konstantu v podmínce tak, aby byla procedura uvw() volána právě 85 krát. i = 0; while (i < 10) { for (j = i; j < ___; j++) uvw(); i++; } Řešení Označme hledanou konstantu k. Při prvním průchodu vnějšího cyklu proběhne vnitřní cyklus k krát. Při druhém průchodu vnějšího cyklu proběhne vnitřní cyklus k-1 krát. Při třetím průchodu vnějšího cyklu proběhne vnitřní cyklus k-2 krát, atd. Protože vnější cyklus proběhne celkem 10 krát, platí rovnost: k + (k-1) + (k-2) + (k-3) + ... + (k-8) + (k-9) = 85 Odstraněním závorek získáme : 10k - 1 - 2 - 3 - ... - 8 - 9 = 85 10k - 45 = 85 10k = 130 k = 13.
3 6. Ke zpracování k-tého řádku matice velikosti n×n je zapotřebí 2k operací. Celkem je ke zpracováni matice zapotřebí operací a) b) c) d) e)
2n2 (n2)/2 n(n+1)/2 n(n–1) n(n+1)
Řešení Celkem je zapotřebí operací 2·1 + 2·2 + 2·3 + ... + 2·n = 2· (1 + 2 + 3 + ... + n) = 2 · n · (n–1) /2 = n · (n–1). Platí varianta e).
7. Úloha, jejíž doba řešení je C·n2, kde n je rozsah vstupních dat, se řeší na počítači pro n = 5000. Je zakoupen nový počítač, který je cca 2.5 krát rychlejší. Jak je možno zvětšit rozsah vstupních dat, aby byla úloha vyřešena na novém počítači ve stejném čase? Řešte pro různé závislosti doby řešení na rozsahu vstupních dat: C·n3, C·n0.5, C·n·log2(n) ... Řešení Na starém počítači se v daném čase T musí provést C·50002 operací. Na novém počítači se ve stejném čase T provede 2.5 krát více operací, tedy 2.5·C·50002 operací. V čase T se má také provést C·x2 operací, kde x neznámý nový rozsah vstupních dat. Musí tedy platit rovnost 2.5·C·50002 = C·x2 odtud získáváme x2 = 2.5·50002 = 2.5·25000000 = 62500000. x = 7 905.7 přibližně. Nový počítač je sice 2.5 krát rychlejší, ale rozsah vstupních dat lze zvětšit jen sqrt(2.5) krát, tedy cca 1.58 krát. Platí samozřejmě také 5000·sqrt(2.5) = 7 905.6941504... Analogicky pro další zadané závislosti doby řešení na rozsahu vstupních dat získáme: 2.5·C·50003 = C·x3 ⇒ 312500000000 =.x3 ⇒ x = 6786.04 Rozsah dat lze zvětšit cca 6786.04/5000 = 1.357 krát. (sqrt(2.5) = 1.357) 2.5·C·50000.5 = C·x0.5 ⇒ 176.7766952966 = x0.5 ⇒ x = 31250. Rozsah dat lze zvětšit 31250/5000 = 6.25 krát. (2.52 = 6.25) 2.5·C·5000·log2(5000) = C·x·log2(x) ⇒ 153596.4047 = x·log2(x) ⇒ x = 11397.41931 Rozsah dat lze zvětšit cca 11397.41931/5000 = 2.28 krát.
4 8. Stroj provádí 109 operací za sekundu. Pro výpočet je k dispozici 1 hodina. Určete, jaká může být maximální hodnota n, která určuje velikost vstupních dat, v případě že počet nezbytných instrukcí pro zpracování dat o velikosti n je: n3/2, n5/4, n·log2(n)·log2(log2(n)), n2·log2(n), ... a další. Řešení Jedna hodina představuje 109 · 3600 = 3.6 · 1011 operací. Snadno dopočítáme: n3/2 = 3.6 · 1011 ⇒ n = (3.6 · 1011)2/3 = 50 605 959.9 n5/4 = 3.6 · 1011 ⇒ n = (3.6 · 1011)4/5 = 1 758 093 630.95 n·log2(n)·log2(log2(n)) = 3.6 · 1011 ⇒ n = 2.332467476·109 n2·log2(n) = 3.6 · 1011 ⇒ n = 144905.7 (K vypočtení posledních dvou hodnot použijeme vhodný numerický software :-))
9. Metoda A potřebuje k vyřešení úlohy n2 + 17 operací, Metoda B potřebuje 2n + 80 operací, přičemž celé číslo n popisuje rozsah vstupních dat. Pro jaká n je výhodnější použít metodu A? Řešení Metoda A je výhonější pro taková n, pro která platí n2 + 17 < 2n + 80, to jest, pro taková n, která splňují nerovnici n2 – 2n – 63 < 0. Kořeny příslušné kvadratické rovnice n2 – 2n – 63 = 0 jsou n1 = –7, n2 = 9. Pro n z intervalu (–7, 9) má výraz n2 – 2n – 63 zápornou hodnotu, a proto je metoda A výhodnější pro n < 9.
5 Asymptotická složitost
10. Pro rostoucí spojité fukce f(x), g(x) platí f(x) ∈ Ω(g(x)). Z toho plyne, že a) b) c) d) e)
f(x) ∈ Ο(g(x)) f(x) ∈ Θ(g(x)) g(x) ∈ Θ(f(x)) g(x) ∈ Ω(f(x)) g(x) ∈ Ο(f(x))
Řešení f(x) ∈ Ω(g(x)) znamená, že f(x) roste rychleji nebo stejně rychle jako g(x). Tudíž g(x) roste pomaleji nebo stejně rychle jako f(x). To vyjadřujeme zápisem g(x) ∈ Ο(f(x)). Platí možnost e).
11. Pro rostoucí spojité fukce f(x), g(x) platí f(x) ∈ O(g(x)). Z toho plyne, že a) b) c) d) e)
f(x) ∈ Θ(g(x)) f(x) ∈ Ω(g(x)) g(x) ∈ Θ(f(x)) g(x) ∈ Ω(f(x)) g(x) ∈ Ο(f(x))
Řešení f(x) ∈ O(g(x)) znamená, že f(x) roste pomaleji nebo stejně rychle jako g(x). Tudíž g(x) roste rychleji nebo stejně rychle jako f(x). To vyjadřujeme zápisem g(x) ∈ Ω(f(x)). Platí možnost d).
12. Pokud funkce f roste asymptoticky rychleji než funkce g (tj. f(x) ∉ Ο(g(x)) ), platí následující tvrzení a) b) c) d) e)
jsou-li v bodě x definovány obě funkce, pak f(x) > g(x) rozdíl f(x) - g(x) je vždy kladný rozdíl f(x) - g(x) je kladný pro každé x > y, kde y je nějaké dostatečně velké číslo obě funkce f i g jsou definovány jen pro nezáporné argumenty nic z předchozího
Řešení Řeč je o asymptotické složitosti, takže vztah funkcí f(x) a g(x) blízko nuly není nijak podstatný. Varianty a) b) a d) žádají z tohoto hlediska příliš mnoho a tedy neplatí. Tvrzení úlohy f(x) ∉ Ο(g(x)) říká, že od určitého okamžiku musí platit f(x) > g(x), což je ekvivalentní variantě c).
6 13. Pokud funkce f roste asymptoticky stejně rychle jako funkce g (tj. f(x) ∈ Θ(g(x)) ), platí právě jedno následující tvrzení. Které? a) b) c) d) e)
jsou-li v bodě x definovány obě funkce, pak f(x) = g(x) ani poměr f(x)/g(x) ani poměr g(x)/f(x) nekonverguje k nule s rostoucím x rozdíl f(x) - g(x) je kladný pro každé x > y, kde y je nějaké dostatečně velké číslo obě funkce f i g jsou definovány jen pro nezáporné argumenty nic z předchozího
Řešení Stejně rychlý asymptotický růst neznamená, že se musí funkce nutně rovnat, varianta a) odpadá. Stejně tak neznamená, že by jedna funkce musela nutně být větší než druhá, odpadá i varianta c). Chování funkcí v okolí nuly není pro asymptotické chování významné, varianta d) zbytečně žádá příliš mnoho. Stejně rychlý asymptotický růst znamená, že v okolí nekonečna poměr f(x)/g(x) ani poměr g(x)/f(x) nepřekročí nějakou pevnou konstantu. To ovšem znamená, že žádný z těchto poměrů nekonverguje k 0, platí varianta b).
14. Pro dvě spojité funkce f(x) a g(x) rostoucí na celém R platí f(x) < g(x) pro každé x ∈ R. To znamená a) b) c) d) e)
f(x) ∉ Ω(g(x)) f(x) ∉ Ο(g(x)) je možné, že f(x) ∈ Ω(g(x)) g(x) ∉ Θ(f(x)) f(x) roste asymptoticky pomaleji než g(x)
Řešení Pokud je f(x) < g(x), nevíme mnoho co se týče asymptotické složitosti těchto funkcí. f(x) může být vůči g(x) nepatrná, maličká, a pak by mohla být f(x) asymptoticky pomalejší. Taky by ale mohla být f(x) docela srovnatelná s g(x), např. f(x) = g(x)-0.01 všude, to by pak rostly obě asymptoticky stejně rychle, tj. mohli bychom říct, že f(x) ∈ Θ(g(x)). Plaí ale: f(x) ∈ Θ(g(x)) ⇒ f(x) ∈ Ο (g(x)) & f(x) ∈ Ω (g(x)). První dvě možnosti odpovědí popírají právě uvedené zjištění. Popírá ji i poslední, protože říká totéž co první (souhlasíte?). Čtvrtá možnost říká, že určitě „g není výrazně nad f“, ale proč by to tak nemohlo být, když f je podle zadání menší?
7 15. Pro dvě spojité funkce f(x) a g(x) rostoucí na celém R platí f(x) ∉ Ω (g(x)), f(x) ∉ Θ(g(x)). Tudíž: a) b) c) d) e)
g(x) ∈ Ο(f(x)) g(x) ∈ Θ(f(x)) f(x) < g(x) pro každé x ∈ R f(x) ≤ g(x) pro každé x ∈ R může existovat y ∈ R takové, že f(y) > g(y)
Řešení Zadání praví, že f(x) ∉ Ω (g(x)), f(x) ∉ Θ(g(x)). Takže platí f(x) ∈Ο(g(x)) (pročpak?). Ekvivalentně můžeme říci, že g(x) ∈ Ω (f(x)). Z posledního ovšem nikterak neplyne ani g(x) ∈ Ο(f(x)), ani g(x) ∈ Θ(f(x)) (malujte si obrázek, je-li to zapotřebí), tudíž první dvě varianty odpovědí neplatí. Hovoříme o asymptotickém chování funkcí, tedy jejich vzájemné vztahy na nějaké omezené podmnožině R (třeba kolem 0) , mohou být zcela libovolné, tvrdit třetí nebo čtvrtou možnost je tu opovážlivostí příliš velkou. To ostatně potvrzuje i správná pátá možnost.
16. Algoritmus A probírá postupně všechny prvky v dvourozměrném poli o velikosti n × n a s každým prvkem provádí další (nám neznámou) akci, jejíž složitost je Θ(log2(n)). Celková asymptotická složitost algoritmu A je tedy a) b) c) d) e)
Θ(n · log2(n)) Θ(n2) Θ(n3) Θ(n2+log2(n)) Θ(n2 · log2(n))
Řešení Je nutno provést n × n akcí o složitosti úměrné log2(n), tedy složitost všech akcí dohromady je úměrná n2 · log2(n). Přesun od jednoho prvku k druhému v poli má složitost konstantní, takže samotný průchod celým polem má složitost úměrnou konstanta · n2. Celkem tak máme složitost Θ(n2 · log2(n) + konstanta · n2) = Θ(n2 · log2(n)). To je právě varianta e).
17. Právě jeden z následujících výroků je nepravdivý. Označte jej. a) b) c) d) e)
x · log2(x) ∈ Ο(x2 – x) x · log2(x) ∈ Ο(x2 – log2(x)) x · log2(x) ∈ Ω(x2 – log2(x)) x · log2(x) ∈ Ω(x + log2(x)) x · log2(x) ∈ Θ( x · log2(x2))
8 Řešení Když k funkci f přičteme funkci g, která roste asymptoticky pomaleji, než funkce f, výsledný součet poroste asymptoticky stejně rychle jako původní funkce f. Proto můžeme pravou stranu zadání v případě a) – d) zjednodušit: a) x · log2(x) ∈ Ο(x2) b) x · log2(x) ∈ Ο(x2) c) x · log2(x) ∈ Ω(x2) d) x · log2(x) ∈ Ω(x) e) x · log2(x) ∈ Θ( x · log2(x2)) = Θ( x · 2 · log2(x)) = Θ( x · log2(x2)) Funkce log2(x) roste pomaleji než funkce x, takže funkce x · log2(x) roste pomaleji než funkce x · x = x2, takže varianta a) i b) je pravdivá. Funkce log2(x) má v plus nekonečnu limitu plus nekonečno, takže funkce x · log2(x) roste asymptoticky rychleji než funkce x, takže varianta d) je pravdivá. Varianta e) po naznačené úpravě je také zřejmě pravdivá. Zbývá jediná nepravdivá varianta c), jejíž nepravdivost ostatně vyplývá již z první věty tohoto odstavce.
18. Algoritmus A provede jeden průchod polem s n prvky. Při zpracování prvku na pozici k provede k+n operací. Operační (=asymptotická) složitost algoritmu A je tedy a) b) c) d) e)
Θ(k+n) Θ( (k+n)·n ) Θ(k2+n) Θ(n2) Θ(n3)
Řešení Celkem je provedený počet operací při zpracování všech prvků roven (1+n) + (2+n) + (3+n) + ... + (n+n) = = n · ((1+n) + (n+n))/2 = n · (1+3n)/2 = 3n2/2 +n/2 ∈ Θ(n2) Povážíme-li navíc ještě režii na přesun od jednoho prvku pole k následujícímu, která má nanejvýš konstantní složitost, připočteme k výsledku ještě člen Θ(konst·n), jenž ovšem na složitosti Θ(n2) nic nemění. Platí varianta d).
19. V následujících vztazích doplňte na prázdná místa (........) symboly Ο nebo Θ nebo Ω tak, aby vznikla pravdivá tvrzení. Je-li možností více, uveďte je všechny, nehodí-li se ani jeden symbol, prázdné místo proškrtněte. a) x2 ·2x ∈ ........((ln(x2))2 + 2x) b) (ln(x2))2 + 2x ∈ ........(x2 + ln(x2) ) c) 2x · (ln(x)) −1 ∉ ........(2x · (ln(x2))−1)
9 Řešení a) funkce nalevo zřejmě roste rychleji než funkce napravo, neboť obě funkce obsahují výraz 2x, který je však nalevo vynásoben výrazem x2, jenž roste asymptoticky rychleji než (pouze!) aditivní výraz (ln(x2))2 napravo. Jediná správná možnost je proto x2 ·2x ∈ Ω((ln(x2))2 + 2x). b) funkce nalevo obsahuje člen 2x, funkce napravo je součtem dvou členů, které oba zřejmě rostou asymptoticky pomaleji než 2x. Funkce nalevo tedy roste asymptoticky rychleji, takže jediná správná možnost je (ln(x2))2 + 2x ∈ Ω(x2 + ln(x2)). c) funkci napravo lze napsat jako 2x · (ln(x2))−1 = 2x · (2·ln(x))−1 = 2−1 · 2x · (ln(x))−1 Tato funkce se od funkce nalevo liší jen o multiplikativní konstantu, takže obě funkce rostou asymptoticky stejně rychle. Platí tudíž všechny tři možnosti: 2x · (ln(x)) −1 ∈ Ο(2x · (ln(x2))−1) 2x · (ln(x)) −1 ∈ Θ (2x · (ln(x2))−1) 2x · (ln(x)) −1 ∈ Ω (2x · (ln(x2))−1), takže situace (se škrtnutým symbolem náležení) v zadání nemůže nastat, tudíž je nutno prázdné místo proškrtnout.
20. V následujících vztazích doplňte na prázdná místa (........) symboly Ο nebo Θ nebo Ω tak, aby vznikla pravdivá tvrzení. Je-li možností více, uveďte je všechny, nehodí-li se ani jeden symbol, prázdné místo proškrtněte. a) x2 · ln(x2) ∈ ........(x2 + ln(x)) b) x3 + ln(x2) ∈ ........(x3 + 2x) c) x3 · ln(x2) ∉ ........(ln(x2) + 2x) Řešení: a) funkce na pravé straně je součtem dvou funkcí, z nichž druhá -- ln(x) -- roste asymptoticky pomaleji než první -- x2. Celkem tedy funkce na pravé straně roste asymptoticky stejně rychle jako x2. Funkce na levé straně však díky multiplikativnímu členu ln(x2) roste asymptoticky rychleji než x2. Tudíž platí právě x2 · ln(x2) ∈ Ω(x2 + ln(x)). b) funkce na pravé straně obsahuje exponenciální člen, funkce na levé straně jen člen polynomiální a logaritmický, jež vesměs rostou asymptoticky pomaleji než exponenciála, takže funkce na pravé straně roste asymptoticky rychleji, platí tedy právě: x3 + ln(x2) ∈ Ο(x3 + 2x). c) podle podobné úvahy jako v b) roste funkce na pravé straně asymptoticky rychleji než funkce na levé straně. Tudíž funkce na levé straně neroste ani asymptoticky stejně rychle ani neroste asymptoticky rychleji. Formálně vyjádřeno: x3 · ln(x2) ∉ Θ(ln(x2) + 2x), x3 · ln(x2) ∉ Ω(ln(x2) + 2x).
10 21. Uveďte příklad tří rostoucích funkcí reálné proměnné f(x), g(x) a h(x), pro které současně platí všechny tři následující vztahy: f(x) ∉ Ο(g(x)), g(x) ∉ Θ(h(x)), h(x) ∉ Ω(f(x)) Pokud taková trojice funkcí nemůže existovat, napište krátké zdůvodnění, proč. Řešení První vztah říká, že f(x) musí růst asymptoticky rychleji než g(x), třetí vztah říká, že f(x) musí růst asymptoticky rychleji než h(x). Druhý vztah říká, že asymptotická rychlost růstu g(x) a h(x) není stejná. Můžeme tedy volit např.: f(x) = x2 g(x) = x h(x) = ln(x).
22.
Uveďte příklad tří rostoucích funkcí reálné proměnné f(x), g(x) a h(x), pro které současně platí všechny tři následující vztahy: f(x) ∉ Ο(g(x)), g(x) ∉ Ω(h(x)), h(x) ∉ Θ(f(x)) Pokud taková trojice funkcí nemůže existovat, napište krátké zdůvodnění, proč. Řešení První vztah říká, že f(x) roste asymptoticky rychleji než g(x), druhý vztah říká, že g(x) roste asymptoticky pomaleji než h(x), celkem tedy g(x) roste asymptoticky pomaleji než f(x) i h(x). Poslední vztah pak říká, že f(x) a h(x) nerostou asymptoticky stejně rychle. Můžeme tedy volit např.: f(x) = x2 g(x) = ln(x) h(x) = x.
