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
• Algebra liniowa
• Analiza matematyczna 1

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, WMT 2004
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

1. Indukcja (ćwiczenia)
2. Rekurencja (ćwiczenia)
3. Zliczanie zbiorów i funkcji (ćwiczenia)
4. Sumy skończone i rachunek różnicowy (ćwiczenia)
5. Współczynniki dwumianowe (ćwiczenia)
6. Permutacje i podziały (ćwiczenia)
7. tytuł (ćwiczenia)
8. tytuł (ćwiczenia)
9. tytuł (ćwiczenia)
10. tytuł (ćwiczenia)
11. tytuł (ćwiczenia)
12. tytuł (ćwiczenia)
13. tytuł (ćwiczenia)
14. tytuł (ćwiczenia)
15. tytuł (ć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