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
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-IN000-ISP-0010
Semestr nominalny:
2 / rok ak. 2016/2017
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) 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, 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. Podstawowe metody zliczania - elementarne zliczanie, funkcje tworzące, zasada włączania-wyłączania. Podzielność liczb naturalnych. 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. 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-23 pkt, 3.5 – 24-27 pkt, 4.0 – 28-31 pkt, 4.5 – 32-35 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

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

Profil ogólnoakademicki - umiejętności

Efekt 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 efekty kierunkowe: K_U01, K_U11
Powiązane efekty obszarowe: T1A_U09, T1A_U09, T1A_U14, T1A_U15
Efekt 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 efekty kierunkowe: K_U04
Powiązane efekty obszarowe: T1A_U09
Efekt 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 efekty kierunkowe: K_U03
Powiązane efekty obszarowe: T1A_U09