Cel kształcenia i wykaz literatury

Główny cel kształcenia:

Ogólne informacje o zajęciach:

Wykaz literatury, wymaganej do zaliczenia zajęć

Literatura wykorzystywana podczas zajęć wykładowych

1	N. Deo	Teoria grafów i jej zastosowania w technice i informatyce	PWN, Warszawa.	1980
2	R. J. Wilson	Wprowadzenie do teorii grafów	PWN, Warszawa .	2000
3	A. Włoch, I. Włoch	Marematyka dyskretna	Oficyna Wydawnicza PRz.	2008

Literatura wykorzystywana podczas zajęć ćwiczeniowych/laboratoryjnych/innych

1	R. Dmytryszyn, G. Drałus	Matematyka dyskretna	Oficyna Wydawnicza PRz.	2002
2	A. Włoch, I. Włoch	Matematyka dyskretna	Oficyna Wydawnicza PRz.	2008

Wymagania wstępne w kategorii wiedzy/umiejętności/kompetencji społecznych

Wymagania formalne:

Wymagania wstępne w kategorii Wiedzy: rachunek macierzowy, równania wielomianowe

Wymagania wstępne w kategorii Umiejętności:

Wymagania wstępne w kategorii Kompetencji społecznych:

Efekty kształcenia dla zajęć

MEK	Student, który zaliczył zajęcia	Formy zajęć/metody dydaktyczne prowadzące do osiągnięcia danego efektu kształcenia	Metody weryfikacji każdego z wymienionych efektów kształcenia	Związki z KEK	Związki z OEK
01	potrafi rozwiązywać równania rekurencyjne liniowe jednorodne	wykład, laboratorium	kolokwium, egzamin cz. pisemna	K_W001+	T1A_W01+
02	zna podstawowe definicje i twierdzenia teorii grafów	wykład, laboratorium	kolokwium, egzamin cz. pisemna	K_U003+	T1A_U05+
03	potrafi zastosować arytmetykę boolowską do znajdywania maksymalnych zbiorów niezależnych lub minimalnych zbiorów dominujących w grafach	wykład, laboratorium	kolokwium, egzamin cz. pisemna	K_W001+ K_K005+	T1A_W01+ T1A_K03+
04	potrafi zliczać drogi o określonej długości w grafie lub wyznaczać liczbę wszystkich drzew rozpinających grafu, wykorzystując rachunek macierzowy	wykład, laboratorium	kolokwium, egzamin cz. pisemna	K_W001+	T1A_W01+

Uwaga: W zależności od sytuacji epidemicznej, jeżeli nie będzie możliwości weryfikacji osiągniętych efektów uczenia się określonych w programie studiów w sposób stacjonarny w szczególności zaliczenia i egzaminy kończące określone zajęcia będą mogły się odbywać przy użyciu środków komunikacji elektronicznej (w sposób zdalny).

Treści kształcenia dla zajęć

Sem.	TK	Treści kształcenia	Realizowane na	MEK
2	TK01	Relacje, relacje równoważnościowe, relacje porządkujące. Indukcja matematyczna.	W01, W02
2	TK02	Elementy kombinatoryki- obiekty kombinatoryczne, reprezentacja obiektów kombinatorycznych, generowanie i zliczanie obiektów kombinatorycznych. Systemy reprezentantów. Zagadnienie optymalnego przydziału.	W03, W04
2	TK03	Zależności rekurencyjne. Metody rozwiązywania równań rekurencyjnych. Liczby Fibonacciego, liczby Lucasa i ich własności.	W05	MEK01
2	TK04	Podstawowe definicje i oznaczenia teorii grafów. Podgrafy grafów. Izomorfizm grafów. Macierzowa interpretacja grafu. Operacje jednoargumentowe i dwuargumentowe na grafach.	W06, W07	MEK02
2	TK05	Drogi i cykle w grafach. Odległość w grafie. Spójność grafu. Grafy Eulera i grafy Hamiltona.	W08	MEK02 MEK04
2	TK06	Charakteryzacje drzew, drzewa binarne, drzewa rozpinające. Twierdzenie Cayley'a.	W9	MEK02 MEK04
2	TK07	Grafy planarne, kryteria planarności grafów. Kolorowanie grafów. Wielomian chromatyczny grafu.	W10, W11	MEK02
2	TK08	Niezależność i dominowanie w grafie. Zbiory niezależne wierzchołkowo i krawędziowo. Zbiory dominujące. Algorytmy boolowskie wyznaczające maksymalne zbiory niezależne i minimalne zbiory dominujące grafów.	W12	MEK02 MEK03

Nakład pracy studenta

Forma zajęć	Praca przed zajęciami	Udział w zajęciach	Praca po zajęciach
Wykład (sem. 2)	Przygotowanie do kolokwium: 15.00 godz./sem.	Godziny kontaktowe: 25.00 godz./sem.	Uzupełnienie/studiowanie notatek: 15.00 godz./sem. Studiowanie zalecanej literatury: 15.00 godz./sem.
Laboratorium (sem. 2)	Przygotowanie do laboratorium: 12.00 godz./sem. Przygotowanie do kolokwium: 10.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.
Konsultacje (sem. 2)	Przygotowanie do konsultacji: 2.00 godz./sem.	Udział w konsultacjach: 4.00 godz./sem.
Egzamin (sem. 2)	Przygotowanie do egzaminu: 10.00 godz./sem.	Egzamin pisemny: 2.00 godz./sem.

Sposób wystawiania ocen składowych zajęć i oceny końcowej

Forma zajęć	Sposób wystawiania oceny podsumowującej
Wykład	Egzamin pisemny
Laboratorium	Warunkiem uzyskania zaliczenia jest zaliczenie wszystkich umiejętności, sformułowanych w warunkach zaliczania modułu co najmniej na ocenę dst
Ocena końcowa	Warunkiem zaliczenia przedmiotu jest zdanie egzaminu, który odbywa się w formie pisemnej.

Przykładowe zadania

Wymagane podczas egzaminu/zaliczenia
(-)

Realizowane podczas zajęć ćwiczeniowych/laboratoryjnych/projektowych
(-)

Inne
(-)

Czy podczas egzaminu/zaliczenia student ma możliwość korzystania z materiałów pomocniczych : nie

Treści zajęć powiazane są z prowadzonymi badaniami naukowymi: nie