Matematyka dyskretna to dział matematyki zajmujący się strukturami przeliczalnymi, czyli nieciągłymi, czy po prostu dyskretnymi. Obiektem badań są np. liczby całkowite (teoria liczb), zbiory, częściowe porządki, grafy, kombinatoryczne gry. Ważnym tematem jest zliczanie obiektów. Czasami wiązać się to będzie z rozwiązaniem układu równań czy rekurencyjnej zależności. Rozważając grafy będziemy próbować zrozumieć ich strukturę i związki pomiędzy najważniejszymi parametrami. Szczególnie wdzięcznym tematem tu są kolorowania grafów.

• aktywność [pdf] (aktualizacja: 7.III)

• na każdym z dwu kolokwiów można zdobyć 40 punktów
• za rozwiązywanie zadań domowych można zdobyć 20 punktów
• za pisemne rozwiązanie wyróżnionych zadań domowych będzie można dostać do 10 punktów bonusowych

Zestawy zadań będą publikowane co siedem dni (z przerwami na święta lub kolokwia). Liczba zestawów będzie równa $Z$, gdzie $Z\in\{10,11,12\}$. Studenci przy pomocy elektronicznego formularza będą deklarować rozwiązania zadań z bieżącego zestawu. Deklaracja rozwiązania równoważna jest gotowości prezentacji rozwiązania przy tablicy. Prezentacja zadania co do zasady ma być bez pomocy (notatek). Oczywiście w sytuacji gdy zadanie jest bardzo rachunkowe będziemy robić wyjątki, jednak student(ka) ma rozumieć rozwiązanie bez notatek. Za deklarację bez pokrycia będą negatywne konsekwencje: zerowanie punktów za zestaw, ujemne punkty, itp. Za rozwiązanie zadań pojedynczego zestawu będzie można uzyskać co najwyżej $X=\frac{20}{Z}$ punktów. Jeśli zestaw zawiera $N$ zadań, a student zadeklarował $M$ zadań, to student uzyskuje $\min(\frac{M}{0.9\cdot N},1)\cdot X$ punktów za zestaw. Deklaracje będą zbierane jedynie od studentów obecnych na zajęciach. Poza tym obecność nie będzie mieć wpływu na ocenę.

Rozwiązania wyróżnionych zadań domowych nie będą podlegać systemowi deklaracji i będą mogły być spisywane w grupach co najwyżej dwuosobowych (dwie osoby mogą być co najwyżej raz razem w grupie; studenci z różnych grup ćwiczeniowych mogą stworzyć grupę). Rozwiązania będą akceptowane jedynie w formacie pdf, który został wygenerowany przez kompilator Latexa. Rozwiązanie pisemne zadania będzie przyjmowane do terminu podanego w zestawiem. Rozwiązanie należy wysyłać na adres matematyka.dyskretna.tcs@gmail.com. Wysłanie rozwiązania równoważne jest gotowości prezentacji rozwiązania przy tablicy. Prowadzący mogą też prosić autorów rozwiązania o indywidualne rozmowy (po zajęciach) weryfikujące poprawność i samodzielność rozwiązania. Za każde poprawnie rozwiązane zadanie wyróżnione student otrzymuje $1$ punkt bonusowy.

Kodeks honorowy: Zabronione jest wyszukiwanie w sieci treści zadania wyróżnionego czy jego rozwiązania oraz konsultowanie rozwiązań poza grupą podpisaną pod rozwiązaniem. Dozwolone jest korzystanie z książek i materiałów z sieci; jeśli student rozwiązał zadanie dzięki znalezieniu go, lub bardzo podobnego, w materiałach to należy podać referencje do tych materiałów. Każda wysłana pisemna praca ma zawierać oświadczenie autorów o zachowaniu powyższych wytycznych. Poza grupami sformowanymi do konkretnych zestawów dyskusje na temat zadań i ich rozwiązań są dozwolone jedynie na forum.tcs oraz poprzez email z prowadzącym zajęcia.

• 5,0 -- (90,100]
• 4,5 -- (80,90]
• 4,0 -- (70,80]
• 3,5 -- (60,70]
• 3,0 -- (50,60]
• 2,0 -- (25,50]
• NZAL -- [0,25]

• 28.II, podstawowe regułu zliczania, współczynniki dwumianowe--liczba podzbiorów, liczba multi-podzbiorów, wzór Pascala, 12 wariantów wkładania obiektów do szuflad, liczby Stirlina drugiego rodzaju
• 29.II, liczby Stirlinga pierwszego rodzaju, podział liczby, liczby Catalana: nieparzyste słowa Dycka, wyprowadzenie zwartego wzoru
• 6.III, liczby Catalan: przegląd rodzin obiektów zliczanych przez liczby Catalana; podstawy teorii liczb
• 20.III, funkcje tworzące
• 5.IV, podziały liczb (nagranie, 39', [mkv])
• 7.IV, posety: twierdzenie dualne do twierdzenia Dilwortha, lemat Erdosa-Szekeresa, twierdzenie Dilwortha, twierdzenie Spernera, nierówność LYM, podział kraty boolowskiej na symetryczne łańcuchy: konstrukcja rekurencyjna i konstrukcja wprost przez nawiasowanie, liczby Dedekinda i ich ograniczenie górne (nagranie, 80', [mp4])
• 10.IV, cienie rodzin w kracie boolowskiej, orginalny dowód twierdzenia Spernera, przecinające rodziny zbiorów, jak duża może być rodzina przecinająca w kracie boolowskiej rzędu n, jak duża może być rodzina przecinająca składająca się z k-elementowych podzbiorów zbioru [n], twierdzenie Erdosa-Ko-Rado, jak mały może być cień dolny rodziny k-elementowych podzbiorów zbioru [n], k-kaskadowa reprezentacja liczb naturalnych, twierdzenie Kruskala-Katony (dowód za notatkami Shagnika: [pdf]), twierdzenie Lovasza, technika przesuwania
• 17.IV, twierdzenie Ramsey'a, liczby Ramsey'a, ograniczenie dolne i górne na symetryczne liczby Ramsey'a (dla 2-kolorowań), twierdzenie Erdosa-Szekeresa dla R(s,t)
• 24.IV, twierdzenie Schura, twierdzenie Erdosa-Szekersa (dwa dowody), twierdzenie Halesa-Jewetta, twierdzenie van der Waerdena (dowód tw. Halesa-Jewetta notowałem z następujących źródeł: [pdf], [pdf])

• 7.III, Zasada szufladkowa, ciąg Fibonacciego, współczynniki dwumianowe [pdf]
• 14.III, Liczby Stirlinga, zasada włączeń i wyłączeń, liczby Bella, liczby Eulera [pdf]
• 21.III, Liczby Catalana [pdf]
• 27.III, Teoria liczb [pdf]
• 4.IV, Funkcje tworzące I [pdf]
• 11.IV, Funkcje tworzące II [pdf]
• 25.IV, Posety i zbiory [pdf]