Matematika III - demonstrační cvičení Michal Bulant 15. prosince 2010 1. demonstrační cvičení Příklad 1. Zobrazte v rovině definiční obory funkcí: a) f(x,y) = ln(^ + 2y), b)f(x,y) = Jl-(f + y- 9 4 ^' c. flx v) - yfc? d) f(x,y) = arccos^. Příklad 2. Určete definiční obor funkcí: a) f{x,y,z) = y^ + lnz, ^ f(x,y,z) = 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 cauchyovská: a) (-7j)n , kde n e N, b) an, kde n G N (v závislosti na hodnotě parametru a G M). c) 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,...}, d;{3(l-£) + 2(-l)";7ieN}. Příklad 6. Určete tečnu křivky dané předpisem, f(t) = (2 cos t + cos 3t, sin 2t, t) v bode t = ?f. Příklad 7. Na křivce (t,t2,t3) najděte takový bod, že jím procházející tečna je rovnoběžná s rovinou x + 2y + z = 1. Příklad 8. Vypočtěte limity: a) lim(X;ž/)^(1;1)-^=f, 2_i_„,2 ^ lim(**)->(°.°) Vx2+ž/2+1_ c; lim(Xjž/)^(0j0) ^2/2 cos ^5-■ 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 sm(y) + ey sin(x) definuje předpisem f(x,y) = 1 pro [x,y] G (0, |) x (0, |) implicitně proměnnou y jako funkci proměnné x. Určete f'(x). Příklad 23. Rozhodněte, zda křivka x2, + y:i — 2xy = 0 leží v okolí bodu [1,1] nad (nebo pod) svojí tečnou. Příklad 24. 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. 4 Příklad 25. Najděte lokálni extrémy funkce y = y (x) dané implicitně rovnici ln \J x2 + y2 = arctg K Příklad 26. Určete parametrickou rovnici tečny v bodě [xo,yo, zq] , zq > O ke křivce, jež vznikla jako průsečík kulové plochy K : x2 + y2 + z2 = 4 s válcovou plochou V : x2 + y2 — 2x = O (tzv. Vivianiho křivka^. 5. demonstrační cvičení Nechť F = (f, g) : M2 —>■ M2 a předpokládejme, že funkce /, g (tj. složky zobrazení F) mají v bodě [aľo,l/o] spojité parciální derivace a že Jacobiho matice F'(xo,yo) = (•^x°'ž/0| ^(x°'ž/°) j zobrazení F v bodě [xo,yo] je regulární, tj. det F'(xo, yo) ^ 0 (det F'(xo, yo) se nazývá ja-cobián zobrazení F v bodě [xo,yo]). Pak existuje okolí bodu [xo,yo], v němž je zobrazení F prosté, tudíž k němu existuje inverzní zobrazení F-1 v okolí bodu F(xo,yo), a pro Jacobiho matici tohoto inverzního zobrazení v bodě [ito,^o] = F(%o,yo) platí (F~ry(uo,vo) = [F'Kž/o)]"1. Příklad 27. Rozhodněte, zda je zobrazení F = (f, g) : M2 —>■ M2, kfe f (x, y) = \fx2~^y2 ,g{x,y) = xy, prosté v nějakém okolí bodu [0,1]. F kladném případě určete Jacobiho matici inverzního zobrazení F~l v bodě F(0,1). Příklad 28. Spočítejte jacobián funkce F, která je transformací dvou proměnných do polárních souřadnic, a příslušné inverzní transformace. Příklad 29. Drát délky l je rozdělen na 3 části. Z jedné části je vytvořen kruh, z druhé čtverec a ze třetí rovnostranný trojúhelník (vždy stočením,, resp. složením, vytvoříme obvod příslušného útvaru). Určete délky jednotlivých částí tak, aby celková plocha omezená těmito útvary byla maximální. Příklad 30. Rozhodněte, zda existují maxima a minima funkce f : M2 —>■ K, f (x, y) = x — 2y na křivce dané rovnici y — x2, — 2x — 1 = 0. Případné extrémy určete. Uvažujte křivku omezenou na interval x G (0,5). 5 Příklad 31. Pomocí metody Lagrangeových multiplikátorů nalezněte body na průniku ploch z2 = x2 + y2 a z = 1 + x + y, které leží nejbliže počátku. Zdůvodněte, že jde skutečně o minimum. Příklad 32. Zjistěte, zda existují maxima a minima funkce f(x, y, z) = x + 2y + 3z na elipse z2 = x2 + y2,x — y + z + \ = Q. Příklad 33. Výrobce uvažuje možnost produkce dvou výrobků V\ a V}.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 Vi 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. 6. demonstrační cvičení Příklad 34. Vypočtěte jjMxyáxáy, kde M je oblast 1 < x < 4, ^ < y < Vx- Příklad 35. 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 36. Zaměňte pořadí integrace f(x,y) dy dx. 6 Příklad 37. Vypočtěte integrál 2 ■ , V sm x cla? áy. Jo Jy Příklad 38. Vypočtěte objem tělesa ohraničeného souřadnými rovinami a plochami z = x2 + y2 ,x + y = 1. Příklad 39. Vypočtěte integrál kde A = {[x,y] G M2 : 1 < x2 + y2 < 4,y > \x\}. Příklad 40. Spočtěte integrál j j áyáx. J 0 J—^x—x1 7. demonstrační cvičení Příklad 41. Pomocí vhodné transformace souřadnic vypočtěte integrál jjA^/xyáxáy, kde množina A je ohraničena křivkami y2 = 2x, y2 = x, xy = 1, xy = 2. Příklad 42. Vypočtěte 1. teziste, 2. momenty setrvačnosti vzhledem k souřadným osám tenké homogenní rovinné lichoběžníkové desky s vrcholy v bodech [—1,0]. [2,0], [2,2] a [-1,1]. Řešení. Hustota p(x, y) = 1 pro libovolná x, y. Integrujeme přes množinu A : —1 < x < 2,0 < y < \{x + 4). Dostaneme M = JfAdA = \,TX = ffAx ■ IdA = \,Ty = £ JJAy • 1 áA = l JX(A) = JJAy2 cL4 = f, Jy(A) = JJAx2 cL4 = f. 7 Příklad 43. Hodnotu integrálu L l+x: 1 odhadněte pomoct (a) obdélníkového pravidla, (b) lichoběžníkového pravidla (c) Simpsonova pravidla, přičemž zadaný interval rozdělte na 3 intervaly téže délky. Dosažené výsledky porovnejte s přesnou hodnotou a pomocí obrázku zdůvodněte míru nepřesnosti jednotlivých pravidel. Příklad 44. Pomocí matice souslednosti určete počet sledů délky 4 z vrcholu O do vrcholu 1 v následujícím, grafu: Příklad 45. Ověřte, zda daná posloupnost je skóre nějakého grafu. Pokud ano, nějaký graf s tímto skóre nakreslete. Příklad 46. V grafu na obrázku najděte všechny mosty a artikulace. (a) (1,2,3,4,5,6,7,8,9), (b) (1,1,1,2,2,3,4,5,5). 8 Příklad 47. Udejte příklad grafu, který obsahuje právě (a) 8 artikulacl a 5 mostU, (b) 3 artikulace a 0 mostU, (c) 2 artikulace a 11 mostU. Příklad 48. Rozhodnete, zda jsou zobrazene grafy (vrcholově) 2-souvisle. 9 Příklad 49. Uzijte DijkstrUv algoritmus k nalezeni nejkratslch cest z vyznačeného vrcholu do věech ostatních vrcholu. Příklad 50. Udejte príklad (a) grafu s alespon 4 vrcholy, který neobsahuje cyklus zaporne delky a na nemz da DijkstrUv algoritmus chybný výsledek. (b) grafu s alesponě 4 vrcholy, kterýy obsahuje (alesponě jednu) nezýapornou hranu a pěresto na něem dýa DijkstrUuv algoritmus spraývnýy výysledek. 10 Příklad 51. Užijte Bellman-Fordův algoritmus k nalezení nejkratších cest z vyznačeného vrcholu do všech ostatních vrcholu. Hrany procházejte v poradí dle počátečního (příp. koncového) vrcholu zprava doleva a shola dolu . Zmente ohodnocení hrany z 18 na -18, algoritmus proveďte s tímto novym grafem a ukazte, jak se detekují zaporne cykly. 18 1 2 1 1 1 8 8. demonstrační cvičení Příklad 52. Uveďte Floydův algoritmus pro nalezení nejkratčích cest mezi vsemi dvojicemi vrcholu. Tento algoritmus pouzijte na orientovaný graf na obrízku. Jednotlivé mezivypocty zapisujte do matic. Uveďte, jak se v průběhu vypoctu detekují cykly zaporne délky. 11 Příklad 53. 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é). Nalezněte eulerovské tahy pomocí 1. algoritmu prodlužování cyklů; 2. Fleuryho algoritmu (prodlužování tahů s vyhýbáním, se mostům). (Očíslujte vrcholy a při průchodu algoritmu číslování dodržujte.) 12 Příklad 54. Problém čínského pošíáka v hranově ohodnoceném, neorientovaném, grafu je problémem nalezení nejkratšího uzavřeného sledu, který obsahuje každou hranu v grafu. Nalezněte řešení tohoto problém/a pro graf na obrázku. Příklad 55 (Nutná podmínka toho, aby graf mohl být hamilto-novský). Je-li G = (V, E) hamiltonovský a 0 ^ W C V, pak G\W má nejvýše \W\ komponent souvislosti. Ukažte na konkrétním příkladu grafu, že opak obecně neplatí. Příklad 56 (Postačující podmínky pro to, aby graf byl hamiltonovský). Dirac: stupeň každého vrcholu je aspoň \ V\/2. Ore: součet stupňů libovolných dvou nesousedních vrcholů je aspoň \V\- Bondy-Chvátal: G je hamiltonovský právě když G + uv je hamiltonovský (u, v jsou nesousední vrcholy, jejichž součet stupňů je aspoň \V\ - opakováním přidáváním takových hran, dokud to jde, získáme tzv. uzávěr grafu cl(G)). 1. Dokažte, že z B ondy-Chvátalovy věty plyne Oreho a z ní Diracova. 2. Udejte příklad hamiltonovského grafu, který splňuje podmínku Oreho věty ale ne věty Diracovy. 3. Udejte příklad hamiltonovského grafu, jehož uzávěr není úplný graf. 13 Příklad 57. Rozhodnete (a zdUvodnete), zda v Petersenove grafu existuje 1. hamiltonovskýa cesta, 2. hamiltonovskýa kruěznice. Příklad 58. Rozhodnete, zda je dany graf rovinny. ZdUvodnete. Příklad 59. Rozhodnete, zda existuje graf mající skíre (6, 6, 6, 7, 7, 7, 7,8, 8,8). Pokud ano, existuje i rovinny graf daneho skíre ? Příklad 60. Rozhodnete, zdaje dany rovinny graf maximílní. Doplníte co nejvíce hran pri zachovíní rovinnosti. 14 9. demonstrační cvičení Příklad 61. Každé z následujících tvrzení dokažte nebo ukažte vhodný protipříklad. (a) Každý graf s mene 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žzdíý hamiltonovskíý grafje rovinníý. (g) Žádný hamiltonovský graf není rovinný. (h) Kažzdíý eulerovskíý grafje rovinníý. (i) žaídníý eulerovskíý grafneníí rovinníý. Příklad 62. Urcete vžechný (neizomorfní) stromý 1. na ctýžech vrcholech. 2. na sesti vrcholech. Příklad 63. Urcete kád grafu na obmzku jako 1. p est eníeho stromu, 2. stromu 15 Příklad 64. Rozhodněte, zda existují stromy s následujícími kódy. V případě, že ano, potom, daný strom, nakreslete. • 00011001111001, • 00000110010010111110010100001010111111. Příklad 65. Určete počet koster 1. KA, K5 2- C20Í0, 3. vějíře Vn ( kde vějířem, vn řádu n nazveme graf nan + l vrcholech 0,1,... ,n, který má následujících 2n — 1 hran: vrchol 0 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), z odvozeného rekurentního vztahu vypočtěte několik prvních hodnot, všimněte si souvislosti s Fibonacciho posloupností a tuto souvislost dokažte; 4- žebříku Žn (tvořeného děma cestami délky n a příslušnými dvojicemi vrcholů spojenými hranou) - odvoďte pouze rekurentní vztah. 16 10. demonstrační cvičení Příklad 66. Pomocí kódu dokažte izomorfismus stromů: Příklad 67. 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. 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\ + W2- • 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,. 17 • 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':16, >B>:13, >C>:9, >D>:12, }E':^5, 'F':5]. Příklad 68. Najděte minimální kostru grafu na obrázku pomocí (a) Kruskalova (b) Jarníkova (Primová) algoritmu. (c) Borůvková algoritmu. Jak se výpočet změní, pokud hledáme maximální kostru? A K 4 12 17 1 3 1 v7 W H > 1 1 5 3 2 2 5 Příklad 69. Najděte minimální kostru pomocí maticové verze Jarník-Primova algoritmu v grafu zadaném maticí ohodnocení hran I - 12 - 16 - - - 13\ 12 — 16 — — — 14 — — 16 — 12 — 14 — — 16 — 12 — 13 — — — - - - 13 - 14 - 15 — — 14 — 14 — 15 — - 14 - - - 15 - 14 13 - - - 15 - 14 V 7 18 Příklad 70. 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 71. Maximální párování v bipartitním grafu • perfektní párování v obecném grafu (viz CPP - chinese postman problém) • Tutteho věta - graf má perfektní párování, právě když pro každé S C V počet lichých komponent G\S nepřevyšuje \S\. Maďarský algoritmus (König, Egerváry, Kuhn) Označujme kvůli jednoduchosti popisu vrcholy jedné skupiny v bipar-titní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. 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. 19 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 72. 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. I- 16 24 12 - - - -\ ----30------ 9 6 12 - ------21 - -----9-15 -------9 ------ - 18 A X 7 Příklad 73. Na obrázku je uveden tok v dané síti (čísla f je 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. 20 11. demonstrační cvičení Příklad 74. Naleznete maximální tok a minimální rez v síti na obrázku (zdroj=1,stok=14 ). 21 Příklad 75. Pomocí Ford-Fulkersonova algoritmu (prohledáváni do hloubky, vrcholy volte vzestupně podle čísel) nalezněte maximální tok v síti na množině vrcholů {1, 2,..., 9} se zdrojem 1 a stokem, 9. Nalezněte minimální řez v této síti. Jednotlivé kroky svého postupu podrobně popište. Hrany e G E , dolní omezení, resp. horní omezení na tok danou hranou (d(e), resp. h(e)) a současný tok na dané hraně f(e) jsou uvedeny v tabulce: e d{e) h(e) m (1,2) 0 6 0 (1,3) 0 6 0 (1,6) 0 4 0 (2,3) 0 2 0 (2,4) 0 3 0 (3,4) 0 4 0 (3,5) 0 4 0 (4,5) 3 5 4 (4,8) 0 3 0 e d{e) h(e) m (5,1) 0 3 0 (5,6) 0 6 0 (5,7) 0 5 4 (5,8) 0 5 0 (6,9) 0 5 0 (7,4) 1 6 4 (7,9) 0 3 0 (8,9) 0 9 0 Příklad 76. Kolika způsoby je možné koupit 12 balíčků kávy, mají-li v prodejně kávu pěti druhů? Dále tuto úlohu řešte s následujícími modifikacemi: (a) od každé kávy je třeba koupit aspoň 2 balíčky; (b) od každé kávy má být koupen sudý počet balíčků; (c) jedné z káv (např. arabské) jsou k dispozici pouze 3 balíčky. 12. demonstrační cvičení Příklad 77. Určete kolika způsoby je možné naplnit tašku n kusy uvedených druhů ovoce, přičemž jednotlivé kusy téhož druhu nerozlišujeme, nemusí být využity všechny druhy a navíc: • jablek může být libovolný počet, • banánů musí být sudý počet, • hrušek musí být násobek 4, 22 • pomeranče mohou být nejvýše 3 a • pomelo může být pouze jedno (nebo žádné), Příklad 78. Rozviňte do mocninné řady funkci fL ) X2+X+l \Us 2x3+3x2+l' Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (ai + bi) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení (a • clí) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a • a(x) příslušné vytvořující funkce. • Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. • Pro posunutí posloupnosti doleva o k míst (tj. vynechání prvních k míst posloupnosti) nejprve od a(x) odečteme polynom bk(x) odpovídají posloupnosti (ao,..., a>k-i, 0,...) a poté podělíme vytvořující funkci xk. • Substituci polynomu f(x) — oíx za x odpovídá vynásobení £-tého členu posloupnosti skalárem ak, podobně dosazení f(x) = xn nám do posloupnosti mezi každé dva členy vloží n — 1 nul. Příklad 79. (a) Určete vytvořující funkci posloupnosti (1,2,3,4,5,...). (b) Určete vytvořující funkci posloupnosti (1,4,9,16,...). (c) Určete vytvořující funkci posloupnosti (1,1,2,2,4,4,8,8,...). 23 (d) Určete vytvořující funkcí posloupností (9,0,0,2-16,0,0,4-25,0,0,8-36,...). (e) Určete vytvořující funkcí posloupností (9,1, -9,32,1, -32,100,1, -100,...,). Příklad 80. Vyřešte rekurencí ao = CL\ = 1 0>n = CLn-í + 2<2n_2 + ( — 1)" Příklad 81. Řešte rekurencí 3 1 dn = -jCin-l - 2fln-3, «0 = O, CL\ = 1, CL2 = 13/2. Příklad 82. S využitím vytvořující funkce pro Fíbonaccího posloupnost F{x) = x/(l — x — x2) určete vytvořující funkcí "poloviční" Fíbonaccího posloupností (Fo, F2, F4,...). Příklad 83 (viz. Př. 65). Vějířem řádu n nazveme graf na 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). Kolík koster má takový graf? (Návod: Využijte dříve odvozené rekurence n—í Vn = Vn-i + + 1,Vq = 0.) k=í 24