**Program:**
**Elementy Algebry i Teorii Liczb**
1. Funkcje całkowitoliczbowe, arytmetyka modularna, operacje sufit i podłoga zaokrąglania liczb rzeczywistych, algorytm mergesort. (2 godz.)
2. Asymptotyka funkcji liczbowych z uwzględnieniem zastosowań w szacowaniu złożoności czasowej algorytmów. (2 godz.)
3. Podzielność liczb, algorytm Euklidesa. (2 godz.)
4. Liczby Fibonacciego. (1 godz.)
5. Liczby pierwsze i względnie pierwsze. Rozkład na czynniki. Funkcja Eulera. Kwadraty łacińskie. Chińskie twierdzenie o resztach. Twierdzenie Eulera (4 godz.)
**Kombinatoryka**
1. Rozmieszczenia, permutacje, kombinacje, podziały (zbioru, liczby), Lemat Burnside'a. (4 godz.)
2. Metody generowania prostych obiektów kombinatorycznych. (2 godz.)
3. Przykłady prostych problemów definiowanych rekurencyjnie. (2 godz.)
4. Rozwiązywanie równań rekurencyjnych, funkcje tworzące. (4 godz.)
5. Liczby Catalana. (1 godz.)
6. Zasada włączania i wyłączania. (2 godz.)
**Teoria grafów i zbiorów uporządkowanych**
1. Relacje porządku i równoważności i ich przykłady. (1 godz.)
2. Rozszerzenia liniowe zbiorów uporządkowanych - zastosowanie w konstrukcji algorytmów sortujących. (1 godz.)
3. Definicje i przykłady krat, krat rozdzielnych i Algebr Boole'a. (2 godz.)
4. Definicja i przykłady grafów, grafy pełne, dwudzielne skierowane, stopień wierzchołka. (2 godz.)
5. Drogi i cykle w grafach: grafy spójne i dwudzielne. (1 godz.)
6. Drzewa - równoważność różnych definicji. (1 godz.)
7. Komputerowa reprezentacja grafów. (1 godz.)
8. Metody BFS i DFS przeszukiwania grafów. (2 godz.)
9. Minimalne drzewa rozpinające - algorytmy Kruskala i Prima-Dijkstry. (2 godz.)
10. Przechodnie domkniecie: algorytmy Dijkstry i Warshalla. Złożoność problemu. (3 godz.)
11. Cykle i drogi Eulera. (1 godz.)
12. Cykle i drogi Hamiltona tw. Ore i wielomianowa redukcja problemu drogi do cyklu i odwrotnie. (2 godz.)
13. Grafy planarne. Tw. Kuratowskiego i wzór Eulera. (3 godz.)
14. Kolorowanie grafów: zastosowanie - planowanie sesji egzaminacyjnej. Algorytm sekwencyjny i twierdzenie o 5-kolorowaniu grafów planarnych. (2 godz.)
**Elementy rachunku prawdopodobieństwa**
1. Przestrzeń zdarzeń elementarnych, zdarzenia, prawdopodobieństwo w dyskretnych przestrzeniach zdarzeń. (2 godz.)
2. Prawdopodobieństwo warunkowe i wzór na prawdopodobieństwo całkowite. Wzór Bayesa. (2 godz.)
3. Niezależność zdarzeń. Schemat Bernoulliego. (2 godz.)
4. Zmienne losowe, wartość oczekiwana i wariancja. Prawa wielkich liczb. (2 godz.)
5. Prawdopodobieństwo w ciągłych przestrzeniach zdarzeń. Rozkład normalny. (2 godz.)
**Wymagania:** Nauczenie studentów elementów matematyki przydatnych w analizie
algorytmów.
