Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Wstęp do Matematyki Dyskretnej
Tok studiów:
2019/2020
Kod:
AMAT-1-405-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Matematyka
Semestr:
4
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Stacjonarne
Prowadzący moduł:
dr Zwonek Małgorzata (zwonek@agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

Podstawowe pojęcia i twierdzenia niektórych dziedzin matematyki dyskretnej (m.in. teoria grafów, równania rekurencyjne, kwadraty łacińskie, konfiguracje).

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 dziedzin matematyki dyskretnej (m.in. teoria grafów, równania rekurencyjne, kwadraty łacińskie, konfiguracje) MAT1A_W01, MAT1A_W04 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_W002 zna przykłady modelowania matematycznego wykorzystującego matematykę dyskretną MAT1A_U29, MAT1A_W01 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ń MAT1A_W01, MAT1A_U01 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_U002 rozpoznaje problemy kombinatoryczne, w tym zagadnienia praktyczne, i potrafi je rozwiązać algorytmicznie MAT1A_K04, MAT1A_W01 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
Kompetencje społeczne: jest gotów do
M_K001 docenia możliwości zastosowań matematyki dyskretnej w praktyce MAT1A_K04, MAT1A_W01 Aktywność na zajęciach,
Egzamin,
Kolokwium,
Odpowiedź ustna
M_K002 Docenia potrzebę i konieczność ścisłego rozumowania i potrafi je zastosować w życiu codziennym MAT1A_K04, MAT1A_K07, MAT1A_W01 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 podstawowe pojęcia i twierdzenia niektórych dziedzin matematyki dyskretnej (m.in. teoria grafów, równania rekurencyjne, kwadraty łacińskie, konfiguracje) + + - - - - - - - - -
M_W002 zna przykłady modelowania matematycznego wykorzystującego matematykę dyskretną + + - - - - - - - - -
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 tym zagadnienia praktyczne, i potrafi je rozwiązać algorytmicznie + + - - - - - - - - -
Kompetencje społeczne
M_K001 docenia możliwości zastosowań matematyki dyskretnej w praktyce + + - - - - - - - - -
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 142 godz
Punkty ECTS za moduł 5 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 godz
Przygotowanie do zajęć 40 godz
Samodzielne studiowanie tematyki zajęć 40 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. Elementy teorii grafów

    Grafy proste. Twierdzenie o uściskach dłoni. Digrafy, multigrafy. Izomorfizm. Ścieżki, cykle. Spójność. Drzewa. Dopełnienie. Iloczyn kartezjański. Zastosowanie do problemu sztywności kratownic.

  2. Skojarzenia w grafach

    Skojarzenia w grafach dwudzielnych G(X,Y;E). Skojarzenie z X do Y. Problem małżeństw. Twierdzenie Halla. Wierzchołki wolne (słabe) i skojarzone (mocne), ścieżki przemienne i powiększające. Twierdzenie Berge’a. Dowód tw. Halla.

  3. Skojarzenia mksymalne

    Znajdywania maksymalnego skojarzenia. Algorytm (dający przy okazji minimalne pokrycie). Twierdzenie Königa. Twierdzenie Königa-Egervaryego (o macierzach 0-1). Problem przydziału zadań.

  4. Macierze permutacyjne i bistochastyczne

    Macierze permutacyjne i bistochastyczne. Twierdzenie Birkhoffa-von Neumanna. Twierdxenie o szczęściu i monogamii. Problem stabilności małżeństw. Algorytm.

  5. Zbiory częściowo uporządkowane

    Diagramy Hassego. Łańcuchy i antyłańcuchy. Twierdzenie Dilwortha. Wzmianka o innych twierdzeniach minimaksowych (Forda-Fulkersona, Mengera).

  6. Ciągi rekurencyjne

    Ciąg Fibonacciego. Równania rekurencyjne liniowe o stałych współczynnikach. Przykłady.

  7. Funkcje tworzące

    Funkcje tworzące (zwykłe i wykładnicze). Przykłady zastosowań.

  8. Kwadraty i prostokąty łacińskie

    Twierdzenie o rozszerzaniu prostokąta p na n do kwadratu n na n. Zastosowanie pierścieni Z_n.

  9. Problem 36 oficerów

    Wzajemnie ortogonalne łacińskie kwadraty (WOŁK-i). Zastosowanie ciał Galois GF do tworzenia n-1 WOŁK-ów rzędu n.

  10. Konfiguracje

    Konfiguracje kombinatoryczne (ang: BIBD) o parametrach (v,b,r,k,λ). Podstawowe związki między parametrami. Macierz konfiguracji. Nierówność Fishera. Konfiguracje symetryczne (kwadratowe).

  11. Tworzenie konfiguracji

    Konfiguracje, a WOŁK-i. Zbiory różnicowe. Konfiguracje dualne. Konfiguracje, a rozkłady grafów.

  12. Kody

    Kody wykrywające i korygujące błędy. Waga słowa. Odległość Hamminga. Kody grupowe. Kodowanie macierzowe.

  13. Wykorzystanie konfiguracji do tworzenia kodów

    Przykład kodu doskonałego. Interpretacja geometryczna (kostka).

  14. Problemy komunikacji w grafach

    Problemy komunikacji w grafach. Kostka jako minimalny graf dyfuzji.

Ćwiczenia audytoryjne (30h):
Rozwiązywanie zadań i problemów dotyczących treści przekazywanych na wykładzie.

Rozwiązywanie zadań i problemów teoretycznych ilustrujących tematykę wykładów

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 są skorelowane czasowo z egzaminami poprawkowymi.

Zasady udziału w zajęciach:
  • Wykład:
    – 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 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. Zaliczenie ćwiczeń wystawiane jest na podstawie oceny aktywności studenta i trzech prac pisemnych (takich samych i tak samo poprawianych dla całego roku);
    #Warunkiem koniecznym uzyskania pozytywnej oceny końcowej OK jest otrzymanie pozytywnej oceny z ćwiczeń i z egzaminu. Przy czym warunkiem dopuszczenia do egzaminu jest posiadanie pozytywnej oceny z ćwiczeń.
  2. Ocenę końcową wyznacza się na podstawie średniej ważonej SW obliczonej według wzoru
    SW = 0,5 OC + 0,5 OE,
    gdzie OC jest oceną uzyskaną z ćwiczeń, a OE jest oceną uzyskana z egzaminu.
  3. 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:

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 :

Nie podano wymagań wstępnych lub dodatkowych.

Zalecana literatura i pomoce naukowe:
  1. V. BRYANT, Aspekty kombinatoryki, WN-T, Warszawa 1993.
  2. W. LIPSKI I W. MAREK, Analiza kombinatoryczna, PWN, Warszawa 1986.
  3. Z. PALKA I A. RUCIŃSKI, Wykłady z kombinatoryki, WN-T, Warszawa 1998.
  4. R.J. WILSON, Wprowadzenie do teorii grafów, PWN, Warszawa 1985.
  5. M. WOŹNIAK, Dyfuzja informacji w grafach, Wyd. AGH (skrypt 1475), Kraków 1996.
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. On \emph(Cn;k) stable graphs / Sylwia CICHACZ, Agnieszka GÖRLICH, Małgorzata ZWONEK, Andrzej ŻAK // The Electronic Journal of Combinatorics [Dokument elektroniczny]. — Czasopismo elektroniczne ; ISSN 1077-8926. — 2011 vol. 18 iss. 1 poz. 205, s. [1–10]. — Tryb dostępu: http://www.combinatorics.org/Volume_18/PDF/v18i1p205.pdf [2012-02-20]

7. (H, k) stable bipartite graphs with minimum size / Aneta DUDEK, Małgorzata ZWONEK // Discussiones Mathematicae. Graph Theory ; ISSN 1234-3099. — 2009 vol. 29 no. 3, s. 573–581.
tekst: http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1465/c/dmgt.1465.pdf

8. A note on t-complementing permutations for graphs / Lech ADAMUS, Beata ORCHEL, Artur SZYMAŃSKI, A. Paweł WOJDA, Małgorzata ZWONEK // Information Processing Letters ; ISSN 0020-0190. — 2009 vol. 110 iss. 2, s. 44–45.
http://www.sciencedirect.com/science/article/pii/S0020019009002956/pdfft?md5=ba6331bacc9edc6a5f7fb5e78c340bf9&pid=1-s2.0-S0020019009002956-main.pdf

9. (H, k) stable graphs with minimum size / Aneta DUDEK, Artur SZYMAŃSKI, Małgorzata ZWONEK // Discussiones Mathematicae. Graph Theory ; ISSN 1234-3099. — 2008 vol. 28 nr 1, s. 137–149. — tekst: http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1397/c/dmgt.1397.pdf

10. On arc-coloring of digraphs / Małgorzata ZWONEK // Opuscula Mathematica ; ISSN 1232-9274. — Tytuł poprz.: Scientific Bulletins of Stanisław Staszic Academy of Mining and Metallurgy. Opuscula Mathematica. — 2006 vol. 26 no. 1, s. 185–195. — http://journals.bg.agh.edu.pl.ftlf1r4q0b48.wbg2.bg.agh.edu.pl/OPUSCULA/26-1/26-1-14.pdf

Informacje dodatkowe:

Brak