Cel kształcenia i wykaz literatury

Główny cel kształcenia: Celem tego modułu kształcenia jest zapoznanie studentów z podstawowymi metodami matematycznymi stosowanymi do analizy i rozwiązywania zadań matematyki komputerowej, zwanej dyskretną. Materiał dydaktyczny, realizowany w ramach tego przedmiotu, można podzielić na dwie zasadnicze części: kombinatorykę i teorię grafów. Studenci poznają definicje, właściwości i metody zliczania wybranych obiektów kombinatorycznych oraz niektóre zagadnienia teorii grafów, ilustrowane algorytmami.

Ogólne informacje o zajęciach: Priorytetem nauczania tego przedmiotu jest zwrócenie uwagi studentów na duże znaczenie matematyki w informatyce, w szczególności kombinatoryki i teorii grafów. Chociaż te działy matematyki można studiować w oderwaniu od informatyki, gdyż z powodzeniem istniały zanim pojawiły się komputery, to jednak dopiero połączenie technik komputerowych z teorią grafów i kombinatoryką przyczyniło się do dynamicznego rozwoju tych i jeszcze innych obszarów matematyki. Efektem tych wysiłków było opracowanie wielu nowych algorytmów, które znalazły zastosowanie do rozwiązywania problemów w różnych dziedzinach życia i techniki.

Materiały dydaktyczne: na stronie pei.prz.edu.pl - dostępne po zalogowaniu - login i hasło zostaną podane na laboratorium

Inne: mathworld.wolfram.com/topics/DiscreteMathematics.html

Wykaz literatury, wymaganej do zaliczenia zajęć

Literatura wykorzystywana podczas zajęć wykładowych

1	Kenneth A. Ross, Charles R. B. Wright	Matematyka Dyskretna	Wydawnictwo naukowe PWN.	2012
2	Victor Bryant	Aspekty kombinatoryki	WNT, Warszawa.	2007
3	J. Wojciechowski, K. Pieńkosz	Grafy i sieci	PWN, Warszawa.	2013
4	R. J. Wilson	Wprowadzenie do teorii grafów	PWN, Warszawa.	2012
5	Zbignie Palka, Andrzej Ruciński	Wykłady z kombinatoryki	WNT, Warszawa.	1998

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

1	A. Szczepański	Biblioteka kombinatoryczno-grafowa dla programu Maxima	opracowanie prywatne.	2021
2	R. Dmytryszyn, G. Drałus	Matematyka dyskretna	Oficyna Wydawnicza PRz.	2002
3	Witold Lipski	Kombinatoryka dla programistów	WNT.	2009
4	Jerzy Wałaszek	grafy: http://eduinf.waw.pl/inf/alg/001_search/0122.php	Tarnów.	2017

Literatura do samodzielnego studiowania

1	Kenneth A. Ross, Charles R. B. Wright	Matematyka dyskretna	PWN.	2012
2		https://discrete.openmathbooks.org/more/mdm/ch_basic-combinatorics.html	.

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

Wymagania formalne: rejestracja na drugi semestr studiów inżynierskich

Wymagania wstępne w kategorii Wiedzy: opanowanie podstaw algebry i rachunku macierzowego

Wymagania wstępne w kategorii Umiejętności: umiejętność logicznego i algorytmicznego myślenia oraz zmysł kombinatoryczny

Wymagania wstępne w kategorii Kompetencji społecznych: gotowość do systematycznej pracy i wytrwałość

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 PRK
01	zna różne sposoby zapisu permutacji oraz umie obliczać liczbę permutacji danego typu, znak permutacji oraz potrafi rozkładać permutacje na transpozycje i rozwiązywać równanie permutacyjne	wykład, ćwiczenia rachunkowe, laboratorium	zaliczenie pisemne, sprawdzian pisemny, sprawozdanie z laboratorium	K_W01++ K_U02++ K_K04+	P6S_KO P6S_KR P6S_UO P6S_UW P6S_WG
02	zna definicje podstawowych obiektów kombinatorycznych, potrafi je rozróżniać oraz zna podstawowe techniki zliczania takich obiektów i potrafi je stosować do rozwiązywania prostych zadań tekstowych	wykład, ćwiczenia rachunkowe, laboratorium	zaliczenie pisemne, sprawozdanie z laboratorium	K_W01++ K_U02++ K_K04+	P6S_KO P6S_KR P6S_UO P6S_UW P6S_WG
03	potrafi rozwiązywać jednorodne równania rekurencyjne liniowe pierwszego i drugiego rzędu metodą równania charakterystycznego oraz niejednorodne równania rekurencyjne liniowe pierwszego i drugiego rzędu metodą przewidywań	wykład, ćwiczenia rachunkowe, laboratorium	sprawdzian pisemny, sprawozdanie z laboratorium	K_W01++ K_U02++ K_K04+	P6S_KO P6S_KR P6S_UO P6S_UW P6S_WG
04	potrafi zastosować arytmetykę boolowską do znajdywania maksymalnych zbiorów niezależnych wierzchołków i krawędzi, minimalnych pokryć wierzchołkowych i krawędziowych, minimalnych zbiorów dominujących	wykład, ćwiczenia rachunkowe, laboratorium	sprawdzian pisemny, sprawozdanie z laboratorium	K_W01++ K_U02++ K_K04+	P6S_KO P6S_KR P6S_UO P6S_UW P6S_WG
05	potrafi wyznaczyć drzewo z kodu Prufera, umie obliczyć liczbę drzew rozpinających wykorzystując rachunek macierzowy, zna algorytmy Prima i Kruskala wyznaczania minimalnego drzewa rozpinającego	wykład, ćwiczenia rachunkowe, laboratorium	sprawdzian pisemny, sprawozdanie z laboratorium	K_W01++ K_U02++ K_K04+	P6S_KO P6S_KR P6S_UO P6S_UW P6S_WG
06	potrafi metodą graficzną wyznaczyć wielomian chromatyczny grafu, a następnie jego liczbę chromatyczną i indeks chromatyczny oraz umie obliczać liczbę prawidłowych kolorowań jego wierzchołków i krawędzi	wykład, ćwiczenia rachunkowe, laboratorium	egzamin pisemny, zaliczenie pisemne, sprawozdanie z laboratorium	K_W01++ K_U02++ K_K04+	P6S_KO P6S_KR P6S_UO P6S_UW P6S_WG
07	zna twierdzenia rozstrzygające o istnieniu w grafie cyklów Eulera oraz Hamiltona	wykład, ćwiczenia rachunkowe	egzamin ustny	K_W01++ K_U02++ K_K04+	P6S_KO P6S_KR P6S_UO P6S_UW P6S_WG
08	zna twierdzenia dotyczące grafów płaskich oraz grafów na powierzchniach	wykład, ćwiczenia rachunkowe	sprawdzian pisemny	K_W01++ K_U02++ K_K04+	P6S_KO P6S_KR P6S_UO P6S_UW P6S_WG

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	Definicja permutacji. Metody zapisu permutacji (funkcyjny, jedno- i dwuwierszowy, macierzowy, cyklowy, grafowy). Złożenie dwóch lub więcej permutacji. Transpozycja jako najprostsza permutacja. Przedstawienie permutacji w postaci złożenia transpozycji sąsiednich i niesąsiednich elementów. Permutacja odwrotna. Typ permutacji. Potęga i rząd permutacji. Liczba permutacji określonego typu. Permutacje nieporządki. Permutacje samoodwrotne - inwolucje. Permutacje parzyste i nieparzyste - znak permutacji i sposoby jego obliczania. Równania permutacyjne.	W1, W2, C1, L1, L2	MEK01
2	TK02	Podstawowe techniki zliczania. Permutacje bez powtórzeń i z powtórzeniami. Kombinacje bez powtórzeń i z powtórzeniami. Wariacje bez powtórzeń i z powtórzeniami. Uporządkowane podziały zbioru. Podziały liczby. Kompozycje liczby. Zliczanie rozmieszczeń kul w pudełkach i dróg w kracie. Zasada włączania/wyłączania. Liczby Stirlinga pierwszego i drugiego rodzaju.	W3, W4, C2, L3	MEK02
2	TK03	Równania rekurencyjne jednorodne i niejednorodne. Równanie charakterystyczne równania rekurencyjnego. Metoda przewidywań dla równania niejednorodnego. Przewidywanie rozwiązania szczególnego w przypadku, gdy funkcja niejednorodności jest iloczynem funkcji potęgowej i wielomianu. Rozwiązywanie problemów zliczania poprzez sprowadzenie ich do równania rekurencyjnego. Zliczanie permutacji, liczby ruchów potrzebnych do ułożenia wież Hanoi, zliczanie obszarów płaszczyzny, kompozycji liczby, podziałów zbioru.	W5, W6, C3, L4	MEK03
2	TK04	Systemy reprezentantów ciągu podzbiorów. Definicja permanentu i sposoby jego obliczania. Rozwinięcie metodą Laplace'a. Wzór Rysera na obliczanie permanentu macierzy 0-1. Algorytm generowania wszystkich transversal. Zastosowanie permanentu do zliczania wariacji bez powtórzeń z ograniczeniami na występowanie liczb na danych pozycjach w wariacji oraz do zliczania rozmieszczeń wież na szachownicy z zabronionymi polami.	W7, C4	MEK02
2	TK05	Niezależność w grafie. Zbiory niezależne wierzchołków i minimalne pokrycia wierzchołkowe. Wyznaczanie maksymalnych zbiorów niezależnych metodą algebry Boole'a. Niezależność krawędzi - skojarzenia. Minimalne zbiory dominujące wierzchołków. Minimalne pokrycia krawędziowe. Wyznaczanie pełnego skojarzenia w grafie dwudzielnym metodą drogi powiększającej.	W8, W9, C5, L5	MEK04
2	TK06	Definicja i podstawowe własności drzew. Drzewa binarne. Metody kodowania drzew - prosty i odwrotny kod Prufera. Twierdzenie Cayley’a o liczbie drzew grafu pełnego Kn. Drzewa rozpinające grafu. Metody wyznaczania minimalnego drzewa rozpinającego (algorytm Prima i Kruskala). Wyznaczanie liczby drzew rozpinających grafu prostego w oparciu o macierz Laplace'a.	W10, W11, C6, L6	MEK05
2	TK07	Kolorowanie grafów. Prawidłowe kolorowanie wierzchołków grafu. Liczba chromatyczna i wielomian chromatyczny grafu. Kolorowanie krawędzi - indeks chromatyczny. Wyznaczanie wielomianu chromatycznego metodami usuwania i dodawania krawędzi.	W12, W13, C7, L7	MEK06
2	TK08	Drogi i cykle w grafach. Wyznaczanie liczby dróg określonej długości za pomocą macierzy sąsiedztw. Warunki istnienia cykli Eulera i Hamiltona. Problem chińskiego listonosza. Algorytm Flaury'ego dla cyklu Eulera.	W14, C8	MEK07
2	TK09	Topologiczna teoria grafów. Grafy planarne. Twierdzenia Eulera dla grafów płaskich. Grafy na powierzchniach.	W15	MEK08

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.	Uzupełnienie/studiowanie notatek: 5.00 godz./sem. Studiowanie zalecanej literatury: 5.00 godz./sem.
Ćwiczenia/Lektorat (sem. 2)	Przygotowanie do ćwiczeń: 3.50 godz./sem. Przygotowanie do kolokwium: 6.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.	Dokończenia/studiowanie zadań: 3.50 godz./sem.
Laboratorium (sem. 2)	Przygotowanie do kolokwium: 5.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.	Dokończenia/wykonanie sprawozdania: 8.00 godz./sem. Inne: 7.00 godz./sem.
Konsultacje (sem. 2)
Zaliczenie (sem. 2)

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

Forma zajęć	Sposób wystawiania oceny podsumowującej
Wykład	za obecność i aktywność
Ćwiczenia/Lektorat	za sprawdziany i aktywność na zajęciach
Laboratorium	za sprawozdania
Ocena końcowa	Przedmiot nie kończy się egzaminem, ale będzie zaliczenie wykładu. Na ocenę końcową z przedmiotu mają wpływ w równym stopniu oceny końcowe z wykładu, ćwiczeń i laboratorium komputerowego. Jeżeli ćwiczenia i laboratorium zaliczono (każde z osobna) na co najmniej 3,0, wówczas cały przedmiot będzie zaliczony. W razie wątpliwości, co do oceny końcowej, student zostanie przepytany ustnie przez koordynatora tego przedmiotu.

Przykładowe zadania

Wymagane podczas egzaminu/zaliczenia
(-)

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

Inne
Zadania.pdf
Zadania.pdf

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

Dostępne materiały : Student może na egzaminie korzystać z notatek sporządzonych na wykładach, ćwiczeniach i laboratoriach. Zabrania się korzystać z laptopa, tableta i smartfona. Można używać sprzętowego kalkulatora.

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