Cel kształcenia i wykaz literatury

Główny cel kształcenia: Zapoznanie studentów z wybranymi metodami analitycznymi i wybranymi metodami numerycznymi stosowanymi w analizie kombinatorycznej.

Ogólne informacje o zajęciach: Zagadnienia realizowane w ramach 15 godzin wykładu i 7 godzin ćwiczeń, związane z matematyką dyskretną, która stanowi jedną z dwóch części tematycznych tego modułu. 1. Ciągi liczbowe i sposoby reprezentacji ciągów: lista wyrazów ciągu, funkcja zmiennej n, zależność rekurencyjna. Ważniejsze ciągi liczbowe: ciąg arytmetyczny i geometryczny, ciąg kwadratów i sześcianów liczb naturalnych, ciągi binarne, nieporządki, współczynniki dwumianowe Newtona. 2. Specjalne ciągi liczbowe i ich właściwości: liczby Fibonacciego, Catalana, liczby harmoniczne jako dyskretny odpowiednik logarytmu naturalnego, liczby Stirlinga pierwszego i drugiego rodzaju, liczby Bella. 3. Równania rekurencyjne pierwszego i drugiego rzędu, jednorodne i niejednorodne, jako metoda określania liczebności zbioru w funkcji jego rozmiaru. Warunki początkowe równania rekurencyjnego. Zastosowanie równania charakterystycznego do rozwiązywania równań liniowych jednorodnych o stałych współczynnikach. Przykłady problemów matematyki dyskretnej, które można rozwiązać formułując odpowiednie równanie rekurencyjne. 4. Metoda przewidywań dla równań niejednorodnych. Rozwiązanie ogólne i szczególne. Zasada przewidywań rozwiązania szczególnego dla funkcji niejednorodności w postaci iloczynu wielomianu i funkcji potęgowej. Wyprowadzenie i rozwiązanie zależności rekurencyjnych dla specjalnych ciągów liczbowych: liczba nieporządków, liczba podziałów zbioru, liczby Fibonacciego itp. 5. Sumy w analizie ciągów. Zwyczajna i wykładnicza funkcja tworząca ciągu liczbowego. Funkcje tworzące ważniejszych ciągów. Podstawowe tw. dotyczące funkcji tworzących: tw. o liniowości, przesunięciu, pochodnej, całce i splocie zwykłym oraz dwumianowym. Zastosowanie funkcji tworzących do rozwiązywania równań rekurencyjnych, do wyznaczania postaci jawnej ciągu na podstawie ciągu jego wartości. Zastosowanie funkcji tworzących do rozwiązywania zagadnień zliczania wyborów i permutacji z ograniczeniami na liczbę wystąpień konkretnego elementu. 6. Różnice skończone. Operator różnicy jako dyskretny odpowiednik różniczkowania w dziedzinie ciągłej. Operator przesunięcia. Twierdzenia o różnicy iloczynu, k-ta różnica, tw. Leibniza, tw. o różnicy ilorazu. Wybrane funkcje i ich różnice. Malejąca i rosnąca funkcja potęgowa oraz konwersje między tymi funkcjami. Tw. o potęgowaniu. Tw. o malejącej funkcji potęgowej dwumianu. Tw. Newtona jako dyskretny odpowiednik szeregu Maclaurina. Sekwencja różnic i tabele różnic. Zastosowanie sekwencji różnic do znajdowania wielomianu najniższego stopnia, przechodzącego przez zadane punkty. Proste równania różnicowe. 7. Antyróżnica i reguły sumowania. Operatory antyróżnicy jako dyskretny odpowiedniki całkowania w dziedzinie ciągłej. Suma nieoznaczona. Tw. o liniowości i o sumowaniu przez części. Transformacja Abela. Antyróżnice i sumy skończone wybranych funkcji. Zastosowanie teorii antyróżnic do wyznaczania postaci zwięzłej sum oznaczonych. Tematyka wykładów 8-15 i ćwiczeń 4-7 dotyczy wybranych, podstawowych metod numerycznych i zostanie określona przez drugiego opiekuna modułu. Lista zagadnień 30-godzinnego wykładu i 15-godzinnych ćwiczeń, gdy moduł ten prowadzony był tylko przez prof. R. Dmytryshyna: Moduł Matematyka Dyskretna i Metody Numeryczne jest zbiorem nowoczesnych algorytmów, służący do rozwoju u studentów zdolności kombinatorycznych oraz wiedzy z matematyki stosowanej w zakresie analizy dokładności komputerowych obliczeń. W01: Podstawy i problematyka przedmiotu. Rys historyczny. Grafy, tablice i macierze. Komputerowa reprezentacja tablic i grafów. Asymptotyka funkcji liczbowych. Podzielność liczb naturalnych. W02: Struktury algebraiczne. Kombinatoryka: zliczanie i generowanie obiektów kombinatorycznych. Generowanie iloczynu kartezjańskiego, permutacji. Graf permutacji, transpozycja, inversja. Indukcja matematyczna. W03: Typy wzorów. Odwrotna notacja polska. Drzewo wzoru. Generowanie nawiasów i zagnieżdżenie wzorów. Generowania wzoru wyznacznika. Drzewa skierowane.W04: Problem komiwojażera. Szukanie najtańszej (najkrótszej) ścieżki. Algorytmy Dijkstry, Warshala. W05: Redukcja wierzchołków digrafu. Tablica najtańszych ścieżek. Algorytm Kruskala. W06: Ścieżki, drzewa i cykle Hamiltona. Szukanie jednocyklowych permutacji. Zastosowanie grafów do analizy obwodów elektrycznych. Sieci transportowe. W07: Rekurencja: definicje i równania rekurencyjne. Algorytm Feussnera. W08: Metody numeryczne.Teoria błędów. Podstawowe źródła i metody obliczania błędów. Błędy działań arytmetycznych na liczbach przybliżonych. W09: Możliwości MathCADa. Liczby zespolone. Algorytm zapisu macierzy admitancji dla obwodów elektrycznych. Wykresy amplitudy i fazy. W10: Zastosowanie redukcji Gaussa do obliczenia wyznaczników i rozwiązywania układów równań liniowych. W11: Uwarunkowanie macierzy. W12: Obliczanie funkcji analitycznej. Schemat Hornera. W13: Aproksymacja i Interpolacja. W14: Liczby losowe. Normalny rozkład. Dzwon Gaussa. Metoda Monte Carlo i symulacja. W15: Laboratoria wirtualny. C01. Plan ćwiczeń. Podstawy MathCad. C02: Kolokwium A. C03: Kolokwium A (cd). C04: Ćwiczenie 1 w MathCad. C05: Ćwiczenie 2 w MathCad. C06: Ćwiczenie 3 w MathCad. C07: Zaliczenie.

Materiały dydaktyczne: http://www.pei.prz.rzeszow.pl/dydaktyka.html - Materiały są dostępne po zalogowaniu.

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	Deo N.	Teoria grafów i jej zastosowania w technice i informatyce	PWN, Warszawa , s. 607.	1980
2	Ake Bjorck, Germund Dahlquist	Metody numeryczne	PWN, Warszawa.	1987
3	Ronald L. Graham, Donald E. Knuth, Oren Patashnik	Matematyka konkretna	Wydawnictwo Naukowe PWN.	2015

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

1	Dmytryszyn R., Drałus G.	Matematyka Dyskretna (materiały pomocnicze)	Oficyna PRz, s.125.	2003
2	Marciniak A., Gregulec D., Kaczmarek J.	Podstawowe procedury numeryczne w języku Turbo Pascal	„NAKOM”, Poznań..	1997
3	Włoch A., Włoch I.	Matematyka dyskretna (podstawowe metody i algorytmy teorii grafów)	Oficyna Wydawnicza PRz.	2004

Literatura do samodzielnego studiowania

1

Deo N.

Teoria grafów i jej zastosowania w technice i informatyce

Wydawnictwo Naukowe PWN, Warszawa, s. 607.

1980

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

Wymagania formalne: Matematyka: rozwiązywanie równań algebraicznych, funkcje trygonometryczne, liczby zespolone

Wymagania wstępne w kategorii Wiedzy: Ma wiedzę w zakresie równań matematycznych, funkcji trygonometrycznych, liczb zespolonych oraz komputerowych obliczeń

Wymagania wstępne w kategorii Umiejętności: Potrafi rozwiązywać równania liniowe i kwadratowe, operować na liczbach zespolonych, wykonywać różniczkowanie prostych funkcji.

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	01.Student po zakończeniu kursu potrafi efektywnie stosować metody grafowe i kombinatoryczne	wykład interaktywny, ćwiczenia problemowe,	egzamin pisemny	K_W01+ K_W03++ K_U05++ K_K02++	T1A_W01++ T1A_U05++ T1A_K02++ InzA_K01++
02	02.Student po zakończeniu kursu potrafi efektywnie szacować błędy obliczeniowe przy zastosowaniu metod numerycznych	wykład interaktywny, ćwiczenia problemowe, gra dydaktyczna, dyskusja dydaktyczna	egzamin cz. pisemna,	K_W03+ K_U05+ K_K02+	T1A_W01+ T1A_U05+ T1A_K02+ InzA_K01+

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	01. Matematyka dyskretna	W01..W07, C01..C03	MEK01
2	TK02	02. Metody numeryczne	W08..W15, C04..C07	MEK02

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: 4.00 godz./sem.	Godziny kontaktowe: 30.00 godz./sem.	Uzupełnienie/studiowanie notatek: 2.00 godz./sem. Studiowanie zalecanej literatury: 5.00 godz./sem.
Ćwiczenia/Lektorat (sem. 2)	Przygotowanie do ćwiczeń: 6.00 godz./sem. Przygotowanie do kolokwium: 5.00 godz./sem. Inne: 4.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.	Dokończenia/studiowanie zadań: 5.00 godz./sem. Inne: 4.00 godz./sem.
Konsultacje (sem. 2)	Przygotowanie do konsultacji: 2.00 godz./sem.	Udział w konsultacjach: 2.00 godz./sem.
Egzamin (sem. 2)	Przygotowanie do egzaminu: 15.00 godz./sem.	Egzamin pisemny: 2.00 godz./sem. Egzamin ustny: 4.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	Po rozmowie dydaktycznej, z uwzględnieniem obecności i aktywności na wykładach
Ćwiczenia/Lektorat	Po rozmowie dydaktycznej, z uwzględnieniem zaliczenia za ćwiczenia
Ocena końcowa	"dst", "db", "bdb" w zależności od wyników egzaminu ustnego, obecności i aktywności na wykładach, ocen za kolokwia na wykładzie i ćwiczeniach

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 : Na egzaminie z matematyki dyskretnej można mieć notatki osobiste, książki, pliki z serwera zakładowego (w wersji drukowanej). Zabrania się korzystać ze smartfona.

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