Nauczenie studentów elementów matematyki przydatnych w analizie algorytmów.
'''Elementy Algebry i Teorii Liczb'''
#Funkcje całkowitoliczbowe, arytmetyka modularna, operacje sufit i podłoga zaokrąglania liczb rzeczywistych, algorytm mergesort. (2 godz.)
#Asymptotyka funkcji liczbowych z uwzględnieniem zastosowań w szacowaniu złożoności czasowej algorytmów. (2 godz.)
#Podzielność liczb, algorytm Euklidesa. (2 godz.)
#Liczby Fibonacciego. (1 godz.)
#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'''
#Rozmieszczenia, permutacje, kombinacje, podziały (zbioru, liczby), Lemat Burnside'a. (4 godz.)
#Metody generowania prostych obiektów kombinatorycznych. (2 godz.)
#Przykłady prostych problemów definiowanych rekurencyjnie. (2 godz.)
#Rozwiązywanie równań rekurencyjnych, funkcje tworzące. (4 godz.)
#Liczby Catalana. (1 godz.)
#Zasada włączania i wyłączania. (2 godz.)
'''Teoria grafów i zbiorów uporządkowanych'''
#Relacje porządku i równoważności i ich przykłady. (1 godz.)
#Rozszerzenia liniowe zbiorów uporządkowanych - zastosowanie w konstrukcji algorytmów sortujących. (1 godz.)
#Definicje i przykłady krat, krat rozdzielnych i Algebr Boole'a. (2 godz.)
#Definicja i przykłady grafów, grafy pełne, dwudzielne skierowane, stopień wierzchołka. (2 godz.)
#Drogi i cykle w grafach: grafy spójne i dwudzielne. (1 godz.)
#Drzewa - równoważność różnych definicji. (1 godz.)
#Komputerowa reprezentacja grafów. (1 godz.)
#Metody BFS i DFS przeszukiwania grafów. (2 godz.)
#Minimalne drzewa rozpinające - algorytmy Kruskala i Prima-Dijkstry. (2 godz.)
#Przechodnie domkniecie: algorytmy Dijkstry i Warshalla. Złożoność problemu. (3 godz.)
#Cykle i drogi Eulera. (1 godz.)
#Cykle i drogi Hamiltona tw. Ore i wielomianowa redukcja problemu drogi do cyklu i odwrotnie. (2 godz.)
#Grafy planarne. Tw. Kuratowskiego i wzór Eulera. (3 godz.)
#Kolorowanie grafów: zastosowanie - planowanie sesji egzaminacyjnej. Algorytm sekwencyjny i twierdzenie o 5-kolorowaniu grafów planarnych. (2 godz.)
M.Ch. Klin, R. Poesche, K. Rosenbaum, Algebra stosowana dla matematyków i informatyków: grupy, grafy, kombinatoryka, WNT, Warszawa 1992.
R.L. Graham, D.E. Knuth, O. Patashnik, Matematyka konkretna, PWN, 1996.
J.L. Kulikowski, Zarys teorii grafów, PWN, Warszawa 1986.
W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa 1982.
E.M. Reingold, J. Deo, N. Nievergelt, Algorytmy kombinatoryczne, PWN, Warszawa 1985.
K.A. Ross, Ch.B. Wright, Matematyka dyskretna, PWN, 1996.
M.M. Sysło, N. Deo, J. S. Kowalik, Algorytmy optymalizacji dyskretnej, PWN, Warszawa 1993.
R.J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 1985.
M. Zakrzewski, T. Żak, Kombinatoryka, prawdopodobieństwo i zdrowy rozsądek, Quadrivium, Wrocław 1993
