Diszkrét matematikai játékok

Követelmények

Előfeltétel:

• új BSc nappali: Diszkrét matematika (MBNK14)
• új OT nappali: Bevezetés az algebrába (MTNM113)
• régi OT nappali: Algebra és számelmélet 2 (MTN212)
• régi BSc nappali: Diszkrét matematika (MBNK12)

Írásbeli és szóbeli vizsga közül lehet választani:

• Írásbeli vizsga (három alkalommal): 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 legfeljebb 3 előadásról hiányzik, az 1 pluszpontot kap. Így összesen 10 pont szerezhető, az érdemjegy pedig: pontszám – 4.
• 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