Diszkrét matematikai játékok (levelező)

Tudnivalók a követelményekkel kapcsolatban

Mintafeladatsor az írásbeli vizsgához

Levelezős órarend

Az előadások anyaga és a könyvből (Csákány Béla: Diszkrét matematikai játékok) elolvasandó (al)fejezetek:

szeptember 12 (péntek) 8-11 (online). Kombinatorikai játékok, (nyerő) stratégia, mag, Sprague–Grundy-függvény, nim-összeadás

Játékok, mint matematikai struktúrák, végességi feltételek, Kőnig-lemma, kombinatorikai játékok. Bachet játéka, pénzlerakós játék, ω2-játék, Sarokba a bástyát! játék. A stratégia fogalma, stratégiai játékok, nyerő és biztonságos stratégia, Neumann János alaptétele. Egyszerű játék magja és Sprague–Grundy-függvénye (egzisztencia és unicitás), egyszerű példák. A nim-összeadás definíciója, bináris összeadás.

október 10 (péntek) 10-12 (Vályi terem). Játékok összege, nim játék, rontom-bontom játékok, Wythoff-nim

Játékok összege, összeg SG-függvénye. A nim játék nyerő stratégiája. Kivonási játékok, a SG-függvény periodicitása véges kivonási halmaz esetén. Rontom-bontom játékok: Grundy-nim, kugli, Dawson-sakk. Sarokba a királynőt! és Wythoff-nim, a Wythoff-nim magjának leírása rekurzióval, illetve Fibonacci számrendszerben és aranymetszéssel, a jó lépések meghatározása.

november 8 (szombat) 9-12 (online). Betli játékok, malomszerű játékok, permutációs játékok, szoliter, sejtautomaták

Betli játék visszavezetése normál játékra hisztizéssel. Betli kivonási játékok: Ferguson-párok, Ferguson tétele. Betli nim és betli Wythoff nim. Malomszerű játékok, stratégialopás, Építő-Romboló játékok, minimalom (tic-tac-toe), amőba. Hex, Nash tétele, hex aszimmetrikus táblán. Tizenötös játék, cserélgetős játékok, permutációk paritása. A bűvös kocka elérhető állásainak leírása. Szoliter, szoliterhadsereg. Conway-féle életjáték, sejtautomaták, édenkert-tétel, Langton hangyája.

november 28 (péntek) 10-12 (Vályi terem). Elővizsga