- Nazwa przedmiotu:
- Matematyka Dyskretna I
- Koordynator przedmiotu:
- prof. dr hab. Zbigniew Lonc
- Status przedmiotu:
- Obowiązkowy
- Poziom kształcenia:
- Studia I stopnia
- Program:
- Informatyka
- Grupa przedmiotów:
- Wspólne
- Kod przedmiotu:
- Semestr nominalny:
- 2 / rok ak. 2013/2014
- Liczba punktów ECTS:
- 4
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- 1. godziny kontaktowe – 60 h; w tym
a. obecność na wykładach – 30 h
b. obecność na ćwiczeniach – 30 h
2. przygotowanie do ćwiczeń – 30 h
3. zapoznanie się z literaturą – 10 h
4. konsultacje – 5 h
5. przygotowanie do kolokwiów – 15 h
Łączny nakład pracy studenta wynosi 120 h co odpowiada 4 pkt. ECTS
- Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- 1. obecność na wykładach – 30 h
2. obecność na ćwiczeniach – 30 h
3. konsultacje – 5 h
Razem 65 h, co odpowiada 3 pkt. ECTS
- 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 I, Algebra z geometrią analityczną, Elementy logiki i teorii mnogości.
- Limit liczby studentów:
- Bez limitu
- 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 16 punktów, aktywność na ćwiczeniach 8 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:
- W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa 1986.
W. Lipski, Kombinatoryka dla programistów, Warszawa, WNT 2004.
Z. Palka, A. Ruciński, Wykłady z Kombinatoryki, cz. 1, WNT, Warszawa 1998.
V. Bryant, Aspekty kombinatoryki, WNT, Warszawa 1997.
R. J. Wilson, Wstęp do teorii grafów, PWN, Warszawa 1998.
K. A. Ross, C.R.B.Wright, Matematyka Dyskretna, PWN 1999.
- Witryna www przedmiotu:
- brak
- 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