Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Kombinatoryka Ekstremalna
Tok studiów:
2019/2020
Kod:
AMAT-2-022-MO-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Matematyka obliczeniowa i komputerowa
Kierunek:
Matematyka
Semestr:
0
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Stacjonarne
Strona www:
 
Prowadzący moduł:
prof. zw. dr hab. Wojda Adam Paweł (wojda@agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

Pogłębioną wiedza z zakresu algebry abstrakcyjnej i kombinatoryki.

Opis efektów uczenia się dla modułu zajęć
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Powiązania z KEU Sposób weryfikacji i oceny efektów uczenia się osiągniętych przez studenta w ramach poszczególnych form zajęć i dla całego modułu zajęć
Wiedza: zna i rozumie
M_W001 Posiada pogłębioną wiedzę z zakresu algebry abstrakcyjnej i kombinatoryki MAT2A_W01 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
M_W002 Zna powiązanie zagadnień kombinatoryki z algebrą liniową i abstrakcyjną MAT2A_W07 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
Umiejętności: potrafi
M_U001 Posiada umiejętność dowodzenia twierdzeń z zakresu kombinatoryki MAT2A_U01 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
M_U002 W zagadnieniach matematycznych dostrzega struktury związane z podstawowymi działami matematyki MAT2A_U04 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
M_U003 Potrafi stosować metody algebraiczne w rozwiązywaniu problemów kombinatoryki MAT2A_U10 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
Kompetencje społeczne: jest gotów do
M_K001 Potrafi samodzielnie wyszukiwać informacje w literaturze, także w językach obcych MAT2A_K06 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
Liczba godzin zajęć w ramach poszczególnych form zajęć:
SUMA (godz.)
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
30 15 15 0 0 0 0 0 0 0 0 0
Matryca kierunkowych efektów uczenia się w odniesieniu do form zajęć i sposobu zaliczenia, które pozwalają na ich uzyskanie
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Forma zajęć dydaktycznych
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Wiedza
M_W001 Posiada pogłębioną wiedzę z zakresu algebry abstrakcyjnej i kombinatoryki + + - - - - - - - - -
M_W002 Zna powiązanie zagadnień kombinatoryki z algebrą liniową i abstrakcyjną + + - - - - - - - - -
Umiejętności
M_U001 Posiada umiejętność dowodzenia twierdzeń z zakresu kombinatoryki + + - - - - - - - - -
M_U002 W zagadnieniach matematycznych dostrzega struktury związane z podstawowymi działami matematyki + + - - - - - - - - -
M_U003 Potrafi stosować metody algebraiczne w rozwiązywaniu problemów kombinatoryki + + - - - - - - - - -
Kompetencje społeczne
M_K001 Potrafi samodzielnie wyszukiwać informacje w literaturze, także w językach obcych + + - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 50 godz
Punkty ECTS za moduł 2 ECTS
Udział w zajęciach dydaktycznych/praktyka 30 godz
Samodzielne studiowanie tematyki zajęć 13 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Dodatkowe godziny kontaktowe 5 godz
Szczegółowe treści kształcenia w ramach poszczególnych form zajęć (szczegółowy program wykładów i pozostałych zajęć)
Wykład (15h):
  1. Metody zliczania

    Przypomnienie metod poznanych wcześniej (współczynniki dwumienne Newtona,
    wariacje z powtórzeniami). Liczby Stirlinga I i II rodzaju. Liczba permutacji typu
    (l_1,l_2,…,l_n) zbioru n-elementowego (tw. Cauchy’ego), liczba podziałów typu
    (l_1,l_2,…,l_n) zbioru n-elementowego. Wybory z powtórzeniami – sformułowanie
    Lovásza, Pélikana i Vesztergombiego.
    Metoda podwójnego zliczania – liczby Turána T(n,k,l) . Metoda średnich.

  2. Teoria zliczania Frobeniusa-Burnside'a

    Teoria zliczania Frobeniusa-Burnside’a (przypomnienie) i twierdzenie Redfielda-Polya.

  3. Zasada włączania i wyłączania

    Zasada włączania i wyłączania (przypomnienie) – liczba nieporządków.

  4. Zasada gołębnika

    Zasada gołębnika – twierdzenie Erdősa-Szekeresa.

  5. Twierdzenie Erdősa-Ko-Rado

    Słoneczniki – rodziny zbiorów przecinających. Twierdzenie Erdősa-Ko-Rado.

  6. Metody algebraiczne

    Przestrzenie wektorów incydencji: nierówność Fishera. Miasta parzyste i nieparzyste.Funkcje k-progowe – lemat Razborowa (z dowodem Lovásza, Shmoysa i Tardosa).

  7. Przestrzenie wielomianów

    Twierdzenia o liczności zbiorów punktów równoodległych i zbioru punktów o dwóch odległościach. Twierdzenie o rodzinach zbiorów L-przecinających. Twierdzenie Bollobása (z algebraicznym dowodem Lovásza.

  8. Grafy Ramseya

    Twierdzenia van der Waerdena i Ramseya (dla zbiorów i dla grafów). Konstrukcja grafów Ramseya (Frankl i Wilson).

Ćwiczenia audytoryjne (15h):
Program ćwiczeń pokrywa się z programem wykładu

Podczas ćwiczeń rozwiązywane są zadania ilustrujące zagadnienia omawiane na wykładach.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Wykład jest klasycznym wykładem tablicowym. Mile widziana aktywność studentów podczas wykładu - np. zadawanie pytań wykładowcy.
  • Ćwiczenia audytoryjne: Podczas zajęć audytoryjnych studenci na tablicy rozwiązują zadane wcześniej problemy. Prowadzący na bieżąco dokonuje stosowanych wyjaśnień i moderuje dyskusję z grupą nad danym problemem.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Dwa terminy zaliczeń poprawkowych

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Nie
    – Zasady udziału w zajęciach: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
  • Ćwiczenia audytoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci przystępując do ćwiczeń są zobowiązani do przygotowania się w zakresie wskazanym każdorazowo przez prowadzącego (np. w formie zestawów zadań). Ocena pracy studenta może bazować na wypowiedziach ustnych lub pisemnych w formie kolokwium, co zgodnie z regulaminem studiów AGH przekłada się na ocenę końcową z tej formy zajęć.
Sposób obliczania oceny końcowej:
  1. Ocenę końcową OK wyznacza się na podstawie średniej ważonej SW obliczonej według wzoru
    SW = 1/3 SOK + 2/3 OKZal,
    gdzie SOK jest średnią z ocen z wszystkich kolokwiów pisanych podczas całego semestru,
    a OKZal jest oceną uzyskaną z kolokwium zaliczeniowego.
  2. Ocena końcowa OK. jest obliczana według algorytmu:
    Jeżeli SW ≥ 4.75, to OK = 5.0 (bdb),
    jeżeli 4.75 > SW ≥ 4.25, to OK = 4.5 (db),
    jeżeli 4.25 > SW ≥ 3.75, to OK = 4.0 (db),
    jeżeli 3.75 > SW ≥ 3.25, to OK = 3.5 (dst),
    jeżeli 3.25 > SW ≥ 3.00, to OK = 3.0 (dst).
Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Indywidualnie

Wymagania wstępne i dodatkowe, z uwzględnieniem sekwencyjności modułów :

Algebra liniowa, algebra abstrakcyjna, matematyka dyskretna

Zalecana literatura i pomoce naukowe:
  1. L. Babai i P. Frankl, Linear Algebra Methods in Combinatorics, Preliminary Version 2, University of Chicago 1993.
  2. S. Jukna, Extremal Combinatorics: With Applications in Computer Science, Springer 2001.
  3. W. Lipski i W. Marek, Analiza kombinatoryczna, PWN 1986
  4. L. Lovász, D.B. Shmoys i E. Tardos, Combinatorics in computer science, w: Handbook of Combinatorics, R. Graham, M. Grötschel, i L. Lovász, Elsevier Science, vol. 2, 1995.
  5. A. Slomson, An Introduction to Combinatorics, Chapman & Hall/CRC.
Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. Gosselin, Shonda; Szymański, Artur; Wojda, Adam Pawel
Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs;
Discrete Math. Theor. Comput. Sci. 15, No. 2, 215-222, electronic only (2013).

2. Fouquet, Jean-Luc; Thuillier, Henri; Vanherpe, Jean-Marie; Wojda, Adam Paweł
On (K q ,k) stable graphs with small k.
Electron. J. Comb. 19, No. 2, Research Paper P50, 10 p., electronic only (2012).

3. Fouquet, J.-L.; Thuillier, H.; Vanherpe, J.-M.; Wojda, A.P.
On (K q ,k) vertex stable graphs with minimum size.
Discrete Math. 312, No. 14, 2109-2118 (2012).

4. Szymanski, Artur; Wojda, A.Paweł
Cyclic partitions of complete uniform hypergraphs. (English) Zbl 1204.05066
Electron. J. Comb. 17, No. 1, Research Paper R118, 12 p., electronic only (2010).

5. Adamus, Lech; Orchel, Beata; Szymański, Artur; Wojda, A.Paweł; Zwonek, Małgorzata
A note on t-complementing permutations for graphs.
Inf. Process. Lett. 110, No. 2, 44-45 (2009).

6. Szymański, Artur; Wojda, Adam Paweł
Self-complementing permutations of k-uniform hypergraphs;
Discrete Math. Theor. Comput. Sci. 11, No. 1, 117-124, electronic only (2009).

Informacje dodatkowe:

Brak