Cel kształcenia i wykaz literatury

Główny cel kształcenia: dostarczyć studentom metod matematycznych, które w połączeniu z programowaniem komputerów będą stanowić skuteczne narzędzie rozwiązywania problemów kombinatorycznych lub grafowych

Ogólne informacje o zajęciach: Celem tego modułu kształcenia jest rozszerzenie, pogłębienie wiedzy i umiejętności w zakresie wybranych obiektów kombinatorycznych i metod matematycznych mających związek z informatyką, a poznanych na studiach pierwszego stopnia.

Materiały dydaktyczne: http://www.pei.prz.rzeszow.pl/dydaktyka.html Dysk P: MatDys

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

Wykaz literatury, wymaganej do zaliczenia zajęć

Literatura wykorzystywana podczas zajęć wykładowych

1	Deo N.	Teoria grafów i jej zastosowania w technice i informatyce	,, PWN, Warszawa , s. 607,.	1980
2	Włoch A., Włoch I.	Matematyka dyskretna (podstawowe metody i algorytmy teorii grafów)	Oficyna wydawnicza PRz, s.154,.	2004

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

1

Dmytryszyn R., Drałus G.

Matematyka Dyskretna (materiały pomocnicze)

Oficyna Wydawnicza PRz, s.125.

2003

Literatura do samodzielnego studiowania

1

Sysło M.

Algorytmy,

WSiP, Warszawa.

1997

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

Wymagania formalne: rozwiązywanie równań algebraicznych, rozumienie obiektów kombinatorycznych: zbiory, wariacje, kombinacje, permutacje

Wymagania wstępne w kategorii Wiedzy: ma wiedzę w zakresie algebry, równań matematycznych oraz komputerowych obliczeń

Wymagania wstępne w kategorii Umiejętności: potrafi wykonywać zadania określone w sposób algorytmiczny, ma dobrze rozwinięty zmysł kombinatoryczny

Wymagania wstępne w kategorii Kompetencji społecznych: ma świadomość odpowiedzialności za pracę własną oraz gotowość podporządkowania się zasadom 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	Umie stosować funkcje tworzące do badania ciągów liczbowych i w zagadnieniach zliczania.	wykład problemowy, laboratorium	sprawdzian pisemny, egzamin cz. pisemna	K_W01+ K_K03+	T2A_W01++ T2A_K06+
02	Zna różne właściwości permutacji i potrafi wykonywać obliczenia z nimi związane.	wykład problemowy, laboratorium	sprawdzian pisemny, egzamin cz. pisemna	K_W01++	T2A_W01++
03	Potrafi zliczać i algorytmicznie generować wybrane obiekty kombinatoryczne (podziały liczby, zbioru, itp.).	wykład problemowy, laboratorium	sprawdzian pisemny, egzamin cz. pisemna	K_W01++ K_U07+	T2A_W01++ T2A_U07+
04	Potrafi rozwiązywać niejednorodne równania rekurencyjne.	wykład problemowy, laboratorium	sprawdzian pisemny, egzamin cz. pisemna	K_W01++	T2A_W01++

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
1	TK01	Permutacje. Sposoby zapisu (jedno- i dwuwierszowy, cyklowy, macierzowy, grafowy). Cykle rozłączne i nierozłączne. Permutacja odwrotna, Złożenie permutacji. Znak permutacji. Transpozycja jako najprostsza permutacja. Znak transpozycji. Sposoby przedstawienia permutacji w postaci złożenia transpozycji: sąsiednich albo niesąsiednich elementów. Inwersje, związek inwersji ze znakiem permutacji. Typ permutacji. Liczba permutacji określonego typu. Rząd permutacji. Liczba permutacji określonego rzędu. Permutacja parzysta, nieparzysta. Inwolucja, czyli permutacja samoodwrotna. Nieporządek. Liczba nieporządków. Potęgowanie permutacji. Równania permutacyjne.	W01, W02, W03, W04, L01, L02, L03, L04	MEK02 MEK03
1	TK02	Grupa permutacji. Tabela mnożenia. Podgrupa. Grupa generowana przez permutację. Grupa symetryczna Sn. Grupy izometrii figur geometrycznych. Grupa automorfizmów grafu. Grupy dwuścianów. Grupy obrotów wielościanów. Działanie grup na zbiorach. Orbity. Wyznaczanie liczby orbit. Zastosowanie teorii grup do zliczania kolorowań obiektów kombinatorycznych i zliczania oznakowań grafu oraz automorfizmów grafu. Twierdzenie Polyi oraz Frobeniusa-Burnside'a. Zliczanie istotnie różnych kolorowań wierzchołków, krawędzi i ścian figur płaskich oraz brył. Wielomian cyklowy grupy permutacji. Zliczanie kolorowań co najwyżej k kolorami i dokładnie k kolorami. Kolorowanie określoną liczbą i rodzajem kolorów. Zliczanie grafów skierowanych i nieskierowanych. Zliczanie kolorowań naszyjników.	W05, W06, W07, W08, L05, L06, L07, L08	MEK01 MEK03
1	TK03	Niejednorodne równania rekurencyjne. Rozwiązywanie takich równań metodą przewidywań. Przewidywanie rozwiązania dla funkcji niejednorodności w postaci iloczynu funkcji potęgowej i wielomianu. Przykłady problemów sprowadzających się do równań niejdnorodnych. Zliczanie podziałów zbioru. Zliczanie podziałów płaszczyzny, liczby ruchów w łamigłówce o wieżach Hanoi itp.	W09, W10, W11, L09, L10	MEK04
1	TK04	Zwyczajna i wykładnicza funkcje tworzące. Zastosowanie ich do rozwiązywania równań rekurencyjnych i wyznaczania ciągów o podanej postaci. Zastosowanie funkcji tworzących do zliczania wyborów z ograniczeniami na liczbę wystąpień danego elementu i zliczania ciągów (wariacji) z ograniczeniami na liczbę wystąpień danego elementu. Rozwiązywanie nieliniowych równań rekurencyjnych za pomocą funkcji tworzącej. Badanie równania na liczbę nieporządków, inwolucji, permutacji bez powtórzeń itp.	W12, W13, W14, W15, L11, L12	MEK01

Nakład pracy studenta

Forma zajęć	Praca przed zajęciami	Udział w zajęciach	Praca po zajęciach
Wykład (sem. 1)	Przygotowanie do kolokwium: 5.00 godz./sem.	Godziny kontaktowe: 30.00 godz./sem.	Uzupełnienie/studiowanie notatek: 5.00 godz./sem. Studiowanie zalecanej literatury: 10.00 godz./sem.
Laboratorium (sem. 1)	Przygotowanie do laboratorium: 5.00 godz./sem. Przygotowanie do kolokwium: 10.00 godz./sem. Inne: 10.00 godz./sem.	Godziny kontaktowe: 30.00 godz./sem.	Dokończenia/wykonanie sprawozdania: 5.00 godz./sem.
Konsultacje (sem. 1)	Przygotowanie do konsultacji: 2.00 godz./sem.	Udział w konsultacjach: 2.00 godz./sem.
Egzamin (sem. 1)	Przygotowanie do egzaminu: 15.00 godz./sem.	Egzamin pisemny: 2.00 godz./sem. Egzamin ustny: 1.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 i obecności na wykładach
Laboratorium	w oparciu o wyniki kolokwiów oraz za aktywność w trakcie zajęć
Ocena końcowa	zależy od wyników egzaminu pisemnego, obecności i aktywności na wykładach, oraz ocen za kolokwia na laboratoriach

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 : Notatki osobiste, książki, pliki z serwera zakładowego, ale tylko wydrukowane. Nie można korzystać ze smartfona ani z komputera.

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