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
• Bartłomiej Bosek
• Piotr Micek

Wymagania wstępne

• Logika i teoria mnogości

Zawartość

• Indukcja matematyczna
  • zasada indukcji
  • zasady minimum i maksimum
  • zależności rekurencujne
• Sumy skończone
• Zliczanie zbiorów i funkcji
  • zliczanie podzbiorów
  • zliczanie bijekcji
  • zliczanie injekcji
  • zliczanie funkcji
  • współczynniki dwumianowe
• Permutacje i liczby Stirlinga
• Funkcje tworzące
• Zliczanie obiektów kombinatorycznych
  • zasada szufladkowa Dirichleta
  • zasada włączania-wyłączania
  • liczby Catalana
  • podziały liczby na sumy
• Asymptotyka
  • notacja $O,\mathrm{\Omega },\mathrm{\Theta },o,\omega$
  • twierdzenie o rekursji uniwersalnej
• Grafy
  • podstawowe pojęcia
  • drzewa i cykle
  • cykle Eulera i Hamiltona
  • spójność (i tw. Mengera)
  • dwudzielność (i tw. Halla)
  • planarność (i tw. Kuratowskiego)
  • sieci i przepływy
• Kolorowania grafów (w tym planarnych)
• Metody algebraiczne w teorii grafów
• Teoria liczb
  • NWD, NWW, liczby pierwsze
  • algorytm Euklidesa
  • rozkład na czynniki pierwsze
• Arytmetyka modularna
  • twierdzenie Fermata
  • chińskie twierdzenie o resztach

Literatura

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

Moduły

• [[MD Moduł 1|]] (Ćwiczenia)
• [[MD Moduł 2|]] (Ćwiczenia)
• [[MD Moduł 3|]] (Ćwiczenia)
• [[MD Moduł 4|]] (Ćwiczenia)
• [[MD Moduł 5|]] (Ćwiczenia)
• [[MD Moduł 6|]] (Ćwiczenia)
• [[MD Moduł 7|]] (Ćwiczenia)
• [[MD Moduł 8|]] (Ćwiczenia)
• [[MD Moduł 9|]] (Ćwiczenia)
• [[MD Moduł 10|]] (Ćwiczenia)
• [[MD Moduł 11|]] (Ćwiczenia)
• [[MD Moduł 12|]] (Ćwiczenia)
• [[MD Moduł 13|]] (Ćwiczenia)
• [[MD Moduł 14|]] (Ćwiczenia)
• [[MD Moduł 15|]] (Ćwiczenia)

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