Domácí úlohy z minulého týdne Jak by mohla vypadat zkouška Vytvořující funkce Drsná matematika III ­ 14. demonstrovaná cvičení Vytvořující funkce Martin Panák Masarykova univerzita Fakulta informatiky 19.12. 2006 Domácí úlohy z minulého týdne Jak by mohla vypadat zkouška Vytvořující funkce 1 Domácí úlohy z minulého týdne 2 Jak by mohla vypadat zkouška 3 Vytvořující funkce Domácí úlohy z minulého týdne Jak by mohla vypadat zkouška Vytvořující funkce Příklad 1. Uvažujme hru nim dvou hráčů s jednou hromádkou s devíti sirkami: hráči se střídají v tazích, tah je odebrání jedné až tří sirek. Kdo nemůže odebrat žádnou sirku prohrává. Vyjádřete tuto hru ve tvaru acyklického grafu a spočítejte Spragueovu-Grundyovu hodnotu všech jeho vrcholů. Pro kterého hráče existuje výherní strategie? Domácí úlohy z minulého týdne Jak by mohla vypadat zkouška Vytvořující funkce Příklad 2. Uvažujme hru nim se dvěma hromádkami, jedna s čtyřmi, jedna se šesti sirkami. Opět můžeme odebírat jeden až tři sirky. Vyjádřete tuto hru ve tvaru acyklického grafu a spočítejte Spragueovu-Grundyovu hodnotu všech jeho vrcholů. Využijte toho, že tato hra je součtem dvou her. Pro kterého hráče existuje výherní strategie? Domácí úlohy z minulého týdne Jak by mohla vypadat zkouška Vytvořující funkce Příklad 3. Uvažme následující hru dvou hráčů: na tabuli jsou napsána přirozená čísla od jedné do deseti. Hráči se střídají v tazích, tah spočívá ve smazání nějakého čísla na tabuli a také všech jeho dělitelů. Vyjádřete tuto hru ve tvaru acyklického grafu a spočítejte Spragueovu-Grundyovu hodnotu všech jeho vrcholů. Pro kterého hráče existuje výherní strategie? Domácí úlohy z minulého týdne Jak by mohla vypadat zkouška Vytvořující funkce 1 Domácí úlohy z minulého týdne 2 Jak by mohla vypadat zkouška 3 Vytvořující funkce Domácí úlohy z minulého týdne Jak by mohla vypadat zkouška Vytvořující funkce Příklad 1. Určete minima a maxima funkce x2 + y + z na křivce v R3: x + y + z = 0, x2 - y2 + z2 = 0. Příklad 2. Určete objem tělesa omezeného elipsoidem x2 + 2y2 + z2 = 4 a poloprostorem obsahujícím bod [1, 3, 5] a ohraničeném rovinou x + y + z = 1. Příklad 3. Nakreslete nějaký graf o sedmi vrcholech, který má právě šest koster. Kolik je těchto koster až na izomorfismus? Příklad 4. Nestandardní úloha vyžadující nápad? Příklad 5. Dokažte, že pokud Dijkstrův algoritmus běží z vrcholu a na grafu G = (V , H) s ohodnocením w : H R+, tak libovolnou hranu stačí testovat pouze jednou (tj. je-li U : V R funkce udávající aktuální minimální vzdálenost od vrcholu a po dosud objevených cestách, tak pokud otestujeme nejprve podmínku U(x) + w(x, y) U(y) v aktivním vrcholu x, tak potom již nemusíme testovat podmínku U(y) + w(y, x) U(x) v momentě, kdy bude aktivním vrcholem y). Domácí úlohy z minulého týdne Jak by mohla vypadat zkouška Vytvořující funkce 1 Domácí úlohy z minulého týdne 2 Jak by mohla vypadat zkouška 3 Vytvořující funkce Domácí úlohy z minulého týdne Jak by mohla vypadat zkouška Vytvořující funkce Určete počet slov s(n) délky 2n v bezkontextové gramatice a N|ab b LaP Řešení. Označme s vytvořující funkci posloupnosti udávající počet slov vzniklých z neterminálu a, dále t vytvořující funkci posloupnosti udávající počet slov vzniklých z neterminálu b. Rozborem prvního pravidla gramatiky dostáváme: s = st + 1 t = x2 s Dosadíme a vyřešíme: 2 Domácí úlohy z minulého týdne Jak by mohla vypadat zkouška Vytvořující funkce