Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Gry Kombinatoryczne
Tok studiów:
2019/2020
Kod:
AMAT-2-205-MU-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Matematyka ubezpieczeniowa
Kierunek:
Matematyka
Semestr:
2
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Stacjonarne
Strona www:
 
Prowadzący moduł:
dr Mielczarek Dominik (dmielcza@wms.mat.agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

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

Opis efektów uczenia się dla modułu zajęć
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Powiązania z KEU Sposób weryfikacji i oceny efektów uczenia się osiągniętych przez studenta w ramach poszczególnych form zajęć i dla całego modułu zajęć
Wiedza: zna i rozumie
M_W001 zna podstawowe pojęcia oraz twierdzenia (wraz z dowodami) z teorii gier kombinatorycznych MAT2A_W02, MAT2A_W04 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_W002 zna podstawowe gry kombinatoryczne, zna model matematyczny odpowiadający danej grze, umie wyznaczyć strategię wygrywającą MAT2A_U10, MAT2A_U02, MAT2A_W02 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Umiejętności: potrafi
M_U001 posługuje się pojęciem gra, P i N pozycja, funkcja SG, MAT2A_U10, MAT2A_W08, MAT2A_U02 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_U002 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 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_U003 potrafi wykonywać działania w ciele NIM oraz zastosować je do znalezienia ruchów wygrywających MAT2A_U17, MAT2A_U13 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Kompetencje społeczne: jest gotów do
M_K001 wie, że matematyki należy uczyć się ze zrozumieniem MAT2A_K05, MAT2A_K02 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Liczba godzin zajęć w ramach poszczególnych form zajęć:
SUMA (godz.)
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 30 0 0 0 0 0 0 0 0 0
Matryca kierunkowych efektów uczenia się w odniesieniu do form zajęć i sposobu zaliczenia, które pozwalają na ich uzyskanie
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Forma zajęć dydaktycznych
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Wiedza
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ą + + - - - - - - - - -
Umiejętności
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 + + - - - - - - - - -
Kompetencje społeczne
M_K001 wie, że matematyki należy uczyć się ze zrozumieniem + + - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 150 godz
Punkty ECTS za moduł 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 godz
Przygotowanie do zajęć 41 godz
Samodzielne studiowanie tematyki zajęć 47 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Szczegółowe treści kształcenia w ramach poszczególnych form zajęć (szczegółowy program wykładów i pozostałych zajęć)
Wykład (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.

Ćwiczenia audytoryjne (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.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: 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ń.
  • Ćwiczenia audytoryjne: 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:

Warunkiem koniecznym dopuszczenia do egzaminu jest posiadanie oceny pozytywnej z ćwiczeń.
Dwa terminy zaliczeń poprawkowych są skorelowane czasowo z egzaminami poprawkowymi.

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: 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.
  • Ćwiczenia audytoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: 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ęć.
Sposób obliczania oceny końcowej:
  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).
Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Student powinien zgłosić się do prowadzącego w celu ustalenia indywidualnego sposobu nadrobienia zaległości.

Wymagania wstępne i dodatkowe, z uwzględnieniem sekwencyjności modułów :

Nie podano wymagań wstępnych lub dodatkowych.

Zalecana literatura i pomoce naukowe:

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

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

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

Informacje dodatkowe:

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