SylabUZ

Wygeneruj PDF dla tej strony

Matematyka dyskretna 1 - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Matematyka dyskretna 1
Kod przedmiotu 11.1-WA-IiEP-MatDys1-S17
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Informatyka i ekonometria
Profil ogólnoakademicki
Rodzaj studiów pierwszego stopnia z tyt. licencjata
Semestr rozpoczęcia semestr zimowy 2019/2020
Informacje o przedmiocie
Semestr 2
Liczba punktów ECTS do zdobycia 6
Typ przedmiotu obowiązkowy
Język nauczania polski
Sylabus opracował
  • dr Anna Fiedorowicz
  • dr hab. Ewa Drgas-Burchardt, prof. UZ
  • dr hab. Elżbieta Sidorowicz, 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 - - Zaliczenie na ocenę
Ćwiczenia 30 2 - - Zaliczenie na ocenę

Cel przedmiotu

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

Wymagania wstępne

Algebra liniowa 1.

Zakres tematyczny

Wykład

  1. Podstawowe prawa przeliczania, zasada włączeń i wyłączeń, zasada podziałowa.
  2. Rekurencja.
  3. Podstawowe pojęcia teorii grafów: sąsiedztwo, incydencja, izomorfizm, ścieżki i cykle, spójność, podgrafy. Macierze grafów i inne sposoby reprezentacji grafów.
  4. Wybrane klasy grafów (drogi, cykle, pełne, n-dzielne). Wybrane operacje na grafach (dopełnienie, suma, złączenie).
  5. Drzewa i ich własności.
  6. Algorytmy przeszukiwania grafów (DFS, BFS).
  7. Przestrzenie wektorowe związane z grafami.
  8. n-spójność grafów.
  9. Grafy Eulera i Hamiltona, algorytmy z powracaniem.
  10. Grafy planarne, charakterystyka.
  11. Pokrycia, niezależność i dominowanie.
  12. Systemy różnych reprezentantów, twierdzenie Halla; skojarzenie pełne w grafie dwudzielnym, wyznaczanie systemu różnych reprezentantów.

Ćwiczenia

  1. Rozpoznawanie obiektów kombinatorycznych w zadaniach z treścią. Wykorzystanie znanych wzorów w celu zliczania tych obiektów.
  2. Zastosowanie zasady włączeń i wyłączeń, zasady podziałowej w zadaniach z treścią.
  3. Dowodzenie prostych tożsamości kombinatorycznych.
  4. Tworzenie związków rekurencyjnych. Rozwiązywanie jednorodnych równań rekurencyjnych, z wykorzystaniem równania charakterystycznego oraz indukcji matematycznej.
  5. Zapoznanie z podstawowymi pojęciami z teorii grafów, przykłady ilustrujące te pojęcia. Omówienie sposobów reprezentacji grafu, podstawowych klas grafów i operacji na grafach na przykładach.
  6. Badanie podstawowych własności drzew. Zliczanie drzew zaetykietowanych, przeszukiwanie grafów znanymi algorytmami z uwzględnieniem konstrukcji zbiorów cykli fundamentalnych i przekrojów elementarnych. Generowanie przestrzeni cykli i przekrojów grafu.
  7. Badanie spójności grafu.
  8. Wyznaczanie cykli Eulera i Hamiltona w grafie, z wykorzystaniem odpowiednich algorytmów. Zadania związane z własnościami grafów Eulera i Hamiltona.
  9. Planarność grafu, zadania z zastosowaniem twierdzeń Eulera i Kuratowskiego.
  10. Znajdowanie liczb niezależności i pokrycia oraz dominowania w grafie, zastosowanie tych pojęć także w zagadnieniach praktycznych.
  11. Zadania z zastosowaniem twierdzenia Halla.

Metody kształcenia

Tradycyjny wykład; ćwiczenia audytoryjne, podczas których studenci rozwiązują zadania.

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

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

Warunki zaliczenia

Ocena za przedmiot składa się z oceny z ćwiczeń (50%) i wykładu (50%). Warunkiem uzyskania pozytywnej oceny końcowej jest uzyskanie pozytywnych ocen z ćwiczeń oraz wykładu. Warunkiem przystąpienia do zaliczenia wykładu jest uzyskanie pozytywnej oceny z ćwiczeń.

Literatura podstawowa

1.     R.J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa, 1998.

2.     V. Bryant, Aspekty kombinatoryki, WNT, Warszawa, 1997.

3.     Z. Palka, A. Ruciński, Wykłady z kombinatoryki, cz. 1, WNT, Warszawa, 1998. 

Literatura uzupełniająca

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

2.        W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa, 1989.

3.        K. A. Ross, Ch.R.B. Wright, Matematyka dyskretna, PWN, Warszawa, 1996.

Uwagi


Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 19-10-2020 13:18)