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

Generate PDF for this page

Discrete Mathematics 2 - course description

Aim of the course

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

Prerequisites

Save changes

Matematyka dyskretna 1.

Scope

Wykład/ćwiczenia

1. Wybrane klasy grafów:grafy przedziałów, k-drzewa, cięciwowe, krawędziowe i ich własności.
2. Różne rodzaje dominowania w grafach.
3. Digrafy, definicje i oznaczenia.
4. Digrafy silnie spójne,  tranzytywne i acykliczne, ich własności.
5. Wybrane algorytmy digrafowe.
6. Definicja matroidu. Przykłady i podstawowe własności.

 

Teaching methods

Wykład: konwencjonalny, konwersatoryjny.

Ćwiczenia: klasyczna metoda problemowa.

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

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.

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 zaliczających ćwiczenia i wykład.

Recommended reading

1. J. Bang-Jensen, G.Gutin, Digraphs, Theory and Algorithms, 2001.
2. R. Distel, Graph Theory, Springer-Verlag, New York 1997.
3. R.J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 1998.
4. D. J. A. Welsh, Matroid theory, Academic Press, Inc., New York, 2010.

Further reading

1. W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 2005.
2. H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth,Theoretical Computer Science 209 (1998) 1-45.
3. A. Brandstadt, V.B. Le, J.P.Spinrad, Graph Classes: a survey, SIAM 2004

Notes

Przedmiot oferowany również w semestrze IV.

Modified by dr Alina Szelecka (last modification: 19-05-2022 21:46)