**Cel zajęć** : zapoznanie z podstawowymi technikami matematyki dyskretnej.
**Program:**
1. Asymptotyka funkcji liczbowych w zastosowaniu do szacowania złożoności algorytmów.
2. Elementy kombinatoryki: permutacje, podziały, wariacje z powtórzeniami i bez powtórzeń, współczynniki dwumianowe.
3. Metody zliczania, w tym zasada włączeń-wyłączeń oraz lemat Burnside'a.
4. Rekurencje i rozwiązywanie równań rekurencyjnych. Metoda anihilatorów.
5. Elementarna teoria liczb: podzielność, liczby pierwsze, rozkład na czynniki pierwsze, NWD i algorytm Euklidesa.
6. Arytmetyka modularna: małe twierdzenie Fermata i twierdzenie Eulera, chińskie twierdzenie o resztach.
7. Funkcje tworzące.
8. Teoria grafów: grafy dwudzielne, grafy skierowane, ścieżki i spójność, drzewa rozpinające, metody przeszukiwania grafów, skojarzenia, twierdzenie Halla, cykle Eulera i Hamiltona, planarność, kolorowalność wierzchołkowa grafu.
9. Znajdowanie najkrótszych ścieżek w grafie.
**Wymagania:**