Poznanie podstawowych pojęć matematyki dyskretnej w aspekcie teoretycznym i algorytmicznym.
Wymagania wstępne
Wstęp do matematyki, Algebra liniowa 1.
Zakres tematyczny
Wykład
Podstawowe prawa przeliczania, zasada włączeń i wyłączeń, zasada podziałowa.
Rekurencja.
Funkcje tworzące.
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.
Wybrane klasy grafów (drogi, cykle, pełne, n-dzielne). Wybrane operacje na grafach (dopełnienie, suma, złączenie).
Drzewa i ich własności.
Algorytmy przeszukiwania grafów (DFS, BFS).
Przestrzenie wektorowe związane z grafami.
n-spójność grafów.
Grafy Eulera i Hamiltona, algorytmy z powracaniem.
Grafy planarne, charakterystyka.
Pokrycia, niezależność i dominowanie.
Systemy różnych reprezentantów, twierdzenie Halla; skojarzenie pełne w grafie dwudzielnym, wyznaczanie systemu różnych reprezentantów.
Ćwiczenia
Rozpoznawanie obiektów kombinatorycznych w zadaniach z treścią. Wykorzystanie znanych wzorów w celu zliczania tych obiektów.
Zastosowanie zasady włączeń i wyłączeń, zasady podziałowej w zadaniach z treścią.
Dowodzenie prostych tożsamości kombinatorycznych.
Tworzenie związków rekurencyjnych. Rozwiązywanie jednorodnych równań rekurencyjnych, z wykorzystaniem równania charakterystycznego oraz indukcji matematycznej.
Wykorzystanie funkcji tworzących do rozwiązywania równań rekurencyjnych oraz przeliczania obiektów kombinatorycznych oznaczonych.
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.
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.
Badanie spójności grafu.
Wyznaczanie cykli Eulera i Hamiltona w grafie, z wykorzystaniem odpowiednich algorytmów. Zadania związane z własnościami grafów Eulera i Hamiltona.
Planarność grafu, zadania z zastosowaniem twierdzeń Eulera i Kuratowskiego.
Znajdowanie liczb niezależności i pokrycia oraz dominowania w grafie, zastosowanie tych pojęć także w zagadnieniach praktycznych.
Zadania z zastosowaniem twierdzenia Halla.
Metody kształcenia
Tradycyjny wykład; ćwiczenia audytoryjne, podczas których studenci rozwiązują zadania.
Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się
Opis efektu
Symbole efektów
Metody weryfikacji
Forma zajęć
Warunki zaliczenia
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ń.
Literatura podstawowa
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.
Literatura uzupełniająca
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.
Uwagi
Zmodyfikowane przez dr Robert Dylewski, prof. UZ (ostatnia modyfikacja: 09-04-2017 16:35)
Ta strona używa ciasteczek (cookies), dzięki którym nasz serwis może działać lepiej. Korzystając z niniejszej strony, wyrażasz zgodę na ich używanie. Dowiedz się więcej.