ITN w XIV LO we Wrocławiu 2016/2017, klasy drugie, grupa podstawowa - semestr letni

Aleksander Łukasiewicz's homepage - teaching

Zajęcia 16 marca

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.

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

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.