Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Matematyka dyskretna

Informacje ogólne

Kod przedmiotu: 1000-134MAD
Kod Erasmus / ISCED: 11.114 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0541) Matematyka Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Matematyka dyskretna
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty fakultatywne dla studiów 1 stopnia na matematyce
Punkty ECTS i inne: 6.00 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
Rodzaj przedmiotu:

fakultatywne

Skrócony opis:

Przegląd wybranych elementów kombinatoryki i teorii grafów. Podstawowe prawa i metody zliczania, zliczanie różnych obiektów związanych ze zbiorami skończonymi. Wykorzystanie zależności rekurencyjnych w problemach zliczania. Zliczanie orbit grup przekształceń. Podstawy teorii grafów: cykle Eulera i Hamiltona, zliczanie drzew, grafy planarne, skojarzenia w grafach. Na wykładzie pojawiają się elementarne pojęcia z algebry i analizy, ale główny nacisk położony jest na dowody kombinatoryczne, w szczególności znajdowanie bijekcji pomiędzy danymi skończonymi zbiorami różnych obiektów kombinatorycznych.

Pełny opis:

1. Podstawowe prawa i metody zliczania: prawa dodawania i mnożenia, zasada bijekcji, zasada szufladkowa. Współczynniki dwumianowe, dowody kombinatoryczne.

2. Zasada włączania i wyłączania, zliczanie funkcji „na” i nieporządków, problem małżeństw Lucasa.

3. Zliczanie podziałów, liczby Stirlinga II rodzaju, liczby Bella.

4. Zliczanie permutacji, liczby Stirlinga I rodzaju.

5. Rozmieszczenia kul w urnach.

6. Zależności rekurencyjne i funkcje tworzące, liczby Fibonacciego, Catalana i Bella, rozwiązywanie rekurencji liniowych ze stałymi współczynnikami.

7. Zliczanie orbit grup przekształceń: lemat Burnside’a, twierdzenie Polyi o liczbie istotnie różnych, ze względu na ustaloną grupę przekształceń, kolorowań danego zbioru obiektów.

8. Podstawowe pojęcia teorii grafów. Cykle Eulera, grafy eulerowskie i twierdzenie Eulera o ich charakteryzacji, cykle Hamiltona, grafy hamiltonowskie i twierdzenie Orego.

9. Drzewa: charakteryzacje i zliczanie drzew, twierdzenie Cayleya.

10. Grafy planarne i płaskie, twierdzenie Kuratowskiego (bez dowodu), wzór Eulera, kolorowanie wierzchołkowe grafów, twierdzenie o 5 barwach.

11. Skojarzenia w grafach: twierdzenie Halla i jego zastosowania.

Literatura:

1. V. Bryant, Aspekty kombinatoryki, WNT, Warszawa 2007.

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

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

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

Efekty uczenia się:

Student:

1. Zna podstawowe prawa i metody zliczania, potrafi przeprowadzać kombinatoryczne dowody tożsamości dwumianowych.

2. Zna rozmaite szczególne liczby występujące w kombinatoryce (współczynniki dwumianowe, liczby Stirlinga, Bella, Fibonacciego i Catalana), ich kombinatoryczne interpretacje oraz własności.

3. Zna zasadę włączania i wyłączania i potrafi ją zastosować w zagadnieniach zliczania różnych obiektów kombinatorycznych.

4. Zna pojęcie funkcji tworzącej ciągu liczbowego; zna przykłady zastosowań aparatu funkcji tworzących do znajdowania wzoru ogólnego na n-ty wyraz ciągu,

5. Zna pojęcie zależności rekurencyjnej i umie je wykorzystać jako narzędzie kombinatoryczne; potrafi rozwiązywać rekurencje liniowe ze stałymi współczynnikami.

6. Zna lemat Burnside’a; potrafi znaleźć liczbę istotnie różnych, ze względu na ustaloną grupę przekształceń, kolorowań danego zbioru obiektów.

7. Zna podstawowe pojęcia teorii grafów i potrafi je zilustrować przykładami.

8. Zna twierdzenie Eulera o charakteryzacji grafów eulerowskich oraz twierdzenie Orego o grafach hamiltonowskich.

9. Zna twierdzenie Cayleya i umie znaleźć liczbę drzew o danym zbiorze wierzchołków.

10. Zna wzór Eulera i potrafi go zastosować do znajdowania ilościowych zależności w grafach planarnych.

11. Zna twierdzenie Halla i przykłady jego zastosowania.

Metody i kryteria oceniania:

Egzamin pisemny, ewentualnie dodatkowo egzamin ustny.

Zajęcia w cyklu "Semestr letni 2023/24" (w trakcie)

Okres: 2024-02-19 - 2024-06-16
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Piotr Zakrzewski
Prowadzący grup: Joanna Jaszuńska, Piotr Zakrzewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Wykład - Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.2.0-80474ed05 (2024-03-12)