Matematyka dyskretna II

stacjonarne

I stopnia

obowiązkowy

W 16/X; C 14/+

Matematyka dyskretna I/ K_U03, K_U17, K_W02

wszystkie kierunki Wydziału Cybernetyki

dr hab. inż. Andrzej Bolesław Chojnacki

LICZBA GODZIN REALIZOWANYCH PRZY BEZPOŚREDNIM

UDZIALE NAUCZYCIELA / GODZINY KONTAKTOWE/

43 - 1.5 ECTS

Udział w wykładach

16 - 0.6 ECTS

Udział w ćwiczeniach, laboratoriach, projektach, seminariach

14 - 0.5 ECTS

Udział w konsultacjach

10 - 0.3 ECTS

Udział w egzaminie/ kolokwium zaliczeniowym itp.

3 - 0.1 ECTS

SAMODZIELNA PRACA STUDENTA / GODZINY NIEKONTAKTOWE

45 - 1.5 ECTS

Przygotowanie do wykładu

5 - 0.1 ECTS

Przygotowanie do ćwiczeń, laboratoriów, projektów, seminariów itp.

20 - 0.7 ECTS

Przygotowanie do egzaminu / kolokwium

20 - 0.7 ECTS

CAŁKOWITE OBCIĄŻENIE STUDENTA

88 - 3 ECTS

Techniki zliczania. Współczynniki dwu- i multimianowe. Zliczanie zbiorów i funkcji. Funkcje tworzące i ich zastosowania. Podzielność liczb całkowitych. Kongruencje.

- Techniki zliczania

Prezentacja przedmiotu. Podstawowe oznaczenia. Prawo sumy. Prawo różnicy. Prawo iloczynu. Zasada szufladkowa Dirichleta. Zasada włączeń i wyłączeń. Uogólnione prawo mnożenia. Uogólniona zasada szufladkowa Dirichleta.

- Współczynniki dwu- i multimianowe

Współczynnik dwumianowy i jego właściwości. Liczność zbioru potęgowego. Trójkąt Pascala. Tożsamość Cauchy'ego. Liczba przejść po kracie. Liczba rozwiązań liniowego równania diofantycznego bez ograniczeń. Współczynnik multimianowy i jego właściwości. Liczność zbioru wszystkich funkcji na zbiorach skończonych.

- Zliczanie zbiorów i funkcji

Liczby Stirlinga pierwszego rodzaju. Podział i pokrycie zbioru. Liczby Stirlinga drugiego rodzaju. Liczby Bella. Potęga przyrastająca i ubywająca. Zliczanie injekcji, bijekcji, permutacji i surjekcji. Liczby Eulera. Wierzchołek wewnętrzny drzewa binarnego. Liczby Catalana. Podział liczby na składniki.

- unkcje tworzące

Oznaczenie K.E.Iversona. Funkcje „podłoga” i „sufit” oraz ich właściwości. Ciąg liczbowy nieskończony i skończony. Definicja funkcji tworzącej. Przykłady funkcji tworzących. Operacje na ciągach i ich funkcjach tworzących. Splot ciągów. Funkcje tworzące szeregów. Funkcja tworząca funkcji wykładniczej. Wykładnicza funkcja tworząca. Różniczkowanie i całkowanie funkcji tworzących. Funkcje tworzące liczb Stirlinga pierwszego i drugiego rodzaju. Wykładnicza funkcja tworząca dla liczb Bella. Funkcja tworząca liczb Catalana. Funkcja tworząca dla podziałów liczb na składniki.

- Zastosowania funkcji tworzących

Wyznaczanie liczby rozwiązań liniowego równania diofantycznego z ograniczeniami. Zbiory z powtórzeniami. Analizy liczby podzbiorów zbiorów z powtórzeniami. Zastosowania funkcji tworzących w rozwiązywaniu równań rekurencyjnych.

- Podzielność liczb całkowitych

Działanie modulo. Algorytm dzielenia. Relacja podzielności. Liczby pierwsze i względnie pierwsze. Największy wspólny dzielnik. Algorytm Euklidesa. Binarny algorytm znajdowania największego wspólnego dzielnika. Zmodyfikowany algorytm Euklidesa. Podstawowe twierdzenie arytmetyki. Sito Eratostenesa. Rozwiązywanie liniowego równania diofantycznego w zbiorze liczb całkowitych.

- Kongruencje

Relacja kongruencji. Właściwości kongruencji. Małe twierdzenie Fermata. Rozwiązywanie kongruencji liniowych. Rozwiązywanie układu kongruencji liniowych. Chińskie twierdzenie o resztach. Funkcja Eulera. Twierdzenie Eulera.

A. B. Chojnacki, Jak to rozwiązać? Matematyka dyskretna. Część II, Wojskowa Akademia Techniczna, Warszawa, 2021

R. L. Graham, D. E. Knuth, O. Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN, Warszawa, 2021

H. Rasiowa, Wstęp do matematyki współczesnej, Wydawnictwo Naukowe PWN, Warszawa, 2021

K. A. Ross, Ch. Wright, Matematyka dyskretna, Wydawnictwo Naukowe PWN,Warszawa.2014

- umie posługiwać się językiem matematyki wykorzystując właściwe symbole, określenia i twierdzenia oraz umie formułować i rozwiązywać proste problemy metodami algebry, geometrii analitycznej, analizy matematycznej i probabilistyki;

- potrafi samodzielnie planować i realizować własne permanentne uczenie się, pozyskiwać informacje z literatury, baz danych i innych źródeł, dokonywać syntezy i analizy tych informacji;

- zna i rozumie symbole, podstawowe pojęcia, określenia i twierdzenia logiki, teorii mnogości, algebry z geometrią, analizy matematycznej, matematyki dyskretnej, optymalizacji, probabilistyki i matematycznych podstaw kryptologii, potrzebne dla rozumienia i studiowania przedmiotów kierunkowych

- Moduł kształcenia zaliczany jest na podstawie: wyników testu pisemnego oraz zaliczenia ćwiczeń rachunkowych.

- Zaliczenie jest przeprowadzane w formie: testu pisemnego, w którym oceniane są odpowiedzi poprawne, brak odpowiedzi poprawnych i odpowiedzi błędne. Podczas testu nie można korzystać z żadnych materiałów. Po teście może odbyć się część ustna w przypadku trudności z dokonaniem oceny pracy. Ocena wyników dokonywana jest na podstawie tabel opracowanych przez wykładowcę.

- Warunkiem dopuszczenia do zaliczenia jest: uzyskanie pozytywnej oceny z zaliczenia ćwiczeń rachunkowych.

- Warunek konieczny do uzyskania zaliczenia: uzyskanie pozytywnej oceny z testu pisemnego wystawionej na podstawie tabel.

- Zaliczenie ćwiczeń jest przeprowadzane w oparciu o następujące zasady:

- wystawiana jest średnia ocena za odpowiedzi ustne udzielane podczas ćwiczeń, rozwiązywanie zadań rachunkowych na tablicy oraz aktywność na ćwiczeniach - musi być pozytywna; dopuszczalne się dwie nieobecności na ćwiczeniach (wpływają na ocenę aktywności) w przypadku większej liczby nieobecności przeprowadza się oddzielne oceniania na konsultacjach;

- przeprowadzane są dwa oddzielnie oceniana kolokwia w terminach zapowie-dzianych, za które wystawiana jest ocena średnia; ocena średnia musi być pozytywna; oceny z kolokwiów mogą być poprawiane podczas konsultacji za zgodą prowadzącego ćwiczenia rachunkowe

- wystawiana jest ocena łączna za zadania domowe - nie musi być pozytywna

­- ocena łączna za ćwiczenia rachunkowe jest średnią powyższych ocen średnich zaokrągloną w górę.

- Efekty kształcenia sprawdzane są testem pisemnym, kolokwiami oraz zadaniami rozwiązywanymi na ćwiczeniach rachunkowych i zadaniami domowymi.