Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Komunikacja w Grafach
Tok studiów:
2019/2020
Kod:
AMAT-2-306-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ł:
prof. dr hab. Woźniak Mariusz (mwozniak@agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć
Pojęcia i twierdzenia niektórych problemów sieci komunikacyjnych. Przykłady modelowania matematycznego sieci komunikacyjnych wykorzystującego teorię grafów.
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 podstawowe pojęcia i twierdzenia niektórych problemów sieci komunikacyjnych MAT2A_W05, MAT2A_K01, MAT2A_U14, MAT2A_U01, MAT2A_W06, MAT2A_W01, MAT2A_U16, MAT2A_W02, MAT2A_K02, MAT2A_W03, MAT2A_U10, MAT2A_U04, MAT2A_U02 Aktywność na zajęciach,
Egzamin,
Kolokwium
M_W002 zna przykłady modelowania matematycznego sieci komunikacyjnych wykorzystującego teorię grafów MAT2A_W05, MAT2A_K01, MAT2A_U14, MAT2A_U01, MAT2A_W06, MAT2A_W01, MAT2A_U16, MAT2A_W02, MAT2A_K02, MAT2A_W03, MAT2A_U10, MAT2A_U04, MAT2A_U02 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Umiejętności: potrafi
M_U001 potrafi ze zrozumieniem przedstawić w mowie i piśmie poznane na wykładzie dowody twierdzeń MAT2A_W05, MAT2A_K01, MAT2A_U14, MAT2A_U01, MAT2A_W06, MAT2A_W01, MAT2A_U16, MAT2A_W02, MAT2A_K02, MAT2A_W03, MAT2A_U10, MAT2A_U04, MAT2A_U02 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_U002 rozpoznaje problemy kombinatoryczne w sieciach komunikacyjnych, w tym zagadnienia praktyczne, i potrafi je rozwiązać algorytmicznie MAT2A_W05, MAT2A_K01, MAT2A_U14, MAT2A_U01, MAT2A_W06, MAT2A_W01, MAT2A_U16, MAT2A_W02, MAT2A_K02, MAT2A_W03, MAT2A_U10, MAT2A_U04, MAT2A_U02 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Kompetencje społeczne: jest gotów do
M_K001 docenia możliwości zastosowań matematyki dyskretnej (teorii grafów) w praktyce (w zagadnieniach dotyczących sieci komunikacyjnych) MAT2A_W05, MAT2A_K01, MAT2A_U14, MAT2A_U01, MAT2A_W06, MAT2A_W01, MAT2A_U16, MAT2A_W02, MAT2A_K02, MAT2A_W03, MAT2A_U10, MAT2A_U04, MAT2A_U02 Egzamin
M_K002 Docenia potrzebę i konieczność ścisłego rozumowania i potrafi je zastosować w życiu codziennym MAT2A_W05, MAT2A_K01, MAT2A_U14, MAT2A_U01, MAT2A_W06, MAT2A_W01, MAT2A_U16, MAT2A_W02, MAT2A_K02, MAT2A_W03, MAT2A_U10, MAT2A_U04, MAT2A_U02 Egzamin
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 30 0 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 podstawowe pojęcia i twierdzenia niektórych problemów sieci komunikacyjnych + - - - - - - - - - -
M_W002 zna przykłady modelowania matematycznego sieci komunikacyjnych wykorzystującego teorię grafów + - - - - - - - - - -
Umiejętności
M_U001 potrafi ze zrozumieniem przedstawić w mowie i piśmie poznane na wykładzie dowody twierdzeń + - - - - - - - - - -
M_U002 rozpoznaje problemy kombinatoryczne w sieciach komunikacyjnych, w tym zagadnienia praktyczne, i potrafi je rozwiązać algorytmicznie + - - - - - - - - - -
Kompetencje społeczne
M_K001 docenia możliwości zastosowań matematyki dyskretnej (teorii grafów) w praktyce (w zagadnieniach dotyczących sieci komunikacyjnych) + - - - - - - - - - -
M_K002 Docenia potrzebę i konieczność ścisłego rozumowania i potrafi je zastosować w życiu codziennym + - - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 100 godz
Punkty ECTS za moduł 4 ECTS
Udział w zajęciach dydaktycznych/praktyka 30 godz
przygotowanie projektu, prezentacji, pracy pisemnej, sprawozdania 20 godz
Samodzielne studiowanie tematyki zajęć 43 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. Przypomnienie podstawowych pojęć i notacji teorii grafów

    Stopień, tw. o uściskach dłoni, grafy zwykłe, digrafy, multigrafy; podgrafy; drogi, ścieżki, cykle. Iloczyn kartezjański. Ciągi 0-1. Kody Graya.

  2. Spójność wierzchołkowa i krawędziowa

    Parametry κ i κ’. Tw. Whitneya. Grafy 2-spójne. Lemat o rozszerzaniu. Warunki równoważne 2-spójności.

  3. Rozkłady "uchate"

    Rozkłady uchate. Ucho. Rozkład uchaty. Tw. Whitneya o rozkładzie uchatym.
    Uogólnione rozkłady uchate. Spójność w digrafach. Tw. Robbinsa.

  4. Dyfuzja

    Dyfuzja (broadcasting). Minimalne grafy dyfuzji. Kostka p-wymiarowa jako minimalny graf dyfuzji.

  5. Wymiana informacji Gossiping. Kostka p-wymiarowa jako minimalny graf wymiany. Wymiana w grafie pełnym.
  6. Minimalizacja liczby połączeń

    Tw. Bakera-Shostaka.

  7. Dowód twierdzenia Bakera-Shostaka
  8. Realizacja permutacji. Algorytm dla ścieżki i kraty
  9. Motyle otwarte FFT

    Własności rekursywne. Sieci Beneša. Ścieżki rozłączne w sieciach Beneša.

  10. Realizacja permutacji dla motyli zwiniętych BF.
  11. Motyl jako sieć uniwersalna
  12. Zanurzenia grafów

    Dylatacja, zatłoczenie, ekspansja. Zanurzanie krat w kostkę.

  13. Zanurzanie grafów

    Zanurzanie drzew binarnych i drzew BDR. Graf CCC (cube-connected-graph). Zanurzenie grafu CCC w graf BF

  14. Sieci komutacyjne

    Sieci dynamiczne (komutacyjne). Sieci bez blokady. Sieci ustawne. Sieci Closa. Inne sieci komutacyjne.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Wykład jest klasycznym wykładem tablicowym.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Obecność na wykładach nie jest obowiązkowa.

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

We własnym zakresie.

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

Nie podano wymagań wstępnych lub dodatkowych.

Zalecana literatura i pomoce naukowe:
  1. J. de Rumeur, Communications dans les réseaux de processeurs, Paryż, Masson 1994.
  2. M. Woźniak, Dyfuzja informacji w grafach, Kraków, Wydawnictwa AGH, 1996.
  3. M. Woźniak, Wprowadzenie do problemów komunikacji w grafach, Kraków, Wydawnictwa AGH, 1999.
Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. Baudon, O.; Bensmail, J.; Przybyło, J.; Woźniak, M.; On decomposing regular graphs into locally irregular subgraphs; Eur. J. Comb. 49, Article ID 2413, 90-104 (2015).

2. Pilśniak, Monika; Woźniak, Mariusz; On the total-neighbor-distinguishing index by sums; Graphs Comb. 31, No. 3, 771-782 (2015).

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

4. Baudon, Olivier; Foucaud, Florent; Przybyło, Jakub; Woźniak, Mariusz;
On the structure of arbitrarily partitionable graphs with given connectivity;
Discrete Appl. Math. 162, Part 1, 381-385 (2014).

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

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

7. 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, electronic only (2014).

8. Baudon, Olivier; Bensmail, Julien; Przybyło, Jakub; Woźniak, Mariusz
Partitioning powers of traceable or Hamiltonian graphs;
Theor. Comput. Sci. 520, 133-137 (2014).

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

10. Kemnitz, Arnfried; Przybyło, Jakub; Schiermeyer, Ingo; Woźniak, Mariusz;
Rainbow connection in sparse graphs.
Discuss. Math., Graph Theory 33, No. 1, 181-192 (2013).

11. Flandrin, Evelyne; Marczyk, Antoni; Przybyło, Jakub; Saclé, Jean-François; Woźniak, Mariusz;
Neighbor sum distinguishing index; Graphs Comb. 29, No. 5, 1329-1336 (2013).

12. Hornak, Mirko; Wozniak, Mariusz; On neighbour-distinguishing colourings from lists;
Discrete Math. Theor. Comput. Sci. 14, No. 2, 21-28, electronic only (2012).

13. Baudon, Olivier; Gilbert, Frédéric; Woźniak, Mariusz; Recursively arbitrarily vertex-decomposable graphs; Opusc. Math. 32, No. 4, 689-706 (2012).

14. Horňák, Mirko; Marczyk, Antoni; Schiermeyer, Ingo; Woźniak, Mariusz
Dense arbitrarily vertex decomposable graphs. Graphs Comb. 28, No. 6, 807-821 (2012).

15. Plachta, Leonid; Przybyło, Jakub; Woźniak, Mariusz;
Seifert graphs and the braid index of classical and singular links;
Discrete Math. 312, No. 18, 2819-2831 (2012).

16. Pilśniak, Monika; Woźniak, Mariusz; On packing of two copies of a hypergraph;
Discrete Math. Theor. Comput. Sci. 13, No. 3, 67-74, electronic only (2011).

Informacje dodatkowe:

Brak