SylabUZ

Wygeneruj PDF dla tej strony

Analiza kombinatoryczna - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Analiza kombinatoryczna
Kod przedmiotu 11.1-WK-MATD-AK-W-S14_pNadGenT0E38
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Matematyka
Profil ogólnoakademicki
Rodzaj studiów drugiego stopnia z tyt. magistra
Semestr rozpoczęcia semestr zimowy 2017/2018
Informacje o przedmiocie
Semestr 2
Liczba punktów ECTS do zdobycia 5
Typ przedmiotu obieralny
Język nauczania polski
Sylabus opracował
  • dr Magdalena Łysakowska
Formy zajęć
Forma zajęć Liczba godzin w semestrze (stacjonarne) Liczba godzin w tygodniu (stacjonarne) Liczba godzin w semestrze (niestacjonarne) Liczba godzin w tygodniu (niestacjonarne) Forma zaliczenia
Wykład 30 2 - - Zaliczenie na ocenę
Ćwiczenia 30 2 - - Zaliczenie na ocenę

Cel przedmiotu

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

Wymagania wstępne

Podstawowy kurs analizy matematycznej, algebry liniowej i matematyki dyskretnej.

Zakres tematyczny

  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.)

Metody kształcenia

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

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu Symbole efektów Metody weryfikacji Forma zajęć

Warunki zaliczenia

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.

Literatura podstawowa

  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.

Literatura uzupełniająca

  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.

Uwagi

Przedmiot oferowany również w semestrze IV.


Zmodyfikowane przez dr Robert Dylewski, prof. UZ (ostatnia modyfikacja: 09-04-2017 16:04)