Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Matematyka dyskretna
Koordynator przedmiotu:
dr inż. Krzysztof Bryś
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka
Grupa przedmiotów:
Przedmioty podstawowe
Kod przedmiotu:
MDUZ
Semestr nominalny:
1 / rok ak. 2020/2021
Liczba punktów ECTS:
5
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
samodzielna praca z podręcznikiem - 60 godzin konsultacje on-line z wykładowcą - 5 godzin konsultacje - 4 godziny egzamin - 2 godziny rozwiązywanie zadań domowych - 20 godzin przygotowanie do egzaminu - 24 godziny RAZEM: 115 godzin
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
1 ECTS konsultacje on-line z wykładowcą - 5 godzin konsultacje - 4 godziny egzamin - 2 godziny RAZEM: 11 godzin
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
3 ECTS samodzielna praca z podręcznikiem - rozwiązywanie zadań do samodzielnego rozwiązania - 30 godzin rozwiązywanie zadań domowych - 20 godzin przygotowanie do egzaminu - rozwiązywanie przykładowych zadań egzaminacyjnych - 15 godzin RAZEM: 65 godzin
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia30h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Prawa logiki matematycznej, relacje, funkcje, moc zbioru, działania na macierzach, ciagi liczbowe, szeregi liczbowe, rachunek różniczkowy, rachunek całkowy, algorytmy
Limit liczby studentów:
30
Cel przedmiotu:
Zapoznanie z matematycznymi podstawami informatyki. Przedstawienie struktur i metod matematyki dyskretnej, które wykorzystuje się w informatyce oraz zaprezentowanie ich zastosowań. Przygotowanie studenta do samodzielnego rozwiązywania problemów przy użyciu poznanych narzędzi matematycznych.
Treści kształcenia:
Elementarne pojęcia matematyki dyskretnej. Działania na zbiorach. Podstawowe własności funkcji. Definicja i własności ciągu liczbowego. Zbiór liczb naturalnych. Podstawowe obiekty kombinatoryczne: permutacja, kombinacja, wariacja. Zliczanie podstawowych obiektów kombinatorycznych. Podstawowe techniki zliczania: prawo dodawania i prawo mnożenia. Wyznaczanie liczby wszystkich podstawowych obiektów kombinatorycznych. Schematy wyboru. Reprezentowanie podzbioru jako ciągu binarnego. Wyznaczenie liczby wszystkich podzbiorów. Definicja kombinatoryczna i własności symbolu Newtona. Interpretacja kombinatoryczna wzoru dwumiennego Newtona. Tożsamości kombinatoryczne. Podziały zbioru . Zliczanie podziałów zbioru na podzbiory poetykietowane. Wyznaczanie liczby podziałów zbioru na podzbiory o zadanych mocach. Definicja podziału zbioru na bloki. Liczby Stirlinga drugiego rodzaju. Podziały liczb Definicja podziału liczby. Wzory na ilość podziałów liczby. Schematy podziału. Generowanie podstawowych obiektów kombinatorycznych. Algorytm generowania wszystkich ciągów. Algorytm generowania wszystkich podzbiorów. Algorytm generowania wszystkich podziałów zbioru. Rekurencja. Indukcja matematyczna. Pojęcie rekurencji. Tworzenie zależności rekurencyjnej. Metody rozwiązywania równań rekurencyjnych. Przykłady tworzenia i rozwiązywania zależności rekurencyjnych. Definicja i zastosowania ciągu Fibonacciego. Funkcje tworzące. Pojęcie funkcji tworzącej. Przykłady znajdowania funkcji tworzących niektórych ciągów. Zastosowania funkcji tworzących do dowodzenia tożsamości oraz do obliczania ilości podziałów. Rozwiązywanie równań rekurencyjnych metodą funkcji tworzących. Obliczenie liczb Fibonacciego metodą funkcji tworzących. Zasada włączania-wyłączania. Wzór na moc sumy trzech zbiorów. Zasada włączania-wyłączania w przypadku dowolnej liczby zbiorów. Przykładowe zastosowania. Pojęcie nieporządku. Wzór na liczbę wszystkich nieporządków. Podzielność liczb naturalnych. Relacja podzielności. Algorytm Euklidesa. Podstawowe prawa podzielności. Liczby pierwsze. Liczby względnie pierwsze. Arytmetyka modulo. Elementarne pojęcia teorii grafów.
Metody oceny:
W trakcie półsemestru studenci dostaną (mailem) 2 zestawy zadań domowych (w każdym zestawie 5 zadań), których rozwiązania należy do prowadzącego. Pierwszy zestaw będzie zawierał zadania dotyczące pierwszej połowy wykładów i analogiczne do zadan z dwoch pierwszych zestawow zadan do samodzielnego rozwiazania zamieszczonych w podreczniku, drugi będzie zawierał zadania dotyczące drugiej połowy wykładów. Za każdym razem na przesłanie rozwiązań będzie 14 dni. Za każdy zestaw zadań domowych można będzie dostać maksymalnie 20 punktów (po 4 punkty za każde zadanie). Do zdobytej w ten sposób liczby punktów dodane zostaną punkty zdobyte w czasie egzaminu (maksymalnie 60 punktów). Egzamin będzie składał się z 5 zadań (po 12 punktów każde). Ocena końcowa zostanie wystawiona na podstawie uzyskanej w ten sposób sumy punktów według następujących kryteriów: 51-60 punktów - ocena 3.0 61-70 punktów - ocena 3.5 71-80 punktów - ocena 4.0 81-90 punktów - ocena 4.5 91-100 punktów - ocena 5.0 Zadania domowe jak i zadania na egzaminie będą zbliżone (ale nie identyczne) do zadań znajdujących się na listach zadań do samodzielnego rozwiązania.
Egzamin:
tak
Literatura:
V. Bryant – Aspekty kombinatoryki, WNT, Warszawa 1997. R.L. Graham, D.E. Knuth, O. Patashnik – Matematyka konkretna, PWN, Warszawa K.A. Ross, C.R.B. Wright - Matematyka dyskretna, PWN, Warszawa 2000. R.J. Wilson - Wprowadzenie do teorii grafów, PWN, Warszawa 1998
Witryna www przedmiotu:
https://red.okno.pw.edu.pl/witryna/home.php
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka MD_W01
zna teoretyczne podstawy technik zliczania
Weryfikacja: rozwiązywanie zadań domowych, egzamin
Powiązane charakterystyki kierunkowe: K2_W01
Powiązane charakterystyki obszarowe: I.P7S_WG, P7U_W, I.P7S_WG.o
Charakterystyka MD_W02
zna podstawy teoretyczne metod rozwiązywania równań rekurencyjnych
Weryfikacja: rozwiązywanie zadań domowych, egzamin
Powiązane charakterystyki kierunkowe: K2_W01
Powiązane charakterystyki obszarowe: I.P7S_WG, P7U_W, I.P7S_WG.o
Charakterystyka MD_W03
zna podstawowe pojecia i twierdzenia teorii grafów
Weryfikacja: rozwiązywanie zadań domowych, egzamin
Powiązane charakterystyki kierunkowe: K2_W01
Powiązane charakterystyki obszarowe: I.P7S_WG, P7U_W, I.P7S_WG.o
Charakterystyka MD_W04
zna podstawowe prawa podzielności liczb
Weryfikacja: rozwiązywanie zadań domowych, egzamin
Powiązane charakterystyki kierunkowe: K2_W01
Powiązane charakterystyki obszarowe: P7U_W, I.P7S_WG.o, I.P7S_WG

Profil ogólnoakademicki - umiejętności

Charakterystyka MD_U01
potrafi stosować podstawowe techniki zliczania
Weryfikacja: rozwiązywanie zadań domowych, egzamin
Powiązane charakterystyki kierunkowe: K2_U07
Powiązane charakterystyki obszarowe: I.P7S_UW, III.P7S_UW.2.o, P7U_U, I.P7S_UW.o, III.P7S_UW.o
Charakterystyka MD_U02
potrafi rozwiązywać równania rekurencyjne
Weryfikacja: rozwiązywanie zadań domowych, egzamin
Powiązane charakterystyki kierunkowe: K2_U07
Powiązane charakterystyki obszarowe: I.P7S_UW, III.P7S_UW.2.o, P7U_U, I.P7S_UW.o, III.P7S_UW.o
Charakterystyka MD_U03
potrafi stosować w praktyce prawa podzielności liczb
Weryfikacja: rozwiązywanie zadań domowych, egzamin
Powiązane charakterystyki kierunkowe: K2_U07
Powiązane charakterystyki obszarowe: I.P7S_UW, III.P7S_UW.2.o, P7U_U, I.P7S_UW.o, III.P7S_UW.o

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka MD_K01
rozumie wagę wiedzy i umiejętności z zakresu matemtyki dyskretnej w zastosowaniach praktycznych
Weryfikacja: rozwiązywanie zadań domowych, egzamin
Powiązane charakterystyki kierunkowe: K2_K02
Powiązane charakterystyki obszarowe: I.P7S_KK, I.P7S_KR, P7U_K
Charakterystyka MD_K02
rozumie potrzebę ciągłego uczenia się
Weryfikacja: rozwiązywanie zadań domowych, egzamin
Powiązane charakterystyki kierunkowe: K1_K01
Powiązane charakterystyki obszarowe: