**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.
W semestrze zimowym 23/24: wtorki 12.00-13.00. Proszę o wcześniejsze (przynajmniej dzień wcześniej) potwierdzanie mailem chęci przyjścia na konsultacje. Można próbować umawiać się mailowo na inne terminy.
