Domácí úlohy z minulého týdne Návodné úlohy Drsná matematika III – 12. demonstrovaná cvičení Stromové hry Martin Panák Masarykova univerzita Fakulta informatiky 6.12. 2006 Domácí úlohy z minulého týdne Návodné úlohy Plán přednášky 1 Domácí úlohy z minulého týdne 2 Návodné úlohy Domácí úlohy z minulého týdne Návodné úlohy Příklad. 1. Řezem v síti (V , E, z, s, w) můžeme také rozumět množinu hran C ⊂ S takovou, že v síti (V , E \ C, z, s, w) neexistuje žádná orientovaná cesta ze zdroje z do stoku (cíle, spotřebiče) s, ale pokud z C odebereme libovolnou hranu e, tak už nová množina tuto vlastnost mít nebude, tedy v (V , E \ C ∪ e, z, s, w) existuje orientovaná cesta ze z do s. Určete všechny tyto řezy (a jejich hodnoty) v následující síti: Domácí úlohy z minulého týdne Návodné úlohy Příklad. 2. Najděte maximální tok v síti z příkladu 1 pomocí Fordova-Fulkersonova algoritmu (algoritmu z přednášky). Domácí úlohy z minulého týdne Návodné úlohy Příklad. 3. Rozhodněte zda platí (při definici řezu z příkladu 1): a) Počet řezů v síti je roven počtu orientovaných cest ze zdroje do stoku. b) Počet maximálních toků v síti je roven počtu minimálních řezů. c) Řezů v síti může být jak více tak méně než orientovaných cest ze zdroje do stoku. Domácí úlohy z minulého týdne Návodné úlohy Plán přednášky 1 Domácí úlohy z minulého týdne 2 Návodné úlohy Domácí úlohy z minulého týdne Návodné úlohy Nestranné hry dvou hráčů Hra je popsána množinou všech možných pozic ve hře. Mezi některými pozicemi lze přecházet pomocí tahů. Možné tahy v dané pozici závisí pouze na této pozici, nikoliv na tom, který hráč je právě na tahu. Žádnou pozici není možné v průběhu hry zopakovat. Takovéto hry můžeme dobře popsat pomocí acyklických orientovaných grafů: vrcholy pozice, hrany tahy. Domácí úlohy z minulého týdne Návodné úlohy Vyhrávající a prohrávající pozice. Všechny pozice ve zkoumaných hrách můžeme rozdělit na vyhrávající (pro prvního hráče), či prohrávající. Vyhrávající pozice je taková, že pokud hrají oba hráči bez chyb, tak nutně vyhraje první, v prohrávající pozici prohrává druhý. Spragueova-Grundyova funkce f . Ohodnocení pozic ve hře (vrcholů v odpovídajícím acyklickém orientovaném grafu) přirozenými čísly. Začínáme koncovými pozicemi (pozice, ve kterých není možný žádný další tah). Takové pozice jsou prohrávající pro hráče, který je na tahu. Tyto pozice označíme číslem 0 a rekurzivně proti směru šipek v grafu označujeme postupně další vrcholy: f (v) = min{N \ S}, kde S je množina následníků vrcholu (pozice) v v dané hře (orientovaném acyklickém grafu). Hra je vítězná za prvního hráče, právě když má počáteční pozice ohodnocení různé od nuly. Domácí úlohy z minulého týdne Návodné úlohy Součet her. Součet G + H dvou her je hra, ve které hráči hrají paralelně obě hry, tah hráče spočívá v tahu v právě jedné z her G a H. Hry G a H jsou ekvivalentní, je-li pro lib. jinou hru I hra G + I vyhrávající pro prvního hráče právě tehdy, když je hra H + I vyhrávající pro prvního hráče. (též G + H má hodnotu 0). Spragueova-Grundyova věta. Dvě hry jsou ekvivalentní, právě když je hodnota h Spragueovy-Grundyovy funkce v počátečních pozicích těchto her shodná (jsou pak ekvivalentní hře nim s jednou hromádkou o h sirkách). Ohodnocení počáteční pozici hry G + H je rovno g ⊕ h, kde g je hodnota počáteční pozice G, h hodnota počáteční pozice H a ⊕ je xor binárních zápisů čísel g a h. Domácí úlohy z minulého týdne Návodné úlohy Nim Několik variant: vždy dva hráči. Několik hromádek sirek. Hráči se střídají na tahu. Tak spočívá v odstranění několika (alespoň jedné; může být též zadáno horní omezení) sirek z jedné hromádky. Dvě varianty konce: prohrává ten, kdo již nemůže táhnout (normální hra), ve druhé variantě prohrává ten, kdo vezme poslední sirku.