Matematyka Dyskretna: grupa 2

Zajecia odbywają się w środy, w godzinach 12.15-14.45 (z 15 minutową przerwą).

Mój dyżur: wtorek 14.00 - 16.00.

28 lutego współczynniki dwumianowe, wzór Pascala, dwumian Newtona, tożsamości współczynników dwumianowych, 12 wariantów problemu podziału: n obiektów (rozróżnialne lub nierozróżnialne), k szuflad (rozróżnialne lub nierozróżnialne) i wkładamy obiekty do szuflad (jakkolwiek lub każda szuflada ma co najwyżej 1 obiekt lub każda szuflada ma co najmniej 1 obiekt)
7 marca zasada włączeń i wyłączeń, liczby Stirlinga pierwszego i drugiego rodzaju, liczby Catalana
14 marca posety i krata Boolowska, Twierdzenie Dilwortha i dualne do niego, Lemat Erdősa-Szekeresa, Twierdzenie Spernera, podział kraty Boolowskiej na łańcuchy symetryczne, Twierdzenie Erdősa-Ko-Rado
21 marca Twierdzenie Ramsey'a, ograniczenia górne i dolne na liczby Ramsey'a
28 marca Twierdzenie Schura, Twierdzenie Erdősa-Szekeresa (dwa dowody: jeden wykorzystujący Twierdzenie Ramsey'a i drugi z kubkami i czapeczkami), Twierdzenie Van der Waerdena, Twierdzenie Halesa-Jewetta
11 kwietnia funkcje tworzące, podstawowe operacje i ich interpretacje: dodawanie, mnożenie o stałą, przesunięcie w prawo, przesunięcie w lewo podstawienie x -> cx, podstawienie x -> x^n, różniczkowanie, całkowanie i splot czyli mnożenie tworzących; Uogólnione Twierdzenie Dwumianowe, funkcja tworząca liczb Fibonacciego, rozwiązywanie równań rekurencyjnych
18 kwietnia liczby Catalana i ich interpretacje (przykłady były też na ćwiczeniach); funkcje tworzące dla podziałów liczb, zastosowania do zliczania podziałów (twierdzenie Eulera)
9 maja podstawowe definicje w teorii grafów, ograniczenie dolne na liczbę nieizomorficznych grafów na n wierzchołkach, algorytm weryfikacji czy zadany ciąg liczb jest ciągiem stopni pewnego grafu. Sieci przepływowe: Twierdzenie o maksymalnym przepływie i minimalnym przekroju
16 maja twierdzenie o 4 kolorach (bez dowodu), proste ograniczenia górne na liczbę chromatyczną (w terminach liczby krawędzi, maksymalnego stopnia), liczba kolorująca grafu i (wielomianowy) algorytm jej obliczania, twierdzenie Brooksa, konstrukcja Mycielskiego, konstrukcja Zykova
23 maja Grafy o dużej liczbie chromatycznej i małej liczbie klikowej. Konstrukcje: Mycielskiego, Zykova, Erdosa-Hajnala (shift grafy) i Tutte. Kilorowanie krawędziowe grafów: twierdzenie Koniga i twierdzenie Vizinga
30 maja grafy planarne: liczba kolorująca, liczba chromatyczna, i listowa liczba chromatyczna. Grafy przedziałowe; grafy przecięć obiektów geometrycznych na płaszczyźnie, w szczególności grafy przecięć: kwadratów i prostokątów; ograniczenia górne na liczbę chromatyczną i liczbę kolorującą tych grafów w terminach liczby klikowej
6 czerwca Twierdzenie Mantela (czyli pierwszy przypadek twierdzenia Turana), czyli o maksymalnej liczbie krawędzi w grafie na n wierzchołkach bez trójkąta, twierdzenie Turana. Macierz Tutte i dopasowanie doskonałe w grafach

Tabela aktywności
Na jednych zajęciach można dostać maksymalnie dwa plusy.
P - obecność, A - nieobecność nieusprawiedliwiona, U - nieobecność usprawiedliwiona.

Punktacja:
Razem -- sumaryczna liczba punktów za całe ćwiczenia.
Punkty -- wystawiane zgodenie ze wzorem: Razem/19 x 25 x 5/4, zaokrąglane w dół do 25 (19 to maksy7malna liczba punktów za ćwiczenia)


Student 28.II 7.III14.III21.III28.III 4.IV11.IV18.IV25.IV (K) 9.V (W)16.V23.V30.V 6.VI13.VI RazemPunkty
Bober Daniel 1 PP P APP   PAA A  11.65
Buczek Wojciech O 11 1 110.5   21.5P P  914.8
Cichosz Julia P 11 P A0.50.5   AAA A  34.93
Dyczek Jakub A 11 1 1.51.51   1.51.52 2  1423.03
Gaiński Piotr P 11.5 1.5 1.51.51.5   212 1  14.523.85
Gontarek Karolina P 11 1 11.52   21.52 0.5  13.522.20
Górski Mateusz 1 PP A P1.52   21.52 1.5  11.518.91
Helm Piotr 1 11 1.5 1.51.51.5   212 1  1524.67
Jankowski Rafał P PP P P0.51   0.5AA 1  34.93
Koprowska Katarzyna P 1P 1.5 11.5A   AAA A  58.22
Król Katarzyna P 1P 1 0.50.51.5   21.52 1.5  11.518,91
Maćkowski Mateusz P 11 P 110.5   21.51.5 1.5  1118.09
Panek Michał P 1 P 0.50.50.5   P1.51 P  58.22
Pardyl Adam 1 11 1 1.51.52   222 1.5  16.525
Pobiedziński Feliks 1 P1 0.5 APP   1.51.51.5 0.5  7.512.34
Rachek Vladyslav 1 PP 1.5 21.5P   212 1.5  12.520.56
Simajchel Przemysław 1 11.5 2 221.5   221.5 2  18.525
Szczepanek Bartosz 1 1P 1 P0.50.5   11.51.5 0.5  8.513.98
Twaróg Mikołaj A 1P 0.5 10.51   1.50.5P 0  69.87
Yevdokymov Ruslan 1 11 1.5 0.51.52   21.52 1.5  15.525
Zysiak Krzysztof 1 P  0.5 0.51.51.5   212 1  1118.09

    Pytania egzaminacyjne (literatura):
  1. Zasada włączeń i wyłączeń. Problem złośliwej sekretarki (IDM, DM)
  2. Liczby Stirlinga pierwszego rodzaju. Zależność rekurecyjna (DM)
  3. Liczby Stirlinga drugiego rodzaju. Zależność rekurencyjna (DM)
  4. Liczba ścieżek Dycka (ścieżki w gridzie nad diagonalą). Liczby Catalana -- wzór i zależność rekurencyjna
  5. Zliczanie obiektów w szufladkach -- wszystkie możliwe wersje (wykład)
  6. Twierdzenie Dilwortha i twierdzenie dualne (Wiki)
  7. Rozmiar największego antyłańcucha w kracie zbiorów. Twierdzenie Spernera i nirówność LYM (IDM)
  8. Twierdzenie Erdosa-Ko-Rado o maksymalnej rodzinie wzajemnie przecinających się k-zbiorów (Wiki)
  9. Ogólne twierdzenie Ramseya (GT - inny dowód od tego prezentowanego na wykładzie)
  10. Ograniczenia na symetryczne liczby Ramseya (przypadkek grafowy) (IDM)
  11. Twierdzenie Erdosa-Szekeresa o punktach w pozycji wypukłej -- dwa dowody (wykład)
  12. Funkcje tworzące -- rozwiązywanie rekurencji liniowych jednorodnych (DM)
  13. Funkcje tworzące -- wyznaczanej n-tej liczby Catalana (MK)
  14. Zastosowanie funkcji tworzących do zliczania podziałów liczb (w czasie O(n\sqrt{n})). Twierdzenie Eulera (DM)
  15. Algorytm weryfikacji czy dany ciąg jest ciągiem stopni wierzchołków w grafie (IDM)
  16. Sieci przepływowe - twierdzenie o maksymalnym przepływie i nimimalnym przekroju (DM)
  17. Liczba kolorująca grafu i (wielomianowy) algorytm jej obliczania (GT)
  18. Ograniczenia liczby chromatycznej w terminach maksymalnego stopnia w grafów. Twierdzenie Brooksa (GT)
  19. Grafy bez trójkątów z dużą liczbą chromatyczną: konstrukcje Mycielskiego, Zykowa, Tutte, shift-grafy (wykład)
  20. Grafy planarne: wzór Eulera, liczba kolorująca (GT, IDM)
  21. Grafy planarne: listowa liczba chromatyczna (GT)
  22. Kolorowanie krawędziowe grafów dwudzielnych. Twierdzenie Vizinga (bez dowodu) (DM,GT)
  23. Skojarzenia w grafach dwudzielnych. Twierdzenie Halla (DM, GT)
  24. Twierdzenie Turana o maksymalnej liczbie krawędzi w grafie K_{r+1}-wolnym (GT)