1. SylabUZ
2. Faculty of Mathematics, Computer Science and Econometrics
3. winter term 2020/2021
4. Informatics and Econometrics - First-cycle studies leading to Bachelor's degree
5. Discrete Mathematics 1

Generate PDF for this page

Discrete Mathematics 1 - course description

Aim of the course

Poznanie podstawowych pojęć matematyki dyskretnej w aspekcie teoretycznym i algorytmicznym.

Prerequisites

Save changes

Algebra liniowa 1.

Scope

Wykład

1. Podstawowe prawa przeliczania, zasada włączeń i wyłączeń, zasada podziałowa.
2. Rekurencja.
3. Podstawowe pojęcia teorii grafów: sąsiedztwo, incydencja, izomorfizm, ścieżki i cykle, spójność, podgrafy. Macierze grafów i inne sposoby reprezentacji grafów.
4. Wybrane klasy grafów (drogi, cykle, pełne, n-dzielne). Wybrane operacje na grafach (dopełnienie, suma, złączenie).
5. Drzewa i ich własności.
6. Algorytmy przeszukiwania grafów (DFS, BFS).
7. Przestrzenie wektorowe związane z grafami.
8. n-spójność grafów.
9. Grafy Eulera i Hamiltona, algorytmy z powracaniem.
10. Grafy planarne, charakterystyka.
11. Pokrycia, niezależność i dominowanie.
12. Systemy różnych reprezentantów, twierdzenie Halla; skojarzenie pełne w grafie dwudzielnym, wyznaczanie systemu różnych reprezentantów.

Ćwiczenia

1. Rozpoznawanie obiektów kombinatorycznych w zadaniach z treścią. Wykorzystanie znanych wzorów w celu zliczania tych obiektów.
2. Zastosowanie zasady włączeń i wyłączeń, zasady podziałowej w zadaniach z treścią.
3. Dowodzenie prostych tożsamości kombinatorycznych.
4. Tworzenie związków rekurencyjnych. Rozwiązywanie jednorodnych równań rekurencyjnych, z wykorzystaniem równania charakterystycznego oraz indukcji matematycznej.
5. Zapoznanie z podstawowymi pojęciami z teorii grafów, przykłady ilustrujące te pojęcia. Omówienie sposobów reprezentacji grafu, podstawowych klas grafów i operacji na grafach na przykładach.
6. Badanie podstawowych własności drzew. Zliczanie drzew zaetykietowanych, przeszukiwanie grafów znanymi algorytmami z uwzględnieniem konstrukcji zbiorów cykli fundamentalnych i przekrojów elementarnych. Generowanie przestrzeni cykli i przekrojów grafu.
7. Badanie spójności grafu.
8. Wyznaczanie cykli Eulera i Hamiltona w grafie, z wykorzystaniem odpowiednich algorytmów. Zadania związane z własnościami grafów Eulera i Hamiltona.
9. Planarność grafu, zadania z zastosowaniem twierdzeń Eulera i Kuratowskiego.
10. Znajdowanie liczb niezależności i pokrycia oraz dominowania w grafie, zastosowanie tych pojęć także w zagadnieniach praktycznych.
11. Zadania z zastosowaniem twierdzenia Halla.

Teaching methods

Tradycyjny wykład; ćwiczenia audytoryjne, podczas których studenci rozwiązują zadania.

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Ocena za przedmiot składa się z oceny z ćwiczeń (50%) i wykładu (50%). Warunkiem uzyskania pozytywnej oceny końcowej jest uzyskanie pozytywnych ocen z ćwiczeń oraz wykładu. Warunkiem przystąpienia do zaliczenia wykładu jest uzyskanie pozytywnej oceny z ćwiczeń.

Recommended reading

1.     R.J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa, 1998.

2.     V. Bryant, Aspekty kombinatoryki, WNT, Warszawa, 1997.

3.     Z. Palka, A. Ruciński, Wykłady z kombinatoryki, cz. 1, WNT, Warszawa, 1998. 

Further reading

1.        W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 2005.

2.        W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa, 1989.

3.        K. A. Ross, Ch.R.B. Wright, Matematyka dyskretna, PWN, Warszawa, 1996.

Notes

Modified by dr Alina Szelecka (last modification: 19-10-2020 13:07)