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. 2011/2012
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 I, Algebra z geometrią analityczną, Elementy logiki i teorii mnogości.
Limit liczby studentów:
Cel przedmiotu:
Zapoznanie studentów z podstawowymi koncepcjami, strukturami, rezultatami i metodami matematyki dyskretnej oraz pokazanie ich użyteczności w informatyce. 
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:
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:
Uwagi:

Efekty uczenia się