Drukuj Eksport do pliku (MS Word)
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