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

  1. Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Matematyka konkretna, PWN 2011
  2. Robin J. Wilson, Wprowadzenie do teorii grafów, PWN 2010
  3. P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2008
  4. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, 1986
  5. Wykład 13.03
    1. $\displaystyle \sum_k{l\choose m+k}{s\choose n+k}={l+s\choose l-m+n}$
    2. Permutacje, cykle, transpozycje
    3. Wektor inwersji
  6. Wykład 20.03 Liczby Stirlinga
  7. Wykład 27.03
    1. Grafy
    2. Izomorfizm grafów, grupa $\Gamma(G)$
  8. Wykład 3.04 Twierdzenie Halla
  9. Wykład 17.04 Funkcje tworzące
  10. Wykład 24.04 Liczby Catalana
  11. Wykład 8.05 Klasy kombinatoryczne, wprowadzenie
  12. Wykład 15.05 Klasy kombinatoryczne, kontynuacja
  13. Wykład 22.05 Klasy kombinatoryczne, przykłady zastosowań, klasa cykli
  14. Wykład 29.05 Ograniczone klasy kombinatoryczne, funkcje tworzące dwóch zmiennych
  15. Wykład 5.06 Wykładnicze funkcje tworzace

Rozwiązania zadań

  1. Zad 16 lista 1 rozwiązanie
  2. Zad 17 lista 2 rozwiązanie
  3. Zad 10 lista 3 rozwiązanie
  4. Zad 4 lista 4 rozwiązanie
  5. Zad 11 lista 4 rozwiązanie
  6. Zad 10 lista 5 rozwiązanie
  7. 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ń:

  1. Symbol Newtona
  2. Liczby Stierlinga I i II rodzaju
  3. Grafy
  4. Funkcje tworzące
  5. 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:
PunktyOcena
0-9,52,0
10-12,53,0
13-16,53,5
17-20,54,0
21-24,54,5
25-27,55,0
28-305,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ę.
PunktyOcena
0-11 0-92,0
12-14 10-113,0
15-16 12-133,5
17-19 14-154,0
20-21 16-174,5
22-24 18-195,0
205,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ł

  1. Zasada Indukcji Matematycznej
    1. Zbiory skończone, podstawowe tożsamości
    2. Zasada Włączeń i Wyłączeń
    3. Klasyczna definicja prawdopodobieństwa
  2. Współczynniki dwumianowe Newtona
    1. $\displaystyle {n\choose k}=\left|\left[\{1,2,\ldots,n\}\right]^k\right|$
    2. $\displaystyle r^{\underline{k}}=\prod_{i=0}^{k-1}(r-i),\qquad r^{\overline{k}}=\prod_{i=0}^{k-1}(r+i)$
    3. Dla liczby rzeczywistej $r$ oraz całkowitej dodatniej $k$ definiujemy $\displaystyle{r\choose k}=\frac{r^{\underline{k}}}{k!}$
    4. $\displaystyle {r\choose k}={r-1\choose k}+{r-1\choose k-1}$
    5. Negowanie górnego indeksu $\displaystyle {r\choose k}=(-1)^k{k-r-1\choose k}$
    6. $\displaystyle (x+y)^n=\sum_k{n\choose k}x^ky^{n-k}$
    7. $\displaystyle (x+y)^r=\sum_k{r\choose k}x^ky^{r-k}$ dla $\displaystyle\left|\frac{x}{y}\right|<1$
    8. Tożsamość Cauchy'ego $\displaystyle {n+m\choose k}=\sum_j{n\choose j}{m\choose k-j}$
    9. Tożsamość Cauchy'ego w ogólnej postaci $\displaystyle {r+s\choose k}=\sum_j{r\choose j}{s\choose k-j}$
    10. $\displaystyle \sum_k{l\choose m+k}{s\choose n+k}={l+s\choose l-m+n}$
  3. Permutacje
    1. Grupa $S_n$, permutacja odwrotna, mnożenie (składanie) permutacji
    2. Rozkład permutacji na cykle
    3. Rozkład permutacji na transpozycje, transpozycje liczb sąsiednich
    4. Wektor inwersji
    5. Znak permutacji $sgn(\sigma )$
    6. $sgn(\sigma\tau)=sgn(\sigma )sgn (\tau )$
      1. dowód "obrazkowy"
      2. dowód indukcyjny opatry na lemacie $sgn(\sigma\tau)=-sgn (\tau )=sgn(\tau\sigma)$ dla $\sigma=(j,j+1)$
    7. Grupa alternująca $A_n=\{\sigma\in S_n:\ sgn(\sigma)=1\}$
    8. $A_n\vartriangleleft S_n$
  4. Liczby Stirlinga
    1. Liczby pierwszego rodzaju (cykliczne) $\genfrac{[}{]}{0pt}{}{n}{k}$
    2. $\genfrac{[}{]}{0pt}{}{n}{1}=(n-1)!$ dla $n>0$
    3. $\genfrac{[}{]}{0pt}{}{n}{n}=1,\ \genfrac{[}{]}{0pt}{}{n}{n-1}={n\choose 2}$
    4. $\genfrac{[}{]}{0pt}{}{n}{k}=\genfrac{[}{]}{0pt}{}{n-1}{k-1}+(n-1)\genfrac{[}{]}{0pt}{}{n-1}{k}$
    5. Liczby drugiego rodzaju (partycyjne) $\genfrac{\{}{\}}{0pt}{}{n}{k}$
    6. $\genfrac{\{}{\}}{0pt}{}{n}{1}=1$ dla $n>0$
    7. $\genfrac{\{}{\}}{0pt}{}{n}{n}=1,\ \genfrac{\{}{\}}{0pt}{}{n}{n-1}={n\choose 2}$
    8. $\genfrac{\{}{\}}{0pt}{}{n}{k}=\genfrac{\{}{\}}{0pt}{}{n-1}{k-1}+k\genfrac{\{}{\}}{0pt}{}{n-1}{k}$
    9. $x^n=\sum_k\genfrac{\{}{\}}{0pt}{}{n}{k}x^{\underline{k}}$
    10. $x^{\overline{n}}=\sum_k\genfrac{[}{]}{0pt}{}{n}{k}x^k$
    11. Liczby Bella $B_n=\sum_k\genfrac{\{}{\}}{0pt}{}{n}{k}$
  5. Grafy
    1. Grafy proste
    2. Przykłady: $K_n,\ L_n,\ C_n,\ K_{n,m}$
    3. Grafy spójne, cykle w grafach
    4. Drzewa
    5. Grafy dwudzielne
    6. Stopień wierzchołka, $\sum_{v\in V}deg_G(v)=2|E|$
    7. Twierdzenie Halla
  6. Funkcje tworzące
    1. Ciąg Fibonacciego
    2. Worek monet, różniczkowanie i całkowanie funkcji tworzących
    3. Ukorzenione drzewa binarne, liczby Catalana $C_n=\frac{1}{n+1}{2n\choose n}$
    4. Liczby Catalana, więcej przykładów
  7. Klasy kombinatoryczne
    1. Klasa kombinatoryczna $(\mathcal A, |\cdot |)$, $|\cdot|:\mathcal A\to\mathbb{N}$
    2. $\mathcal A_n=\{a\in \mathcal A:\ |a|=n\}$, $a_n=|\mathcal A_n|$
    3. Funkcja tworząca klasy kombinatorycznej $A(x)=\displaystyle\sum_{n=0}^\infty a_nx^n$
    4. Przykłady $\mathcal E,\ Z$
    5. Suma $\mathcal A +\mathcal B$ oraz produkt $\mathcal A\times \mathcal B$ klas kombinatorycznych
    6. Jeśli $\mathcal C= \mathcal A +\mathcal B$, to $C(x)=A(x)+B(x)$
    7. Jeśli $\mathcal D=\mathcal A\times \mathcal B$, to $D(x)=A(x)B(x)$
    8. Klasa kombinatoryczna $\mathcal Seq(\mathcal A)$
    9. Jeśli $\mathcal B=\mathcal Seq(\mathcal A)$, to $\displaystyle B(x)=\frac{1}{1-A(x)}$
    10. Podklasa
    11. Tworzenie klas kombinatorycznych z wykorzystaniem relacji równoważności
    12. Klasa kombinatoryczna $\mathcal Pset(\mathcal A)$ oraz $\mathcal Cycle(\mathcal A)$
    13. 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)$
    14. Analiza przypadku $a_0\neq 0$ w konstrukcji klasy $\mathcal Pset(\mathcal A)$ oraz jej funkcji tworzącej
    15. Klasa kombinatoryczna $\mathcal Mset(\mathcal A)$ (o ile $\mathcal A_0=\emptyset$)
    16. 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)$
    17. 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)$
    18. Podstawowe własności funkcji Eulera $\varphi$
    19. Pomocnicza klasa $\Delta(\mathcal A)=\{(a,a):\ a\in\mathcal A\}$
    20. 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)$
    21. Ograniczone klasy kombinatoryczne $\mathcal Pset_k(\mathcal A),\ \mathcal Mset_k(\mathcal A)$
    22. Jeśli $\mathcal B=\mathcal Pset_2(\mathcal A)$, to $\displaystyle B(x)=\frac{1}{2}(A(x)^2-A(x^2))$
    23. Jeśli $\mathcal B=\mathcal Mset_2(\mathcal A)$, to $\displaystyle B(x)=\frac{1}{2}(A(x)^2+A(x^2))$
    24. Funkcje tworzące dwóch zmiennych
      1. Jeśli $\mathcal B=\mathcal Seq(\mathcal A)$, to $\displaystyle B(x,y)=\frac{1}{1-yA(x)}$
      2. 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)$
      3. 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)$
  8. Wykładnicze funkcje tworzące
    1. Dla ciągu $(a_n)_{n\in\mathbb{N}}$ definiujemy $\hat{A}(x)=\displaystyle \sum_n\frac{a_n}{n!}x^n$
    2. Dwumianowy splot i iloczyn wykładniczych funkcji tworzących
    3. Liczby Bella $B_n$ oraz zależność $\hat{B}'(x)=e^x\hat{B}(x)$
    4. $\hat{B}(x)=e^{e^x-1}$
    5. Wzór Dobińskiego $B_n=\displaystyle \frac{1}{e}\sum_{k=0}^\infty\frac{k^n}{k!}$

Powrót