Uniwersytet Ślaski w Katowicach - Centralny System Uwierzytelniania
Strona główna

MATEMATYKA DYSKRETNA

Informacje ogólne

Kod przedmiotu: 0301-MDS-01
Kod Erasmus / ISCED: 11.1 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (brak danych)
Nazwa przedmiotu: MATEMATYKA DYSKRETNA
Jednostka: Instytut Matematyki
Grupy: PRZEDMIOTY OBOWIĄZKOWE - 7 SEM. MATEMATYKI (INFORMATYKA)- NOWA SIATKA
Punkty ECTS i inne: (brak) Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
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.

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Ślaski w Katowicach.
kontakt deklaracja dostępności USOSweb 7.0.3.0 (2024-03-22)