ELEMENTY MATEMATYKI DYSKRETNEJ A

podstawowy

obowiązkowy

Brak

Moduł ma na celu: zaznajomienie studentów z elementarnymi zagadnieniami kombinatoryki skończonej i teorii grafów oraz wykształcenie umiejętności zliczania obiektów kombinatorycznych i przeprowadzania obliczeń z wykorzystaniem prostych chwytów kombinatorycznych.

Moduł ma na celu: zaznajomienie studentów z elementarnymi zagadnieniami kombinatoryki skończonej i teorii grafów oraz wykształcenie umiejętności zliczania obiektów kombinatorycznych i przeprowadzania obliczeń z wykorzystaniem prostych chwytów kombinatorycznych.

Przewiduje się realizację następujących treści programowych:

1. Kombinacje, własności współczynników dwumiennych Newtona, obliczanie skończonych sum zawierających współczynnik

Newtona.

2. Znajdowania liczby funkcji spełniających pewne ograniczenia, rozmieszczenia przedmiotów, wariacje, permutacje, multizbiory.

3. Własności permutacji, rozkład na cykle, rozkład na transpozycje, typ permutacji, liczby Stirlinga I rodzaju i ich własności.

4. Podział zbioru na bloki, liczby Stirlinga II rodzaju i ich własności, podziały liczby i ich własności.

5. Metoda zliczania obiektów: metoda bijektywna, reguła włączania i wyłączania, zasada szufladkowa Dirichleta.

6. Równania rekurencyjne i funkcje tworzące. Liczby Fibonacciego i Catalana.

7. Elementy teorii grafów: podstawowe pojęcia, minimalne drzewa rozpinające, problem minimalnych odległości, grafy Eulera

i Hamiltona, problem komiwojażera.

Literatura obowiązkowa:

W. Lipski, W. Marek, Analiza kombinatoryczna, PWN 1986

Z. Palka, A. Ruciński, Wykłady z kombinatoryki, WNT 1998.

R. J. Wilson, Wprowadzenie do teorii grafów, PWN 1985.

Literatura uzupełniająca:

V. Bryant, Aspekty kombinatoryki, PWN 1997.

R.L. Graham, D.E. Knuth, O. Patashnik, Matematyka konkretna, PWN 2010.

1. Student potrafi wyznaczać liczby podzbiorów zbioru, permutacji, wariacji i kombinacji. Stosuje zasadę włączania i wyłączania.

2. Student potrafi sprawnie posługiwać się współczynnikami Newtona i obliczać proste sumy z tymi współczynnikami.

3. Student potrafi rozkładać permutacje na cykle.

4. Student zna pojęcie i własności liczb Stirlinga I oraz II rodzaju.

5. Student potrafi wyznaczyć drzewo spinające grafu i fundamentalny zbiór cykli.

6. Student zna warunki konieczne i wystarczające na istnienie drogi/cyklu Eulera w grafie.

1. Aktywność na zajęciach - weryfikacja znajomości treści wykładów na podstawie pytań zadawanych przez prowadzącego konwersatorium na zajęciach.

2. Kolokwium pisemne - weryfikacja umiejętności rozwiązywania zadań na podstawie analizy rozwiązań zadań z kolokwium.

3. Egzamin pisemny - weryfikacja umiejętności na podstawie analizy rozwiązań zadań egzaminacyjnych, weryfikacja znajomości pojęć i faktów w oparciu o analizę odpowiedzi na pytania egzaminacyjne o charakterze teoretycznym.

Brak