Uniwersytet Kazimierza Wielkiego w Bydgoszczy - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Matematyka dyskretna 1300-Inf12MD-SP
Ćwiczenia (CW) Semestr letni 2018/19

Informacje o zajęciach (wspólne dla wszystkich grup)

Liczba godzin: 30
Limit miejsc: (brak limitu)
Zaliczenie: Zaliczenie na ocenę
Rygory zaliczenia zajęć: zaliczenie na ocenę
Literatura uzupelniająca: 1. Z. Pałka, A. Ruciński, Wykłady z kombinatoryki - cz. 1: Przeliczanie, Wydawnictwa Naukowo-Techniczne, Warszawa 1998.
Metody dydaktyczne: ćwiczenia konwersatoryjne
metody dyskusyjne
metody problemowe
Literatura:

1. K. A. Rybnikow (red.), Analiza kombinatoryczna w zadaniach, PWN, Warszawa 1988.

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

Efekty uczenia się:

opisują podstawowe schematy kombinatoryczne, tłumaczą związki i różnice między nimi, wyjaśniają kwestie związane z rozróżnialnością zliczanych obiektów;

opisują podstawowe typy grafów, podają przykłady grafów danego typu;

potrafią właściwie dobierać i stosować schematy kombinatoryczne dla rozwiązywania niskiej trudności problemów zliczania;

potrafią rozwiązywać niskiej trudności związki rekurencyjne;

poznają grafy o określonych własnościach, wyznaczają wartości określonych parametrów dla danego grafu;

korzystają z odpowiednich własności grafów dla stworzenia właściwego modelu zadania praktycznego.

Metody i kryteria oceniania:

Do uzyskania zaliczenia konwersatorium wymagane jest:

- aktywna obecność na zajęciach;

- uzyskanie pozytywnych ocen z dwóch sprawdzianów pisemnych (kombinatoryka i zliczanie oraz teoria grafów).

Zakres tematów:

1. Algebra zbiorów, indukcja matematyczna, relacje.

2. Schematy kombinatoryczne: wariacje, kombinacje, permutacje, etc.

3. Równania rekurencyjne i funkcje tworzące.

4. Pojęcia wstępne teorii grafów: graf i digraf, stopnie wierzchołków, rodzaje grafów (grafy dwudzielne, regularne, turnieje, etc.).

5. Planarność grafu, wzór Eulera z zastosowaniami.

6. Drogi i cykle, drogi i cykle Eulera, drogi i cykle Hamiltona.

7. Drzewa i lasy, drzewa (lasy) rozpinające, twierdzenia Cayleya i Kirchhoffa o zliczaniu drzew rozpinających.

8. Niezależność zbiorów wierzchołków i krawędzi. Optymalne (najliczniejsze/najmniej liczne) zbiory niezależne/pokrywające (tożsamości Gallaia, kryterium Berge’a), twierdzenia minimaksowe (Koeniga), twierdzenie Halla, liczba i indeks chromatyczny (oszacowania).

Grupy zajęciowe

zobacz na planie zajęć

Grupa Termin(y) Prowadzący Miejsca Akcje
1 każdy piątek, 11:45 - 13:15, sala 14
Waldemar Sieg 20/25 szczegóły
2 każdy czwartek, 10:00 - 11:30, sala 02
Waldemar Sieg 25/25 szczegóły
3 każda środa, 12:35 - 14:05, sala 5
Waldemar Sieg 26/26 szczegóły
Wszystkie zajęcia odbywają się w budynku:
Budynek przy ulicy M. Kopernika
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Kazimierza Wielkiego w Bydgoszczy.