Module also offered within study programmes:
General information:
Name:
Combinatorial Game Theory
Course of study:
2019/2020
Code:
AMAT-2-206-MU-s
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Insurance Mathematics
Field of study:
Mathematics
Semester:
2
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
dr Mielczarek Dominik (dmielcza@wms.mat.agh.edu.pl)
Module summary

Moduł dotyczy zastosowań matematyki. Prezentowane modele matematyczne różnych gier kombinatorycznych wraz z przykładami zastosowania.

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence: is able to
M_K001 wie, że matematyki należy uczyć się ze zrozumieniem MAT2A_K05, MAT2A_K02 Activity during classes
Skills: he can
M_U001 potrafi zapisać grę przy pomocy grafu skierowanego, umie znaleźć funkcję SG dla danej gry oraz wyznaczyć dla niej strategię wygrywającą MAT2A_U02, MAT2A_U16 Oral answer,
Test
M_U002 potrafi wykonywać działania w ciele NIM oraz zastosować je do znalezienia ruchów wygrywających MAT2A_U17, MAT2A_U13 Oral answer,
Test
M_U003 posługuje się pojęciem gra, P i N pozycja, funkcja SG, MAT2A_U10, MAT2A_W08, MAT2A_U02 Oral answer,
Test
Knowledge: he knows and understands
M_W001 zna podstawowe gry kombinatoryczne, zna model matematyczny odpowiadający danej grze, umie wyznaczyć strategię wygrywającą MAT2A_U10, MAT2A_U02, MAT2A_W02 Oral answer,
Test
M_W002 zna podstawowe pojęcia oraz twierdzenia (wraz z dowodami) z teorii gier kombinatorycznych MAT2A_W02, MAT2A_W04 Oral answer,
Test
Number of hours for each form of classes:
Sum (hours)
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 30 0 0 0 0 0 0 0 0 0
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Social competence
M_K001 wie, że matematyki należy uczyć się ze zrozumieniem + + - - - - - - - - -
Skills
M_U001 potrafi zapisać grę przy pomocy grafu skierowanego, umie znaleźć funkcję SG dla danej gry oraz wyznaczyć dla niej strategię wygrywającą + + - - - - - - - - -
M_U002 potrafi wykonywać działania w ciele NIM oraz zastosować je do znalezienia ruchów wygrywających + + - - - - - - - - -
M_U003 posługuje się pojęciem gra, P i N pozycja, funkcja SG, + + - - - - - - - - -
Knowledge
M_W001 zna podstawowe gry kombinatoryczne, zna model matematyczny odpowiadający danej grze, umie wyznaczyć strategię wygrywającą + + - - - - - - - - -
M_W002 zna podstawowe pojęcia oraz twierdzenia (wraz z dowodami) z teorii gier kombinatorycznych + + - - - - - - - - -
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 102 h
Module ECTS credits 4 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 h
Preparation for classes 30 h
Realization of independently performed tasks 10 h
Examination or Final test 2 h
Module content
Lectures (30h):

1. Proste gry Take-Away. Przykłady gier Take-Away. Indukcja wsteczna.
P i N pozycje dla gier kombinatorycznych i ich rekurencyjna definicja. Charakterystyka własności.
2. Gra Nim. Gry Subtraction. Wersja Misere gry Nim. Dynamiczna wersja gier Subtraction. Zastosowanie twierdzenia Zeckendorfa w teorii gier.
3. Gry grafowe. Gry na grafach skierowanych. Funkcja Sprague-Grundego dla grafów i jej związek z P i N pozycjami dla gier kombinatorycznych.
4. Twierdzenie Boutona. Zastosowanie twierdzenia Boutona do wyznaczania
ruchów wygrywających. Uogólnienie twierdzenia Boutona. Twierdzenie Moora.
5. Twierdzenie Sprague-Grandy oraz jego zastosowanie. Lasker’s Nim jako przykłąd gry Take-and-break.
6. Suma gier kombinatorycznych. Twierdzenie o funkcji SG dla sumy gier. Suma grafów skierowanych.
7. Gry kombinatoryczne polegające na zamianie monet. Równoważność gier kombinatorycznych. Gry Subtractions jako gry polegające na zamianie monet. Gry Twins i Mock Turtles. “Dobre” i “złe” liczby.
8. Dwuwymiarowe gry polegające na zamianie monet. Acrostic Twins, Turning Corners i Rugs jako przykłady gier dwuwymiarowych.
9. Twierdzenie Tartana. Zastosowanie twierdzenia Tartana do wyznaczania ruchów wygrywających.
10. Nim mnożenie i jego własności. Związek między twierdzeniem Tartana a NIM mnożeniem.
11. Green Hackenbush. Zasada Colon oraz zasada Fusion.
12. Rims. P i N pozycje w grze Rims.
13. Staircase Nim. P i N pozycje w grze Staircase Nim.
14. Wythoff Nim. P i N pozycje w grze Wythoff Nim.

Wszystkie twierdzenia zostaną podane z dowodami.

Program ćwiczeń pokrywa się z programem wykładów. Przewidziane są 2 kolokwia w ciągu semestru.

Auditorium classes (30h):
Program ćwiczeń pokrywa się z programem wykładów

Rozwiązywanie zadań ilustrujących treści prezentowane na wykładach. Przewidziane są 2 kolokwia w ciągu semestru.

Additional information
Teaching methods and techniques:
  • Lectures: Treści prezentowane na wykładzie są przekazywane w formie prezentacji multimedialnej w połączeniu z klasycznym wykładem tablicowym wzbogaconymi o pokazy odnoszące się do prezentowanych zagadnień.
  • Auditorium classes: Podczas zajęć audytoryjnych studenci na tablicy rozwiązują zadane wcześniej problemy. Prowadzący na bieżąco dokonuje stosowanych wyjaśnień i moderuje dyskusję z grupą nad danym problemem.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Dwa zaliczenia poprawkowe.

Participation rules in classes:
  • Lectures:
    – Attendance is mandatory: Yes
    – Participation rules in classes: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
  • Auditorium classes:
    – Attendance is mandatory: Yes
    – Participation rules in classes: Studenci przystępując do ćwiczeń są zobowiązani do przygotowania się w zakresie wskazanym każdorazowo przez prowadzącego (np. w formie zestawów zadań). Ocena pracy studenta może bazować na wypowiedziach ustnych lub pisemnych w formie kolokwium, co zgodnie z regulaminem studiów AGH przekłada się na ocenę końcową z tej formy zajęć.
Method of calculating the final grade:

Ocena zaliczenia ćwiczeń.

Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Według indywidualnego uzgodnienia studenta z prowadzącym zajęcia.

Prerequisites and additional requirements:

Prerequisites and additional requirements not specified

Recommended literature and teaching resources:

#E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways for your mathematical plays, vols. 1 and 2, Academic Press, New York, 1982.

#J. H. Conway, On Numbers and Games, Academic Press, New York, 1976.

#T.S. Ferguson, Game Theory, http://www.math.ucla.edu/~tom/Game_Theory/Contents.html

#G. Owen, Teoria Gier, PWN, 1984.

#P.Straffin, Game Theory and Strategy, Mathematical Association of America, 1993.

Scientific publications of module course instructors related to the topic of the module:

1. Szlachtowska, Ewa; Mielczarek, Dominik; Generalized duality mapping; J. Indian Math. Soc., New Ser. 82, No. 1-2, 169-183 (2015).

2. Góra, Michał; Mielczarek, Dominik; Comments on ”necessary and sufficient stability condition of fractional-order interval linear systems” [Automatica 44 (2008), 2985-2988];
Automatica 50, No. 10, 2734-2735 (2014).

3. Rydlewski, Jerzy P.; Mielczarek, Dominik; On the maximum likelihood estimator in the generalized beta regression model; Opusc. Math. 32, No. 4, 761-774 (2012).

4. Szlachtowska, Ewa; Mielczarek, Dominik; On the uniqueness of minimal projections in Banach spaces.
Opusc. Math. 32, No. 3, 579-590 (2012).

5. Mielczarek, Dominik; Minimal and co-minimal projections in spaces of continuous functions;
Opusc. Math. 30, No. 4, 457-464 (2010).

Additional information:

Na II stopniu studiów moduł może być także zaliczany bez egzaminu ( wykład, ćwiczenia audytoryjne, zaliczenie ćwiczeń, 4 ECTS).