Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Metody probabilistyczne w matematyce dyskretnej
Tok studiów:
2017/2018
Kod:
AMA-2-311-MZ-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Matematyka w zarządzaniu
Kierunek:
Matematyka
Semestr:
3
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
dr hab, prof. AGH Kalinowski Rafał (kalinows@agh.edu.pl)
Osoby prowadzące:
dr hab, prof. AGH Kalinowski Rafał (kalinows@agh.edu.pl)
Krótka charakterystyka modułu

Grafy losowe. Metoda probabilistyczną Erdősa, w tym metoda wartości oczekiwanej i lokalny lemat Lovásza.

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 zna metodę probabilistyczną Erdősa, w tym metodę wartości oczekiwanej i lokalny lemat Lovásza. MA2A_W05, MA2A_U11 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_W002 zna podstawy teorii grafów losowych. MA2A_W05, MA2A_U13 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Umiejętności
M_U001 potrafi zastosować poznane metody probabilistyczne do rozwiązywania deterministycznych problemów matematyki dyskretnej. MA2A_W07, MA2A_W01, MA2A_U01, MA2A_U13, MA2A_U16, MA2A_U14 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_U002 umie wyznaczyć rozkłady podstawowych niezmienników grafów losowych. MA2A_U11 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_U003 rozumie dowody twierdzeń przedstawionych na wykładzie i potrafi je przedstawić w mowie i piśmie. MA2A_U01, MA2A_U02 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 zna metodę probabilistyczną Erdősa, w tym metodę wartości oczekiwanej i lokalny lemat Lovásza. + + - - - - - - - - -
M_W002 zna podstawy teorii grafów losowych. + + - - - - - - - - -
Umiejętności
M_U001 potrafi zastosować poznane metody probabilistyczne do rozwiązywania deterministycznych problemów matematyki dyskretnej. + + - - - - - - - - -
M_U002 umie wyznaczyć rozkłady podstawowych niezmienników grafów losowych. + + - - - - - - - - -
M_U003 rozumie dowody twierdzeń przedstawionych na wykładzie i potrafi je przedstawić w mowie i piśmie. + + - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

1. Zliczanie obiektów kombinatorycznych, w tym kombinacje z powtórzeniami, rozmieszczenia. 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.

4. Podstawowa metoda probabilistyczna i jej zastosowanie do oszacowania liczb Ramseya i liczb van der Waerdena.

5. 2-kolorowanie hipergrafów. Systemy różnych reprezentantów

6.. Metoda wartości oczekiwanej i jej zastosowanie: zbiory wolne od sum, 2-kolorowanie hipergrafów.

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

8. Twierdzenie Tutte’a o grafach bez trójkątów o dowolnie dużej liczbie chromatycznej – z dowodem Mycielskiego. Twierdzenie Erdősa o istnieniu grafów z dowolnie dużą talią i dużą liczbą chromatyczną.

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

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

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

12. Własności asymptotycznie prawie wszystkich grafów. Przykłady.

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

14. Twierdzenie o funkcji progowej dla własności zawierania kliki rzędu k. Ewolucja grafów losowych (bd.).

Ćwiczenia audytoryjne:
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

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 wykładach 30 godz
Samodzielne studiowanie tematyki zajęć 60 godz
Udział w ćwiczeniach audytoryjnych 30 godz
Przygotowanie do zajęć 30 godz
Dodatkowe godziny kontaktowe z nauczycielem 5 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Pozostałe informacje
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.
Wymagania wstępne i dodatkowe:

Nie podano wymagań wstępnych lub dodatkowych.

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, J.Wiley & Sons 1992.
Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. Kalinowski, Rafał; Pilśniak, Monika; Distinguishing graphs by edge-colourings; Eur. J. Comb. 45, 124-131 (2015).

2. Kalinowski, Rafał; Woźniak, Mariusz; Edge-distinguishing index of a graph; Graphs Comb. 30, No. 6, 1469-1477 (2014).

3. Imrich, Wilfried; Kalinowski, Rafał; Lehner, Florian; Pilśniak, Monika; Endomorphism breaking in graphs. Electron. J. Comb. 21, No. 1, Research Paper P1.16, 13 p., electronic only (2014).

4. Kalinowski, Rafał; Pilśniak, Monika; Przybyło, Jakub; Woźniak, Mariusz; How to personalize the vertices of a graph? Eur. J. Comb. 40, 116-123 (2014).

5. Horňák, Mirko; Kalinowski, Rafał; Meszka, Mariusz; Woźniak, Mariusz
Minimum number of palettes in edge colorings. Graphs Comb. 30, No. 3, 619-626 (2014).

6. Baudon, Olivier; Bensmail, Julien; Kalinowski, Rafał; Marczyk, Antoni; Przybyło, Jakub; Woźniak, Mariusz
On the Cartesian product of of an arbitrarily partitionable graph and a traceable graph; Discrete Math. Theor. Comput. Sci. 16, No. 1, 225-232, (2014).

7. Kalinowski, Rafał; Pilśniak, Monika; Przybyło, Jakub; Woźniak, Mariusz; Can colour-blind distinguish colour palettes?; Electron. J. Comb. 20, No. 3, Research Paper P23, 12 p., electronic only (2013).

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

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

10. The distinguishing index of the Cartesian product of finite graphs; Aleksandra GORZKOWSKA, Rafał KALINOWSKI, Monika PILŚNIAK; Ars Mathematica Contemporanea (2017) vol. 12 no. 1, s. 77–87

11. Distinguishing cartesian products of countable graphs; Ehsan Estaji, Wilfried Imrich, Rafał KALINOWSKI, Monika PILŚNIAK, Thomas Tucker; Discussiones Mathematicae. Graph Theory (2017) vol. 37 iss. 1, s. 155–164.

Informacje dodatkowe:

Brak