1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2018/2019
4. Matematyka - pierwszego stopnia z tyt. licencjata
5. Matematyka dyskretna 1

Wygeneruj PDF dla tej strony

Matematyka dyskretna 1 - opis przedmiotu

Cel przedmiotu

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

Wymagania wstępne

Zapisz zmiany

Wstęp do matematyki, Algebra liniowa 1.

Zakres tematyczny

Wykład

1. Podstawowe pojęcia teorii grafów: sąsiedztwo, incydencja, izomorfizm, ścieżki i cykle, spójność, podgrafy (2 godz.).
2. Macierze grafów (2 godz.).
3. Wybrane klasy grafów (drogi, cykle, pełne, n-dzielne) (2 godz.).
4. Wybrane operacje na grafach (dopełnienie, suma, złączenie, produkty) (2 godz.).
5. Drzewa i ich własności (4 godz.).
6. Algorytmy przeszukiwania grafów (DFS, BFS) (2 godz.).
7. Przestrzenie wektorowe związane z grafami (2 godz.).
8. n-spójność grafów (2 godz.).
9. Grafy Eulera i Hamiltona (3 godz.).
10. Planarność: twierdzenie Kuratowskiego, zewnętrzna planarność, twierdzenie Harary’ego (3 godz.).
11. Pokrycia i niezależność (2 godz.).
12. Kolorowania grafów (klasyczne, z listy), twierdzenia: Brookesa, Szekeres-Wilf, Vizinga, Thomassena (4 godz.).

Ćwiczenia

1. Odczytywanie danych na temat grafu z jego macierzy, list incydencji, zbiorów par. Interpretacja działań na macierzach grafów. Macierze grafów otrzymanych w wyniku operacji grafowych (4 godz.).
2. 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. Konstrukcja drzewa modularnej dekompozycji grafu (8 godz.).
3. Analiza spójności grafu (2 godz.).
4. Badanie własności grafów Eulera i Hamiltona oraz związku tych własności z innymi własnościami grafu, znajdowanie zamkniętego łańcucha Eulera i cyklu Hamiltona poprzez stosowanie znanych algorytmów (4 godz.).
5. Rozpoznawanie problemów badania planarności, znajdowania liczb niezależności i liczb pokrycia w grafie w zagadnieniach praktycznych. Stosowanie wiedzy teoretycznej do rozwiązywania  problemów z tego zakresu (4 godz.).
6. Rozpoznawanie problemów kolorowania grafów w zagadnieniach praktycznych. Algorytmiczne i teoretyczne rozwiązywanie tych problemów (6 godz.).
7. Kolokwium zaliczeniowe (2 godz.).

 

Metody kształcenia

Wykład konwersatoryjny, wykład tradycyjny. Ćwiczenia, dyskusja.

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu	Symbole efektów	Metody weryfikacji	Forma zajęć

Warunki zaliczenia

Warunki zaliczenia poszczególnych zajęć:

1. Sprawdzanie stopnia przygotowania studentów oraz ich aktywności w trakcie ćwiczeń.
2. Sprawdzian, podczas ćwiczeń, z zadaniami o zróżnicowanym stopniu trudności, pozwalający na ocenę czy i w jakim stopniu, student osiągnął wymienione efekty kształcenia głównie w zakresie umiejętności i kompetencji.
3. Konwersacja podczas wykładu w celu weryfikacji wyższych poziomów efektów kształcenia w zakresie wiedzy i umiejętności.
4. Egzamin pisemny weryfikujący efekty kształcenia w zakresie wiedzy i kompetencji.
5. Egzamin ustny pozwalający studentowi na uzupełnienie swej wypowiedzi pisemnej.

Na ocenę z przedmiotu składa się ocena z ćwiczeń (50%) i ocena z egzaminu (50%). Warunkiem przystąpienia do egzaminu jest uzyskanie pozytywnej oceny z ćwiczeń. Warunkiem zaliczenia przedmiotu jest uzyskanie pozytywnych ocen z ćwiczeń i z egzaminu.

Literatura podstawowa

1. V. Bryant, Aspekty kombinatoryki, WNT, Warszawa, 1997.
2. W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 2005.
3. K.A. Ross, Ch.R.B. Wright, Matematyka dyskretna, PWN, Warszawa 1996.
4. R. J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa, 1998.

Literatura uzupełniająca

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

Uwagi

Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 28-04-2018 08:54)