Semestr letni 2008/09
Semestr zimowy 2009/10
Semestr zimowy 2010/11
Semestr zimowy 2011/12
Semestr zimowy 2012/13
Semestr letni 2013/14
Matematyka dyskretna MAT1205
Treści programowe:
1. Indukcja matematyczna,Arytmetyka modularna relacja podzielności liczb całkowitych, liczby pierwsze, największy wspólny dzielnik, algorytm Euklidesa, kongruencje, tw. Eulera.
2. Kombinatoryka: moce zbiorów, rozmieszczenia. dwumianowy symbol Newtona. Techniki zliczania obiektów kombinatorycznych. Szufladkowa zasada Dirichleta, Zasada włączeń i wyłączeń. Liczby Stirlinga pierwszego i drugiego rodzaju. Elementy asymptotyki
3. Teoria grafów. Komputerowa reprezentacja grafu. Drzewa, ich charakteryzacja i zliczanie drzew rozpinających graf. Twierdzenie Cayley'a. Grafy Eulera, Hamiltona ich charakteryzacja. Grafy planarne.Grafy dwudzielne. Twierdzenie Halla o małżeństwach Kolorowania.
4. Liniowe równania rekurencyjne. Funkcje tworzące.
Efekty kształcenia: Opanowanie podstawowych metod matematyki dyskretnej stosowanej w informatyce
Rodzaj przedmiotu
Koordynatorzy przedmiotu
W cyklu 2009Z: | W cyklu 2011Z: | W cyklu 2010Z: | W cyklu 2012Z: | W cyklu 2013L: |
Literatura
a) podstawowa:
1. Victor Bryant, Aspekty kombinatoryki, Wydawnictwo Naukowo-Techniczne, Warszawa 1997.
2. Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN, Warszawa 1998.
3. Witold Lipski, Kombinatoryka dla programistów, Wydawnictwo Naukowo-Techniczne, Warszawa 1982.
4. Kenneth A. Ross, Charles R.B. Wright, Matematyka dyskretna, Wydawnictwo Naukowe PWN, Warszawa 2001.
5. Robin J. Wilson, Wstęp do teorii grafów, Wydawnictwo Naukowe PWN, Warszawa 1998.
b) uzupełniająca:
1. Martin Aigner, Gunter M. Ziegler, Dowody z Księgi, Wydawnictwo Naukowe PWN, Warszawa 2004.
2. Tadeusz Gerstenkorn, Tadeusz Śródka, Kombinatoryka i rachunek prawdopodobieństwa, PWN, Warszawa 1974.
3. Ralph P. Grimaldi, Discrete and combinatorial mathematics - An applied introduction, Addison-Wesley Publishing Company.
4. Leon Jeśmianowicz, Jerzy Łoś, Zbiór zadań z algebry, Państwowe Wydawnictwo Naukowe, Warszawa 1976.