Zajęcia 16 marca

Omówione zagadnienia

• Przypomnienie podstawowych pojęć z kombinatorycznej teorii gier.
  • Definicja gry.
  • Gry impartial i partisan, gry normal i misère.
  • Gra nim.
  • Funkcja Sprague-Grundy'ego, minimum excluded.
  • Twierdzenie Sprague-Grundy'ego.
• Metody rozwiazywania zadań z teorii gier - redukcja do nima.
  • Gra staircase nim.
  • Zadanie z braćmi grającymi o spadek: https://www.codechef.com/NCL2017/problems/NCL1705.

Zadanie domowe

• Lista 5 zadań na Themisie. Otrzymana ocena = liczba zrobionych zadań + 1. Wskazówka - wszystkie zadania są na pewien sprytny pomysł, a implementacja wymyślonego rozwiązania jest już prosta (czasem nawet w 10-20 linijek).
• Zaakceptowanie zadania na Themisie jest równoznacze z deklaracją, że umie się przeprowadzić dowód algorytmu. Zamierzam zapytać na następnych zajęciach z dowodów tych zadań.
• Należy przypomnieć sobie dowód Tw. Sprague-Grundy'ego (najlepiej skorzystać z wykładu Jakuba Radoszewskiego). Zamierzam zapytać na następnych zajęciach z dowodu tego twierdzenia.
• Dla zainteresowanych - wspomniałem o zadaniu Gra z XI OI oraz o tym, że można je sprowadzić do staircase nima, nie podałem jednak jak to zrobić. Możecie się nad tym zastanowić.

Materiały

• Teoria gier - wykład Jakuba Radoszewskiego.
• B. Szreder, "Elementarz chakiera" - rozdział "Kombinatoryczna teoria gier".

Poprawianie ocen

• Jeśli ktoś chciałby poprawić swoją ocenę za zadania matematyczne z teorii liczb, to poprawkowa lista zadań z teorii liczb jest tutaj. Zadania należy oddać do 23.03.17.
• Można poprawiać ostatnio otrzymane oceny za listy zadań i kartkówki. Najlepiej w tym celu najpierw skonsultować się ze mną, ale można też dobić zadanka i następnie mnie poinformować o tym fakcie. Wtedy poprawię ocenę, uwzględniając to jak dużo czasu minęło od terminu wykonania zadań. Proszę dobijać zadanka w rozsądnych ramach czasowych, gdy opóźnienie będzie duże, to mogę nie zaakceptować poprawy.