Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Matematyka Dyskretna 1
Koordynator przedmiotu:
Dr Michał Tuczyński
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka i Systemy Informacyjne
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-IN000-ISP-0123
Semestr nominalny:
2 / rok ak. 2020/2021
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia30h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Analiza matematyczna 1 Algebra liniowa z geometrią Elementy logiki i teorii mnogości
Limit liczby studentów:
Ćwiczenia – 30 os. /grupa
Cel przedmiotu:
Celem przedmiotu jest zapoznanie studentów z podstawowymi koncepcjami, strukturami, rezultatami i metodami matematyki dyskretnej oraz pokazanie ich użyteczności w informatyce. Studenci poznają własności struktur dyskretnych pod kątem ich wykorzystania do rozwiązywania problemów informatycznych. Po ukończeniu kursu studenci powinni znać następujące pojęcia matematyki dyskretnej (i związanych z nią dziedzin matematyki) i ich własności: indukcja matematyczna, definicja rekurencyjna, permutacje, podzbiory zbioru, podziały zbioru i liczby, tożsamości kombinatoryczne, współczynniki Newtona, funkcje tworzące, równania rekurencyjne, kody korygujące błędy, grafy, drzewa. Powinni także posiadać następujące umiejętności: - przeprowadzenia prostego dowodu indukcyjnego, - rozwiązania elementarnych typów równań rekurencyjnych, - generowania podstawowych obiektów kombinatorycznych (permutacji, podzbiorów zbioru, podziałów zbioru i liczby), - przekształcania i pokazywania prawdziwości tożsamości kombinatorycznych, - zliczania obiektów dyskretnych za pomocą podstawowych metod (rozumowań indukcyjnych, funkcji tworzących, zasady włączania-wyłączania), - posługiwania się prostymi kodami korygującymi błędy do zakodowania i odkodowania informacji, - znajdowania drzewa rozpinającego o minimalnej wadze w grafie.
Treści kształcenia:
Indukcja matematyczna. Rekurencja: definicje i równania rekurencyjne. Asymptotyka funkcji liczbowych. Podstawy kombinatoryki – podstawowe struktury kombinatoryczne, wariacje, permutacje, kombinacje, podziały zbioru i liczby, algorytmy generowania powyższych struktur. Tożsamości kombinatoryczne - współczynniki Newtona, metody znajdowania i dowodzenia tożsamości kombinatorycznych. Rozwiązywanie równań rekurencyjnych, funkcje tworzące. Podstawowe metody zliczania – elementarne zliczanie, funkcje tworzące, zasada włączania-wyłączania. Kody korygujące błędy – odległość Hamminga, problem wykrywania i korygowania błędów, przykłady konstrukcji kodów, kody liniowe, kody doskonałe. Twierdzenia minimaksowe – twierdzenie Dilwortha, dualne twierdzenie Dilwortha. Podstawy teorii grafów – podstawowe pojęcia, drzewa, minimalne drzewa rozpinające.
Metody oceny:
Podstawę zaliczenia stanowią dwa kolokwia po 17 punktów, aktywność na ćwiczeniach 6 pkt. Razem 40 pkt. Ocena: 3.0 – (20;24] pkt, 3.5 – (24;28] pkt, 4.0 – (28;32] pkt, 4.5 – (32;36] pkt, 5.0 – (36;40] pkt. Obecność na ćwiczeniach obowiązkowa, dopuszczalna dwa razy nieusprawiedliwiona nieobecność.
Egzamin:
nie
Literatura:
1. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa 1986. 2. W. Lipski, Kombinatoryka dla programistów, Warszawa, WNT 2004. 3. Z. Palka, A. Ruciński, Wykłady z Kombinatoryki, cz. 1, WNT, Warszawa 1998. 4. V. Bryant, Aspekty kombinatoryki, WNT, Warszawa 1997. 5. R. J. Wilson, Wstęp do teorii grafów, PWN, Warszawa 1998. 6. K. A. Ross, C. R. B. Wright, Matematyka Dyskretna, PWN 1999.
Witryna www przedmiotu:
e.mini.pw.edu.pl
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka W01
Ma wiedzę z matematyki dyskretnej przydatną do formułowania i rozwiązywania prostych zadań związanych z informatyką
Weryfikacja: kolokwia
Powiązane charakterystyki kierunkowe: K_W01
Powiązane charakterystyki obszarowe:
Charakterystyka W02
Ma wiedzę ogólną w zakresie algorytmów kombinatorycznych i ich złożoności obliczeniowej
Weryfikacja: kolokwia
Powiązane charakterystyki kierunkowe: K_W04
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - umiejętności

Charakterystyka U01
Potrafi wykorzystać nabytą wiedzę z matematyki dyskretnej do tworzenia modeli w obszarze informatyki oraz do konstruowania prostych algorytmów
Weryfikacja: kolokwia i ocena punktowa aktywności na zajęciach
Powiązane charakterystyki kierunkowe: K_U01, K_U11
Powiązane charakterystyki obszarowe:
Charakterystyka U02
Potrafi zidentyfikować dyskretne struktury matematyczne w problemach i wykorzystać teoretyczną wiedzę dotyczącą tych struktur do analizy i rozwiązania tych problemów
Weryfikacja: kolokwia i ocena punktowa aktywności na zajęciach
Powiązane charakterystyki kierunkowe: K_U04
Powiązane charakterystyki obszarowe:
Charakterystyka U03
Potrafi wykorzystać wiedzę z teorii grafów do tworzenia, analizowania i stosowania modeli matematycznych służących do rozwiązywania problemów z różnych dziedzin
Weryfikacja: kolokwia i ocena punktowa aktywności na zajęciach
Powiązane charakterystyki kierunkowe: K_U03
Powiązane charakterystyki obszarowe: