Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Matematyka dyskretna

Informacje ogólne

Kod przedmiotu: 1000-134MAD Kod Erasmus / ISCED: 11.114 / (0541) Matematyka
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
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.

Zajęcia w cyklu "Semestr letni 2019/20" (zakończony)

Okres: 2020-02-17 - 2020-08-02
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Joanna Jaszuńska
Prowadzący grup: Joanna Jaszuńska, Piotr Zakrzewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Wykład - Egzamin

Zajęcia w cyklu "Semestr letni 2020/21" (jeszcze nie rozpoczęty)

Okres: 2021-02-22 - 2021-06-13
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Joanna Jaszuńska
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.