Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Metody probabilistyczne w matematyce dyskretnej
Tok studiów:
2019/2020
Kod:
AMAT-2-302-MI-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Matematyka w informatyce
Kierunek:
Matematyka
Semestr:
3
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Stacjonarne
Strona www:
 
Prowadzący moduł:
dr hab, prof. AGH Kalinowski Rafał (kalinows@agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

Metoda probabilistyczna Erdősa, w tym metoda wartości oczekiwanej i lokalny lemat Lovásza. Podstawy teorii grafów losowych.

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 zna podstawy teorii grafów losowych. MAT2A_W05, MAT2A_W09, MAT2A_W07, MAT2A_W01, MAT2A_U13 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_W002 zna metodę probabilistyczną Erdősa, w tym metodę wartości oczekiwanej i lokalny lemat Lovásza. MAT2A_W05, MAT2A_W09, MAT2A_U11 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Umiejętności: potrafi
M_U001 rozumie dowody twierdzeń przedstawionych na wykładzie i potrafi je przedstawić w mowie i piśmie. MAT2A_U01, MAT2A_U02 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_U002 potrafi zastosować poznane metody probabilistyczne do rozwiązywania deterministycznych problemów matematyki dyskretnej. MAT2A_U12, MAT2A_W12, MAT2A_U14, MAT2A_U01, MAT2A_U16, MAT2A_U13, MAT2A_U11 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_U003 umie wyznaczyć rozkłady podstawowych niezmienników grafów losowych. MAT2A_U17, MAT2A_U18, MAT2A_U16, MAT2A_U11 Aktywność na zajęciach,
Egzamin,
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
60 30 30 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 zna podstawy teorii grafów losowych. + + - - - - - - - - -
M_W002 zna metodę probabilistyczną Erdősa, w tym metodę wartości oczekiwanej i lokalny lemat Lovásza. + + - - - - - - - - -
Umiejętności
M_U001 rozumie dowody twierdzeń przedstawionych na wykładzie i potrafi je przedstawić w mowie i piśmie. + + - - - - - - - - -
M_U002 potrafi zastosować poznane metody probabilistyczne do rozwiązywania deterministycznych problemów matematyki dyskretnej. + + - - - - - - - - -
M_U003 umie wyznaczyć rozkłady podstawowych niezmienników grafów losowych. + + - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 157 godz
Punkty ECTS za moduł 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 godz
Przygotowanie do zajęć 30 godz
Samodzielne studiowanie tematyki zajęć 60 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 (30h):

1. Zliczanie obiektów kombinatorycznych. Zasada włączania i wyłączania. Działanie grupy na zbiorze.

2. Podstawowy model grafów losowych. Wybrane niezmienniki grafów jako zmienne losowe.

3. Twierdzenie Ramseya. Liczby Ramseya. Podstawowa metoda probabilistyczna. Metoda wartości oczekiwanej i jej zastosowania do oszacowania liczb Ramseya.

4. Metoda modyfikacji i jej zastosowanie do oszacowania liczby niezależności grafu. Twierdzenie o zbiorze dominującym.

5. Twierdzenie Turana (z dowodem Alona-Spencera).

6. Twierdzenie Tutte’a o grafach bez trójkątów o dowolnie dużej liczbie chromatycznej (z dowodem Mycielskiego).

7. Twierdzenie Erdősa o istnieniu grafów z dowolnie dużą talią i dużą liczbą chromatyczną.

8. Lokalny lemat Lovásza (LLL) w wersji symetrycznej (bd.) i jego zastosowanie do 2-kolorowania regularnych hipergrafów jednolitych.

9. Twierdzenie Erdősa-Lovásza o kolorowaniu prostej.

10. LLLL i jego zastosowanie do 2-kolorowania hipergrafów.

11. Własności asymptotycznie prawie wszystkich grafów. Lemat Erdősa-Rényiego.

12. Funkcje progowe własności grafów. Metoda pierwszego momentu. Metoda drugiego momentu.

13. Twierdzenie Erdősa-Rényiego. Funkcja progowa dla własności zawierania ustalonego podgrafu wyważonego.

14. Funkcja progowa dla spójności grafu. Ewolucja grafów losowych.

15. Nieskończony graf losowy.

Ćwiczenia audytoryjne (30h):
Program ćwiczeń pokrywa się z programem wykładów

Rozwiązywanie problemów (głównie związanych z zagadnieniami teoretycznymi) ilustrujących treści przekazywanych na kolejnych 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 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:

Warunkiem koniecznym dopuszczenia do egzaminu jest posiadanie oceny pozytywnej z ćwiczeń.
Dwa terminy zaliczeń poprawkowych są skorelowane czasowo z egzaminami poprawkowymi.

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 uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci mogą na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
Sposób obliczania oceny końcowej:
  1. Warunkiem koniecznym dopuszczenia do egzaminu jest posiadanie oceny pozytywnej z ćwiczeń.
  2. Ocenę końcową OK wyznacza się na podstawie średniej ważonej SW obliczonej według wzoru
    SW = 1/3 OC + 2/3 OE,
    gdzie OC jest oceną uzyskaną z ćwiczeń,
    a OE jest oceną uzyskaną z egzaminu.
Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Student powinien zgłosić się do prowadzącego w celu ustalenia indywidualnego sposobu nadrobienia zaległości.

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

Wymagane jest zaliczenie modułów:
- teoria grafów,
- wstęp do rachunku prawdopodobieństwa.

Zalecana literatura i pomoce naukowe:
  1. Z. Palka, A. Ruciński, Niekonstruktywne metody matematyki dyskretnej, WNT 1996.
  2. N. Alon, J. Spencer, The Probabilistic Method, 4th ed., Wiley 2016.
Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. R.Kalinowski, Dense on-line arbitrarily partitionable graphs, Discrete Appl. Math. 226 (2017), 71–77.

2. E. Estaji, W. Imrich, R.Kalinowski, M. Pilśniak, T.Tucker, Distinguishing Cartesian products of countable graphs, Discuss. Math. Graph Theory 37 (2017), 155–164.

3. W. Imrich, R.Kalinowski, M. Pilśniak, M. Shekarriz, Bounds for Distinguishing Invariants of Infinite Graphs, Electron. J. Combin. 24(3) (2017), #P3.6 [14 pp.].

4. R. Kalinowski, M. Pilśniak, M.Woźniak, A Note on Breaking Small Automorphisms in Graphs, Discrete Appl. Math. 232 (2017), 221–225.

5. A. Gorzkowska, R. Kalinowski, M. Pilśniak, The distinguishing index of the Cartesian product of finite graphs, Ars Math. Contemp. 12(1) (2017), 77–87.

6. Kalinowski, Rafał; Pilśniak, Monika; Schiermeyer, Ingo; Woźniak, Mariusz; Dense arbitrarily partitionable graphs, Discuss. Math. Graph Theory 36 (2016) 5-22.

7. Kalinowski, Rafał; Pilśniak, Monika; Woźniak, Mariusz; Distinguishing graphs by total colourings, Ars Math. Contemp. 11 (2016), 79-89.

8. Kalinowski, Rafał; Pilśniak, Monika; Distinguishing graphs by edge-colourings.; European J. Combin. 45, 124-131 (2015).

9. R.Kalinowski, M. Pilśniak, J. Przybyło, M.Woźniak, How to personalize the vertices of a graph?, European J. Combin. 40 (2014), 116–123.

10. W. Imrich, R.Kalinowski, F. Lehner, M. Pilśniak, Endomorphism breaking in graphs, Electron. J. Combin. 21(1) (2014), #P1.16 [13 pp.].

Informacje dodatkowe:

Brak