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

Celem modułu jest umożliwienie studentom zapoznanie się z teorią hipergrafów. Teoria ta jest jednym z ważniejszych działów współczesnej kombinatoryki z licznymi zastosowaniami.

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 najważniejsze fakty z historii teorii hipergrafów oraz wybrane nierozstrzygnięte hipotezy MAT2A_W06, MAT2A_W03 Egzamin,
Aktywność na zajęciach
M_W002 zna przykłady modelowania matematycznego wykorzystującego teorię grafów i hipergrafów MAT2A_W04, MAT2A_W07, MAT2A_W05 Aktywność na zajęciach,
Egzamin
M_W003 zna podstawowe pojęcia i twierdzenia teorii hipergrafów zna przykłady modelowania matematycznego wykorzystującego teorię grafów i hipergrafówzna najważniejsze fakty z historii teorii hipergrafów oraz wybrane nierozstrzygnięte hipotezy MAT2A_W01, MAT2A_W02, MAT2A_W04, MAT2A_W03, MAT2A_W07, MAT2A_W05 Aktywność na zajęciach,
Egzamin
Umiejętności: potrafi
M_U001 potrafi wykorzystać wiedzę z innych działów matematyki (algebra liniowa, topologia, matematyka dyskretna) w teorii hipergrafów MAT2A_U13, MAT2A_U10, MAT2A_U04 Aktywność na zajęciach,
Egzamin
M_U002 potrafi samodzielnie przeprowadzić proste dowody wykorzystując poznaną wiedzę z teorii hipergrafów MAT2A_U01, MAT2A_U02, MAT2A_U03 Egzamin,
Aktywność na zajęciach
M_U003 potrafi ze zrozumieniem przedstawić w mowie i piśmie poznane na wykładzie dowody twierdzeń MAT2A_U14, MAT2A_U01, MAT2A_U02, MAT2A_U03 Egzamin,
Aktywność na zajęciach
Kompetencje społeczne: jest gotów do
M_K001 umie ocenić stopień zrozumienia przez siebie problemu i brakujące elementy rozumowania MAT2A_K04, MAT2A_K02, MAT2A_K05, MAT2A_K01 Egzamin,
Aktywność na zajęciach
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 najważniejsze fakty z historii teorii hipergrafów oraz wybrane nierozstrzygnięte hipotezy + + - - - - - - - - -
M_W002 zna przykłady modelowania matematycznego wykorzystującego teorię grafów i hipergrafów + + - - - - - - - - -
M_W003 zna podstawowe pojęcia i twierdzenia teorii hipergrafów zna przykłady modelowania matematycznego wykorzystującego teorię grafów i hipergrafówzna najważniejsze fakty z historii teorii hipergrafów oraz wybrane nierozstrzygnięte hipotezy + + - - - - - - - - -
Umiejętności
M_U001 potrafi wykorzystać wiedzę z innych działów matematyki (algebra liniowa, topologia, matematyka dyskretna) w teorii hipergrafów + + - - - - - - - - -
M_U002 potrafi samodzielnie przeprowadzić proste dowody wykorzystując poznaną wiedzę z teorii hipergrafów + + - - - - - - - - -
M_U003 potrafi ze zrozumieniem przedstawić w mowie i piśmie poznane na wykładzie dowody twierdzeń + + - - - - - - - - -
Kompetencje społeczne
M_K001 umie ocenić stopień zrozumienia przez siebie problemu i brakujące elementy rozumowania + + - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 152 godz
Punkty ECTS za moduł 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 godz
Przygotowanie do zajęć 60 godz
Samodzielne studiowanie tematyki zajęć 30 godz
Egzamin lub kolokwium zaliczeniowe 2 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. Hipergrafy. Podstawowe definicje. Macierz incydencji. Hipergrafy jednolite.

2. Układy Steinera. Przestrzenie liniowe. Płaszczyzna Fano. Tw. de Bruijna-Erdoesa.

3. Nawiązanie do geometrii na płaszczyźnie. Tw. Sylvestra-Gallaia.

4. Tw. de Bruijna-Erdoesa (dowód algebraiczny). Interpretacja grafowa.

5. Skończone płaszczyzny rzutowe.

6. Liczba chromatyczna i talia hipergrafu. Grafy Zykowa. Grafy Mycielskiego. Grafy Tutte’a. Grafy Erdoesa-Hajnala.

7. Grafy Knesera. Topologiczny dowód tw. o liczbie chromatycznej grafów Knesera.

8. Zasada Dirichleta.

9. Elementy teorii Ramseya. Podstawowe oszacowania.

10. Uogólnienia teorii Ramseya. Tw. Chvatala

11. Zastosowania teorii Ramseya. Tw. Schura. Tw. Erdoesa-Szekares.

12. Liczby van der Waerdena.

13. Zliczanie i prawdopodobieństwo. Elementy ekstremalnej teorii grafów i hipergrafów. Tw. Spernera. Tw. Erdoesa-Ko-Rado.

14. Pakowanie grafów i hipergrafów.

Ćwiczenia audytoryjne (30h):
-
Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Wykład jest klasycznym wykładem tablicowym.
  • Ćwiczenia audytoryjne: Podczas zajęć audytoryjnych studenci na tablicy rozwiązują zadane wcześniej problemy.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Warunkiem przystąpienia do egzaminu
jest uzyskanie zaliczenia ćwiczeń. Studentowi przysługuje jeden termin poprawkowy zaliczenia.

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. 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
Sposób obliczania oceny końcowej:

Ocena końcowa jest równa ocenie 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 :

brak wymagań wstępnych

Zalecana literatura i pomoce naukowe:

M. Aigner, G.M. Ziegler, Proofs trom the BOOK, Springer, 2001

C. Berge, Graphes et hypergraphes, Dunod, 1970

R.Diestel, Graph Theory, 5th Edition, Springer-Verlag, 2016

W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, 1986

D.B. West, Introduction to Graph Theory, 2001

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

M.Woźniak, Packing of Graphs, Dissertationes Mathematicae 362 (1997),
pp.78.

J-F.Sacle and M.Woźniak, The Erdors-Sos conjecture for graphs without
C4, J. Combin. Theory, Series B 70 (2) (1997), 367–372.

C.Bazgan, A.Harkat-Benhamdine, H.Li and M.Woźniak, On the vertexdistinguishing
proper edge-colorings of graphs, J. Combin. Theory, Series
B 75 (1999), 288–301.

M.Woźniak, Packing of graphs and permutation — a survey, Discrete
Math. 276 (2004), 379–391.

M. Pilśniak and M. Woźniak, A note on packing of two copies of a
hypergraph, Discussiones Mathematicae-Graph Theory 27 (1) (2007),
45–49.

E. Gyori, M. Hornak, C. Palmer and M. Woźniak, General neighbourdistinguishing
index of a graph, Discrete Math. 308 (5-6) (2008),
827–831.

J. Przybyło and M. Woźniak, On a 1,2 Conjecture, Discrete Math.
Theoretical Computer Science, 12 (1) (2010), 101–108.

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

R. Kalinowski and M. Woźniak, Edge-distinguishing index of a graph,
Graphs and Combinatorics 30 (6) (2014), 1469–1477

R. Kalinowski, M. Pilśniak, M. Woźniak, Distinguishing graphs by total
colourings, ARS MATHEMATICA CONTEMPORANEA 11 (2016),
79–89.

M. Hornak, J. Przybyło, M. Woźniak, A note on a directed version of
the 1-2-3 Conjecture, Discrete Applied Math. 236 (2018), 472-476.

A. Gorzkowska, M. Pilśniak, Precise bounds for the distinguishing index of the Cartesian product,
Theoretical Computer Science 687 (2017), 62–69.

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

Informacje dodatkowe:

brak