SylabUZ

Wygeneruj PDF dla tej strony

Matematyka dyskretna 2 - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Matematyka dyskretna 2
Kod przedmiotu 11.1-WK-MATP-MD2-W-S14_pNadGenZAMHC
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Matematyka
Profil ogólnoakademicki
Rodzaj studiów pierwszego stopnia z tyt. licencjata
Semestr rozpoczęcia semestr zimowy 2018/2019
Informacje o przedmiocie
Semestr 4
Liczba punktów ECTS do zdobycia 6
Typ przedmiotu obieralny
Język nauczania polski
Sylabus opracował
  • dr hab. Ewa Drgas-Burchardt, prof. UZ
Formy zajęć
Forma zajęć Liczba godzin w semestrze (stacjonarne) Liczba godzin w tygodniu (stacjonarne) Liczba godzin w semestrze (niestacjonarne) Liczba godzin w tygodniu (niestacjonarne) Forma zaliczenia
Wykład 30 2 - - Egzamin
Ćwiczenia 30 2 - - Zaliczenie na ocenę

Cel przedmiotu

Poznanie zaawansowanych pojęć matematyki dyskretnej w aspekcie teoretycznym i algorytmicznym.

Wymagania wstępne

Matematyka dyskretna 1.

Zakres tematyczny

Wykład

  1. Różne rodzaje dominowania w grafach (6 godz.).
  2. Grafy przecięć rodzin zbiorów, krawędziowe, totalne, przedziałowe, łukowe i inne; ich własności i zastosowania (8 godz.).
  3. Digrafy, definicje i oznaczenia, digrafy tranzytywne i acykliczne, ich własności (8 godz.).
  4. Matroidy i ich własności, twierdzenie Rado-Edmondsa, twierdzenie Rado o niezależnych transwersalach (8 godz.).

Ćwiczenia

  1. Rozpoznawanie w zadaniach z treścią problemów grafowych związanych z dominowaniem. Teoretyczne i algorytmiczne rozwiązywanie tego typu problemów, w szczególności znajdowanie  liczb dominujących grafu. Dowodzenie prostych faktów teoretycznych związanych z tą tematyką (6 godz.).
  2. Badanie własności grafów przecięć ze szczególnym zwróceniem uwagi na zastosowania tych grafów (6 godz.).
  3. Macierzowe reprezentacje digrafów w kontekście badania ich własności w szczególności tranzytywności i acykliczności, analiza algorytmów digrafowych (8 godz.).
  4. Zapoznanie się z pojęciem matroidu z uwzględnieniem matroidu grafowego, kografowego, wektorowego i jednorodnego. Badanie własności matroidu poprzez dowodzenie prostych faktów związanych z tym pojęciem. Poznanie znaczenia tej struktury w kontekście algorytmu zachłannego (8 godz.).
  5. Kolokwium zaliczeniowe (2 godz.).

Metody kształcenia

Wykład konwersatoryjny, wykład tradycyjny, ćwiczenia dyskusyjne.

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu Symbole efektów Metody weryfikacji Forma zajęć

Warunki zaliczenia

Warunki zaliczenia poszczególnych zajęć:

  1. Sprawdzanie stopnia przygotowania studentów oraz ich aktywności w trakcie ćwiczeń.
  2. Sprawdzian, podczas ćwiczeń, z zadaniami o zróżnicowanym stopniu trudności, pozwalający na ocenę czy i w jakim stopniu, student osiągnął wymienione efekty kształcenia głównie w zakresie umiejętności i kompetencji.
  3. Konwersacja podczas wykładu w celu weryfikacji wyższych poziomów efektów kształcenia w zakresie wiedzy i umiejętności.
  4. Praca pisemna weryfikująca efekty kształcenia w zakresie wiedzy i kompetencji zdobyte podczas wykładu.
  5. Odpowiedź ustna uzupełniająca wypowiedź pisemną zaliczającą wykład.

Na ocenę z przedmiotu składa się ocena z ćwiczeń (50%) i ocena z egzaminu (50%). Warunkiem przystąpienia do egzaminu jest uzyskanie pozytywnej oceny z ćwiczeń. Warunkiem zaliczenia przedmiotu jest uzyskanie pozytywnych ocen zaliczających ćwiczenia i wykład.

Literatura podstawowa

  1. J. Bang-Jensen, G.Gutin, Digraphs, Theory and Algorithms, 2001.
  2. K. A. Ross, Ch.R.B. Wright, Matematyka dyskretna, PWN, Warszawa, 1996.
  3. R.J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 1998.

Literatura uzupełniająca

  1. W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 2005.

Uwagi

Przedmiot oferowany również w semestrze VI.


Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 28-04-2018 08:59)