Matematyka dyskretna 1

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 $O,\mathrm{\Omega },\mathrm{\Theta },o,\omega$
  • 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

1. V.Bryant, Aspekty kombinatoryki, Wydawnictwa Naukowo-Techniczne 1977.
2. R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka Konkretna, Państwowe Wydawnictwo Naukowe, Warszawa 1996.
3. W.Lipski, Kombinatoryka dla programistów, Wydawnictwa Naukowo-Techniczne 2004.
4. W.Lipski, W.Marek, Analiza kombinatoryczna, Państwowe Wydawnictwo Naukowe, Warszawa 1986.
5. K.A.Ross, Ch.R.B.Wright, Matematyka Dyskretna, Państwowe Wydawnictwo Naukowe, Warszawa 1996.
6. Z.Pałka, A.Ruciński, Wykłady z kombinatoryki, Wydawnictwa Naukowo-Techniczne, Warszawa 1998.
7. R.J.Wilson, Wprowadzenie do teorii grafów, Państwowe Wydawnictwo Naukowe, Warszawa 1985.

Moduły

1. Indukcja (ćwiczenia) (test)
2. Rekurencja (ćwiczenia) (test)
3. Zliczanie zbiorów i funkcji (ćwiczenia) (test)
4. Sumy skończone i rachunek różnicowy (ćwiczenia) (test)
5. Współczynniki dwumianowe (ćwiczenia) (test)
6. Permutacje i podziały (ćwiczenia) (test)
7. Funkcje tworzące (ćwiczenia) (test)
8. Funkcje tworzące w zliczaniu obiektów kombinatorycznych (ćwiczenia) (test)
9. Asymptotyka (ćwiczenia) (test)
10. Teoria liczb (ćwiczenia) (test)
11. Teoria liczb II (ćwiczenia) (test)
12. Grafy (ćwiczenia) (test)
13. Grafy II (ćwiczenia) (test)
14. Grafy III (ćwiczenia) (test)
15. Metody algebraiczne w teorii grafów (ćwiczenia) (test)

Literatura uzupełniająca

1. N.L.Biggs, Discrete Mathematics, Oxford University Press 1989
2. B.Bollobas, Modern Graph Theory, Springer 1998
3. Th.H.Cormen, Ch.E.Leiserson, R.L.Rivest, C.Stein,Wprowadzenie do algorytmów, WNT, 2004.
4. R.Diestel, Graph Theory, Springer 1997
5. G.Polya, R.E.Tarjan, D.R.Woods, Notes on Introductory Combinatorics, Birkhauser 1983
6. J.Riordan, An Introduction to Combinatorial Analysis, Princeton University Press 1978