Katalog przedmiotów

Matematyka dyskretna

Cele
Celem kształcenia jest przekazanie oraz ugruntowanie wiedzy z wybranych działów kombinatoryki (w wariantach ID i IZ) i teorii grafów (w wariancie ID). Wykład ma zapoznać słuchaczy z podstawowymi definicjami i twierdzeniami oraz zasygnalizować szeroki zakres zastosowań omawianych kwestii w informatyce. Ćwiczenia są zorientowane na utrwalenie pojęć przedstawionych na wykładzie oraz na uzyskanie sprawności w rozwiązywaniu przykładowych zadań wykorzystujących te pojęcia. Mają również nauczyć formułowania praktycznych zagadnień w języku matematyki dyskretnej.

Zakres
W wariantach ID i IZ.
Notacja i przypomnienie podstawowych pojęć. Zdania i funktory zdaniotwórcze, rachunek zdań. Zbiory i operacje na zbiorach. Relacje binarne w iloczynie kartezjańskim zbiorów, relacje w zbiorze. Graf relacji. Cechy relacji w zbiorze: zwrotność, przechodniość, symetryczność, antysymetryczność. Relacje równoważności i relacje częściowego porządku. Klasy abstrakcji relacji równoważności. Pojęcia zbioru częściowo uporządkowanego i liniowo uporządkowanego. Funkcje jako relacje, funkcje różnowartościowe, surjekcje. Funkcje i rozmieszczenia. Formułowanie zagadnień zliczania w języku zliczania funkcji. Twierdzenia o liczbie wszystkich funkcji oraz o liczbie funkcji różnowartościowych ze zbioru n-elementowego w zbiór m-elementowy. Twierdzenie o liczbie rozmieszczeń uporządkowanych n obiektów w m pudełkach. Permutacje. Złożenie permutacji, permutacja identycznościowa, permutacja odwrotna, transpozycja. Formuła Stirlinga do przybliżonego wyznaczania liczby permutacji. Graficzna reprezentacja permutacji. Rozkład permutacji na cykle rozłączne. Inwersje, znak permutacji i typ permutacji. Transpozycje i transpozycje sąsiednich elementów. Twierdzenie o związku znaku permutacji z jej typem. Algorytm o złożoności liniowej znajdowania znaku permutacji. Podzbiory zbioru, wektor charakterystyczny. Algorytm generowania podzbiorów zbioru i kod Graya. Podzbiory k-elementowe zbioru n-elementowego. Współczynniki dwumianowe. Wzór dwumianowy Newtona. Tożsamości związane ze współczynnikami dwumianowymi. Współczynniki wielomianowe. Tożsamości dla współczynników wielomianowych. Zastosowania współczynników wielomianowych. Zbiory z powtórzeniami i ich zastosowania. Podzbiory zbioru z powtórzeniami. Twierdzenie o liczbie podzbiorów k-elementowych zbioru z powtórzeniami przy krotnościach elementów równych k oraz jego zastosowania. Podziały zbioru na bloki. Związki podziałów zbioru z relacjami równoważności i relacjami częściowego porządku. Generowanie wszystkich podziałów zbioru. Liczby Stirlinga drugiego i pierwszego rodzaju. Liczby Bella. Twierdzenie o związku liczb Stirlinga drugiego rodzaju z liczbą funkcji ze zbiou n-elementowego na zbiór m-elementowy. Podziały liczb. Twierdzenia pozwalające na rekurencyjne wyznaczania liczby podziałów. Reprezentacja podziałów liczb na diagramach Ferrersa. Elementy teorii zbiorów częściowo uporządkowanych. Diagram Hassego. Elementy maksymalne, minimalne, najmniejsze, największe, kresy górny i dolny. Łańcuchy i antyłańcuchy w zbiorach częściowo uporządkowanych. Twierdzenie Dilwortha i jego zastosowania. Ciągi nieskończone i operacje na ciągach. Funkcje tworzące ciągów. Operacje na funkcjach tworzących. Zastosowanie funkcji tworzących do wyznaczania liczby rozwiązań równań diofantycznych oraz zliczania podzbiorów zbioru z powtórzeniami. Zastosowanie funkcji tworzących do rozwiązywania liniowych równań rekurencyjnych. Zasada włączania-wyłączania. Zastosowania zasady włączania i wyłączania do wyznaczania liczby surjekcji oraz liczby nieporządków. Zasada szufladkowa i jej zastosowania. Podsumowanie wiadomości o zagadnieniach zliczania.
W wariancie ID.
Wprowadzenie do teorii grafów. Grafy skierowane i nieskierowane. Rysunki grafów. Modelowanie zagadnień praktycznych w języku teorii grafów. Reprezentacje grafów. Macierze incydencji i macierze sąsiedztwa grafów. Izomorfizm grafów. Metody przeszukiwania grafów w głąb i wszerz oraz ich zastosowania. Wybrane klasy grafów i ich właściwości. Grafy dwudzielne. Grafy planarne. Grafy regularne. Grafy wielościanów. Kostki n-wymiarowe. Drogi i cykle w grafach. Drogi i cykle Eulera. Twierdzenie Eulera o istnieniu drogi i cyklu Eulera w grafach nieskierowanych i skierowanych. Algorytm Fleury’ego. Drogi i cykle Hamiltona w grafach. Warunki dostateczne istnienia cyklu Hamiltona w grafie. Twierdzenia Orego, Diraca, Nasha-Williamsa, Meyniela, Chvátala. Turnieje i ich właściwości. Twierdzenia Redei oraz Camiona. Spójność grafu nieskierowanego. Spójność krawędziowa, wierzchołkowa oraz k-spójność. Twierdzenia Mengera w wersji krawędziowej i wierzchołkowej. Spójność grafów skierowanych. Separatory i konektory grafów. Uogólnienia twierdzeń Mengera. Drzewa i lasy. Właściwości drzew. Drzewa rozpinające grafu nieskierowanego. Wyznaczenie i zliczanie drzew rozpinających. Twierdzenie Cayleya o liczbie drzew rozpinających w grafie pełnym. Kod Prüfera drzewa rozpinającego. Twierdzenie Kirchhoffa o liczbie drzew rozpinających. Cykle fundamentalne względem drzewa rozpinającego grafu. Pokrycia krawędziowe i wierzchołkowe grafu i ich zastosowania. Zbiory wierzchołków wewnętrznie stabilnych i skojarzenia w grafie oraz ich zastosowania. Związki między zbiorami stabilnymi a pokryciami w grafach nieskierowanych; tożsamości Gallai. Skojarzenia w grafach dwudzielnych. Twierdzenia Koniga i Halla. Kolorowanie wierzchołków i krawędzi grafu. Twierdzenia Brooksa, twierdzenie o czterech barwach i twierdzenieVizinga. Wprowadzenie do ogólnej teorii zliczania. Pojęcie operacji binarnej na zbiorze. Pojęcie grupy. Grupa symetryczna stopnia n, grupa permutacji stopnia n. Działanie grupy na zbiorze. Klasy równoważności wyznaczane przez grupę permutacji działającą na zbiorze. Twierdzenie Burnside’a o liczbie orbit grupy i jego zastosowania. Klasy równoważności funkcji. Wagi figur i konfiguracji. Szereg zliczający konfiguracji i szereg zliczający wzorów. Indeks cykli grupy i twierdzenie Polyi o szeregu zliczającym wzorów. Zastosowania twierdzenia Polyi w zagadnieniach zliczania.

Literatura podstawowa
1. M. Libura, J. Sikorski: Wykłady z matematyki dyskretnej. Część I:Kombinatoryka. Wyższa Szkoła Informatyki Stosowanej i Zarządzania,Warszawa 2003, str. xiv + 169.
2. M. Libura, J. Sikorski: Wykłady z matematyki dyskretnej. Część II: Teoria grafów. Wyższa Szkoła Informatyki Stosowanej i Zarządzania,Warszawa 2003, str. xiv + 181 (tylko w wariancie ID).
3. K.A. Ross, Ch.R.B. Wright: Matematyka dyskretna. Wydawnictwo NaukowePWN, Warszawa 2003.
4. R.J. Wilson: Wprowadzenie do teorii grafów. Wydawnictwo NaukowePWN, Warszawa 1998 (tylko w wariancie ID).

Literatura uzupełniająca
1. V. Bryant: Aspekty kombinatoryki. Wydawnictwa Naukowo-Techniczne,Warszawa 1997.
2. R.L. Graham, D.E. Knuth, O. Patashnik: Matematyka konkretna.Wydawnictwo Naukowe PWN, Warszawa 1996 (tylko w wariancie ID.
3. W. Lipski: Kombinatoryka dla programistów. Wydawnictwa Naukowo-Techniczne, Warszawa 1989.
4. Z. Palka, A. Ruciński: Wykłady z kombinatoryki. WydawnictwaNaukowo-Techniczne, Warszawa 1998.

Punkty ECTS
5 - niestacjonarne,
5 - stacjonarne

Rodzaje studiów, na których przedmiot jest realizowany
niestacjonarne - 1-go stopnia (inż.),
stacjonarne - 1-go stopnia (inż.)

Specjalności, na których przedmiot jest realizowany
Informatyka w telekomunikacji,
Bazy danych,
Inżynieria oprogramowania,
Komputerowe wspomaganie grafiki,
Sieci komputerowe

Prowadzący
dr Grażyna Grygiel, dr hab. inż. Marek Libura, dr inż. Jarosław Sikorski, dr Leszek Pysiak, mgr inż. Elżbieta Janaszewska-Błaszczyk