Informacje dla kandydatów

Matematyka dyskretna

Stacks Image 707
Na wykładzie omawiane są najważniejsze elementy Matematyki Dyskretnej wykorzystywane w Informatyce do analizy i projektowania algorytmów.

Na zajęciach opanujesz formalne narzędzia Matematyki Dyskretnej oraz nabierzesz wprawy w posługiwaniu się podstawowymi obiektami matematyki dyskretnej:
  • zbiory skończone
  • multizbiory
  • partycje
  • permutacje
  • podziały
  • klasy kombinatoryczne
  • funkcje tworzące
  • drzewa
Stacks Image 714
Dowiesz się na przykład, jak policzyć liczbę możliwych triangulacji wielokąta, liczbę drzew binarnych i liczbę sposobów rozstawienia nawiasów.
Zostanie wyprowadzony wzór na \(n\)-ty wyraz ciągu Catalana:

$$C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)! n!} = \prod_{k=2}^n \frac{n+k}{k},\; \mbox{dla \(n \ge 0\)},$$

który jest równy liczbie triangulacji wielokąta o \(n+2\) bokach, ale również równy liczbie drzew binarnych o \(n+1\) liściach a nawet równy liczbie możliwych rozstawień nawiasów grupujących \(n+1\) czynników.

Dodatkowe materiały

Katedra Informatyki
Politechnika Wrocławska
Wydział Podstawowych Problemów Techniki