Politechnika Warszawska - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Wybrane zagadnienia kombinatoryki

Informacje ogólne

Kod przedmiotu: 1120-MAMNI-NSP-0236 Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Wybrane zagadnienia kombinatoryki
Jednostka: Wydział Matematyki i Nauk Informacyjnych
Grupy: Przedmioty obieralne, wydz. MiNI PW
Przedmioty obowiązkowe, sem. 1 MNI (rozpoczęcie w r. ak. parzystym)
Przedmioty obowiązkowe, sem. 3 MNI (rozpoczęcie w r. ak. nieparzystym)
Punkty ECTS i inne: 4.00 LUB 6.00 (zmienne w czasie)
zobacz reguły punktacji
Język prowadzenia: polski
Skrócony opis:

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.

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

Pełny opis:

Program przedmiotu: 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.

Program wykładu i ćwiczeń:

1. Obliczanie sum skończonych podstawowymi metodami (repertuaru, czynnika sumacyjnego, zaburzeń itd.).

2. Rachunek różnicowy.

3. Rozwiązywanie równań rekurencyjnych przy użyciu metod funkcji tworzących oraz przy użyciu opanowanych wcześniej metod sumowania.

4. Przybliżone rozwiązywanie równań rekurencyjnych poprzez pewne metody formalnego rachunku w obrębie notacji „O dużego”

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.

Metody i kryteria oceniania:

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ść.

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. zimowy" (zakończony)

Okres: 2018-10-01 - 2019-02-17
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Paweł Naroski
Prowadzący grup: Paweł Naroski
Lista studentów: (nie masz dostępu)
Zaliczenie: Zaliczenie na ocenę

Zajęcia w cyklu "rok akademicki 2017/2018 - sem. zimowy" (zakończony)

Okres: 2017-10-01 - 2018-02-18
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Paweł Naroski
Prowadzący grup: Paweł Naroski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Ocena łączna
Ćwiczenia - Zaliczenie
Wykład - Egzamin

Zajęcia w cyklu "rok akademicki 2016/2017 - sem. zimowy" (zakończony)

Okres: 2016-10-01 - 2017-02-19
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Paweł Naroski
Prowadzący grup: Paweł Naroski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie
Wykład - Egzamin

Zajęcia w cyklu "rok akademicki 2014/2015 - sem. zimowy" (zakończony)

Okres: 2014-09-29 - 2015-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Paweł Naroski
Prowadzący grup: Paweł Naroski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie
Wykład - Egzamin

Zajęcia w cyklu "rok akademicki 2013/2014 - sem. zimowy" (zakończony)

Okres: 2013-10-01 - 2014-02-23
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Paweł Naroski
Prowadzący grup: Paweł Naroski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie
Wykład - Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.