Matematyka Dyskretna

Forma kursu:
Wykład i ćwiczenia z wykorzystaniem programu MATHEMATICA.
Opis kursu:
Kurs zaznajamia słuchaczy z podstawowymi problemami i metodami badawczymi z zakresu matematyki dyskretnej. Obejmuje w szczególności: - problemy zliczania i porządkowania wraz z zastosowaniem do problemów projektowania eksperymentów, - metody określania i rozwiązywania równań rekurencyjnych jednorodnych i niejednorodnych, - podstawy teorii grafów wraz z problemami optymalizacyjnymi, problemami przydziałów, pokryć, spójności, planarności czy kolorowania. Omówione są także zastosowanie grup skończonych do problemów obliczeń różnych kolorowań z uwzględnieniem symetrii, w tym tw.Burnside'a oraz tw. Polya. Na koniec prezentowane są elementy teorii kodowania i kryptografii oraz kombinatoryki na słowach w celu wskazania możliwej kontynuacji tej tematyki na kursach: "Kryptografia i teoria kodowania" oraz "Wybrane modele matematyki dyskretnej" (zawiera elementy teorii shiftów).

Treści programowe:

• Podstawy kombinatoryki; zasada gołębnika i jej uogólnienia; liczba bijekcji (permutacji), injekcji, surjekcji - Liczby Stirlinga I i II rodzaju; tw. o dwumianie i jego uogólnienie; zasada sita i zastosowanie
• Projektowanie eksperymentów; konfiguracje kombinatoryczne; kwadraty łacińskie
• Elementy teorii liczb; podstawowe tw. arytmetyki; liczby pierwsze; NWD, NWW; alg. Euklidesa i uogólnienie; arytmetyka modularna, równ. ax=b mod n; tw. Fermata; tw. Eulera; funkcje Eulera i Mobiusa; formuła odwrotna; tw. chińskie o resztach i jego uogólnienie; równania diofantyczne
• Elementy teorii grafów; grafy i ich rodzaje; drzewa, algorytmy sortowania i przeszukiwania; twierdzenie Ramseya, liczby Ramseya
• Grafy dwudzielne; przydziały (skojarzenia); pakowania i pokrycia
• Spójność; 2-spójność;3-spójność; tw Menger'a; tw.Madera
• Planarność i dualność; kryteria planarności; tw Kuratowskiego
• Problemy kolorowania, liczba chromatyczna, wielomian; kolorowanie wierzchołkowe;, krawedziowe; kolorowanie mapy (grafy planarne)
• Cykle Hamiltona i ścieżki Eulera; warunki
• Grafy skierowane; sieci; problemy optymalizacyjne w grafach - algorytmy, minimalne drzewo rozpinające; problem najkrotszej ścieżki; przepływy, tw. Forda-Fulkersona; hipotezy Tutte'a
• macierzowa reprezentacja grafu; przestrzeń wektorowa grafu
• Problemy rekurencyjne; rekursja liniowa jednorodna- rozwiazanie ogólne (wielomian charakterystyczny); rekursja niejednorodna
• Funkcje generujące (tworzące); ułamki proste; rekursja liniowa jednorodna i niejednorodna - rozwiazanie w obu przypadkach z wykorzystaniem funkcji generujacych; funkcje generujace wykładnicze - zastosowania
• Podziały liczby naturalnej - rozwiazanie problemu przez funkcje generujące;
• Symetrie i obliczenia; zastosowanie grup skończonych do problemów obliczeń różnych kolorowań z uwzględnieniem symetrii; tw.Burnside'a, tw. Poly'a
• Elementy teorii kodowania i kryptografii;
• Elementy kombinatoryki na słowach (skończonych i nieskończonych)

Literatura:

• J.A. Anderson, Discrete Mathematics with combinatorics, Prentice-Hall, 2001
• N.L.Biggs, Dicrete Mathematics, Oxford Science Publ., Oxford 1995
• R.Diestel, Graph Theory, Springer Verlag, Heidelberg, New York 2005
• R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka Konkretna, Państwowe Wydawnictwo Naukowe, Warszawa 1996.
• P.Giblin, Primes and programming, An introduction to number theory with computing, Cambridge Univ. Press, 1994.
• N. Koblitz, Wykład z teorii liczb i kryptografii, WNT, Warszawa 1995
• Handbook of Discrete and Combinatorial Mathematics, K.H.Rosen ed., CRC Press, 2000