ELEMENTY MATEMATYKI DYSKRETNEJ
Informacje ogólne
Kod przedmiotu: | 0301-MT-N1-12-EMDY |
Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
Nazwa przedmiotu: | ELEMENTY MATEMATYKI DYSKRETNEJ |
Jednostka: | Instytut Matematyki |
Grupy: |
Przedmioty obowiązkowe - 2 sem. matematyki /nst.I st./ |
Strona przedmiotu: | http://el2.us.edu.pl/wmfich/ |
Punkty ECTS i inne: |
(brak)
|
Język prowadzenia: | polski |
Poziom przedmiotu: | podstawowy |
Rodzaj przedmiotu: | obowiązkowy |
Wymagania wstępne: | brak |
Skrócony opis: |
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. |
Pełny opis: |
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: |
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. V. Bryant, Aspekty kombinatoryki, PWN 1997. R.L. Graham, D.E. Knuth, O. Patashnik, Matematyka konkretna, PWN 2010. |
Efekty uczenia się: |
Student: Potrafi wyznaczać liczby podzbiorów zbioru, permutacji, wariacji i kombinacji. Stosuje zasadę włączania i wyłączania. Potrafi sprawnie posługiwać się współczynnikami Newtona i obliczać proste sumy z tymi współczynnikami. Potrafi rozkładać permutacje na cykle. Zna pojęcie i własności liczb Stirlinga I oraz II rodzaju. Potrafi wyznaczyć drzewo spinające graf i fundamentalny zbiór cykli. Zna warunki konieczne i wystarczający istnienia drogi/cyklu Eulera w grafie. |
Metody i kryteria oceniania: |
Aktywność na zajęciach: Aktywność na zajęciach będzie oceniona na podstawie krótkich pisemnych zapytań o znajomość teorii z wykładów potrzebnej do realizacji poszczególnych konwersatoriów a także przygotowanie rozwiązań zadań z zestawu. Kolokwium zaliczeniowe: kolokwium pisemne sprawdzające znajomość zadań z dostarczonych w trakcie zajęć zestawów. Egzamin pisemny: składa się z jednej części: pytania dotyczą teorii. |
Praktyki zawodowe: |
Nie dotyczy. |
Właścicielem praw autorskich jest Uniwersytet Ślaski w Katowicach.