Module also offered within study programmes:
General information:
Annual:
2017/2018
Code:
AMA-2-025-MZ-s
Name:
Combinatorial Game Theory
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Matematyka w zarządzaniu
Field of study:
Mathematics
Semester:
0
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)
Academic teachers:
dr Mielczarek Dominik (dmielcza@wms.mat.agh.edu.pl)
mgr Szlachtowska Ewa (szlachto@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
M_K001 wie, że matematyki należy uczyć się ze zrozumieniem; potrafi wyartykułować, czego nie rozumie; stara się doskonalić swoje kwalifikacje matematyczne Activity during classes,
Examination,
Test,
Oral answer
Skills
M_U001 posługuje się pojęciem gra, P i N pozycja, funkcja SG, Activity during classes,
Examination,
Test,
Oral answer
M_U002 potrafi zapisać grę przy pomocy grafu skierowanego, umie znaleźć funkcję SG dla danej gry oraz wyznaczyć dla niej strategię wygrywającą Activity during classes,
Examination,
Test,
Oral answer
M_U003 potrafi wykonywać działania w ciele NIM oraz zastosować je do znalezienia ruchów wygrywających Activity during classes,
Examination,
Test,
Oral answer
Knowledge
M_W001 zna podstawowe pojęcia oraz twierdzenia (wraz z dowodami) z teorii gier kombinatorycznych Activity during classes,
Examination,
Test,
Oral answer
M_W002 zna podstawowe gry kombinatoryczne, zna model matematyczny odpowiadający danej grze, umie wyznaczyć strategię wygrywającą Activity during classes,
Examination,
Test,
Oral answer
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
Others
E-learning
Social competence
M_K001 wie, że matematyki należy uczyć się ze zrozumieniem; potrafi wyartykułować, czego nie rozumie; stara się doskonalić swoje kwalifikacje matematyczne + + - - - - - - - - -
Skills
M_U001 posługuje się pojęciem gra, P i N pozycja, funkcja SG, + + - - - - - - - - -
M_U002 potrafi zapisać grę przy pomocy grafu skierowanego, umie znaleźć funkcję SG dla danej gry oraz wyznaczyć dla niej strategię wygrywającą + + - - - - - - - - -
M_U003 potrafi wykonywać działania w ciele NIM oraz zastosować je do znalezienia ruchów wygrywających + + - - - - - - - - -
Knowledge
M_W001 zna podstawowe pojęcia oraz twierdzenia (wraz z dowodami) z teorii gier kombinatorycznych + + - - - - - - - - -
M_W002 zna podstawowe gry kombinatoryczne, zna model matematyczny odpowiadający danej grze, umie wyznaczyć strategię wygrywającą + + - - - - - - - - -
Module content
Lectures:

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:
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.

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 150 h
Module ECTS credits 6 ECTS
Participation in lectures 30 h
Realization of independently performed tasks 46 h
Contact hours 9 h
Participation in auditorium classes 30 h
Preparation for classes 30 h
Examination or Final test 5 h
Additional information
Method of calculating the final grade:
  1. Warunkiem koniecznym dopuszczenia do egzaminu jest posiadanie oceny pozytywnej z ćwiczeń.
  2. Ocenę końcową OK wyznacza się na podstawie średniej ważonej SW obliczonej według wzoru
    SW = 0,49 SOC + 0,51 SOE,
    gdzie SOC jest średnią arytmetyczną ocen uzyskanych we wszystkich terminach zaliczeń z ćwiczeń,
    a SOE jest średnią arytmetyczną ocen uzyskanych we wszystkich terminach z egzaminu.
  3. Ocena końcowa OK. jest obliczana według algorytmu:
    Jeżeli SW ≥ 4.75, to OK = 5.0 (bdb),
    jeżeli 4.75 > SW ≥ 4.25, to OK = 4.5 (db),
    jeżeli 4.25 > SW ≥ 3.75, to OK = 4.0 (db),
    jeżeli 3.75 > SW ≥ 3.25, to OK = 3.5 (dst),
    jeżeli 3.25 > SW ≥ 3.00, to OK = 3.0 (dst).
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).