**Cel zajęć** : zapoznanie z podstawowymi pojęciami i 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, liczby Catalana.
3. Metody zliczania, w tym zasada włączeń-wyłączeń oraz zasada Dirichleta.
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, obliczanie drzewa rozpinającego o minimalnej wadze, metody przeszukiwania grafów, skojarzenia, twierdzenie Halla, cykle Eulera i Hamiltona, planarność, kolorowalność wierzchołkowa grafu, znajdowanie najkrótszych ścieżek, przepływy w sieciach.
**Wymagania:**
1. Podstawy logiki i teorii mnogości.
2. Podstawy algebry.
3. Podstawy analizy matematycznej.
Literatura:
R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka Konkretna
K.A.Ross, Ch.R.B.Wright, Matematyka Dyskretna
W.Lipski, Kombinatoryka dla programistów
Z.Pałka, A.Ruciński, Wykłady z kombinatoryki
R.J.Wilson, Wprowadzenie do teorii grafów
D.West, Introduction to Graph Theory
R. Diestel, Graph Theory
