Matematika III A 4. ledna 2008 (UČO: ) Hodnocení: Bonus Teorie 1. 2. 3. 4. Na každý příklad získáte nezáporný počet bodů. Potřebné minimum (včetně bonusu) je 15 bodů. Na práci máte 90 minut. Teorie: (6krát 1 bod: tj. správně 1 bod, chybně -1 bod, bez odpovědi 0) Odpovězte (škrtnutím nehodícího se ano nebo ne na patřičném řádku), zda jsou pravdivá následující tvrzení (čtěte velmi pozorně!): (a) ano -- ne Jsou-li všechny vlastní hodnoty (čísla) matice A záporné, je A negativně definitní. (b) ano -- ne Rovinný graf o 5 vrcholech a 5 hranách má právě 2 stěny. (c) ano -- ne Existuje-li limita funkce f : En R v daném bodě, pak je jednoznačně určena. (d) ano -- ne Je-li A stacionárním bodem funkce f, pak je buď jejím lokálním maximem nebo minimem. (e) ano -- ne Každá cesta v grafu je zároveň tahem. (f) ano -- ne Existují alespoň 2 neizomorfní kubické (každý vrchol stupně 3) grafy o 6 vrcholech. Příklady: 1. (6 bodů) S využitím integrálního počtu odvodťe vzorec pro obsah obecného lichoběžníku s vrcholy o souřadnicích A = [0, 0], B = [b, 0], C = [c, v], D = [d, v]. (Pozn: řešení přímo využívající znalost vzorce pro obsah lichoběžníku bude považováno za nesprávné!) 2. (6 bodů) Uvedťe algoritmus na nalezení maximálního párování v bipartitním grafu (tj. na nalezení maximální podmnožiny množiny hran, z níž žádné dvě hrany nesdílí společný vrchol). Pomocí tohoto algoritmu nalezněte maximální párování v grafu na obrázku 1 (při provádění algoritmu dodržujte zásadu, že při vybírání z několika vrcholů algoritmus vždy vybere ten s nejnižším číslem). Své kroky komentujte. 3. (6 bodů) S využitím vytvořujících funkcí řešte rekurenci gn = gn-1 + 3 4 gn-2, g0 = 0, g1 = 4. 4. (6 bodů) Pomocí diferenciálu odhadněte hodnotu součinu sin 31 tg 44 . Při výpočtu pracujte s obloukovou mírou (tj. 1 = 180 ). X1 X2 X3 X4 X5 Y1 Y2 Y3 Y4 Y5 Obr. 1: Obrázek k příkladu na párování. Návod k řešení: Teorie: a) ANO - jsou-li všechny vlastní hodnoty kladné (záporné), je matice pozitivně (negativně) definitní; b) NE - chybí předpoklad souvislosti; c) ANO ­ dokáže se snadno z definice limity; d) NE - může být také inflexním bodem nebo sedlovýn bodem; e) ANO - pokud se neopakují vrcholy, jistě se nemohou opakovat ani hrany; f) ANO - např. K3,3 a "šestiúhelník" s vhodnými třemi úhlopříčkami. 1. Integrujeme nejprve ve směru osy x mezi rameny lichoběžníka, poté pro y jdoucí od 0 do v: S = v 0 y(c-b) v +b yd v dx dy = v 0 y(c-b) v + b - yd v dy = = v b+c-d 2 . 2. Řešení buď převedením na hledání maximálního toku v odvozené síti nebo pomocí "maďarského" algoritmu z přednášky. Maximální párování má 4 hrany, které snadno najdeme, ale při předepsaném postupu podle velikosti je nezbytné "se vracet". 3. Vyjádříme rekurenci tak, aby platila pro všechna přirozená n včetně 0 a 1: gn = gn-1 + 3 4 gn-2 + 4[n = 1]. Vynásobíme obě strany xn , sečteme přes všechna n N a dostaneme rovnici G(x) = xG(x) + 3 4 x2 G(x) + 4x. Úpravou snadno dostaneme G(x) = 4x 1 - x - 3 4 x2 . Tuto racionální lomenou funkci upravíme na součet parciálních zlomků (rozložíme jmenovatele na součin kořenových činitelů a např. metodou neurčitých kkoeficinů nalezneme čitatele): G(x) = A/(1 - 3 2 x) + B/(1 + 1 2 x), z čehož roznásobením a porovnáním koeficientů u x0 a x1 , příp. dosazením vhodných hodnot za x dostaneme A = 2, B = -2. Výsledné funkce rozvineme do řady (jde o funkce tvaru 1/(1 - cx)). Celkem gn = 2 3 2 n - 2 -1 2 n = 1 2n-1 3n - (-1)n . 4. f(x, y) = sin x tg y, tedy f x = cos x tg y a f y = sin x/ cos2 y. Pak sin( 6 + dx) tg 4 + dy = 1 2 1 + 3 2 1 dx + 1 2 1 1 2 dy = 1 2 + 3 2 dx + dy. Tedy sin 31 tg 44 1 2 + 3 2 180 - 180 . Matematika III B 4. ledna 2008 (UČO: ) Hodnocení: Bonus Teorie 1. 2. 3. 4. Na každý příklad získáte nezáporný počet bodů. Potřebné minimum (včetně bonusu) je 15 bodů. Na práci máte 90 minut. Teorie: (6krát 1 bod: tj. správně 1 bod, chybně -1 bod, bez odpovědi 0) Odpovězte (škrtnutím nehodícího se ano nebo ne na patřičném řádku), zda jsou pravdivá následující tvrzení (čtěte velmi pozorně!): (a) ano -- ne Graf K4 není rovinný. (b) ano -- ne Existuje v Petersenově grafu hamiltonovská cesta (tj. cesta procházející každým vrcholem právě jednou)? (c) ano -- ne Každá Cauchyovská posloupnost bodů v En je i konvergentní. (d) ano -- ne Funkce ex je exponenciální vytvořující funkcí posloupnosti samých jedniček. (e) ano -- ne Plyne z existence diferenciálu f v bodě a její spojitost v tomto bodě? (f) ano -- ne Libovolná spojitá funkce nabývá na kompaktní množině svého absolutního extrému výhradně v některém stacionárním nebo hraničním bodě. Příklady: 1. (6 bodů) Najděte rovnice tečné roviny a normály k ploše dané implicitně rovnicí z = y + ln x z v bodě (e, 0, 1). 2. (6 bodů) Uvedťe Floydův algoritmus pro nalezení nejkratších cest mezi všemi dvojicemi vrcholů. Tento algoritmus použijte na orientovaný graf na obrázku 1. Jednotlivé mezivýpočty zapisujte do matic. Uvedťe, jak se v průběhu výpočtu detekují cykly záporné délky. 3. (6 bodů) Určete kolika způsoby je možné naplnit tašku n kusy ovoce, přičemž jednotlivé kusy téhož druhu nerozlišujeme a navíc: * jablek musí být sudý počet, * banánů musí být násobek 5, * pomeranče musí být nejvýše 4 a * hruška může být pouze jedna (nebo žádná). (Nápověda: vytvořující funkce) 4. (6 bodů) Pomocí lichoběžníkového pravidla odhadněte určitý integrál 7 0 dx 1+x s využitím hodnot integrované funkce v uzlech 0, 1, 2, 3, 5, 7. Z charakteru integrované funkce odvodťe, jestli tento odhad bude vyšší nebo nižší než skutečná hodnota integrálu. 1 2 3 4 4 -3 -3 5 6 6 3 10 -7 Obr. 1: Obrázek k příkladu na hledání minimálních cest. Návod k řešení: Teorie: a) NE - je rovinný ­ snadno se nakreslí; b) ANO - cesta existuje (snadno), hůře se dokáže neexistence hamiltonovské kružnice; c) ANO - každá konvergentní posloupnost v En má limitu (En je tzv. úplný prostor); d) ANO - je snadno vidět z rozvoje do řady; obyčejnou funkcí samých jedniček je přitom 1/(1 - x); e) ANO - existence diferenciálu je nejsilnější z postupně budovaných požadavků, z nichž žádný ke spojitosti nestačil (parciální derivace, směrové derivace); f) NE - chybí požadavek diferencovatelnosti, protipříkladem je např. obyčejná absolutní hodnota, která žádný stacionární bod nemá, ale absolutní minimum ano. 1. Označme F(x, y, z) = ln x z + y - z. Normálový vektor k ploše z = z(x, y) dané implicitně rovnicí F(x, y, z) = 0 v bodě A = [e, 0, 1] se spočítá jako (F x(A), F y(A), F z(A)). Protože F x = 1 x , F y = 1, F z = -1- 1 z , je (F x(A), F y(A), F z(A)) = (1/e, 1, -2). Normálu můžeme tedy snadno vyjadřít v parametrickém tvaru n = [e, 0, 1] + t (1/e, 1, -2). Normálový vektor nám zároveň udává koeficienty v obecné rovnici tečné roviny (neboť ta je kolmá na normálu) 1 e x + y - 2z = c, kde c určíme tak, aby v dané rovině ležel i bod A (dosazením snadno c = -1, rovnice tečné roviny je tedy 1 e x + y - 2z + 1 = 0. Jinak: Budeme nejprve hledat tečnou rovinu ve tvaru (z - z0) = z x(x - x0) + z y(y - y0) a z ní pak obdobně jako výše odvodíme rovnici normály. Parciální derivace funkce z = z(x, y) přitom dostaneme "derivováním" implicitní rovnice (přitom se ale na z díváme jako na funkci x a y) a vyjádřením hledaných parciálních derivací. Derivací podle x dostaneme: z x z - xz x z2 - z x = 0, odkud z x = z x(1+z) . Podobně podle y: z x -xz y z2 + 1 - z y = 0, a tedy z y = z z+1 . Dosazením x = e, y = 0, z = 1 dostaneme příslušné parciální derivace v bodě A a tedy i rovnici tečné roviny. 2. Floyd-Warshallův algoritmus používá následující myšlenku (vrcholy očíslované 1, . . . , v : Postupně klademe k = 1, . . ., v a v každé iteraci cyklu najdeme nejkratší cestu z i do j, s vlastností, že po cestě můžeme navštívit pouze vrcholy od 1 do k. Toho lze snadno docílit další dvojicí vnořených cyklů pro všechna i a pro všechna j, kdy uvnitř provedeme aktualizaci cesta(i, j) = min(cesta(i, j), cesta(i, k) + cesta(k, j)). Záporný cyklus se detekuje, jakmile se na diagonále objeví záporné číslo. V našem případě algoritmus (při maticovém zápisu) vypadá takto: 0 4 -3 -3 0 -7 10 0 3 5 6 6 0 0 4 -3 -3 0 -7 10 0 3 5 6 2 0 0 4 -3 -3 0 -7 7 10 0 3 3 6 -1 0 0 4 -3 0 -3 0 -7 -4 7 10 0 3 3 6 -1 0 0 4 -3 0 -3 0 -7 -4 6 9 0 3 3 6 -1 0 3. Výsledkem je koeficient u xn v řadě (1+x2 +x4 + )(1+x5 +x10 + )(1+x+x2 +x3 +x4 )(1+x) = 1 (1 - x)2 = 1+2x+3x2 +4x3 + , a tedy odpověď je n + 1. 4. Počítáme obsahy lichoběžníků se základnami určenými příslušnými uzlovými body: 7 0 dx 1+x 1 2 (1 + 1 2 ) + 1 2 (1 2 + 1 3 ) + 1 2 (1 3 + 1 4 ) + (1 4 + 1 6 ) + (1 6 + 1 8 ) = 3 2 + 2 3 = 13 6 . Odhad je vyšší než počítaný integrál (ln 8), protože integrovaná funkce 1/(1+x) je na daném intervalu konvexní.