Matematyka dyskretna, semestr letni 2020/2021

Wykłady
Nagrania kolejnych wykładów dostępne są na platformie Ms Teams. Konsultacje w sprawie wykładu, i nie tylko, prowadzone będą również przez platformę Ms Teams, we czwartki o godzinie 9.15.

Ćwiczenia
Tomasz Krawczyk środy 10.30 - 12.45 na platformie Ms Teams
Tomasz Krawczyk środy 13.00 - 15:15 na platformie Ms Teams


Zestawy zadań
Deklarację rozwiązanych zadań przesyłamy na adres: dydaktyka.tkrawczy@gmail.com. Deklaracja każdego zestawu powinna składać się z numerów rozwiązanych zadań oraz sumarycznej liczby punktów (z przedziału 0-4) za rozwiązania. Progi dla zestawów będą przesyłane w momencie opublikowania zestawu przez USOS. Brak deklaracji oznacza 0 punktów; za deklarację uważa się ostatni mail przesłany przed terminem deklaracji zestawu. Każdy student na ćwiczeniach poświęconych zestawowi ma mieć możliwość przedstawienia swojego rozwiązania (z puli zadeklarowanych rozwiązań) na platformie MS Teams. Brak obecności na zajęciach oznacza 0 punktów za zestaw (brak możliwości weryfikacji rozwiązań).

Zestawy
Indukcja i Zasada Szufladkowa [pdf] termin deklaracji: 2 marzec godz. 20.00
Zliczanie i współczynniki dwumianowe [pdf] termin deklaracji: 9 marzec, godz. 20.00
Zliczanie, liczby Stirlinga i liczby Catalana [pdf] termin deklaracji: 16 marzec, godz. 20.00
Posety i zbiory [pdf] termin deklaracji: 23 marzec, godz. 20.00
Twierdzenia Ramseyowe [pdf] termin deklaracji: 30 marzec, godz. 20.00
Funkcje tworzące I [pdf] termin deklaracji: 13 kwiecień, godz. 20.00
Funkcje tworzące II [pdf] termin deklaracji: 20 kwietnia, godz. 20.00
Grafy: drzewa, ścieżki, cykle, stopnie wierzchołków [pdf] termin deklaracji: 27 kwietnia, godz. 20.00
Przepływy i spójność grafów [pdf] termin deklaracji: 4 maj, godz. 20.00
Grafy: kolorowanie 1 [pdf] termin deklaracji: 11 maj, godz. 20.00
Grafy: kolorowanie 2 [pdf] temin deklaracji: 18 maj, godz. 20.00
Grafy planarne, grafy przecięć [pdf] termin deklaracji: 25 maj, godz. 20.00
Grafy: Zadania różne [pdf] termin deklaracji: 1 czerwiec, godz. 20.00
Przykładowe kolokwium z grafów [pdf]
Kolokwia z lat ubiegłych [kol1.pdf] [kol2.pdf] [kol3.pdf] [kol4.pdf]


Wykłady
25 lutego współczynniki dwumianowe, wzór Pascala, dwumian Newtona, tożsamości współczynników dwumianowych, liczby Stirlinga, podziały liczby
4 marca 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), liczby Catalana, zasada włączeń i wyłączeń, zliczanie cykli Hamiltona w grafie, problem istnienia drzewa Steinera
11 marca posety i krata Boolowska, Twierdzenie Dilwortha i dualne do niego, Lemat Erdősa-Szekeresa
18 marca posety i krata zabiorów, lemat Spernera (nierówność LYM), Twierdzenie Erdősa-Ko-Rado: [slajdy]
Komentarz i zdjęcia: [mp3] [rys1] [rys2] [rys3] [rys4] [rys5] [rys6]
25 marca Twierdzenie Ramsey'a, ograniczenia górne i dolne na liczby Ramsey'a, Twierdzenie Schura, Twierdzenie Erdősa-Szekeresa (dwa dowody: jeden wykorzystujący Twierdzenie Ramsey'a i drugi z kubkami i czapeczkami): [slajdy]
1 kwietnia funkcje tworzące, podstawowe operacje i ich interpretacje: dodawanie, mnożenie o stałą, przesunięcie w prawo, przesunięcie w lewo, różniczkowanie i splot czyli mnożenie tworzących; funkcja tworząca liczb Fibonacciego, rozwiązywanie równań rekurencyjnych, funkcja tworząca liczb Catalana. [slajdy]
Filmy: [part1_short.mp4] [part2_short.mp4] [part3_short.mp4] [part4_short.mp4] [part5_short.mp4] [part6_short.mp4]
8 kwietnia zastosowanie funkcji tworzących do zlicznania podziałów liczb [slajdy]
[part1_short.mp4] [part2_short.mp4] [part3_short.mp4] [part4_short.mp4] [part5_short.mp4] [part6_short.mp4] [part7_short.mp4]
15 kwietnia 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 [slajdy]
24 kwietnia przepływy w sieciach, spójność grafów [slajdy]
[part1_short.mp4] [part2_short.mp4] [part3_short.mp4]
29 kwietnia 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, shift grafy, konstrukcja Tutte'a.
Filmy: [part1_short.mp4] [part2_short.mp4] [part3_short.mp4] [part4_short.mp4] [part5_short.mp4] [part6_short.mp4]
7 maj kolorowania krawędziowe grafów, twierdzenie Vizinga
Filmy: [part1_short.mp4] [part2_short.mp4]
12 maja dopasowania doskonałe w grafach -- twierdzenie Halla, twierdzenie Tutte'a
Filmy: [part1_short.mp4] [part2_short.mp4] [part3_short.mp4] [part4_short.mp4]
19 maja grafy przecięć obiektów geometrycznych na płaszczyźnie, w szczególności grafy przecięć: przedziałów na prostej, kwadratów, prostokątów i odcinków na płaszczyźnie; ograniczenia górne na liczbę chromatyczną tych grafów w terminach liczby klikowej
Filmy: [part1_short.mp4] [part2_short.mp4] [part3_short.mp4]
19 maja grafy planarne - wzór Eulera, liczba kolorująca, liczba chromatyczna (dowód 5-kolorowalności)
Filmy: [part1_short.mp4]
28 maja twierdzenie Mantela, twierdzenie Turana
Filmy: [part1_short.mp4]


Reguły
Za każdy zestaw zadań można zdobyć 4 punkty. Wszystkich zestawów zadań będzie około 13, więc sumarycznie zdobyć będzie można około 52 punktów. Oceny z ćwiczeń wystawiane będą względem następujących progów: Egzamin odbędzie się w sesji letniej i będzie składał się z części zadaniowej (kilka zadań do rozwiązania, w tym zadania z zestawów) oraz części teoretycznej (zagadnienia z wykładu). Do egzaminu mogą przystąpić studenci którzy otrzymali ocenę co najmniej 3,0 z ćwiczeń. Warunkiem przystąpienia do części teoretycznej egzaminu jest zaliczenie części zadaniowej. Egzamin z części zadaniowej będzie przeprowadzony w budynku wydziału (gdyby sytuacja epidemiczna na to nie pozwalała, prowadzący dopuszcza możliwość anulowania tej części egzaminu). Wynikiem egzaminu jest ocena z przedziału 2.0-5.0. Ocena końcowa będzie wystawiana według następującego wzoru: Studenci, którzy otrzymali ocenę 2,0 z ćwiczeń mogą zaliczyć kurs w drugim terminie (we wrześniu): (1) zdając kolokwium poprawkowe, (2) zdając egzamin poprawkowy. Studenci, którzy otrzymali co najmniej ocenę 3,0 z ćwiczeń ale 2,0 z egzaminu mogą zaliczyć kurs w drugim terminie zdając egzamin poprawkowy.

Literatura
Tematy egzaminacyjne