Cel kształcenia i wykaz literatury

Główny cel kształcenia: Głównym celem tego modułu kształcenia jest zapoznanie studentów z podstawowymi pojęciami kombinatoryki i teorii grafów oraz matematycznymi metodami stosowanymi w tych obszarach. W ramach laboratorium studenci poznają metody komputerowe badania obiektów kombinatorycznych oraz grafów.

Ogólne informacje o zajęciach: Matematyka dyskretna to dział matematyki ściśle związany z informatyką. Stosowana jest, przede wszystkim, do analizy złożoności algorytmów. Dostarcza również twierdzeń i aparatu matematycznego do projektowania algorytmów, w szczególności algorytmów grafowych. Wyewoluowała z różnych działów algebry i kombinatoryki. Rozwinęła się mocno pod koniec ubiegłego wieku w związku z upowszechnieniem komputerów, jako narzędzi do rozwiązywania problemów naukowych i technicznych.

Materiały dydaktyczne: pei.prz.edu.pl - w zakladce Dydaktyka->Materiały dla studentów

Inne: http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1

Wykaz literatury, wymaganej do zaliczenia zajęć

Literatura wykorzystywana podczas zajęć wykładowych

1	R. J. Wilson	Wprowadzenie do teorii grafów	PWN, Warszawa.	2007
2	A. Włoch, I. Włoch	Marematyka dyskretna	Oficyna Wydawnicza PRz.	2008
3	Kenneth A. Ross, Charles R.B. Wright	Matematyka Dyskretna	Wydawnictwo Naukowe PWN, Warszawa.	2012

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

1

A. Szczepański

Dokumentacja biblioteki procedur i funkcji kombinatoryczno-grafowych dla programu Maxima.

opracowanie własne.

2021

Literatura do samodzielnego studiowania

1	N. Deo	Teoria grafów i jej zastosowania w technice i infromatyce	PWN, Warszawa.	1980
2	Witold Lipski	Kombinatoryka dla programistów	WNT, Warszawa.	2004
3	Victor Bryant	Apsekty kombinatoryki	Wydanie drugie.

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

Wymagania formalne: rejestracja na drugi semestr studiów

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

Wymagania wstępne w kategorii Umiejętności: umiejętność logicznego rozumowania i wnioskowania, zdolność kombinatorycznego myślenia

Wymagania wstępne w kategorii Kompetencji społecznych: gotowość do systematycznej pracy, wytrwałość w dążeniu do celu

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 podstawowe właściwości permutacji i potrafi rozwiązywać zadania związane z tym tematem	wykład, ćwiczenia rachunkowe, laboratorium	egzamin pisemny, sprawozdanie z laboratorium	K_W01++ K_U02+ K_K04+	P6S_KO P6S_KR P6S_UO P6S_UW P6S_WG
02	zna podstawowe techniki zliczania obiektów kombinatorycznych i potrafi je praktycznie stosować do rozwiązywania zadań	wykład, ćwiczenia rachunkowe, laboratorium	egzamin pisemny, sprawozdanie z laboratorium	K_W01++ K_U02+ K_K04+	P6S_KO P6S_KR P6S_UO P6S_UW P6S_WG
03	potrafi rozwiązywać jednorodne i niejednorodne równania rekurencyjne liniowe pierwszego i drugiego rzędu	wykład, ćwiczenia rachunkowe	raport pisemny	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 w grafach	wykład, ćwiczenia rachunkowe, laboratorium	egzamin 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ę wszystkich drzew rozpinających grafu, wykorzystując rachunek macierzowy; zna algorytmy Prima i Kruskala wyznaczania minimalnego drzewa rozpinającego	wykład, ćwiczenia rachunkowe, laboratorium	egzamin pisemny, sprawozdanie z laboratorium	K_W01++ K_U02+ K_K04+	P6S_KO P6S_KR P6S_UO P6S_UW P6S_WG
06	potrafi wyznaczyć wielomian chromatyczny grafu, jego liczbę chromatyczną oraz obliczać liczbę kolorowań jego wierzchołków i krawędzi	wykład, ćwiczenia rachunkowe, laboratorium	egzamin pisemny, sprawozdanie z laboratorium	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	Permutacje: metody zapisu, rodzaje, pojęcie typu, permutacja odwrotna, składanie permutacji, potęgowanie permutacji, transpozycja jako najprostsza permutacja, inwolucja, zapis permutacji w postaci złożenia transpozycji, permutacje parzyste i nieparzyste, znak permutacji i sposoby jego obliczania, rząd permutacji, grupa permutacji, równania permutacyjne i sposoby jego rozwiązywania. Wyznaczanie liczby permutacji określonego typu oraz liczby permutacji spełniających zadany warunek logiczny. Zastosowania permutacji.	W1, W2, C1, L1	MEK01
2	TK02	Podstawowe techniki zliczania. Podzbiory zbioru. Kombinacje bez powtórzeń i z powtórzeniami. Permutacje bez powtórzeń i z powtórzeniami. Wyznaczanie liczby rozmieszczeń kul w pudełkach i dróg w kracie. Uporządkowane i nieuporządkowane podziały zbioru. Zasad włączeń i wyłączeń.	W3, W4, C2, L2	MEK02
2	TK03	Liniowe zależności rekurencyjne jednorodne i niejednorodne. Metody rozwiązywania równań rekurencyjnych. Metoda przewidywań i metoda równania charakterystycznego. Liczby Fibonacciego, liczby Lucasa i ich własności.	W5, W6, C3	MEK03
2	TK04	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.	W7, C4, L3	MEK04
2	TK05	Definicja drzewa, rodzaje drzew, drzewa binarne, drzewa rozpinające, drzewa oznakowane i nieoznakowane. Twierdzenie Cayley'a o liczbie drzew rozpinających grafu pełnego. Prosty i dowrotny kod Prufera dla drzewa. Minimalne drzewa rozpinające w grafie ważonym. Algorytmy Prima i Kruskala. Macierzowa i graficzna metody wyznaczania liczby drzew rozpinających.	W8, C4, L4	MEK05
2	TK06	Prawidłowe kolorowanie wierzchołków grafu. Liczba chromatyczna grafu. Liczby chromatyczne popularnych rodzin grafów. Wielomian chromatyczny grafu. Właściwości wielomianu chromatycznego. Graficzna metoda wyznaczania wielomianu chromatycznego. Wielomiany chromatyczne popularnych rodzin grafów. Kolorowanie krawędzi grafu. Indeks chromatyczny grafu. Kolorowanie krawędzi jako kolorowanie wierzchołków grafu krawędziowego. Wyznaczanie liczby prawidłowych kolorowań wierzchołków oraz krawędzi grafu za pomocą dokładnie k kolorów.	W9, W10, C5, L5	MEK06

Nakład pracy studenta

Forma zajęć	Praca przed zajęciami	Udział w zajęciach	Praca po zajęciach
Wykład (sem. 2)		Godziny kontaktowe: 20.00 godz./sem.	Uzupełnienie/studiowanie notatek: 10.00 godz./sem. Studiowanie zalecanej literatury: 5.00 godz./sem.
Ćwiczenia/Lektorat (sem. 2)	Przygotowanie do ćwiczeń: 5.00 godz./sem. Przygotowanie do kolokwium: 5.00 godz./sem.	Godziny kontaktowe: 10.00 godz./sem.	Dokończenia/studiowanie zadań: 5.00 godz./sem.
Laboratorium (sem. 2)	Przygotowanie do kolokwium: 5.00 godz./sem.	Godziny kontaktowe: 10.00 godz./sem.	Dokończenia/wykonanie sprawozdania: 15.00 godz./sem. Inne: 15.00 godz./sem.
Konsultacje (sem. 2)
Egzamin (sem. 2)	Przygotowanie do egzaminu: 10.00 godz./sem.	Inne: 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	Na podstawie egzaminu pisemnego.
Ćwiczenia/Lektorat	Na podstawie jednego sprawdzianu.
Laboratorium	Na podstawie sprawozdań zawierających obliczenia ręczne i wyniki komputerowe.
Ocena końcowa	Warunkiem zaliczenia przedmiotu jest pozytywne zaliczenie ćwiczeń i laboratoriów, a następnie zdanie egzaminu, który odbywa się w formie pisemnej. Ocena końcowa w równym stopniu zależy od tych trzech ocen cząstkowych.

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 : tak

Dostępne materiały : W trakcie egzaminu student może korzystać z notatek sporządzonych na wykładach, ćwiczeniach oraz laboratoriach, ale tylko w postaci papierowej. Nie może korzystać ze smartfona ani innego komputera.

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