Matematyka dyskretna 1
Z Studia Informatyczne
Forma zajęć
Wykład (30 godzin) + ćwiczenia (30 godzin)
Opis
Wykład wprowadza aparat matematyczny niezbędny do konstruowania i analizy algorytmów. Składa się z elementów kombinatoryki, teorii grafów i teorii liczb.
Sylabus
Autorzy
- Paweł Idziak — Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
- Bartłomiej Bosek — Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
- Piotr Micek — Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
Wymagania wstępne
- Logika i teoria mnogości
- Algebra liniowa z geometrią analityczną
- Analiza matematyczna 1
Zawartość
- Indukcja matematyczna:
- zasada indukcji
- zasady minimum i maksimum
- liczby harmoniczne
- Rekurencja:
- definicje rekurencyjne
- zależności rekurencyjne
- liczby Fibonacciego
- rozwiązywanie równań rekurencyjnych
- Zliczanie zbiorów i funkcji:
- zliczanie podzbiorów
- zliczanie bijekcji
- zliczanie injekcji
- zliczanie funkcji
- zasada szufladkowa Dirichleta
- zasada włączania-wyłączania
- Sumy skończone i rachunek różnicowy:
- metody obliczania sum skończonych
- rachunek różnicowy
- dolna i górna silnia
- sumowanie przez części
- Współczynniki dwumianowe
- Permutacje i podziały:
- rozkład permutacji na cykle
- cyklowe liczby Stirlinga
- podziałowe liczby Stirlinga
- podziały liczby na sumy
- Funkcje tworzące:
- rozwijanie funkcji wymiernych w szereg
- funkcje tworzące w rozwiązywaniu zależności rekurencyjnych
- Funkcje tworzące w zliczaniu obiektów kombinatorycznych:
- liczby Catalana
- podziały liczby na sumy
- liczby Stirlinga
- liczby Bella
- Asymptotyka:
- notacja asymtotyczna
- twierdzenie o rekursji uniwersalnej
- metoda przybliżeń
- Teoria liczb:
- podzielność, NWD, NWW, liczby pierwsze
- algorytm Euklidesa
- rozkład na czynniki pierwsze
- gęstość liczb pierwszych
- Arytmetyka modularna:
- twierdzenie Fermata
- twierdzenie Eulera
- chińskie twierdzenie o resztach
- rozwiązywanie równań modularnych
- funkcja Mobiusa
- Grafy:
- podstawowe pojęcia
- drzewa i cykle
- cykle Eulera i Hamiltona
- grafy dwudzielne, skojarzenia i twierdzenie Halla
- spójność, wielospójność i twierdzenie Mengera
- sieci, przepływy, przekroje i twierdzenie Forda-Fulkersona
- planarność i twierdzenie Kuratowskiego
- kolorowanie grafów (w tym planarnych)
- Metody algebraiczne w teorii grafów:
- macierz sąsiedztwa i domkniecie przechodnie grafu
- macierz incydencji
- permanent i skojarzenia
- wartości własne
Literatura
- V.Bryant, Aspekty kombinatoryki, WNT 1977
- R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka Konkretna, PWN 1996
- W.Lipski, Kombinatoryka dla programistów, WMT 2004
- W.Lipski, W.Marek, Analiza kombinatoryczna, PWN 1986
- K.A.Ross, Ch.R.B.Wright, Matematyka Dyskretna, PWN 1996
- Z.Pałka, A.Ruciński, Wykłady z kombinatoryki, WNT 1998
- R.J.Wilson, Wprowadzenie do teorii grafów, PWN 1985
Moduły
- Indukcja (ćwiczenia) (test)
- Rekurencja (ćwiczenia) (test)
- Zliczanie zbiorów i funkcji (ćwiczenia) (test)
- Sumy skończone i rachunek różnicowy (ćwiczenia) (test)
- Współczynniki dwumianowe (ćwiczenia) (test)
- Permutacje i podziały (ćwiczenia) (test)
- Funkcje tworzące (ćwiczenia) (test)
- Funkcje tworzące w zliczaniu obiektów kombinatorycznych (ćwiczenia) (test)
- Asymptotyka (ćwiczenia) (test)
- Teoria liczb (ćwiczenia) (test)
- Teoria liczb II (ćwiczenia) (test)
- Grafy (ćwiczenia) (test)
- Grafy II (ćwiczenia) (test)
- Grafy III (ćwiczenia) (test)
- Metody algebraiczne w teorii grafów (ćwiczenia) (test)
Literatura uzupełniająca
- N.L.Biggs, Discrete Mathematics, Oxford University Press 1989
- B.Bollobas, Modern Graph Theory, Springer 1998
- Th.H.Cormen, Ch.E.Leiserson, R.L.Rivest, C.Stein,Wprowadzenie do algorytmów, WNT, 2004.
- R.Diestel, Graph Theory, Springer 1997
- G.Polya, R.E.Tarjan, D.R.Woods, Notes on Introductory Combinatorics, Birkhauser 1983
- J.Riordan, An Introduction to Combinatorial Analysis, Princeton University Press 1978