MATEMATYKA DYSKRETNA
Informacje ogólne
Kod przedmiotu: | 0301-MDS-01 |
Kod Erasmus / ISCED: |
11.1
|
Nazwa przedmiotu: | MATEMATYKA DYSKRETNA |
Jednostka: | Instytut Matematyki |
Grupy: |
PRZEDMIOTY OBOWIĄZKOWE - 7 SEM. MATEMATYKI (INFORMATYKA)- NOWA SIATKA |
Punkty ECTS i inne: |
(brak)
|
Język prowadzenia: | (brak danych) |
Rodzaj przedmiotu: | obowiązkowy |
Pełny opis: |
Wiadomości ogólne: zbiory skończone, rodziny podzbiorów, podziały zbioru, zbiory funkcji odwzorowujących zbiór skończony w zbiór skończony, relacje, macierz relacji, relacje równoważnościowe i wzajemnie jednoznaczna odpowiedniość z podziałami zbioru, relacje porządkujące, kraty, ranga elementu kraty, współczynniki Newtona i Gaussa, liczby Stirlinga I i II rodzaju, liczby Bella. Podziały liczb. Grafy i ich związki z relacjami. Proste algorytmy kombinatoryczne: algorytmy generujące wszystkie permutacje, funkcje różnowartościowe, wariacje z powtórzeniami, podzbiory zbioru. Poprawność i złożoność obliczeniowa tych algorytmów. Funkcja i wzór inwersyjny Möbiusa: przykłady funkcji Möbiusa, wzory inwersyjne, zasada włączania i wyłączania. Funkcje tworzące: funkcje tworzące ciągów, ciągi rekurencyjne. Inne metody zliczania. Grafy: drogi i cykle w grafach, drzewa i ich własności. Wyznaczanie minimalnego drzewa rozpinającego (algorytm Kruskala), drogi i cykle Eulera i Hamiltona, problem komiwojażera. Wyznaczanie minimalnych odległości (algorytm Dijkstry). Zagadnienia minimaksowe: twierdzenie Dilwortha, przepływy w sieciach, twierdzenie Mengera. Problem małżeństw, twierdzenie Halla o systemach reprezentantów. |
Literatura: |
1. W. Lipski, W. Marek, Analiza kombinatoryczna, BM 59, PWN, 1986. 2. W. Lipski, Kombinatoryka dla programistów, WNT, 1982. 3. K. A. Ross, Ch. R. B. Wright, Matematyka dyskretna, PWN, 1996. 4. R. J. Wilson, Wprowadzenie do teorii grafów, PWN, 1985. |
Właścicielem praw autorskich jest Uniwersytet Ślaski w Katowicach.