Matematika III - demonstrační cvičení Michal Bulant 18. prosince 2009 1. demonstrační cvičení Příklad 1. Zobrazte v rovině definiční obory funkcí: a) f(x,y) = \n(% + 2y), b)f(x,y) = Jl-(Í + y- 9 ~r 4 ;, c. flx,) - v^ Ž/) = arccos^. Příklad 2. Určete definiční obor funkcí: a) f(x,y,z) = yi + lnz, ^ /(>, 2/, *) = arccos * Příklad 3. Načrtněte vrstevnice funkcí: a) f(x,y) = x2 -y2, b) f(x,y) = xy, c) f(x,y) = y/xy. Příklad 4. Rozhodněte, zda je daná posloupnost cauchyovska: a) (-7j)n, kde n G N7 b) an, kde n G N (v závislosti na hodnotě parametru a GlJ. 1 Příklad 5. Určete všechny hromadné body množiny: a) Z, b)Q, C; {1,1,2,1,2,3,1,2,3,4,...}, /a2a+y+1_ť cj lim(x?ž/)^(0?0)^l/2cos^2, Gř;iim(X;ž/H(0,o)^, ej lim(x?ž/M0?0) f^, /; lim(X;ž/Mo0;0o)(:r2 + y2)e-{x+^ ^lim(x>yMoo>i)(l + i I x+y 2. demonstrační cvičení Příklad 9. Dokažte, že následující limity neexistují: a) lim(x?ž/M0?0) ^2, U ) ľ 1—cos(x2+y2) ty lim(x?ž/)^(0?0) (x2+ž/2)xž/ • 2 Příklad 10. Vypočtěte všechny parciální derivace (i smíšené) funkce f(x,y) = xi + 10x2y3-2y6 až do řádu 3 včetně. Příklad 11. Určete směrovou derivaci funkce f(x,y) = aictg(x2+y2) v bodě [—1,1] ve směru vektoru (1,2). Příklad 12. Vypočtěte parciální derivace 1. řádu funkcí a) f(x,y) = xxy, x-y b) f{x,y) = a,ictgj+xy Příklad 13. Určete diferenciál v daném bodě: a) f(x,y) = xy + ^y v bodě [1,1], b) f(x, y) = arcsin , x v bodě [1, y/Š]. y x2+y2 3. demonstrační cvičení Příklad 14. Rozhodněte, zda je funkce f(x,y) = ^/\xy\ diferencovatelná v [0,0]. Příklad 15. Pomocí diferenciálu přibližně vypočtěte: a) arcsin j2!!, &;i,042'02. Příklad 16. Určete rovnici tečné nadroviny ke grafu funkce v daném bodě: a) f(x,y) = x2 + xy + 2y2, [x0,yo,z0} = [1,1,4], b) f(x,y) = arctgf, [x0,y0,zo] = [1,-1,?]. 3 Příklad 17. Určete Taylorův polynom 2. stupně se středem v daném bodě: a) liiyV + y2, [x0,yo] = [1,1], b)x*, [x0, y0, z0] = [1,1,1] • Příklad 18. Pomocí Taylorova polynomu 2. stupně přibližně vypočtěte a) sin 29° tg 46°, 6;in(aľ2 + y2 + l) v Ďocřé [1,1; 1,2]. Příklad 19. Pomocí vrstevnic funkce f(x,y) = \x\ + \y\ určete její největší a nejmenší hodnotu na množině M : (x — l)2 + (y-l)2■ M, f (x,y) = x2y+y2x — xy a rozhodněte, které z těchto bodů jsou lokálními extrémy a jakého druhu. Příklad 22. Ukažte, že funkce f(x, y) = ex sin(y) + ey sin(aľ) definuje předpisem f(x, y) = 1 pro [a:, y] G (0, |) x (0, |) implicitně proměnnou y jako funkci proměnné x. Určete f'{x). Příklad 23. Rozhodněte, zda existují maxima a minima funkce f : M2 —>■ M, f (x, y) = x — 2y na křivce dané rovnici y — x2, — 2x — 1 = 0. Uvažujte křivku omezenou na interval (0,5). 4 Příklad 24. Zjistěte, zda existuji maxima a minima funkce f(x, y, z) = x + 2y + 3z na elipse z2 = x2 + y2,x — y + z + l = 0. 5. demonstrační cvičení Příklad 25. Rozhodněte, zda křivka x* + y3 — 2xy = 0 leží v okolí bodu [1,1] nad (nebo pod) svojí tečnou. Příklad 26. Rozhodněte, zda plocha daná v okolí [1,0,1] G E% rovnicí x2, + y:i + zz — Sxyz — x — y — z = 0 leží v bodě [1, 0,1] nad nebo pod tečnou rovinou. Příklad 27. Najděte lokální extrémy funkce y = y (x) dané implicitně rovnicí In y'x2 + y2 = arctg K Příklad 28. Určete parametrickou rovnici tečny v bodě [xo, yo, zq] , zq > 0 ke křivce, jež vznikla jako průsečík kulové plochy K : x2 + y2 + z2 = 4 s válcovou plochou V : x2 + y2 — 2x = 0 (tzv. Vivianiho křivka^. Příklad 29. Výrobce uvažuje možnost produkce dvou výrobků V\ a V'1-Pro jejich výrobu může počítat s využitím 180 kg surovin, 240 hodin práce speciálních strojů a náklady jsou přitom omezeny částkou 160 tis. Kč. Na základě předpokládaných tržeb byl stanoven očekávaný zisk za 1 kus výrobku V\ na 7 tis. Kč a za 1 kus výrobku V2 na 9 tis. Kč. Z předběžného průzkumu zájmu vyplynulo, že oba výrobky lze prodat v libovolném množství. V rámci přípravy produkce byla stanovena náročnost obou výrobků z hlediska spotřeby zdrojů na 1 kus: Výrobek spotřeba surovin [kg] spotřeba času [hj náklady [tis. Kč] Ví 3 5 10 v2 5 4 2 Vzhledem k uvedeným skutečnostem naplánujte výrobu tak, aby výrobci přinesla nejvyšší zisk. 5 6. demonstrační cvičení Příklad 30. Vypočtěte jjM xyáxáy, kde M je oblast 1 < x < 4, ^ < y < y/x. Příklad 31. Převeďte dvojný integrál JjAf(x,y)áA na dvojnásobný (obě možnosti pořadí integrace) pro množinu A ohraničenou přímkami y = x,y = x — 3,y = 2,y = 4. Ověřte (přímo nebo s využitím SW např. MAW) rovnost výsledku pro konkrétní funkci f(x,y) = y. Příklad 32. Zaměňte pořadí integrace jQ f2* f(x,y)áyáx. Příklad 33. Vypočtěte integrál / / (x + y) ckcdy, kde A je ohraničena grafy funkcí y = x2, y = x. Příklad 34. Vypočtěte integrál /IT /II y2 si11 x2 &x áy. JO Jy Příklad 35. Vypočtěte objem tělesa ohraničeného souřadnými rovinami a plochami z = x2 + y2,x + y = 1. Příklad 36. Vypočtěte integrál JJ 2{x2 + y2)áA) kde A = {[x,y] G M2 : 1 < x2 + y2 < 4, y > \x\}. Příklad 37. Spočtěte integrál j j áyáx. J 0 J — \/x—x2 Příklad 38. Pomocí vhodné transformace souřadnic vypočtěte integrál ffA ^/x~yáxáy, kde množina A je ohraničena křivkami y2 = 2x) y2 = x) xy = 1, xy = 2. 6 7. demonstrační cvičení Příklad 39. Vypočtěte integrál JJJA(r + y2 + z2)dA, kde A : x2 + y2 < a2, z > 0, z < b, a, b > 0 jsou parametry. Příklad 40. Vypočtěte objem množiny A, která je průnikem koulí x2 + y2 + z2 < 16, x2 + y2 + z2 < 8z (a) pomocí válcových souřadnic, (b) pomocí sférických souřadnic. Příklad 41. Vypočtěte integrál JJLxydA' kde A:x2 + y2 + (z-2)2 y'x2 + y2. Příklad 42. Určete souřadnice těžiště tělesa daného nerovnostmi x2 + y2 ■ 52,2 —> 43,3 —> 64,4. 5 již navštívená => 64,2, návrat ^,2, návrat 52,2, další hrana —>■ 95,5 —>■ 8ßß —>■ 117,7. 8 již navštívená => lhß, návrat 8ß,6- Uzavřena komponenta 11,8. Návrat 95,5 —>■ 108,8 —> 3g,g, 9 ju navštívená => 3g?57 návrat 108,5, 6 ju navštívená => 108,4, návrat 95,4, návrat 02,2; 10 již navštívená => 52,2 f&e^e změny). Uzavřena komponenta 3,10,9,6,4,5. Návrat li,i. Uzavřena komponenta 1. Ještě existují nezařazené vrcholy, začneme s 2io,io —>■ 7n,n, 2 již navštívená => 7n,io, návrat 2i0,io- Uzavřena komponenta 7,2. Postup z vrcholu 7: postup do hloubky: 7i,i —>■ 22,2 —> 13,3 —> 54,4 —>■ 95,5 —>■ 8ß?6 —> 117,7- 8 ju navštívená => lhß, návrat 8ß,6- Uzavřena komponenta 11,8. Návrat 95,5, další hrana —>■ 10s,8 —> 3g,g. 9 již navštívená => 3g,5, návrat 108,5, da/si hrana 610,10, 5 ju navštívená => 610,4, návrat 108,4, návrat 95,4, návrat 54,4, další hrana 4n,n, 6 ju navštívená^* 4n,io, návrat 54,4, 10 již navštívená^* 54,4 (beze změny). 10 Uzavřena komponenta 4,6,3,10,9,5. Návrat I33. Uzavřena komponenta 1. Návrat %i;i, hrana (2,1) nemění nic, 7 již navštívená => 22,i7 návrat 7i;i; hrana (7,11) nic nemění. Uzavřena komponenta 2,7. Rozmyslete si změnu v případě, že by v grafu nebyla napf. hrana (11,8) - nedojde k aktualizaci čísla u vrcholu 11 a tak zůstanou vrcholy 11 i 8 v samostatných komponentách. Příklad 52. Užijte Dijkstrův algoritmus k nalezení nejkratších cest z vyznačeného vrcholu do všech ostatních vrcholů. O Ô—2 18 1 2 1 7 1 3 1. 1—0 7 .5 Příklad 53. Udejte příklad (a) grafu s alespoň 4 vrcholy, který neobsahuje cyklus záporné délky a na němž dá Dijkstrův algoritmus chybný výsledek. (b) grafu s alespoň 4 vrcholy, který obsahuje (alespoň jednu) nezápornou hranu a přesto na něm, dá Dijkstrův algoritmus správný výsledek. Příklad 54. Užijte Bellman-Fordův algoritmus k nalezení nejkratších cest z vyznačeného vrcholu do všech ostatních vrcholů. Změňte ohodnocení hrany z 18 na -18, algoritmus proveďte s tímto novým grafem a ukažte, jak se detekují záporné cykly. 11 Příklad 55. Uveďte Floydův algoritmus pro nalezení nejkratších cest mezi všemi dvojicemi vrcholů. Tento algoritmus použijte na orientovaný graf na obrázku. Jednotlivé mezivypočty zapisujte do matic. Uveďte, jak se v průběhu výpočtu detekují cykly záporné délky. Příklad 56. Rozhodněte, zda jsou následující grafy eulerovské. Pokud nejsou, doplňte je přidáním hran na eulerovské (je-li to možné). 12 Nalezněte eulerovské tahy. Příklad 57. Rozhodněte (a zdůvodněte), zda v Petersenově grafu existuje 1. hamiltonovská cesta, 2. hamiltonovská kružnice. Příklad 58. Rozhodněte, zda je daný graf rovinný. Zdůvodněte. Příklad 59. Rozhodněte, zda existuje graf mající skóre (6, 6, 6, 7, 7, 7, 7,8, 8,8). Pokud ano, existuje i rovinný graf daného skóre ? 13 Příklad 60. Rozhodněte, zda je daný rovinný graf maximální. Doplňte co nejvíce hran při zachování rovinnosti. Příklad 61. Každé z následujících tvrzení dokažte nebo ukažde vhodný protipříklad. (a) Každý graf s méně než 9 hranami je rovinný. (b) Graf, který není rovinný, není hamiltonovský. (c) Graf, který není rovinný, je hamiltonovský. (d) Graf, který není rovinný, není eulerovský. (e) Graf, který není rovinný, je eulerovský. (f) Každý hamiltonovský graf je rovinný. (g) Žádný hamiltonovský graf není rovinný, (h) Každý eulerovský graf je rovinný. (i) Žádný eulerovský graf není rovinný. Příklad 62. Určete kód pěstěného strom/a na obrázku 14 Příklad 63. Nakreslete pěstěný strom, který má kód 00000110010010111110010100001010111111. Příklad 64. Určete počet (homo)morfismů grafů (a) P'i do K4, (b) P3 do K7, (c) K4 do K7. Příklad 65. Najděte minimální kostru grafu 8 2 16 f-----------------f-----------------f-----------------f 0---------------------1 13 4 »------------------------------------------------------1 5 10 »---------------------------o 6 17 d----------------------------( 3 »----------------------------( 1---------------------0 1 15 14 15 Příklad 66. Najděte minimální kostru grafu na obrázku pomocí (a) Kruskalova (b) Jarníkova (Primová) algoritmu. Jak se výpočet změní, pokud hledáme maximální kostru? K37\ A K 4 12 17 1 3 1. Příklad 67. Udejte příklad, na němž ukážete nefunkčnost "naivního" algoritmu pro nalezení nejkratší cesty: 1. nalezněte minimální kostru, 2. za nejkratší cestu prohlásíme tu jedinou cestu spojující zadané 2 vrcholy, která leží v nalezení minimální kostře. Příklad 68. Maximální párování v bipartitním grafu Maďarský algoritmus (König, Egerváry, Kuhn) Označujme kvůli jednoduchosti popisu vrcholy jedné skupiny v bipartitním grafu jako červené, vrcholy druhé skupiny jako modré. Budeme předpokládat, že vrcholy jsou obarveny tak, že počet červených vrcholů nepřevyšuje počet modrých. Nechť je dán bipartitní graf G = (V, E) a párování MCE. M-alternující cestou v G nazveme takovou cestu v G, jejíž hrany tvoří střídavě hrany z M a z E \ M. M -rozšiřující cestou v G nazveme M-alternující cestu, která spojuje dosud nepřiřazený červený vrchol u s dosud nepřiřazeným modrým vrcholem v. 16 1. Nalezneme libovolné párování M. Označíme všechny červené vrcholy jako přípustné. 2. Vyberme některý dosud nepřiřazený přípustný červený vrchol v (pokud neexistuje, jsme hotovi) a nalezněme pro něj (např. prostřednictvím, prohledávání do hloubky) M -alternující strom, s kořenem, ve v (pokud neexistuje, označme v jako nepřípustný a proces opakujme s jiným vrcholem). Pokud strom obsahuje nějakou M-rozšiřující cestu, odstraníme M-hrany v této cestě z M a ostatní hrany této cesty do M přidáme. Označme všechny červené vrcholy jako přípustné a proces opakujme. V bipartitním grafu na obrázku najděte takovou maximální podmnožinu hran, že žádné dvě z nich nesdílejí společný vrchol. Příklad 69. Huffmanovo kódování Pracujeme s pěstěnými binárními stromy, kde máme navíc každou hranu obarvenou některým symbolem z dané výstupní abecedy A (často A = {0,1}). Kódovými slovy C jsou slova nad abecedou A, na která převádíme symboly vstupní abecedy. Našim úkolem je reprezentovat daný text pomocí vhodných kódových slov nad výstupní abecedou. Je snadno vidět, že je užitečné chtít, aby seznam kódových slov byl bezprefixový (v opačném případě může nastat problém s dekódováním). Ke konstrukci binárních prefixových kódů (tj. nad abecedou A = {0,1},) využijeme binárních stromů. Označíme-li hrany vycházející z každého uzlu 0, resp. 1, a označíme-li navíc listy stromu symboly vstupní abecedy, dostaneme prefixový kód nad A pro tyto symboly zřetězením označení hran na cestě z kořene do příslušného listu. 17 Takto vytvořený kód je zřejmě prefixový. Uděláme-li tuto konstrukci navíc tak, abychom odrazili četnost symbolů vstupní abecedy v kódovaném textu, dosáhneme tak dokonce bezztrátové komprese dat. Nechť M je seznam četností symbolů vstupní abecedy v textu. Algoritmus postupně zkonstruuje optimální binární strom (tzv. minimum-weight binary tree) a přiřazení symbolů listům. • Vyber dvě nejmenší četnosti w\,W2 z M. Vyrob strom se dvěma listy označenými příslušnými symboly a kořenem označeným w\ + W'i , odeber z M hodnoty w\,W2 a nahraď je hodnotou w\ -\-u>2. • Tento krok opakuj; pouze v případě, že vybraná hodnota z M je součtem,, pak nevyráběj nový list, ale "připoj" příslušný již existující podstrom,. • Kód každého symbolu urči cestou od kořene (např. vlevo="0", vpravo=" 1"). Nalezněte Huffmanův kód pro vstupní abecedu s frekvencemi ['A ' :20, 'B'iíO, 'C: 15, 'D'il, 'E'1^5, >F':5]. 8. demonstrační cvičení Příklad 70. Určete hodnotu maximálního toku a najděte minimální řez v síti dané maticí kapacit A, kde vrchol 1 je zdroj a vrchol 8 stok. í- A 16 24 12 - - - -\ - - - 30 - - - -------------9 6 12 - ------------------------21 - -----------------9-15 ______ 9 ------ 18 V" 7 18 Příklad 71. Na obrázku je uveden tok v dané síti (čísla f /c udávají současný tok a kapacitu dané hrany). Zjistěte, je-li uvedený tok maximální, pokud ano, své tvrzení zdůvodněte. Pokud maximálním tokem není, maximální tok najděte a svůj postup podrobně popište. Uveďte některý minimální řez v dané síti. 18/18 6/6 12/16+Q) Příklad 72. Nalezněte maximální tok a minimální řez v síti na obrázku (zdroj=l,stok=14)- 2/2 6/12 12/30 2/2 10/10 18/18 8/8 0/2 0/14 2/2 12/18 5)— 12/18 8/20 0/8 4/4 22/32 19 Příklad 73. (a) Určete vytvořující funkci posloupnosti (9,0,0,2-16,0,0,4-25,0,0,8-36,...). (b) Určete vytvořující funkci posloupnosti (9,1, -9,32,1, -32,100,1, -100,...,). Příklad 74. S využitím, vytvořujících funkcí řešte rekurenci an+2 = an + n (pro n G N), ao = a\ = 0. Vyjádřete an jako funkci n jediným, vzorcem, bez rozlišování parity n. Příklad 75. Určete najít formuli pro výpočet n-tého členu posloupnosti zadané rekurentně předpisem Fq = O, Fi = 1, Fn+2 = Fn+Í + Fn. Příklad 76. Vyřešte rekurenci <2o = cl\ = 1 0>n = CLn-í + 2<2n_2 + ( — 1)™ Příklad 77. Řešte rekurenci 3 1 an = -jdn-i - 2an-3, a0 = O, ai = 1, a2 = 13/2. Příklad 78. S využitím, vytvořující funkce pro Fibonacciho posloupnost F{x) = x/(l — x — x2) určete vytvořující funkci "poloviční" Fibonacciho posloupnosti (Fo, F2, F4,...). Příklad 79. Řešte rekurenci 9n = ngn-hg0 = 1. Příklad 80. Vějířem řádu n nazveme graf n n+1 vrcholech 0,1,..., n, který má následujících 2n — 1 hran: vrchol O je spojen hranou s každým ze zbylách vrcholů a každý vrchol k je spojen hranou s vrcholem k + 1 (pro 1 < k < n). Kolik koster má takový graf? 20 21 9 7 12 10 14 8 13 6 11 22 © 9 7 © o 10 14 8 13 6 11 23 Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Pak zřejmě F{x) — xF{x) — x2F{x) = x, a tedy F(x) = ------------- 1 - x - X' 24