Cel zajęć: Wykład jest wprowadzeniem do tych działów matematyki dyskretnej, które znajdują szerokie zastosowanie w informatyce. Ćwiczenia powinny nauczyć samodzielnego rozwiązywania zadań i prostych problemów z tych dziedzin.

Program zajęć:

1 Przykłady problemów definiowanych rekurencyjnie (np. wieże Hanoi, problem Józefa Flawiusza), rozwiązywanie równań rekurencyjnych metodą rozwinięcia do sumy.
2 Proste funkcje całkowitoliczbowe i ich własności. Asymptotyka funkcji liczbowych.
3 Elementy teorii liczb: największy wspólny dzielnik i najmniejsza wspólna wielokrotność, liczby pierwsze i względnie pierwsze, faktoryzacja i funkcja Eulera, małe twierdzenie Fermata, Chińskie twierdzenie o resztach.
4 Elementy kombinatoryki: podstawowe obiekty kombinatoryczne (funkcje, permutacje, kombinacje, rozmieszczenia) i metody ich zliczania, własności permutacji, współczynniki dwumienne, zasada włączania i wyłączania. Liczby specjalne i ich własności.
5 Funkcje tworzące i wykładniczo tworzące, rozwiązywanie równań rekurencyjnych.
6 Elementy teorii grafów.

Literatura:

R.L. Graham, D.E. Knuth, O. Patashnik, Matematyka konkretna (1.1, 1.2 - problemy rekurencyjne, 2.1, 2.2, 2.3 - przekszta_canie sum skonczonych, 3. - funkcje pod_oga i sufit, 4.1, 4.2, 4.5, 4.6, 4.7 - teoria liczb, 9.1, 9.2 - asymptotyka);

W. Lipski, W. Marek, Analiza kombinatoryczna (paragrafy 3 - 8 rozdzia_u 1. - wprowadzenie do kombinatoryki, par. 10. rozdz. 1. oraz par. 8. rozdz. 3. - zale–no_ci rekurencyjne i funkcje tworz¤ce);

Z. Palka, A. Ruci„ski, Wyk_ady z kombinatoryki (rozdzia_y 1.- 4. i 6. - kombinatoryka, rozdz. 5. - rôwnania rekurencyjne i funkcje tworz¤ce);

R.J. Wilson, Wprowadzenie do teorii grafôw.




Klasôwka z 2.06.2006 ( .pdf )

Klasôwka z 8.09.2005 ( .pdf )

Klasôwka z 18.04.2005 ( .pdf )

Klasôwka z 4.06.2004 ( .dvi , .ps , .pdf )

Klasôwka z 7.04.2003 ( .dvi , .ps , .pdf )

Klasôwka z 17.05.2002 ( .dvi , .ps , .pdf )

Klasôwka z 8.04.2002 ( .dvi , .ps , .pdf )

Klasôwka z 9.04.2001 ( .dvi , .ps , .pdf )


Egzamin z 2.06.2006 ( .pdf )

Egzamin z 2.06.2006 - wersja z odpowiedziami ( .pdf )

Egzamin z 8.09.2005 ( .pdf )

Egzamin z 8.09.2005 - wersja z odpowiedziami ( .pdf )

Egzamin z 3.06.2005 ( .dvi , .ps , .pdf )

Egzamin z 3.06.2005 - wersja z odpowiedziami ( .pdf )

Egzamin z 7.09.2004 ( .dvi , .ps , .pdf )

Egzamin z 4.06.2004 - wersja z odpowiedziami ( .pdf )

Egzamin z 4.06.2004 ( .dvi , .ps , .pdf )

Egzamin z 16.05.2003 ( .dvi , .ps , .pdf )

Egzamin z 17.05.2002 ( .dvi , .ps , .pdf )

Egzamin z 25.05.2001 ( .dvi , .ps , .pdf )

Egzamin z 2000 r. ( .dvi , .ps , .pdf )

Egzamin z 1999 r. ( .dvi , .ps , .pdf )

Ostatnia modyfikacja 7.01.2006