Matematyka dyskretna 1

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,\Omega, \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