Cel kształcenia i wykaz literatury

Główny cel kształcenia: Celem kursu jest zapoznanie studentów z podstawowymi metodami matematyki dyskretnej.

Ogólne informacje o zajęciach:

Wykaz literatury, wymaganej do zaliczenia zajęć

Literatura wykorzystywana podczas zajęć wykładowych

1	A. Włoch, I. Włoch	Matematyka dyskretna	Oficyna Wydawnicza Politechniki Rzeszowskiej, Rzeszów .	2004
2	K. Ross, Ch. Wright	Matematyka dyskretna	PWN Warszawa.	1996

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

1

R. J. Wilson

Wprowadzenie do teorii grafów

PWN Warszawa.

2000

Literatura do samodzielnego studiowania

1

R. Diestel

Graph Theory

Springer-Verlag, Heidelberg, New York.

2005

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

Wymagania formalne: Zaliczenie kursu analizy matematycznej i algebry.

Wymagania wstępne w kategorii Wiedzy: Opanowanie podstaw analizy matematycznej i rachunku macierzowego.

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	Zna podstawowe obiekty kombinatoryczne, ich liczbę i sposoby generowania.	wykład, ćwiczenia problemowe	zaliczenie cz. pisemna	K_U029+
02	Zna podstawowe pojęcia, twierdzenia i algorytmy teorii grafów.	wykład, ćwiczenia problemowe	zaliczenie cz. pisemna	K_U029+
03	Umie rozpatrywać obiekty kombinatoryczne w trzech aspektach: istnienia, liczby i systematycznego generowania.	ćwiczenia problemowe	zaliczenie cz. pisemna	K_U029+
04	Potrafi zbudować model problemu i rozwiązać problem dyskretny.	ćwiczenia problemowe	zaliczenie cz. pisemna	K_U029+++
05	Potrafi używać programu do wykonania obliczeń, generowania obiektów kombinatorycznych lub tworzenia modelu - w stopniu podstawowym.	ćwiczenia problemowe	zaliczenie cz. pisemna	K_U029+++

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	Indukcja matematyczna. Równania rekurencyjne.	W01, C01	MEK03 MEK04 MEK05
2	TK02	Obiekty kombinatoryczne, reprezentacja obiektów kombinatorycznych, generowanie i zliczanie obiektów kombinatorycznych.	W02, W03, C01, C02	MEK01 MEK02 MEK03 MEK04 MEK05
2	TK03	Funkcje tworzące.	W04, C02	MEK02 MEK04 MEK05
2	TK04	Pojecie grafu, interpretacja geometryczna. Podstawowe definicje i oznaczenia teorii grafów. Rodzaje grafu, potęga i dopełnienie grafu, grafy ważone, produkty dwóch grafów. Izomorfizm grafów. Macierzowa reprezentacja grafu: macierz sąsiedztw, macierz incydencji.	W05, W06, C03	MEK01 MEK03 MEK04 MEK05
2	TK05	Drogi i cykle w grafach.	W07, W08, C04	MEK02 MEK03 MEK04 MEK05
2	TK06	Drzewa. Definicje i podstawowe własności. Drzewa binarne. Metody kodowania drzew, twierdzenie Cayley’a.	W09, C05	MEK01 MEK02 MEK03 MEK04 MEK05
2	TK07	Drzewa rozpinające, metody wyznaczania minimalnego drzewa rozpinającego.	W10, C05	MEK01 MEK02 MEK03 MEK04 MEK05
2	TK08	Topologiczna teoria grafów. Grafy planarne. Grafy na powierzchniach.	W11, C06	MEK02 MEK04 MEK05
2	TK09	Niezależność w grafie. Zbiory niezależne. Skojarzenia.	W12, W13, C07	MEK01 MEK02 MEK03 MEK04 MEK05
2	TK10	Kolorowanie grafów. Kolorowanie wierzchołków. Kolorowanie krawędzi.	W14, W15, C08	MEK01 MEK02 MEK03 MEK04 MEK05

Nakład pracy studenta

Forma zajęć	Praca przed zajęciami	Udział w zajęciach	Praca po zajęciach
Wykład (sem. 2)		Godziny kontaktowe: 30.00 godz./sem.
Ćwiczenia/Lektorat (sem. 2)	Przygotowanie do ćwiczeń: 10.00 godz./sem. Przygotowanie do kolokwium: 5.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.	Dokończenia/studiowanie zadań: 15.00 godz./sem.
Konsultacje (sem. 2)	Przygotowanie do konsultacji: 1.00 godz./sem.	Udział w konsultacjach: 1.00 godz./sem.
Zaliczenie (sem. 2)	Przygotowanie do zaliczenia: 5.00 godz./sem.	Zaliczenie pisemne: 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	Praca pisemna.
Ćwiczenia/Lektorat	Praca pisemna.
Ocena końcowa

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