MATEMATYKA
DYSKRETNA
dla kierunku
Informatyka na Wydziale EITI
- Prawa i metody przeliczania, zasada dodawania,
zasada mnożenia, zasada bijekcji, współczynniki dwumianowe i wielomianowe,
przykłady zastosowań.
- Wzór na liczbę drzew o
zadanych stopniach wierzchołków, dowód.
- Twierdzenie Cayleya,
dowód, kod Prufera.
- Działania grup, wzór na
liczbę elementów orbity, dowód.
- Grafy izomorficzne, wzór
na liczbę grafów izomorficznych.
- Twierdzenie Halla,
dowód, rożne wersje.
- Uogólnione twierdzenie
Halla ( o panach, których chcemy ożenić), dowód.
- Zasada szufladkowa, twierdzenie o liczbie wyrazów
maksymalnego podciągu rosnącego lub malejącego ciągu skończonego - dowód, inne
przykłady zastosowań.
- Zasada dwoistości,
warunek konieczny i wystarczający na dwudzielnośc grafu - dowód, inne
przykłady zastosowań.
- Zasada
włączania/wyłączania, dowód, przykład zastosowania: liczba nieporządków.
- Zastosowania zasady
włączania/wyłączania: funkcja Eulera, liczba surjekcji.
- Uogólniona zasada
włączania/wyłączania, dowód, przykład zastosowania: liczba permutacji o r punktach stałych
- Graf hamiltonowski,
warunek wystarczający, dowód.
- Graf eulerowski, dowód
warunku koniecznego i wystarczającego, graf semi-eulerowski.
- Równania rekurencyjne i funkcje tworzące, przykłady:
liczba permutacji, liczba transwersal,
liczby Bella, nieporządki.
- Równania rekurencyjne i funkcje tworzące, przykłady:
proste na płaszczyżnie, wieża Hanoi, liczba podzbiorów bez sąsiadów,
kolejnośc mnożenia.
- Metoda przewidywań rozwiązania równoń rekurencyjnych, liczby Fibonacciego i
przykłady rozwiązania równań niejednorodnych
- Kolorowanie
wierzchołków, Twierdzenie Brooksa, dowód.
- Kolorowanie krawędzi,
twierdzenie o kolorowaniu krawędzi grafu o nieparzystej liczbie
wierzchołków i stałych stopniach wierzchołków, dowód.
- Kolorowanie krawędzi
grafu pełnego, dowód.
- Twierdzenie Koniga o
kolorowaniu krawędzi grafu dwudzielnego, dowód
- Twierdzenie Vizinga,
dowód.
- Prostokąty i kwadraty
łacińskie, twierdzenia o rozszerzaniu prostokąta łacińskiego do kwadratu
łacińskiego, dowód.