Powrót
Matematyka dyskretna (2019/2020)
Wykład odbywa się w piątki w godz. 9:15 - 11:00 w sali 1.30/C-13.
Przeznaczony jest dla
studentów studiów pierwszego stopnia Informatyki WPPT PWr.
Literatura
- Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Matematyka konkretna, PWN 2011
- Robin J. Wilson, Wprowadzenie do teorii grafów, PWN 2010
- P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2008
- W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, 1986
- Wykład 13.03
- $\displaystyle \sum_k{l\choose m+k}{s\choose n+k}={l+s\choose l-m+n}$
- Permutacje, cykle, transpozycje
- Wektor inwersji
- Wykład 20.03 Liczby Stirlinga
- Wykład 27.03
- Grafy
- Izomorfizm grafów, grupa $\Gamma(G)$
- Wykład 3.04 Twierdzenie Halla
- Wykład 17.04 Funkcje tworzące
- Wykład 24.04 Liczby Catalana
- Wykład 8.05 Klasy kombinatoryczne, wprowadzenie
- Wykład 15.05 Klasy kombinatoryczne, kontynuacja
- Wykład 22.05 Klasy kombinatoryczne, przykłady zastosowań, klasa cykli
- Wykład 29.05 Ograniczone klasy kombinatoryczne, funkcje tworzące dwóch zmiennych
- Wykład 5.06 Wykładnicze funkcje tworzace
Rozwiązania zadań
- Zad 16 lista 1 rozwiązanie
- Zad 17 lista 2 rozwiązanie
- Zad 10 lista 3 rozwiązanie
- Zad 4 lista 4 rozwiązanie
- Zad 11 lista 4 rozwiązanie
- Zad 10 lista 5 rozwiązanie
- Zad 11 lista 5 rozwiązanie
Zaliczenie kursu
12 czerwca o godz. 9:15 (czyli w czasie wykładu) będzie sprawdzenie wiedzy. Odbędzie się w trybie online (każdy z prowadzących ćwiczenia przeprowadzi sprawdzenie dla swojej grupy ćwiczeniowej; osoby nie zapisane do żadnej z grup powinny skontaktować się z wykładowcą, będą wtedy pisały w jego grupie).
Zadania będą przekazane za pomocą e-mail lub strony internetowej prowadzącego (szczegóły ustala prowadzący ćwiczenia). Będzie 5 zadań z następujących zagadnień:
- Symbol Newtona
- Liczby Stierlinga I i II rodzaju
- Grafy
- Funkcje tworzące
- Klasy kombinatoryczne
Czas na nadesłanie rozwiązań (w formie zdjęć lub plików pdf z odręcznie napisanymi podpisanymi rozwiązaniami) to 1h 45min.
Rozwiązania wykazujące nadmierne podobieństwo do innych nie będą akceptowane.
W przypadku wątpliwości sprawdzającego co do samodzielności/poprawności rozwiązania zostanie przeprowadzona krótka rozmowa (przy użyciu zoom lub microsoft teams w terminie ustalonym ze studentem) w celu weryfikacji oceny.
Każde zadanie będzie warte 4 pkt. Razem do zdobycia 20 pkt.
Liczba punktów ze sprawdzenia wiedzy będzie odpowiednikiem liczby punktów z kolokwium (w normalnym trybie).
Ponadto sprawdzenie wiedzy będzie stanowiło (zerowy) termin egzaminu. Zmodyfikowana punktacja poniżej.
Ćwiczenia
Na ćwiczeniach będzie kolokwium. Będzie można zdobyć 20 pkt.
Będzie można zdobywać punkty za aktywność (jeden plus to pół punktu). Maksymalnie z aktywności można otrzymać 10 punktów. Suma punktów zdobytych na kolokwiach i z aktywności stanowi podstawę oceny z ćwiczeń według załączonej tabelki:
Punkty | Ocena |
0-9,5 | 2,0 |
10-12,5 | 3,0 |
13-16,5 | 3,5 |
17-20,5 | 4,0 |
21-24,5 | 4,5 |
25-27,5 | 5,0 |
28-30 | 5,5 |
Egzamin
Egzamin podstawowy odbędzie się 22.06.2020 w salach 322/A-1 oraz 314/A-1 o godz. 13:00 w trybie online.
Na egzamin należy przynieść legitymację studencką, coś do pisania i coś do pisania na (tzn. 6 pojedynczych kartek A4, każde zadanie będzie na osobnej kartce).
Na egzaminie będzie 6 zadań. Każde punktowane po 4 punkty. Suma punktów zdobytych za zadania stanowi podstawę oceny z egzaminu według załączonej tabelki:
Sposób przeprowadzenia egzaminu będzie analogiczny jak sprawdzenia wiedzy. Zadania zostaną przekazane studentom przez wykładowcę.
Punkty | Ocena |
0-11 0-9 | 2,0 |
12-14 10-11 | 3,0 |
15-16 12-13 | 3,5 |
17-19 14-15 | 4,0 |
20-21 16-17 | 4,5 |
22-24 18-19 | 5,0 |
20 | 5,5 |
Egzamin poprawkowy odbędzie się 29.06.2020 w sali 314/A-1 o godz. 13:00 w trybie online.
Ocena końcowa
Ocena z grupy kursów będzie wyznaczona według następującego wzoru
pod warunkiem
uzyskania pozytywnej oceny z egzaminu $$\displaystyle\max\left\{\frac{E+C}{2},E\right\},$$ gdzie $C$ jest oceną
otrzymaną z ćwiczeń, a $E$ - oceną z egzamniu.
Aby otrzymać ocenę celującą (5,5) trzeba otrzymać ocenę 5,5 z powyższego wzoru lub ocenę 5,0 z powyższego wzoru
i zdać egzamin ustny.
Zrealizowany materiał
- Zasada Indukcji Matematycznej
- Zbiory skończone, podstawowe tożsamości
- Zasada Włączeń i Wyłączeń
- Klasyczna definicja prawdopodobieństwa
- Współczynniki dwumianowe Newtona
- $\displaystyle {n\choose k}=\left|\left[\{1,2,\ldots,n\}\right]^k\right|$
- $\displaystyle r^{\underline{k}}=\prod_{i=0}^{k-1}(r-i),\qquad r^{\overline{k}}=\prod_{i=0}^{k-1}(r+i)$
- Dla liczby rzeczywistej $r$ oraz całkowitej dodatniej $k$ definiujemy $\displaystyle{r\choose k}=\frac{r^{\underline{k}}}{k!}$
- $\displaystyle {r\choose k}={r-1\choose k}+{r-1\choose k-1}$
- Negowanie górnego indeksu $\displaystyle {r\choose k}=(-1)^k{k-r-1\choose k}$
- $\displaystyle (x+y)^n=\sum_k{n\choose k}x^ky^{n-k}$
- $\displaystyle (x+y)^r=\sum_k{r\choose k}x^ky^{r-k}$ dla $\displaystyle\left|\frac{x}{y}\right|<1$
- Tożsamość Cauchy'ego $\displaystyle {n+m\choose k}=\sum_j{n\choose j}{m\choose k-j}$
- Tożsamość Cauchy'ego w ogólnej postaci $\displaystyle {r+s\choose k}=\sum_j{r\choose j}{s\choose k-j}$
- $\displaystyle \sum_k{l\choose m+k}{s\choose n+k}={l+s\choose l-m+n}$
- Permutacje
- Grupa $S_n$, permutacja odwrotna, mnożenie (składanie) permutacji
- Rozkład permutacji na cykle
- Rozkład permutacji na transpozycje, transpozycje liczb sąsiednich
- Wektor inwersji
- Znak permutacji $sgn(\sigma )$
- $sgn(\sigma\tau)=sgn(\sigma )sgn (\tau )$
- dowód "obrazkowy"
- dowód indukcyjny opatry na lemacie $sgn(\sigma\tau)=-sgn (\tau )=sgn(\tau\sigma)$ dla $\sigma=(j,j+1)$
- Grupa alternująca $A_n=\{\sigma\in S_n:\ sgn(\sigma)=1\}$
- $A_n\vartriangleleft S_n$
- Liczby Stirlinga
- Liczby pierwszego rodzaju (cykliczne) $\genfrac{[}{]}{0pt}{}{n}{k}$
- $\genfrac{[}{]}{0pt}{}{n}{1}=(n-1)!$ dla $n>0$
- $\genfrac{[}{]}{0pt}{}{n}{n}=1,\ \genfrac{[}{]}{0pt}{}{n}{n-1}={n\choose 2}$
- $\genfrac{[}{]}{0pt}{}{n}{k}=\genfrac{[}{]}{0pt}{}{n-1}{k-1}+(n-1)\genfrac{[}{]}{0pt}{}{n-1}{k}$
- Liczby drugiego rodzaju (partycyjne) $\genfrac{\{}{\}}{0pt}{}{n}{k}$
- $\genfrac{\{}{\}}{0pt}{}{n}{1}=1$ dla $n>0$
- $\genfrac{\{}{\}}{0pt}{}{n}{n}=1,\ \genfrac{\{}{\}}{0pt}{}{n}{n-1}={n\choose 2}$
- $\genfrac{\{}{\}}{0pt}{}{n}{k}=\genfrac{\{}{\}}{0pt}{}{n-1}{k-1}+k\genfrac{\{}{\}}{0pt}{}{n-1}{k}$
- $x^n=\sum_k\genfrac{\{}{\}}{0pt}{}{n}{k}x^{\underline{k}}$
- $x^{\overline{n}}=\sum_k\genfrac{[}{]}{0pt}{}{n}{k}x^k$
- Liczby Bella $B_n=\sum_k\genfrac{\{}{\}}{0pt}{}{n}{k}$
- Grafy
- Grafy proste
- Przykłady: $K_n,\ L_n,\ C_n,\ K_{n,m}$
- Grafy spójne, cykle w grafach
- Drzewa
- Grafy dwudzielne
- Stopień wierzchołka, $\sum_{v\in V}deg_G(v)=2|E|$
- Twierdzenie Halla
- Funkcje tworzące
- Ciąg Fibonacciego
- Worek monet, różniczkowanie i całkowanie funkcji tworzących
- Ukorzenione drzewa binarne, liczby Catalana $C_n=\frac{1}{n+1}{2n\choose n}$
- Liczby Catalana, więcej przykładów
- Klasy kombinatoryczne
- Klasa kombinatoryczna $(\mathcal A, |\cdot |)$, $|\cdot|:\mathcal A\to\mathbb{N}$
- $\mathcal A_n=\{a\in \mathcal A:\ |a|=n\}$, $a_n=|\mathcal A_n|$
- Funkcja tworząca klasy kombinatorycznej $A(x)=\displaystyle\sum_{n=0}^\infty a_nx^n$
- Przykłady $\mathcal E,\ Z$
- Suma $\mathcal A +\mathcal B$ oraz produkt $\mathcal A\times \mathcal B$ klas kombinatorycznych
- Jeśli $\mathcal C= \mathcal A +\mathcal B$, to $C(x)=A(x)+B(x)$
- Jeśli $\mathcal D=\mathcal A\times \mathcal B$, to $D(x)=A(x)B(x)$
- Klasa kombinatoryczna $\mathcal Seq(\mathcal A)$
- Jeśli $\mathcal B=\mathcal Seq(\mathcal A)$, to $\displaystyle B(x)=\frac{1}{1-A(x)}$
- Podklasa
- Tworzenie klas kombinatorycznych z wykorzystaniem relacji równoważności
- Klasa kombinatoryczna $\mathcal Pset(\mathcal A)$ oraz $\mathcal Cycle(\mathcal A)$
- Jeśli $\mathcal B=\mathcal Pset(\mathcal A)$, to $\displaystyle B(x)=\prod_{k=1}^{\infty}(1+x^k)^{a_k}=exp\left(\sum_{k=1}^\infty\frac{(-1)^{k-1}}{k}A(x^k)\right)$
- Analiza przypadku $a_0\neq 0$ w konstrukcji klasy $\mathcal Pset(\mathcal A)$ oraz jej funkcji tworzącej
- Klasa kombinatoryczna $\mathcal Mset(\mathcal A)$ (o ile $\mathcal A_0=\emptyset$)
- Jeśli $\mathcal B=\mathcal Mset(\mathcal A)$, to $\displaystyle B(x)=\prod_{k=1}^{\infty}(1-x^k)^{-a_k}=exp\left(\sum_{k=1}^\infty\frac{1}{k}A(x^k)\right)$
- Jeśli $\mathcal B=\mathcal Cycle(\mathcal A)$, to $\displaystyle B(x)=\sum_{k=1}^{\infty}\frac{\varphi(k)}{k}ln\left(\frac{1}{1-A(x^k)}\right)$
- Podstawowe własności funkcji Eulera $\varphi$
- Pomocnicza klasa $\Delta(\mathcal A)=\{(a,a):\ a\in\mathcal A\}$
- Związek pomiędzy klasami $\mathcal Mset(\mathcal A)$ oraz $\mathcal Pset(\mathcal A)$ opisany równością $M(x)=P(x)M(x^2)$
- Ograniczone klasy kombinatoryczne $\mathcal Pset_k(\mathcal A),\ \mathcal Mset_k(\mathcal A)$
- Jeśli $\mathcal B=\mathcal Pset_2(\mathcal A)$, to $\displaystyle B(x)=\frac{1}{2}(A(x)^2-A(x^2))$
- Jeśli $\mathcal B=\mathcal Mset_2(\mathcal A)$, to $\displaystyle B(x)=\frac{1}{2}(A(x)^2+A(x^2))$
- Funkcje tworzące dwóch zmiennych
- Jeśli $\mathcal B=\mathcal Seq(\mathcal A)$, to $\displaystyle B(x,y)=\frac{1}{1-yA(x)}$
- Jeśli $\mathcal B=\mathcal Pset(\mathcal A)$, to $\displaystyle B(x,y)=\prod_{k=1}^{\infty}(1+yx^k)^{a_k}=exp\left(\sum_{k=1}^\infty\frac{(-1)^{k-1}}{k}y^kA(x^k)\right)$
- Jeśli $\mathcal B=\mathcal Mset(\mathcal A)$, to $\displaystyle B(x,y)=\prod_{k=1}^{\infty}(1-yx^k)^{-a_k}=exp\left(\sum_{k=1}^\infty\frac{1}{k}y^kA(x^k)\right)$
- Wykładnicze funkcje tworzące
- Dla ciągu $(a_n)_{n\in\mathbb{N}}$ definiujemy $\hat{A}(x)=\displaystyle \sum_n\frac{a_n}{n!}x^n$
- Dwumianowy splot i iloczyn wykładniczych funkcji tworzących
- Liczby Bella $B_n$ oraz zależność $\hat{B}'(x)=e^x\hat{B}(x)$
- $\hat{B}(x)=e^{e^x-1}$
- Wzór Dobińskiego $B_n=\displaystyle \frac{1}{e}\sum_{k=0}^\infty\frac{k^n}{k!}$
Powrót