1. SylabUZ
2. Faculty of Mathematics, Computer Science and Econometrics
3. winter term 2022/2023
4. Mathematics - Second-cycle studies leading to MS degree
5. Combinatorial Analysis

Generate PDF for this page

Combinatorial Analysis - course description

Aim of the course

Zapoznanie studenta z podstawowymi pojęciami, metodami analizy kombinatorycznej oraz przykładami ich zastosowań.

Prerequisites

Save changes

Podstawowy kurs analizy matematycznej, algebry liniowej i matematyki dyskretnej.

Scope

1. Współczynniki dwumianowe (2 godz.)
2. Wielomiany szachowe (2 godz.)
3. Kwadraty łacińskie (2 godz.)
4. Twierdzenie van der Waerdena, twierdzenie Schura (2 godz.)
5. Kolorowanie map, twierdzenie o czterech barwach (3 godz.)
6. Twierdzenia minimaksowe (4 godz.)
7. Konfiguracje kombinatoryczne (2 godz.)
8. Zasady kodowania i dekodowania, kody doskonałe, kod Hamminga, macierze Hadamarda, konstrukcja kodów korygujących błędy (5 godz.)
9. Lemat Spernera (3 godz.)
10. Twierdzenie Minkowskiego, twierdzenie Radona, twierdzenie Helly’ego, twierdzenie Tverberga (5 godz.)

    Ćwiczenia

1. Dowodzenie tożsamości kombinatorycznych (2 godz.)
2. Stosowanie wielomianów szachowych w zadaniach z treścią (3 godz.)
3. Uzupełnianie kwadratów łacińskich; dowodzenie własności kwadratów łacińskich (3 godz.)
4. Rozwiązywanie zadań z zastosowaniem twierdzenia van der Waerdena i twierdzenia Schura (2 godz.)

   Kolokwium (2 godz.)

5. Stosowanie twierdzenia o czterech barwach i twierdzeń minimaksowych do rozwiązywania zadań praktycznych (4 godz.)
6. Dowodzenie własności konfiguracji kombinatorycznych; zastosowania konfiguracji kombina-torycznych w zadaniach z treścią (3 godz.)
7. Sprawdzanie czy dany kod jest doskonały; konstruowanie kodów (3 godz.)
8. Rozwiązywanie zadań z zastosowaniem lematu Spernera i podstawowych twierdzeń geometrii kombinatorycznej poznanych na wykładzie (6 godz.)

   Kolokwium (2 godz.)

Teaching methods

Wykład tradycyjny; ćwiczenia, w ramach których studenci rozwiązują zadania; praca w grupach.

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Ocena z przedmiotu jest średnią arytmetyczną oceny z ćwiczeń i oceny z egzaminu. Warunkiem przystąpienia do egzaminu jest pozytywna ocena z ćwiczeń. Warunkiem zaliczenia przedmiotu jest pozytywna ocena z egzaminu.

Recommended reading

1. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa, 1986.
2. K. A. Rybnikow (red.), Analiza kombinatoryczna w zadaniach, PWN, Warszawa, 1988.
3. J. Matoušek, Lectures on Discrete Geometry, Springer, New York, 2002.

Further reading

1. Z. Palka, A. Ruciński, Wykłady z kombinatoryki, WNT, Warszawa, 1998.
2. R. L. Graham, D. E. Knuth, O. Patashnik, Matematyka konkretna, PWN, Warszawa, 2011.
3. V. Bryant, Aspekty kombinatoryki, WNT, Warszawa, 1997.

Notes

Przedmiot oferowany również w semestrze IV.

Modified by dr Alina Szelecka (last modification: 19-05-2022 21:45)