Cel kształcenia i wykaz literatury

Główny cel kształcenia: Głównym celem tego modułu kształcenia jest zapoznanie studentów z podstawami teoretycznymi z zakresu teorii grafów i kombinatoryki oraz pokazanie dużego oddziaływania tych działów matematyki na algorytmy grafowe i kombinatoryczne, które stanowią dział informatyki.

Ogólne informacje o zajęciach: Matematyka dyskretna zajmuje ważne miejsce w informatyce. 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

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: podstawowe wiadomości z algebry i teorii macierzy

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

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

Wymagania wstępne w kategorii Kompetencji społecznych: gotowość do współpracy w zespole

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 właściwości permutacji i zna algorytm ich generowania.	wykład, laboratorium	kolokwium, egzamin cz. pisemna	K_W01++	T1A_W01+
02	potrafi rozwiązywać równania rekurencyjne liniowe	wykład, laboratorium	kolokwium, egzamin cz. pisemna	K_W01++	T1A_W01+
03	zna podstawowe definicje i twierdzenia teorii grafów	wykład, laboratorium	kolokwium, egzamin cz. pisemna	K_W01++ K_U03+	T1A_W01++ T1A_U05++
04	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_W01++ K_K05+	T1A_W01+ T1A_K03+
05	potrafi wyznaczyć drzewo z kodu Prufera oraz wyznaczać liczbę wszystkich drzew rozpinających grafu, wykorzystując rachunek macierzowy	wykład, laboratorium	kolokwium, egzamin cz. pisemna	K_W01++ K_U03+	T1A_W01+ T1A_U05

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.	W01, W02	MEK01
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	MEK01
2	TK03	Zależności rekurencyjne. Metody rozwiązywania równań rekurencyjnych. Liczby Fibonacciego, liczby Lucasa i ich własności.	W05	MEK02
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	MEK03
2	TK05	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.	W08	MEK03 MEK04
2	TK06	Charakteryzacje drzew, drzewa binarne, drzewa rozpinające. Twierdzenie Cayley'a.	W9	MEK03 MEK05
2	TK07	Grafy planarne, kryteria planarności grafów. Kolorowanie grafów. Wielomian chromatyczny grafu.	W10, W11	MEK03
2	TK08	Drogi i cykle w grafach. Odległość w grafie. Spójność grafu. Grafy Eulera i grafy Hamiltona.	W12	MEK03 MEK05

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: 5.00 godz./sem.	Godziny kontaktowe: 25.00 godz./sem.	Uzupełnienie/studiowanie notatek: 15.00 godz./sem. Studiowanie zalecanej literatury: 10.00 godz./sem.
Laboratorium (sem. 2)	Przygotowanie do laboratorium: 10.00 godz./sem. Przygotowanie do kolokwium: 10.00 godz./sem. Inne: 15.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.	Dokończenia/wykonanie sprawozdania: 5.00 godz./sem.
Konsultacje (sem. 2)	Przygotowanie do konsultacji: 1.00 godz./sem.	Udział w konsultacjach: 2.00 godz./sem.
Egzamin (sem. 2)	Przygotowanie do egzaminu: 10.00 godz./sem.	Egzamin pisemny: 2.00 godz./sem. Egzamin ustny: 1.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	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 : tak

Dostępne materiały : W trakcie egzaminu student może korzystać z notatek sporządzonych na wykładzie lub laboratorium, ale tylko w postaci papierowej. Na egzaminie nie można korzystać ze smartfonu.

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