Uniwersytet Ślaski w Katowicach - Centralny System Uwierzytelniania
Strona główna

ELEMENTY MATEMATYKI DYSKRETNEJ

Informacje ogólne

Kod przedmiotu: 0301-MT-N1-12-EMDY
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: ELEMENTY MATEMATYKI DYSKRETNEJ
Jednostka: Instytut Matematyki
Grupy: Przedmioty obowiązkowe - 2 sem. matematyki /nst.I st./
Strona przedmiotu: http://el2.us.edu.pl/wmfich/
Punkty ECTS i inne: (brak) Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
Język prowadzenia: polski
Poziom przedmiotu:

podstawowy

Rodzaj przedmiotu:

obowiązkowy

Wymagania wstępne:

brak

Skrócony opis:

Moduł ma na celu zaznajomienie studentów z elementarnymi zagadnieniami kombinatoryki skończonej i teorii grafów oraz wykształcenie umiejętności zliczania obiektów kombinatorycznych i przeprowadzania obliczeń z wykorzystaniem prostych chwytów kombinatorycznych.

Pełny opis:

Przewiduje się realizację następujących treści programowych:

1. Kombinacje, własności współczynników dwumiennych Newtona, obliczanie skończonych sum zawierających współczynnik Newtona.

2. Znajdowania liczby funkcji spełniających pewne ograniczenia, rozmieszczenia przedmiotów, wariacje, permutacje, multizbiory.

3. Własności permutacji, rozkład na cykle, rozkład na transpozycje, typ permutacji, liczby Stirlinga I rodzaju i ich własności.

4. Podział zbioru na bloki, liczby Stirlinga II rodzaju i ich własności, podziały liczby i ich własności.

5. Metoda zliczania obiektów: metoda bijektywna, reguła włączania i wyłączania, zasada szufladkowa Dirichleta.

6. Równania rekurencyjne i funkcje tworzące. Liczby Fibonacciego i Catalana.

7. Elementy teorii grafów: podstawowe pojęcia, minimalne drzewa rozpinające, problem minimalnych odległości, grafy Eulera i Hamiltona, problem komiwojażera.

Literatura:

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

Z. Palka, A. Ruciński, Wykłady z kombinatoryki, WNT 1998.

R. J. Wilson, Wprowadzenie do teorii grafów, PWN 1985.

V. Bryant, Aspekty kombinatoryki, PWN 1997.

R.L. Graham, D.E. Knuth, O. Patashnik, Matematyka konkretna, PWN 2010.

Efekty uczenia się:

Student:

Potrafi wyznaczać liczby podzbiorów zbioru, permutacji, wariacji i kombinacji. Stosuje zasadę włączania i wyłączania.

Potrafi sprawnie posługiwać się współczynnikami Newtona i obliczać proste sumy z tymi współczynnikami.

Potrafi rozkładać permutacje na cykle.

Zna pojęcie i własności liczb Stirlinga I oraz II rodzaju.

Potrafi wyznaczyć drzewo spinające graf i fundamentalny zbiór cykli.

Zna warunki konieczne i wystarczający istnienia drogi/cyklu Eulera w grafie.

Metody i kryteria oceniania:

Aktywność na zajęciach: Aktywność na zajęciach będzie oceniona na podstawie krótkich pisemnych zapytań o znajomość teorii z wykładów potrzebnej do realizacji poszczególnych konwersatoriów a także przygotowanie rozwiązań zadań z zestawu.

Kolokwium zaliczeniowe: kolokwium pisemne sprawdzające znajomość zadań z dostarczonych w trakcie zajęć zestawów.

Egzamin pisemny: składa się z jednej części: pytania dotyczą teorii.

Praktyki zawodowe:

Nie dotyczy.

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Ślaski w Katowicach.
kontakt deklaracja dostępności USOSweb 7.0.3.0 (2024-03-22)