1. SylabUZ
2. Faculty of Mathematics, Computer Science and Econometrics
3. winter term 2021/2022
4. Data Engineering - First-cycle studies leading to Engineer's degree
5. Combinatorial Foundations of Computer Science

Generate PDF for this page

Combinatorial Foundations of Computer Science - course description

Aim of the course

Celem kursu Kombinatoryczne podstawy informatyki jest zapoznanie studentów z podstawowymi metodami zliczania obiektów kombinatorycznych oznaczonych i nieoznaczonych. Umiejętności te mogą i powinny być wykorzystane w celu szacowania wielkości danych i zasobów niezbędnych do rozwiązania danego problemu  oraz badania jego złożoności obliczeniowej. Ponadto kurs ma na celu pokazanie studentom metod probabilistycznych w kombinatoryce i informatyce oraz sposobów ich derandomizacji.

Prerequisites

Save changes

Podstawy rachunku prawdopodobieństwa,  analizy matematycznej.

Scope

Wykład:

1.      Metody przeliczania obiektów kombinatorycznych oznaczonych (10  godz.)

2.      Metody przeliczania obiektów kombinatorycznych nieoznaczonych, twierdzenie Polya (6 godz.)

3.      Metoda probabilistyczna Erdösa, derandomizacja metody probabilistycznej metodą prawdopodobieństw warunkowych (8 godz.)

4.      Algorytmy zrandomizowane, ich typy i charakterystyki (6 godz.).

Ćwiczenia:

1.      Elementy kombinatoryki oznaczonej:

a.      rozpoznawanie obiektów kombinatorycznych w zadaniu z treścią; odniesienia do pojęcia funkcji działającej na zbiorach skończonych, które są dowolne, różnowartościowe, „na”, malejące, niemalejące; wykorzystanie znanych wzorów w celu zliczenia rozpoznanych obiektów (4 godz.)

b.      stosowanie zasad: podziałowej, włączeń i wyłączeń, podwójnego zliczania, rekurencji (6 godz.)

2.      Stosowanie twierdzenia Polya do zliczania obiektów kombinatorycznych nieoznaczonych (6 godz.)

3.      Metoda probabilistyczna Erdösa: znajdowanie struktur kombinatorycznych z wykorzystaniem metod: naiwnej, wartości oczekiwanej (6 godz.)

4.      Deterministyczne znajdowanie obiektów kombinatorycznych, których istnienie wynika z metody probabilistycznej  (metoda prawdopodobieństw warunkowych) (2 godz.)

5.      Analiza algorytmów zrandomizowanych i ich parametrów losowych (4 godz.)

6.      Kolokwium (2 godz.).

Laboratorium:

1.    Rozwiązywanie bardziej skomplikowanych zadań obliczeniowych z zakresu prowadzonych ćwiczeń z wykorzystaniem wybranego pakietu matematycznego lub samodzielnie napisanego programu komputerowego.

Teaching methods

Wykład konwersatoryjny; wykład tradycyjny; ćwiczenia dyskusyjne; laboratoria audytoryjne.

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Na ocenę z przedmiotu składa się ocena z laboratorium (25%), ocena z ćwiczeń (50%) oraz ocena z egzaminu (25%).

Warunkiem zaliczenia przedmiotu jest uzyskanie pozytywnych ocen z laboratorium, ćwiczeń i egzaminu.

Recommended reading

1. Z. Palka, A. Rucinski, Wykłady z kombinatoryki, cz. I, WNT, Warszawa, 1998.
2. K.A. Ross, Ch.R.B. Wright, Matematyka dyskretna, PWN, Warszawa, 1996.
3. Diesel, Grach Theory, Springer-Verlag, Heidelberg, Gradule Test In Mathematics, Vol. 173.
4. N. Alon, J. Spencer, The Probabilistic Method, Wiley, second edition, 2000.
5. R. Motwani, P. Raghavan, Randomized Algorithms. Cambridge University Press, second edition 2000.

Further reading

1. W. Lipski, Kombinatoryka dla programistów, WNT, 2005.
2. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa, 1989.
3. C.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (seria Klasyka Informatyki).

Notes

Modified by dr Alina Szelecka (last modification: 05-05-2021 13:03)