Wybrane zagadnienia kombinatoryki

Celem przedmiotu jest zapoznanie z podstawowymi metodami zliczania obiektów kombinatorycznych, obliczania sum ciągów liczbowych oraz rozwiązywania równań rekurencyjnych zarówno dokładnie, jak i w sposób przybliżony. Pokazane będą związki omawianych problemów z problemami pojawiającymi się w informatyce.

Przedmioty poprzedzające:

Matematyka Dyskretna, Analiza matematyczna 1, Elementy logiki i teorii mnogości.

Wymagania wstępne: Znajomość podstawowych pojęć matematyki dyskretnej oraz logiki i teorii mnogości. Znajomość szeregów liczbowych i funkcyjnych

Program przedmiotu: W programie przewidziane są między innymi następujące tematy: przegląd metod obliczania sum ciągów liczbowych, elementy rachunku różnicowego, własności współczynników dwumiennych, tożsamości dwumienne, reguła inwersyjna, liczby Stirlinga pierwszego i drugiego rodzaju i ich własności, liczby harmoniczne i ich własności, liczby Bernoulliego, liczby Fibonacciego i ich własności, funkcje tworzące, sploty funkcji tworzących, wykładnicze funkcje tworzące, asymptotyka ciągów liczbowych, notacja dużego „O”, wzór Stirlinga, przybliżenie n-tej liczby pierwszej.

Program wykładu i ćwiczeń:

1. Obliczanie sum skończonych podstawowymi metodami (repertuaru, czynnika sumacyjnego, zaburzeń itd.).

2. Rachunek różnicowy.

3. Rozwiązywanie równań rekurencyjnych przy użyciu metod funkcji tworzących oraz przy użyciu opanowanych wcześniej metod sumowania.

4. Przybliżone rozwiązywanie równań rekurencyjnych poprzez pewne metody formalnego rachunku w obrębie notacji „O dużego”

1. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, 1997.

2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Wprowadzenie do algorytmów, WNT, 2000.

3. M. R. Garey, D. S. Johnson, Computers and Intractability, Freeman 1979.

4. M. A. Weiss, Data Structures and Algorithms in C++, Adison Wesley 1999.

Podstawę zaliczenia stanowią dwa kolokwia po 16 punktów, aktywność na ćwiczeniach 8 pkt. Razem 40 pkt. Ocena 3.0 – 20-23 pkt, 3.5 – 24-27 pkt, 4.0 – 28-31 pkt, 4.5 – 32-35 pkt, 5.0 – 36-40 pkt. Obecność na ćwiczeniach obowiązkowa, dopuszczalna dwa razy nieusprawiedliwiona nieobecność.