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 problemami teorii grafów i kombinatoryki oraz metodami ich rozwiązywania; zostaną również przedstawione wybrane algorytmy kombinatoryczne i grafowe, które zajmują ważne miejsce w informatyce.

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	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
3	A. Szczepański	Dokumentacja biblioteki procedur i funkcji kombinatoryczno-grafowych dla programu Maxima.	.	2020

Literatura do samodzielnego studiowania

1

K.A. Ross, Ch. R. B. Wright

Matematyka dyskretna

PWN, Warszawa.

2012

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 zna algorytm systematycznego ich generowania.	wykład, ćwiczenia rachunkowe, laboratorium	egzamin pisemny, kolokwium, sprawozdanie z laboratorium	K_W01++ K_U03+ K_K05+	P6S_KO P6S_UO P6S_UW P6S_WG
02	potrafi zastosować algorytm węgierski do rozwiązania zagadnienia optymalnego przydziału	wykład interaktywny, ćwiczenia rachunkowe, laboratorium	egzamin pisemny, kolokwium, sprawozdanie z laboratorium	K_W01++ K_U03+ K_K05+	P6S_KO P6S_UO P6S_UW P6S_WG
03	potrafi rozwiązywać równania rekurencyjne liniowe	wykład, ćwiczenia rachunkowe	egzamin pisemny, kolokwium, sprawozdanie z laboratorium	K_W01++ K_U03+ K_K05+	P6S_KO 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 - część pisemna, kolokwium, sprawozdanie z laboratorium	K_W01++ K_U03+ K_K05+	P6S_KO 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 - część pisemna, kolokwium, sprawozdanie z laboratorium	K_W01++ K_U03+ K_K05+	P6S_KO P6S_UO P6S_UW P6S_WG
06	Potrafi wyznaczać wielomian chromatyczny grafu, jego liczbę chromatyczną oraz obliczać liczbę kolorowań jego wierzchołków i krawędzi	wykład interaktywny, ćwiczenia rachunkowe	sprawdzian pisemny, egzamin pisemny, sprawozdanie z lab.	K_W01++ K_U03+ K_K05+	P6S_KO 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, typy, znak, permutacja odwrotna, składanie permutacji, transpozycja, inwolucja, zapis permutacji w postaci złożenia transpozycji. Wyznaczanie liczby permutacji określonego typu. Komputerowe generowanie permutacji. Zastosowania permutacji.	W01, W02, C01, L01	MEK01
2	TK02	Zagadnienie optymalnego przydziału pracowników do prac. Algorytm węgierski - różne przypadki macierzy kosztów (kwadratowa, prostokątna). Minimalizacja kosztu i maksymalizacja zysku. Związek zagadnienia optymalnego przydziału ze skojarzeniami w grafie ważonym. Systemy reprezentantów ciągu zbiorów - transwersale. Permanent macierzy. Metody obliczania permanentu: z definicji, metodą Rysera, metodą Laplace'a. Permanent macierzy pełnej jedynek oraz z zerami na przekątnej.	W03, W04, L02	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.	W05, W06, C02	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.	W07, W08, C03, L03	MEK04
2	TK05	Charakteryzacje drzew, drzewa binarne, drzewa rozpinające, drzewa oznakowane i nieoznakowane. Twierdzenie Cayley'a. Kod Prufera. Minimalne drzewa rozpinające. Algorytmy Prima i Kruskala.	W09, W10, C04, L04	MEK05
2	TK06	Kolorowanie wierzchołków grafu. Wielomian chromatyczny grafu. Liczba chromatyczna grafu. Kolorowanie krawędzi grafu. Indeks chromatyczny grafu. Zliczanie kolorowań.	W11, C05, L05	MEK06
2	TK07	Drogi i cykle w grafach. Odległość w grafie. Spójność grafu. Grafy Eulera i grafy Hamiltona.	W12

Nakład pracy studenta

Forma zajęć	Praca przed zajęciami	Udział w zajęciach	Praca po zajęciach
Wykład (sem. 2)		Godziny kontaktowe: 25.00 godz./sem.	Uzupełnienie/studiowanie notatek: 10.00 godz./sem. Studiowanie zalecanej literatury: 10.00 godz./sem.
Ćwiczenia/Lektorat (sem. 2)	Przygotowanie do ćwiczeń: 5.00 godz./sem. Przygotowanie do kolokwium: 10.00 godz./sem.	Godziny kontaktowe: 10.00 godz./sem.	Dokończenia/studiowanie zadań: 5.00 godz./sem.
Laboratorium (sem. 2)	Przygotowanie do laboratorium: 5.00 godz./sem. Przygotowanie do kolokwium: 5.00 godz./sem. Inne: 10.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.	Dokończenia/wykonanie sprawozdania: 15.00 godz./sem.
Konsultacje (sem. 2)	Przygotowanie do konsultacji: 1.00 godz./sem.	Udział w konsultacjach: 1.00 godz./sem.
Egzamin (sem. 2)	Przygotowanie do egzaminu: 10.00 godz./sem.	Egzamin pisemny: 2.00 godz./sem. Inne: 1.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 kilku krótkich sprawdzianów.
Laboratorium	Na podstawie sprawozdań z zajęć i krótkich sprawdzianów.
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.

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 lub laboratoriach, ale tylko w postaci papierowej. Nie może korzystać ze smartfona ani innego komputera. Moż

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