Politechnika
Warszawska

Katalog
ECTS

Nazwa przedmiotu:

Wybrane zagadnienia kombinatoryki

Koordynator przedmiotu:

Prof. dr hab. Zbigniew Lonc

Status przedmiotu:

Obowiązkowy

Poziom kształcenia:

Studia II stopnia

Program:

Matematyka

Grupa przedmiotów:

Wspólne

Kod przedmiotu:

1120-MAMNI-NSP-0236

Semestr nominalny:

1 / rok ak. 2020/2021

Liczba punktów ECTS:

4

Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:

1. godziny kontaktowe – 50 h; w tym a) obecność na wykładach – 30 h b) obecność na ćwiczeniach – 15 h c) konsultacje – 5 h 2. praca własna studenta – 50 h; w tym a) przygotowanie do ćwiczeń i do kolokwium – 40 h b) zapoznanie się z literaturą – 10 h Razem 100 h, co odpowiada 4 pkt. ECTS

Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:

a) obecność na wykładach – 30 h b) obecność na ćwiczeniach – 15 h c) konsultacje – 5 h Razem 50 h, co odpowiada 2 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
• Ć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:

nie

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

Charakterystyka WZK_W01

Posiada wiedzę o zaawansowanej metodach obliczania sum skończonych
Weryfikacja: Kolokwium
Powiązane charakterystyki kierunkowe: M2_W01, M2MNI_W13
Powiązane charakterystyki obszarowe:

Charakterystyka WZK_W02

Posiada szeroką wiedzę w rozwiązywania równań rekurencyjnych w sposób dokładny i przybliżony
Weryfikacja: Kolokwium
Powiązane charakterystyki kierunkowe: M2MNI_W13
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - umiejętności

Charakterystyka WZK_U01

Potrafi obliczać sumy skończone
Weryfikacja: Kolokwium
Powiązane charakterystyki kierunkowe: M2MNI_U05, M2MNI_U13
Powiązane charakterystyki obszarowe:

Charakterystyka WZK_U02

Potrafi rozwiązywać zawansowane równania rekurencyjne
Weryfikacja: Kolokwium
Powiązane charakterystyki kierunkowe: M2MNI_U05, M2MNI_U13
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka WZK_K01

Rozumie przydatność nabytej wiedzy i umiejętności obliczeniowych do stawiania hipotez oraz z ich weryfikacji w możliwych zastosowaniach optymalizacji.
Weryfikacja: Kolokwium
Powiązane charakterystyki kierunkowe: M2MNI_K02
Powiązane charakterystyki obszarowe: