Matematyka dyskretna 1000-134MAD
1. Podstawowe prawa i metody zliczania: prawa dodawania i mnożenia, zasada bijekcji, zasada szufladkowa. Współczynniki dwumianowe, dowody kombinatoryczne.
2. Zasada włączania i wyłączania, zliczanie funkcji „na” i nieporządków, problem małżeństw Lucasa.
3. Zliczanie podziałów, liczby Stirlinga II rodzaju, liczby Bella.
4. Zliczanie permutacji, liczby Stirlinga I rodzaju.
5. Rozmieszczenia kul w urnach.
6. Zależności rekurencyjne i funkcje tworzące, liczby Fibonacciego, Catalana i Bella, rozwiązywanie rekurencji liniowych ze stałymi współczynnikami.
7. Zliczanie orbit grup przekształceń: lemat Burnside’a, twierdzenie Polyi o liczbie istotnie różnych, ze względu na ustaloną grupę przekształceń, kolorowań danego zbioru obiektów.
8. Podstawowe pojęcia teorii grafów. Cykle Eulera, grafy eulerowskie i twierdzenie Eulera o ich charakteryzacji, cykle Hamiltona, grafy hamiltonowskie i twierdzenie Orego.
9. Drzewa: charakteryzacje i zliczanie drzew, twierdzenie Cayleya.
10. Grafy planarne i płaskie, twierdzenie Kuratowskiego (bez dowodu), wzór Eulera, kolorowanie wierzchołkowe grafów, twierdzenie o 5 barwach.
11. Skojarzenia w grafach: twierdzenie Halla i jego zastosowania.
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
Student:
1. Zna podstawowe prawa i metody zliczania, potrafi przeprowadzać kombinatoryczne dowody tożsamości dwumianowych.
2. Zna rozmaite szczególne liczby występujące w kombinatoryce (współczynniki dwumianowe, liczby Stirlinga, Bella, Fibonacciego i Catalana), ich kombinatoryczne interpretacje oraz własności.
3. Zna zasadę włączania i wyłączania i potrafi ją zastosować w zagadnieniach zliczania różnych obiektów kombinatorycznych.
4. Zna pojęcie funkcji tworzącej ciągu liczbowego; zna przykłady zastosowań aparatu funkcji tworzących do znajdowania wzoru ogólnego na n-ty wyraz ciągu,
5. Zna pojęcie zależności rekurencyjnej i umie je wykorzystać jako narzędzie kombinatoryczne; potrafi rozwiązywać rekurencje liniowe ze stałymi współczynnikami.
6. Zna lemat Burnside’a; potrafi znaleźć liczbę istotnie różnych, ze względu na ustaloną grupę przekształceń, kolorowań danego zbioru obiektów.
7. Zna podstawowe pojęcia teorii grafów i potrafi je zilustrować przykładami.
8. Zna twierdzenie Eulera o charakteryzacji grafów eulerowskich oraz twierdzenie Orego o grafach hamiltonowskich.
9. Zna twierdzenie Cayleya i umie znaleźć liczbę drzew o danym zbiorze wierzchołków.
10. Zna wzór Eulera i potrafi go zastosować do znajdowania ilościowych zależności w grafach planarnych.
11. Zna twierdzenie Halla i przykłady jego zastosowania.
Kryteria oceniania
Egzamin pisemny, ewentualnie dodatkowo egzamin ustny.
Literatura
1. V. Bryant, Aspekty kombinatoryki, WNT, Warszawa 2007.
2. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa 1986.
3. Z. Palka, A. Ruciński, Wykłady z kombinatoryki, WNT, Warszawa 1998.
4. R. J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 1998.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: