Diszkrét matematikai játékok
Követelmények
Előfeltétel: Diszkrét matematika (új BSc), Algebra és számelmélet 2 (OT), Klasszikus algebra (régi BSc) vagy Klasszikus algebra és számelmélet (régi BSc).
Írásbeli és szóbeli vizsga közül lehet választani:
-
Írásbeli vizsga: Az első hét feladatban (1-1 pont) csak a tanult játékok nyerő stratégiáit kell alkalmazni, az utolsó feladatban (2 pont) viszont már kicsit kreatívabban kell alkalmazni a tanult elméletet. Íme egy mintafeladatsor. Az írásbelivel összesen 9 pont szerezhető, ehhez adódnak még az előadások látogatásával szerezhető pluszpontok. Aki az előadások legalább felén (nappalisoknál 7, levelezősöknél 3 alkalom) jelen van, az 1 pluszpontot kap, aki pedig az előadások legalább háromnegyedén (nappalisoknál 10, levelezősöknél 4 alkalom) jelen van, az 2 pluszpontot kap. Így összesen 11 pont szerezhető, az érdemjegy pedig: pontszám – 5.
-
Szóbeli vizsga: A szóbeli vizsgán egy tételt kell húzni a tételsorból, és azt a táblánál szabatosan előadni. Minden tételben lesz bizonyítás, amit tudni és érteni kell a sikeres vizsgához.
Tematika
Játékfogalmak, a játékok osztályozása. Stratégiai játékok. Diszkrét játékok, gráfreprezentációjuk. Stratégia diszkrét játékban. Neumann János alaptétele optimális tiszta stratégia létezéséről véges diszkrét játékban.
Véges fokú szimmetrikus normál játék magja. Sprague és Grundy elmélete a mag kiszámításáról. Néhány nevezetes játék elmélete: Nim, Wythoff-játék, Chomp, oktális játékok. Steinhaus és Kalmár elmélete szorzatjáték magjáról.
Malomszerű játékok. Hex; kapcsolata a Brouwer-féle fixponttétellel. Párosítási stratégiák. Topologikus játékok.
Egyszemélyes játékok. Permutációjátékok: tizenötös játék, bűvös kocka. Szeges szoliter. Sejtautomaták: hangya, Fredkin játéka, Conway-féle életjáték. Édenkert-tételek.
A számfogalom felépítése Conway szerint; kapcsolata a kétszemélyes diszkrét játékokkal.
Ajánlott irodalom
- Csákány Béla: Diszkrét matematikai játékok (Polygon Könyvtár 1998, 2005)
- Elwyn R. Berlekamp, John H. Conway, Richard K. Guy: Winning Ways for your Mathematical Plays
- John H. Conway: On Numbers and Games