- Nazwa przedmiotu:
- Wybrane zagadnienia kombinatoryki
- Koordynator przedmiotu:
- dr Paweł Naroski
- Status przedmiotu:
- Obowiązkowy
- Poziom kształcenia:
- Studia II stopnia
- Program:
- Matematyka
- Grupa przedmiotów:
- Wspólne
- Kod przedmiotu:
- 1120-MAMNI-NSP-0030
- Semestr nominalny:
- 1 / rok ak. 2016/2017
- Liczba punktów ECTS:
- 6
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- godziny kontaktowe – 45 h; w tym
obecność na wykładach – 30 h
obecność na ćwiczeniach – 15 h
przygotowanie do ćwiczeń – 60 h
zapoznanie się z literaturą – 30 h
przygotowanie do egzaminu i obecność na egzaminie – 25 h
Łączny nakład pracy studenta wynosi 160 h co odpowiada 6 pkt. ECTS
- Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- 2
- Język prowadzenia zajęć:
- polski
- Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
- 4
- Formy zajęć i ich wymiar w semestrze:
-
- Wykład30h
- Ćwiczenia15h
- Laboratorium0h
- Projekt0h
- Lekcje komputerowe0h
- Wymagania wstępne:
- Przedmioty poprzedzające:
Matematyka Dyskretna, Analiza matematyczna 1, Elementy logiki i teorii mnogości.
Wymagania wstępne:
Znajomość podstawowych pojęć matematyki dyskretnej oraz logiki i teorii mnogości. Znajomość szeregów liczbowych i funkcyjnych
- Limit liczby studentów:
- Bez limitu
- Cel przedmiotu:
- Celem przedmiotu jest zapoznanie z podstawowymi metodami zliczania obiektów kombinatorycznych, obliczania sum ciągów liczbowych oraz rozwiązywania równań rekurencyjnych zarówno dokładnie, jak i w sposób przybliżony. Pokazane będą związki omawianych problemów z problemami pojawiającymi się w informatyce.
- Treści kształcenia:
- W programie przewidziane są między innymi następujące tematy: przegląd metod obliczania sum ciągów liczbowych, elementy rachunku różnicowego, własności współczynników dwumiennych, tożsamości dwumienne, reguła inwersyjna, liczby Stirlinga pierwszego i drugiego rodzaju i ich własności, liczby harmoniczne i ich własności, liczby Bernoulliego, liczby Fibonacciego i ich własności, funkcje tworzące, sploty funkcji tworzących, wykładnicze funkcje tworzące, asymptotyka ciągów liczbowych, notacja dużego „O”, wzór Stirlinga, przybliżenie n-tej liczby pierwszej.
- Metody oceny:
- Zaliczenie przedmiotu jest na podstawie kolokwium zaliczeniowego
50-59 % ocena 3.0
60-69 % ocena 3.5
70-79 % ocena 4.0
80-89 % ocena 4.5
90-100 % ocena 5.0
- Egzamin:
- tak
- Literatura:
- 1. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, 1997.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Wprowadzenie do algorytmów, WNT, 2000.
3. M. R. Garey, D. S. Johnson, Computers and Intractability, Freeman 1979.
4. M. A. Weiss, Data Structures and Algorithms in C++, Adison Wesley 1999.
- Witryna www przedmiotu:
- brak
- Uwagi:
Efekty uczenia się
Profil ogólnoakademicki - wiedza
- Efekt WZK_W01
- Znajomość rachunku różnicowego i podstawowej struktury pierścienia szeregów formalnych.
Weryfikacja: kolokwia, egzamin
Powiązane efekty kierunkowe:
MNI_W03
Powiązane efekty obszarowe:
X2A_W01
- Efekt WZK_W02
- Znajomość pewnych metod szacowania złożoności obliczeniowej algorytmów. Np. poprzez obliczanie sum skończonych czy rozwiązywanie, dokładne lub przybliżone, równań rekurencyjnych.
Weryfikacja: kolokwia, egzamin
Powiązane efekty kierunkowe:
MNI_W17
Powiązane efekty obszarowe:
X2A_W01, X2A_W04
- Efekt WZK_W03
- Znajomość pewnych metod zliczania.
Weryfikacja: kolokwia, egzamin
Powiązane efekty kierunkowe:
MNI_W16
Powiązane efekty obszarowe:
X2A_W01
Profil ogólnoakademicki - umiejętności
- Efekt WZK_U01
- Obliczanie złożonych sum ciągów liczbowych.
Weryfikacja: kolokwia, egzamin
Powiązane efekty kierunkowe:
MNI_U09
Powiązane efekty obszarowe:
X2A_U01, X2A_U02, X2A_U05
- Efekt WZK_U02
- Rozwiązywanie podstawowych rodzajów równań rekurencyjnych w sposób dokładny i przybliżony.
Weryfikacja: kolokwia, egzamin
Powiązane efekty kierunkowe:
MNI_U10
Powiązane efekty obszarowe:
X2A_U01, X2A_U03