Politechnika Warszawska - Centralny System Uwierzytelniania
Strona główna

Gry kombinatoryczne

Informacje ogólne

Kod przedmiotu: 1120-MA000-LSP-0684
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Gry kombinatoryczne
Jednostka: Wydział Matematyki i Nauk Informacyjnych
Grupy: Przedmioty obieralne - Inżynieria i analiza danych
Przedmioty obieralne dla studentów kierunku "Matematyka i analiza danych"
Przedmioty obieralne prowadzone w semestrze letnim 2023/2024
Przedmioty obieralne, wydz. MiNI PW
Zaawansowane zagadnienia matematyki (blok obieralny)
Punkty ECTS i inne: 4.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.
Język prowadzenia: polski
Skrócony opis:

Wymagania wstępne/ przedmioty poprzedzające: Matematyka dyskretna, Algebra liniowa z geometrią 1-2, Rachunek prawdopodobieństwa

Celem przedmiotu jest zaznajomienie słuchaczy z głównymi wynikami kombinatorycznej teorii liczb, począwszy od klasyki (twierdzenie Schura i Van der Waerdena), na najnowszych wynikach i problemach otwartych kończąc.

Pełny opis:

1. Gry typu „kółko i krzyżyk”.

2. Gry na hipergrafach i kombinatoryczny chaos.

3. Gry Ramseyowskie, kliki w grafach i ciągi arytmetyczne.

4. Twierdzenie Erdosa-Selfridga o potencjałach.

5. Lemat Lokalny Lovasza i jego zastosowania w informatyce.

6. Algorytmiczna wersja lematu lokalnego Lovasza.

7. Rozgrywana wersja lematu lokalnego Lovasza.

8. Gry na grafach, kolorowanie on-line, rozgrywana liczba chromatyczna.

9. Gry komunikacyjne.

10. Testowanie własności, lemat o regularności.

Literatura:

1. J. Beck, Combinatorial Games, Tic-Tac-Toe Theory, Cambridge University Press, 2008.

2. 2. E. Demaine, R. A. Hearn, Games, Puzzles, and Computation, A. K. Peters, 2009.

3. N. Alon, J. Spencer, The probabilistic method, 4th edition, Wiley, 2016.

Metody i kryteria oceniania:

Warunkiem zaliczenia przedmiotu jest zaliczenie projektu i zdanie egzaminu końcowego.

Zajęcia w cyklu "rok akademicki 2023/2024 - sem. letni" (w trakcie)

Okres: 2024-02-19 - 2024-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Projekt, 15 godzin, 15 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Jarosław Grytczuk, Paweł Naroski, Małgorzata Śleszyńska-Nowak
Prowadzący grup: Jarosław Grytczuk, Małgorzata Śleszyńska-Nowak
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "rok akademicki 2022/2023 - sem. letni" (zakończony)

Okres: 2023-02-20 - 2023-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Projekt, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Jarosław Grytczuk, Paweł Naroski, Małgorzata Śleszyńska-Nowak
Prowadzący grup: Jarosław Grytczuk, Paweł Naroski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "rok akademicki 2021/2022 - sem. letni" (zakończony)

Okres: 2022-02-23 - 2022-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Projekt, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Jarosław Grytczuk, Małgorzata Śleszyńska-Nowak, Michał Tuczyński
Prowadzący grup: Joanna Chybowska-Sokół, Jarosław Grytczuk, Michał Tuczyński
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "rok akademicki 2020/2021 - sem. letni" (zakończony)

Okres: 2021-02-20 - 2021-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Projekt, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Jarosław Grytczuk, Małgorzata Śleszyńska-Nowak, Michał Tuczyński
Prowadzący grup: Joanna Chybowska-Sokół, Jarosław Grytczuk, Michał Tuczyński
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. letni" (zakończony)

Okres: 2020-02-22 - 2020-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Projekt, 15 godzin, 15 miejsc więcej informacji
Wykład, 30 godzin, 45 miejsc więcej informacji
Koordynatorzy: Jarosław Grytczuk, Małgorzata Śleszyńska-Nowak, Michał Tuczyński
Prowadzący grup: Jarosław Grytczuk, Małgorzata Śleszyńska-Nowak, Michał Tuczyński
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.
pl. Politechniki 1, 00-661 Warszawa tel: (22) 234 7211 https://pw.edu.pl kontakt deklaracja dostępności USOSweb 7.0.0.0-7 (2024-03-18)